如何计算二叉搜索树中第n个元素的索引？

Question

我将二叉搜索树（BST）存储在一个数组中，其中每个节点的左右子节点的索引计算如下：

N = parent node index
L = 2 * N + 1
R = 2 * N + 2

我希望能够快速（最好在 O(1) 时间内）计算 BST 中第 n 个元素的索引。

例如，给定以下二叉树...

      A
    /   \
  B       C
 / \     /
D   E   F

...它将存储在数组中，就像这样...

Node array[] = { A, B, C, D, E, F };

下表显示了每个元素的索引。

元素	节点	索引
0	D	3
1	B	1
2	E	4
3	A	0
4	F	5
5	C	2

最有效的方法是什么？

注意： BST 将永远完美平衡...

Answer 1

要找到索引，我们需要知道它位于树的哪一层，以及该层中的哪个项目。

让我们从下往上对层数进行编号，从 1 开始。那么，每个项目的层数为

1, 2, 1, 3, 1, 2, 1, 4, 1,,2, 1, 3, 1, 2, 1, ...

。这几乎就是序列

gcd(n, 2^n)

，它看起来就像 BST：

您可以使用欧几里得算法在 O(log n) 时间内计算此值。

为了计算出该项目出现在图层中的哪个位置，我们可以观察到同一图层中索引之间的距离是

2^layer

（您可以通过计算图中的空格来看到这一点。

结合这些信息，你应该能够得到一个索引。

Answer 2

递归树时，您可以使用以下方法计算每个节点的索引：

root.left.index  = 2 * root.index + 1
root.right.index = 2 * root.index + 2