Tools + Simulatorsnanase.cc / tools

赤黒木

赤黒木

赤黒比較回転・色の変更条件違反発見
0 / 0 手順
速さ 速さ

回/秒

n = キーの数

キーの数 キーの数

個

キーの順番
NIL の葉

実行内容計算量n = 31 の平均

比較と回転
0回
比較
0
回転
0
色の変更
0
高さ
–
高さの上限
–
最小の高さ
–
黒の高さ
–
キー
0
利用例
Linux の rbtree・Java の TreeMap・C++ の std::map の主な実装
利用例
実装を短くしたいとき
利用例
実装を短くしたいとき
利用例
検索が多いとき
利用例
要素が少なく、順番がばらばらのとき

音量 音量

dB

動作原理と式

4 つの条件

赤黒木はどのノードも赤か黒に塗った二分探索木です。空いた枝の先には黒の NIL の葉があるとみなします。次の条件を保つと、木は低いままです [1][3]。

  • 根は黒
  • 赤のノードの子は黒（赤が続かない）
  • 根からどの NIL の葉までも、通る黒の数が同じ
  • NIL の葉は黒

根から NIL の葉までの黒の数を黒の高さと呼びます。「NIL の葉」を表示にすると、図に小さな黒の四角で出ます。

高さの上限

赤は続かないので、どの道でも赤は黒より多くなりません。高さ h の木の黒の高さは h/2 以上です。黒の高さが b の部分木には 2b−1 個以上のキーがあるので、次の式が成り立ちます [3]。

h≤2log2(n+1)

記号: n はキーの数です。どのキーも h 回以下の比較で見つかります。

回転

親と子を入れ替えて、片側に寄った部分木をもう片側へ移します。真ん中の部分木は子から親へつなぎ替わります。中順の並びは変わらないので、二分探索木のままです。1 回の回転で書き換えるポインタは 3 本です。

追加の直し方

葉に赤でつなぎます。黒の高さは変わりませんが、親も赤だと赤が続きます。おじ（親の兄弟）の色で直し方が決まります [3]。

  • おじが赤: 親とおじを黒、祖父を赤にする。祖父とその親で赤が続けば、祖父から同じことを繰り返す
  • おじが黒・内側: 親で回転して、外側の形にする
  • おじが黒・外側: 親を黒、祖父を赤にして、祖父で回転する。ここで終わる

色の変更は根へ向かって続くことがありますが、回転は 1 回の追加で 2 回までです。最後に根を黒にします。

削除の直し方

子が 2 つあるノードは、右の部分木の最小と入れ替えてから消します。消したノードが黒なら、その道の黒が 1 つ不足します。兄弟の色と兄弟の子の色で直し方が決まります [3]。

  • 兄弟が赤: 親で回転して、兄弟を黒にする
  • 兄弟の子が両方黒: 兄弟を赤にして、不足を親へ送る
  • 兄弟の遠い子が黒: 兄弟で回転して、遠い子を赤にする
  • 兄弟の遠い子が赤: 親で回転して、遠い子を黒にする。ここで終わる

回転は 1 回の削除で 3 回までです。

2-3-4木との対応

黒のノードと、その赤の子を 1 つの箱にまとめると、キー 1〜3 個の箱の木になります。これは次数 4 の B木（2-3-4木）で、黒の高さは箱の木の段数です [2][1]。追加の「おじが赤」は箱があふれて分かれる操作で、回転は箱の中の並べ替えです。

種類ごとの違い

  • 左傾赤黒木: 赤の子を左だけに置く。直し方は 3 つの規則（右だけが赤なら左回転、左と左の左が赤なら右回転、左右が赤なら色の反転）で、回転は赤黒木より多い [4]
  • AA木: 赤の子を右だけに置き、色の代わりに段の数を持つ。直し方は右回転と左回転の 2 つ [5]
  • AVL木: 色を持たず、どのノードでも左右の部分木の高さの差を 1 以下に保つ。高さの上限は赤黒木より低いが、1 回の削除の回転は最悪で O(logn) 回になる [6][7]
  • 二分探索木（参考）: 形を直さない。右上がりのキーを入れると 1 本の線に伸び、検索の比較はキーの数と同じになる [7]

AVL木の高さの上限は次の式です [7]。

h<1.4405log2(n+2)−0.3277

計算量

比較の回数で表します。回転の列は 1 回の追加・削除での回転の数です。二分探索木は整列したキーで 1 本に伸びるので、最も遅い場合を載せています。

追加検索削除高さの上限回転
赤黒木O(log 𝑛)O(log 𝑛)O(log 𝑛)2 log2(𝑛+1)2・3
左傾赤黒木O(log 𝑛)O(log 𝑛)O(log 𝑛)2 log2(𝑛+1)O(log 𝑛)
AA木O(log 𝑛)O(log 𝑛)O(log 𝑛)2 log2(𝑛+1)O(log 𝑛)
AVL木O(log 𝑛)O(log 𝑛)O(log 𝑛)1.44 log2(𝑛+2)2・O(log 𝑛)
二分探索木（参考）O(𝑛)O(𝑛)O(𝑛)𝑛0

音

音の高さはキーの値で決めます。比べているキーと、回転や色の変更をしたキーを鳴らします。v はキーの値、vmax はキーの最大値です。

f=110×24(v−1)/(vmax−1)Hz

出典

  1. 赤黒木L. J. Guibas, R. Sedgewick, A dichromatic framework for balanced trees, 19th Annual Symposium on Foundations of Computer Science, pp. 8–21, 1978
  2. 赤黒木のもとになった木R. Bayer, Symmetric binary B-Trees: Data structure and maintenance algorithms, Acta Informatica, Vol. 1, No. 4, pp. 290–306, 1972
  3. 追加と削除の手順T. H. Cormen, C. E. Leiserson, R. L. Rivest, C. Stein, Introduction to Algorithms, 4th ed., MIT Press, 2022, Chapter 13
  4. 左傾赤黒木R. Sedgewick, Left-leaning Red-Black Trees, Princeton University, 2008
  5. AA木A. Andersson, Balanced search trees made simple, Algorithms and Data Structures (WADS 1993), Lecture Notes in Computer Science, Vol. 709, pp. 60–71, 1993
  6. AVL木G. M. Adelson-Velsky, E. M. Landis, An algorithm for the organization of information, Soviet Mathematics Doklady, Vol. 3, pp. 1259–1263, 1962
  7. 二分探索木と AVL木の高さD. E. Knuth, The Art of Computer Programming, Vol. 3: Sorting and Searching, 2nd ed., Addison-Wesley, 1998, Sections 6.2.2–6.2.3

このツールで決めたこと

  • 比較はキーどうしを比べた回数で、等しいかどうかの確認も 1 回と数える
  • 色の変更は色が変わったノードの数。AA木は親と同じ段の右の子を赤とみなして数える
  • 赤黒木の削除で子が 2 つあるときは、右の部分木の最小で置き換える
  • 左傾赤黒木は 2-3木と対応する形（色の反転を戻りながら行う形）で動かす
  • AA木の削除は、葉になるまで隣のキーを上へずらしてから葉を消す
  • 回数は工程ごとに 0 から数える
  • 操作の表の回数は、31 個で 8 通りのデータを試した 1 回の平均

関連ツール

すべてのツール