ないすべての赤-黒木がバランス?

Question

直感的に"バランスのとれた木"は木の左右のサブ樹木の各ノードが必要"とほぼ同数のノード。

もちろん、場合についてお話しましたので赤-黒木*(定義を参照してください末)にバランスしたということは 高さ バランスのとれたその意味で、彼らがバランスのとれたものである

を考えます．その正式化の勘ど

定義: バイナリの木は$\mu$-バランスがと，$0\le\mu\leq\frac{1}{2}$が各ノードが$N$の不平等

$$\mu\le\frac{|N_L|+1}{|N+1}\le1-\mu$$

やは$\mu'\gt\mu$あり、一部のノードの上書失敗します。$|N_L|$れは、多数のノードの左側のサブツリーを$N$と$|N|$れは、多数のノードのツリーを$N$としてルートのルート。

と思い、という 重量バランス 樹木の一部の文学んでいます。

できる場合はバイナリの木$n$ノードは$\mu$-バランス（数$\mu\gt0$)、その高さの$\mathcal{O}(\log n)$,このように維持ース検索物件です。

その質問は

あ$\mu\gt0$になるのに十分に大きいの赤-黒ツリーは$\mu$-バランス?

---

のの定義は赤-黒木を使用していまからの紹介のアルゴリズムによるCormen et al)

バイナリ検索の木の各ノードの色は赤と黒

• のルートはブラック
• すべてのノードがNULLの場合は黒く見えます。
• 場合はノードが赤、そしてその子供です。
• 各ノードのすべてのパスからノードとその子孫がNULLのノードが同一のクロノード。

注意：を期待してはいけない場合は、NULLのノードの定義は$\mu$-バランスです。もうない).

Answer 1

請求項:赤-黒木できる任意に国連-$\mu$バランスのとれた

耐ア:記右側のサブツリーとして多くのノードできると左として複数のノードで指定された番号 $k$ 黒ノード毎に根葉ます。

証:を定義する配列 $T_k$ 赤-黒木のよう $T_k$ は $k$ 黒ノード毎のパスからのルートのいず（仮想）である。定義 $T_k=B(L_k,R_k)$ と

• $R_k$ の完全ツリーの高さ $2k-1$ 最初に、...レベルの色の赤、黒、
• $L_k$ の完全ツリーの高さ $k-1$ すべてのノードです。

明らかにすべての $T_k$ 赤-黒木

例えば、これらの $T_1$, $T_2$ や $T_3$, れ、それぞれ

---

^[源]

---

^[源]

---

^[源]

---

それでは、検証のた印象の右側にいて 巨大 と比較します。しない仮想葉;な影響を与えます。

左側のサブツリーの $T_k$ が完了し、常に高 $k-1$ が含まれ $2^k-1$ ノード。右側のサブツリーは、、完全高さ $2k-1$ とthuslyを含む $2^{2k}-1$ ノード。現在の $\mu$-バランスのルートが

$九displaystyle\frac{2^k}{2^k+2^{2k}}=\frac{1}{1+2^k}\underset{k o\infty}{\へ}0$

することがありませんの $\mu>0$ に対応してくれました。

Answer 2

No. 考え赤-黒ツリーは以下の特殊構造。

• 左側のサブツリーが完全にバイナリーツリーの深さ$d$るすべてのノードはブラック。
• 右側のサブツリーが完全にバイナリーツリーの深さ$2d$るすべてのノードで奇深赤、すべてのノードでも深さがします。

で簡単にチェックすることが有効なの赤-黒ツリーです。そのノード数のサブツリー($2^{2次元+1}-1$)は、 スクエア 数のノードの左側のサブツリー($2^{d+1}-1$).