algorithm - 序数インデックスによる赤黒木アクセス

Question

私は赤黒木を持っています（二分木、すべての葉は2レベル以内です）。ノードをナビゲートできます：左、右、または親。私はノードの総数を知っています。

ツリーでN番目に小さい要素を見つける必要があります。O（n）よりも速くこれを行う方法はありますか？インデックスによるアクセスを最適化するアイデアはありますか？

Answer 1

このノードの子の数を示す属性を各ノードに1つ追加できます。この属性を使用すると、O（lgn）を持つN番目に小さいノードを見つけることができます。

これで、ツリーにノードを挿入（または削除）するときに、この属性を処理する必要があります。回転がない場合は扱いやすいですが、回転がある場合は少し難しいですが、できます。

Answer 2

各ノード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 3

赤黒木については、左側のノードの数を追跡する必要はありません。これは、右側にバイアスがかかっている場合（必要がある場合）、左側のノードの数が常にメルセンヌ系列（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