「みんなのデータ構造」で学ぶデータ構造 〜 RedBlackTree

@Panda_Program

「みんなのデータ構造」でプログラミングで使うデータ構造を学ぶ

「みんなのデータ構造」(Amazonリンク)とは、コンピュータ・サイエンスの基礎となるデータ構造の教科書「Open Data Structure」の日本語訳です。Introduction to Algorithmsといったアルゴリズムの名著への橋渡しになるような、実用的なテーマが丁寧に説明されています。

この本でデータ構造を学ぶ意義は、訳者まえがきで以下のように説かれています。

  1. ソフトウェアのほとんどはシンプルなデータ構造の組み合わせでできている。
  2. 「みんなのデータ構造の内容がだいたいわかれば、いいエンジニアになれる。

また、わからない部分は読み飛ばしていいとも書かれています。さらに嬉しいことに、この書籍の中でも実務や学術研究で頻繁に登場する内容がピックアップされています。

書籍のサンプルコードはC++ですが、何か1つプログラミング言語を知っていれば問題なく読み進めることができます。

RedBlackTree

赤黒木(red-black tree)は、木の高さが要素数の対数で抑えられる二分木である。赤黒木の性質は以下の通りである。

  1. n個の要素を含む赤黒木の高さは 2logn2\log n 以下である
  2. add(x)およびremove(x)を最悪の場合でも O(logn)O(\log n) の時間で実行できる
  3. add(x)およびremove(x)における回転の回数は、償却すると定数である

赤黒木は優れた性質を持つが、実装が複雑である。赤黒木を理解するために、まずは背景知識として2-4木を知る必要がある。

2-4木

2-4木の性質は以下である。

  1. [高さ] 全ての葉の深さは等しい
  2. [次数] 全ての内部ノードは2個以上4個以下の子ノードを持つ

また、n個の葉を持つ2-4木の高さは logn\log n 以下である。

葉の追加 (logn\log n 以下)

2-4木に葉を追加するのは簡単。親ノードwの子として葉uを追加したい時は、まず追加をする。その後、次数の制約に沿って処理を行う。wが4つの子を持っていれば、wを分割して子を2つ持つノードwと子を3つ持つノードw'とする。このとき、w'の親はwの親とする。そして、この処理を再帰的に繰り返す。

2-4木の高さは常に logn\log n 以下なので、葉の追加は logn\log n ステップ以下で完了する。

葉の削除 (logn\log n 以下)

2-4木から葉を削除するためには、まず親wから葉uを削除する。そして、wの子が1つだけになれば、次数の制約を満たさなくなるので、修正の処理を加える。

つまり、wの兄弟w'を調べて、w'の子が3つまたは4つなら、そのうち1つをw'からwに移す。w'の子が2つなら、wとw'を併合して、子を3つ持つノードwとする。そして、w'をw'の親から取り除く。

この処理は自分自身w、もしくは兄弟w'が子を3つ以上持つようなノードuが見つかるか、根に到達したら終了する。

2-4木の高さは常に logn\log n 以下なので、葉の削除も追加と同様に logn\log n ステップ以下で完了する。

RedBlackTree: 2-4木をシミュレートする二分木

赤黒木は、各ノードuが赤か黒の色を持つ二分探索木である。赤ノードは0で、黒ノードは1で表現される。赤黒木の性質は以下である。

  1. 葉から根への経路には、いずれも黒ノードが同じ数だけ含まれる。(黒の高さの性質。葉から根への経路について、色の総和は全て等しい)
  2. 赤ノード同士は隣接しない(赤の辺の性質。赤の辺はないということ。根でない任意のノードuについて、 u.color + u.parent.color >= 1が成り立つ)

これらの性質は、根rがどちらの色であっても満たされる。以下では、根が黒であると仮定する。また、赤黒木を更新するアルゴリズムでは、根は黒のまま保たれるとする。なお、外部ノード(nil)は黒ノードとして扱う。

class RedBlackNode : public BSTNode<Node, T> {
	friend class RedBlackTree<Node, T>;
	char color;
}

int red = 0;
int black = 1;

赤黒木と2-4木

赤黒木は2-4木を二分木として効率的にシミュレートするように設計されている。

例えば、赤黒木Tに対して「全ての赤ノードを取り除き、uの2つの子を両方ともuの親(黒ノード)に接続する」という操作を実行すると、T'は黒ノードだけを持つ2-4木になるのである。

2-4木T'はn+1個の葉を持ち、各葉は赤黒木のn+1個の外部ノードと対応する。よって、この木の高さは log(n+1)\log (n+1) 以下である。

黒ノードのみを持つ2-4木T'の高さは log(n+1)\log (n+1) 以下なので、赤黒木Tの黒ノードの個数は log(n+1)\log (n+1) 以下である。また、2つの内部ノードのうち、赤は1追加なので、赤ノードの個数は log(n+1)1\log (n+1) - 1 以下である。よって、n>=1について、根から任意の内部ノードへの経路のうちで最長のものの長さは、次の左辺の値以下である

2logn+12<=2logn2\log n+1 - 2 <= 2\log n

このことから、赤黒木の最も重要な性質を示せる。

  1. n個のノードからなる赤黒木の高さは 2logn2\log n 以下である

Happy Coding 🎉

パンダのイラスト
パンダ

記事が面白いと思ったらツイートやはてブをお願いします!皆さんの感想が執筆のモチベーションになります。最後まで読んでくれてありがとう。

  • Share on Hatena
  • Share on Twitter
  • Share on Line
  • Copy to clipboard