序文インデックスによる赤黒ツリーアクセス

Question

私は赤黒のツリー（2つのツリー、すべての葉が2つのレベル内にあります）を持っています。 私はノードを左から右、または親に移動できます。 私はノードの総数を知っています。

私は木の中で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

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

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

Answer 3

簡単ですそれが適切な（あるべき）偏っているためならば左、左のノードの数は常にますメルセンヌ系列（1,3,7,15,31 ...）または2^depth -1を形成する。

これを念頭に置いて、ノードを再帰的に取得するロジックを書き留めることができます。 上記の回答には、の符号が切り替わっています。これはエリキシルの正しい実装です。について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