按序号索引访问红黑树

Question

我有一棵红黑相间的树(二叉树，所有的叶子都在两层之内)。我可以通过节点导航:向左、向右或向父节点。我知道所有的节点数。

我必须找到树中的第N个最小的元素。有没有比O(n)更快的方法呢？有没有通过索引优化访问的想法？

Answer 1

在你应该存储的每个节点X中，有多少个节点在以X为根的子树中。

count(LEAF) = 1
count(NODE) = count(NODE->LEFT) + count(NODE->RIGHT) + 1

在每次插入/删除期间，您应该使用此公式来更新受旋转影响的节点中的计数。

之后，解决方案就很简单了

NODE nth(NODE root, int n) {
    if (root->left->count <= n) return nth(root->left, n);
    if ( root->left->count + 1 == n) return root;
    return nth(root->right, n - root->left->count - 1);
}

Answer 2

您可以在每个节点中添加一个属性，以显示此节点的子节点数量。有了这个属性，你可以找到第N个最小的节点，O(lgn)。

现在，当您在树中插入(或删除)任何节点时，您只需处理此属性。如果没有旋转，那么它很容易处理，但是当你有旋转的时候，它就有点困难了，但你可以做到。

Answer 3

对于红黑树，你不需要跟踪左边的节点数，因为如果它是右偏的(应该是)，那么左边的节点数将总是形成一个mersenne序列( 1，3，7，15，31 ...)或者2^depth -1。

考虑到这一点，我们可以写下递归获取节点的逻辑。上面接受的答案有它的符号切换。这是elixir中的正确实现。对于package

def nth(%Rbtree{node: r}, n), do: do_nth(r, n)
defp do_nth({_,h,k,v,l,r}, n) do
  l_count = left_count(h)
  cond do
    l_count > n ->
      case l do
        nil -> {k,v}
        _ -> do_nth(l, n)
      end
    l_count == n -> {k,v}
    true ->
      case r do
        nil -> {k,v}
        _ -> do_nth(r, n - l_count - 1)
      end
  end
end
defp left_count(1), do: 0
defp left_count(0), do: 0
defp left_count(h), do: :math.pow(2,h-1)-1 |> round