2

I have a red-black tree (binary tree, all the leaves are within 2 levels). I can navigate through nodes: to left, right or parent. I know the entire count of nodes.

I have to find the N-th smallest element in a tree. Is there any way to do this faster than in O(n)? Any ideas of optimizing access by index?

4

3 回答 3

3

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

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

于 2012-03-31T06:47:36.987 回答
3

在您应该存储的每个节点 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);
}
于 2012-03-31T06:49:14.957 回答
1

对于红黑树，您不需要跟踪左侧节点的数量，因为如果它是右偏（应该），那么左节点的数量将始终形成一个梅森级数（1、3、7、15、31 .. .) 或2^depth -1.

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

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
于 2017-05-25T05:23:46.690 回答