在完美的二叉树中获取顶点的父级

父索引可以在O(log ^* n)时间和O(1)空间中找到.

这里log ^* n表示迭代对数:在结果小于或等于1之前必须迭代地应用对数函数的次数.

实际上,如果我们能够为大型查找表(为树中的每个节点存储父索引)提供O(n)空间,那么可以更快地完成 - 在O(1)时间内.

下面我将描述几个不需要任何额外空间的算法,并给出O(log n)最坏情况时间,O(log log n)预期时间,O(log log n)最坏情况时间和O(log)的结果^* n)最坏的情况时间.它们基于完美二叉树的后序索引的以下属性:

树的最左侧路径上的所有索引等于2 ⁱ -1.

最左边路径上节点的每个右子节点的索引等于2 ⁱ -2.

最左边路径上的任何节点及其右子树都标记有在同一位置上具有最高有效非零位的索引:i.

最左边路径上任何节点的左子树包含2个ⁱ -1个节点.(这意味着在减去2 ⁱ -1之后,我们将得到一个相对于其父节点位置相似的节点,具有相同的深度,但更接近满足属性#1和#2的"特殊"节点).

属性#1和#2给出了简单的算法来获取树的某些节点的父节点:对于形式为2 ⁱ -1的索引,乘以2并加1; 对于2 ⁱ -2 形式的索引,只需添加1.对于其他节点,我们可以重复使用属性#4来到满足属性#1或#2的节点(通过减去几个左子树的大小),然后找到位于最左边路径上的一些父节点,然后再添加回所有节点减去的值.属性#3允许快速找到应减去哪些子树的大小.所以我们有以下算法:

虽然((x+1) & x) != 0并((x+2) & (x+1)) != 0重复步骤2.

清除最重要的非零位并添加1.积累差异.

如果((x+1) & x) == 0,乘以2并加1; 否则,如果((x+2) & (x+1)) == 0,添加1.

添加在步骤2中累积的所有差异.

例如,12(以二进制形式0b1100)在步骤#2转换为0b0101,然后转换为0b0010(或2十进制).累积的差异是10.步骤#3添加1,步骤#4加回 10,结果是13.

其他示例:( 10以二进制形式0b1010)在步骤#2转换为0b0011(或3十进制).步骤#3将它加倍(6),然后加上1(7).步骤#4加回累积的差值(7),结果是14.

时间复杂度为O(log n) - 但仅在所有基本操作在O(1)时间内执行时.

为了提高时间复杂度,我们可以并行执行步骤#2的多次迭代.我们可以得到n/2索引的高位,并计算它们的人口数.如果在将结果添加到剩余的低位后,总和不会溢出到这些高位,我们可以递归地应用此方法,其中O(log log n)复杂度.如果我们有溢出,我们可以回滚到原始算法(逐位).请注意,所有设置的低位都应该被视为溢出.因此产生的复杂性是O(log log n)预期时间.

我们可以使用二进制搜索来处理溢出,而不是逐位回滚.我们可以确定n/2要选择多少个高位(小于),这样我们要么没有溢出,要么(对于索引0b00101111111111)所选择的非零高位的数量是精确的1.请注意,我们不需要多次应用此二进制搜索过程,因为当数字中的位数大于O(log log n)时,不会发生第二次溢出.因此产生的复杂性是O(log log n)最坏情况时间.假设所有基本操作都在O(1)时间内执行.如果在O(log log n)时间内实现某些操作(填充计数,前导零计数),则我们的时间复杂度增加到O(log ² log n).

我们可以使用不同的策略,而不是将索引的位分成两个相等的集合:

计算索引的人口计数并将其添加到索引值.最高有效位从更改0为1确定高阶/低阶位的分离点.

计算高阶位的人口数,然后将结果添加到低阶位.

如果"分离"位非零,((x+1) & x) != 0并且((x+2) & (x+1)) != 0从步骤#1继续.

如果设置了所有低位,并且设置了最低有效位,则将此极限情况作为右子进行处理.

如果((x+1) & x) != 0和((x+2) & (x+1)) != 0,也将此作为正确的孩子处理.

如果((x+1) & x) == 0,乘以2并加1; 否则,如果((x+2) & (x+1)) == 0,添加1.

如果满足步骤#3的条件,则这意味着在步骤#2中的添加导致进入"分离"位.其他低位代表一些不能大于原始人口数的数字.此数字中的设置位数不能大于原始值的总体计数的对数.这意味着每次迭代后的设置位数最多为先前迭代中设置位数的对数.因此,最坏情况时间复杂度为O(log ^* n).这非常接近O(1).例如,对于32位数字,我们需要大约2次或更少的迭代.

该算法的每一步都应该是显而易见的,除了步骤#5,要证明其正确性.请注意,仅当将填充计数结果添加到"分离"位时才执行此步骤,但仅添加高阶位的填充计数不会导致此进位."分离"位对应于值2 ⁱ.所有位的总体计数与仅高位的总体计数之间的差异最多i.因此,步骤#5处理至少2 ⁱ -i 的值.让我们将逐位算法应用于此值.2 ⁱ -i足够大,以便i-1设置位.清除此位并1以位为单位添加值0..i-2.该值至少为2 ^i-1 - (i-1),因为我们只减去了2 ^i-1并添加了1.或者如果我们将索引向右移动一个位置,我们再次至少有2个ⁱ -i.如果我们重复这个过程,我们总会在位置找到非零位i-1.每个步骤逐渐减小比特值0..i-1与最近功率之间的差值2.当出现这种差异时2,我们可以停止这种逐位算法,因为当前节点显然是一个正确的孩子.由于这种逐位算法总是得到相同的结果,我们可以跳过它并始终将当前节点作为正确的子节点处理.

这是该算法的C++实现.可以在ideone上找到更多细节和一些其他算法.

uint32_t getMSBmask(const uint32_t x)
{ return 1 << getMSBindex(x); }

uint32_t notSimpleCase(const uint32_t x)
{ return ((x+1) & x) && ((x+2) & (x+1)); }

uint32_t parent(const uint32_t node)
{
    uint32_t x = node;
    uint32_t bit = x;

    while ((x & bit) && notSimpleCase(x))
    {
        const uint32_t y = x + popcnt(x);
        bit = getMSBmask(y & ~x);
        const uint32_t mask = (bit << 1) - 1;
        const uint32_t z = (x & mask) + popcnt(x & ~mask);

        if (z == mask && (x & (bit << 1)))
            return node + 1;

        x = z;
    }

    if (notSimpleCase(x))
        return node + 1;
    else
        return node + 1 + (((x+1) & x)? 0: x);
}

uint32_t parent(const uint32_t node)
{
    uint32_t x = node;

    while (x > 2)
    {
        const uint32_t y = x + popcnt(x);
        const uint32_t bit = getMSBmask(y & ~x);
        const uint32_t mask = (bit << 1) - 1;
        x = (x & mask) + popcnt(x & ~mask);
    }

    return node + 1 + (x == 1);
}