我有一个完美的二叉树，它枚举了后序方式。这种树的一个例子是
15
7 14
3 6 10 13
1 2 4 5 8 9 11 12
我知道树的大小。我正在寻找一个公式或简单算法，它将一个数字作为输入（我感兴趣的顶点的 ID）并返回一个数字 - 父节点的 ID。从顶部遍历树并获得结果非常容易O(log n)。有更快的解决方案吗？我对叶子最感兴趣，所以如果有针对特殊情况的解决方案，也可以带上它。
父索引可以在 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) 最坏情况时间。它们基于完美二叉树的后序索引的以下属性：
i.属性#1 和#2 给出了获取树的某些节点的父节点的简单算法：对于形式为 2 i -1 的索引，乘以2和加1；对于 2 i -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。例如，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) expected time。
我们可以使用二进制搜索来处理溢出，而不是逐位回滚。我们可以确定要选择多少高位（小于n/2），这样我们要么没有溢出，要么（对于索引0b00101111111111）选择的非零高位的数量正好是1。请注意，我们不需要多次应用此二进制搜索过程，因为当数字中的位数大于 O(log log n) 时，不会发生第二次溢出。所以产生的复杂度是 O(log log n)最坏情况时间。假设所有基本操作都在 O(1) 时间内执行。如果某些操作（人口计数，前导零计数）在 O(log log n) 时间内实现，那么我们的时间复杂度会增加到 O(log 2 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。所有位的填充数与仅高位的填充数之间的差异最多为i. 因此，第 5 步处理的值至少为 2 i -i。让我们对这个值应用逐位算法。2 i -i 足够大，以便i-1设置该位。清除该位并添加1到 bits 中的值0..i-2。这个值至少是 2 i-1 -(i-1) 因为我们刚刚减去了 2i-1并添加1. 或者如果我们将索引向右移动一个位置，我们又至少有 2 个i -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);
}
function getParent(node, size)
{
var rank = size, index = size;
while (rank > 0) {
var leftIndex = index - (rank + 1)/2;
var rightIndex = index - 1;
if (node == leftIndex || node == rightIndex) {
return index;
}
index = (node < leftIndex ? leftIndex : rightIndex);
rank = (rank - 1)/2;
}
}
它从根开始，决定进入哪个分支，并重复直到找到节点。rank 是同层最左边节点的索引：1, 3, 7, 15, ..., k^2 - k + 1.
输入参数为：
node– 您想要其父节点的节点的索引。（基于 1）size– 根节点的索引；15在你的例子中。例子：
>>> r = []; for (var i = 1; i <= 15; i++) r.push(parent(i,15)); r;
[3, 3, 7, 6, 6, 7, 15, 10, 10, 14, 13, 13, 14, 15, undefined]
让我们看看你的树：
15
7 14
3 6 10 13
1 2 4 5 8 9 11 12
将标签n重写为15-n。然后我们得到：
0
8 1
12 9 5 2
14 13 11 10 7 6 4 3
也可以写成
0
+8 +1
+4 +1 +4 +1
+2 +1 +2 +1 +2 +1 +2 +1
好吧，有一个适合你的模式。所以在这个标签方案中，左孩子2^(i+1)比父母多，i孩子的身高在哪里，而右孩子1比父母多。但是，我们如何才能计算出孩子的身高，以及它是左孩子还是右孩子？
不幸的是，如果不计算出节点的整个路径（这意味着对数时间），我无法找到任何方法来获取此信息。但是，您可以直接从节点的标签中推断出节点的路径（此处演示了高度为 3 的树）：
nn == 0，则为根。n - 8 >= 0，它在根的左子树中。设置n = n-8。n - 8 < 0，它在根的右子树中。设置n = n-1。n == 0现在，它是在最后一步中发现的任何子树的根。n - 4 >= 0，则它位于上一步中发现的任何子树的左子树中。放n = n-4n - 4 < 0，则它位于上一步中发现的任何子树的右子树中。设置n = n-1。n-1 >= 0。您可以使用位算术和-1s 来完成所有这些操作，并且在现实世界中它会非常快（在万亿节点树中计算它只需要比 10 节点树长约 12 倍（忽略内存问题））但是它仍然是对数时间。
无论如何，一旦您知道标签的高度以及它是左子还是右子，您就可以使用我之前提到的关系轻松计算父标签。
如果允许您查询节点子节点的 ID，您可以做一些有用的事情。
普通情况1：如果x = size，它是根。
小案例 2：如果x是叶子（查询子 ID 以找出），尝试x + 1. 如果x + 1不是叶子（对子 ID 的其他查询），x则为x + 1. 如果x + 1 是叶子，x是 的左孩子x + 2。
对于内部节点：子节点x是x - 1（右孩子）和x - (1 << height(x) - 1)（左孩子，右孩子是完美的二叉树，所以它有 2 h -1 个节点）。因此，使用 和 之间的差异x，可以确定 :left_child(x)的高度，但它实际上是所需的子树的大小，所以无论如何你都会采用，所以可以删除 。
所以父级是（iff ）或者父级是（否则）。xheight(x) =ctz(x - left_child(x))1 << heightctzxx + 1right_child(x + 1) == xx
x + (x - left_child(x)) * 2
这不如仅在 ID 上进行数学运算那么好，但假设您可以在恒定时间内询问节点的子节点，这是一个恒定时间算法。
import math
def answer(h,q=[]):
ans=[]
for x in q:
if(True):
curHeight=h;
num=int(math.pow(2,h)-1)
if(x==num):
ans.append(-1)
else:
numBE=int(math.pow(2,curHeight)-2)
numL=int(num-int(numBE/2)-1)
numR=int(num-1)
flag=0
while(x!=numR and x!=numL and flag<10):
flag=flag+1
if(x>numL):
num=numR
else:
num=numL
curHeight=curHeight-1
numBE=int(math.pow(2,curHeight)-2)
numL=num-(numBE/2)-1
numR=num-1
ans.append(num)
return ans
很抱歉没有答案，但我认为不可能在 less than 中做到这一点O(log n)，甚至允许恒定时间算术和按位逻辑运算。
节点索引中的每个位都可能对从节点到根的遍历中的几乎每个左/右/停止决策产生影响，包括第一个。此外，检查树的每一层节点的索引，它们是非周期性的（不仅是 2 的幂）。这意味着（我认为）恒定数量的算术运算不足以识别级别，或者节点是左子还是右子。
不过，这是一个有趣的问题，我很想被证明是错误的。我刚刚浏览了我的Hacker's Delight副本——我对他们玩的一些奇特的数字基础寄予厚望，但没有什么很合适的。