赤黒木 (21 min)

このビデオでは、ただの二分探索は

既にお話しので、次のお話に進みたいと思います。

それはバランスされた二分木探索です。これらがリアルタイム性を行たい操作に保証したい時に

あなたが実際に必要とする探索木です。

それはバランスされたままである事が保証されるアルゴリズムです。それは

高さが対数的であることが保証されているということです。つまり、

二分探索木において私たちが学び、愛した全ての操作について

保持するキーの数に対して対数的に処理されるということです。

じゃあ、簡単に振り返りましょう。ツリー構造の基本的な性質ってなんだったでしょうか？

探索木の全てのノードについて、もし左にいくとしたら、

その先のツリーのデータには元のデータよりも小さいものしかありません。

右に行けば、大きなものしかありません。

また本当に大事なポイントは、あるキーの集合があるとき

そのキーについての正当な探索木はたくさんあることです。

この例として

１，２，３，４，５というキーがあるとします。

一方では、ちゃんとバランスされた探索木があります。高さは

２で、1から5までのキーがあります。一方では、無茶苦茶な

連鎖を持ち、連結リストに退化してしまい、高さも要素数N-1と

同じになってしまいます。一般論として、高さについて

指数的な差が生まれます。コストは最良の場合には

対数的と小さいですが、最悪な場合は線形なほど大きくなります。

というわけで、高さについては何にも心配しなくてもよくなるような

性質を持つ探索木が望まれます。そういう木はうまくバランスされることが

わかっています。高さがアルゴリズム的に決まることもわかります

皆さんはもう、うんざりするような線形の高さになるのかと

心配することもなくなります。繰り返しですが、高さが低いことが

なぜそれほど重要なんでしょうか？　なぜなら探索木の

操作の実行時間はすべて、木の高さに依存するからです。

探索するかもしれないし、データを挿入するかも、削除のための置き換えノードを探索するかもしれません。

どんな場合でも、高さが実行時間を支配します。

そして、探索木についての一番大事なアイデアは

皆さんがすでにお考えの通りのものです。つまり、

高さは保持するものの数の対数よりは決して良くならない

ということです。なぜなら、木は二分されるので、どのレベルでも

倍にしかならず、保持しているすべての数に到達するには

対数量が必要になるからです。

さらに、対数的になったとしたら、どんな場合でも対数的に留まる

ということも仮定しましょう。挿入や削除をしてもです。そうしたら

すべて対数時間で行える豊かな操作群を利用できます。

同じように、保持されるキーの数に対して

平衡探索木には物凄くたくさんの種類があります。

それらは、ほとんどの場合、それほど互いには大きくは違いません。

ここでは、その中で一番有名な、赤黒木についてお話します。

これは70年代には見出されていたものです。

ただ、はじめに知られた平衡二分探索木ではありません。

それはAVL木です。赤黒木とそれほど大きな違いがあるわけでは

ありませんが、満たす性質が少しことなります。

もう一つ知っておくとよいこととしては、スプレー木という

面白いアイディアがSleatorとTarjanによって考え出されました。

赤黒木やAVL木では、挿入や削除のときにしか変化しません。

それは、考えてみると、期待されるような性質だと思います。

スプレー木では、自分自身を変更します。探索の場合でも、

検索だけをしているときでもです。

このため、自己調節木と呼ばれることもあります。

それにとてもシンプルで、驚くような性質を保証します。

また最後には、二分木の枠組みを越えて、

B木とB+木も見ておいたほうがよいでしょう。

B木やB+木はデータベースの実装と深い関係があります。

ここでのアイディアは、あるノードについて唯一のキーではなく

多くのキーを持ち、ノードからは持っているキーの数に応じて

多数の枝が出ます。

二分木の枠組みを超えたデータベースにおける動機は

メモリの階層構造にうまくあった構造を持つことです。

これは非常に重要なことですが、この講義の範囲を越えます。

つまり、ここでお話するのは赤黒木についてで、

もっと学ぶ必要があり、学ぶべき場所がわかれば

ここで得られた洞察の多くはほかの平衡木構造に置き換えて考えられるでしょう。

赤黒木はただの二分探索木と同じです。

ただし、新しく幾つかの不変条件を維持しています。

このビデオではじめに説明するのは、

どんな不変条件があるかということ、またどのようにして

その不変条件から、高さが対数的になることを保証するかです。

時間が許せば、どこかの時点で、補助的なビデオで核心となる

赤黒木の実装がどのようにして、挿入や削除のもとで

こうした不変条件を維持するのか説明するかもしれません。

この話はとても込み入っているので、オプショナルな資料に

するほうがよいと思います。ただし、不変条件とはなにか、

不変条件が高さの制御にどのような役割を持つかということは、

あらゆるプログラマが知っておくべきことだと私は思います。

では4つの不変条件を書き出します。そのうち重要なものは

後半ふたつ、つまり3つめと4つめによります。

最初の2つの不変条件は、表面的なものです。

最初のものとして、各ノードに、キーに加えて余計に1ビットの

情報を保存します。このビットによって、あるノードが赤か黒かを

決めます。たぶん、なぜ赤と黒なのか、疑問に思うでしょう。

いや、私も数年前、同じことを同僚のLeo Guibasに

聞きました。教えてくれたところによると、彼と

Sedgewick教授がその論文を書き上げたとき、論文誌では

限られた印刷技術しか使うことができず、出版するには

限られた種類の色しか使えませんでした。だから単に

その色を使い、データ構造に赤黒木と名付け、論文でも

ちゃんと赤と黒の絵を使えたというわけです。残念ながらその後

混乱があり、そうした印刷技術は結局使えませんでした。なので

論文は彼らが思い描いていた通りには印刷されませんでしたが、名前は残ったというわけです。

これが、このデータ構造がどうしてこのような名前になったか

という面白い理由です。次に二番目の不変条件ですが、

探索木のルートノードは常に黒です。赤にはなりません。

いいですか？　では、表面的な不変条件がわかったところで、

残りの2つの主要な条件について見てみましょう。

まずはじめに、赤ノードが並ぶことはありません。

つまり、赤ノードがツリーにあれば、その子ノードは必ず黒です。

もうちょっと考えてみればおわかりでしょうが、つまり

赤ノードがあれば、それは必ず親を持ち、また親は必ず

黒ノードになります。そういう意味で、ツリーのどこででも

赤ノードが並ぶことはありません。最後の不変条件も厳しく、

ルートノードから先端まで取ることのできるどんな経路を取っても

正確に同じ数の黒ノードがなければいけません。

ルートからの経路という意味を明確にしましょう。考えるべきは

失敗した探索ですよね？　失敗した探索では、

ルートからはじめて、大きいか小さいかに応じて

右か左かに行きます。右か左かにたどっていって、

nullポインタに到達します。つまり皆さんに考えてみてほしいのは、

ルートからはじめて、最後にはツリーの末端まで行き着く処理です。

そうするなかで、ある数のノードを調べることになります。

そのうち一部は黒ノードで、一部は赤ノードでしょう。

そして黒ノードの数を考えてみましょう。赤黒木の条件では、

定義上、どんな経路をたどってルートから

nullポインタまでたどっても、たどる黒ノードの数は

全く同じになる、という条件を満たさないといけません。

経路によって変わってはいけません。同じルートからは

完全に同じです。いくつか例を見てみましょう。

こういうことです。赤黒木がうまくバランスしなければ

ならないという考え方を示します。

高さは、基本的には対数的でなければなりません。

考えてみましょう。一番バランスしてないツリーは何でしょう？

それは、このような連鎖ですね。つまり、言いたいのは3ノードの

チェインであっても赤黒木ではないということです。その証明は？

そういうツリーを仮定します。仮に、キーを１，２，３とします。

すると問題は、この3つのノードを赤か黒に色をつけ

4つの不変条件を満たすような方法はあるだろうか、

ということです。ノードを赤か黒にわけます。

条件2から、ルートノードは黒になります。

2と3の色分けについては、4通りの可能性があります。

ですが条件3により、3つの可能性しかありません。

2と3をどちらも赤にしてはいけません。なぜなら、

2つの赤ノードが連続するからです。そこで2が赤で3が黒、

2が黒で3が赤、両方とも黒、という可能性があります。

このどれも同じです。一例として、

2が赤で3が黒としましょう。

ここでは条件4が破られています。実は条件4は

2と3をどのように色分けしても破られます。

条件4は何だったでしょうか？　どんな失敗する探索でも、

全く同じ数の黒ノードを通るということです。

失敗する探索のひとつは、たとえば0です。

0を探索すると、ルートを見て左に行き、nullポインタに

到達します。つまり1つの黒ノードに到達します。

1つです。一方、4を探索したとしましょう。

ルートからはじめて右へ行き、2に行き、さらに右へ、

3に行き、さらに右へ、そしてnullポインタに

到達します。この場合、失敗した探索で

2つの黒ノードにぶつかります。1と3です。

つまり不変条件4が破られています。したがって、

これは赤黒木ではありません。どのように2と3を

塗り分けてもどれかの不変条件が破られるという確認は

自分で確認してみてください。両方赤なら条件3が破られます。

少なくとも1つが赤なら、条件4は破られます。

つまりこれは赤黒木ではないという例です。

では赤黒木の例も見てみましょう。

ある探索木が、実際にノードを赤と黒に塗り分け、

全ての4つの不変条件が満たされるようなものです。

赤黒木のとても簡単な例は、完全にバランスした木です。

たとえば、このように3つのノードがあって、３，５，７のキーがあり

5がルートになっているとします。

両側に子ノードがひとつずつあります。

3と7です。これは赤黒木でしょうか？

問題は何だったでしょうか？

この3つのノードを赤か黒に塗り分けて、4つの不変条件を

全て満たすような方法はあるか？ということです。

ちょっと考えてみると、そう、たしかにこのノードを塗り分けて

条件を満たすことができることがわかるでしょう。

とくに、全部のノードを黒だとしましょう。

条件1は満たされます。すべてのノードには色がついています。

条件2も満たされます。ルートノードは黒です。

条件3も満たされます。赤ノードはないので、

赤ノードが並ぶこともありません。そして、考えてみると、

条件4も満たされます。なぜなら、ツリーは完全にバランスしているからです。

どういう探索で失敗しても、必ず2つの黒ノードを

通過します。たとえば1を検索すると、

3と5を通ります。6を検索すれば、

5と7を通ります。つまり、ルートからのあらゆる経路は正確に

2つの黒ノードを持ち、第4の不変条件も満たされます。

素晴らしい。ですがもちろん、二分探索木のポイントは、

動的にしたいということです。

挿入や削除に対応できないといけません。

挿入や削除のたびに、赤黒木に新しいノードができます。

たとえば挿入の場合、新しいノードができて

色を決めねばなりません。すると突然、4つの不変条件の

どれも破られないか心配になってきますね。

では、あまり大変なことをしなくても挿入できるような、

簡単な場合を見てみます。またの機会に、オプショナルなビデオで

ツリーの回転によって、もっと根本的な探索木の再構築を

行い、4つの不変条件を維持してバランスした状態を保つための

解説をします。では、ここに赤黒木があって、全部のノードが黒

だとします。そして例えば6を挿入します。

ここに。ここでもし、これを黒にすると、

もう赤黒木ではありません。なぜなら、たとえば5.5を探索すると、

3つの黒ノードに遭遇することになるからです。

ここで1を探索すると、2つの黒ノードにしか遭遇しません。

だからこれではうまく行きません。

ですが6を黒にするかわりに、赤にするとうまくいきます。

この場合、6は条件4からは無関係になります。

ルートからのどのパスにもあらわれません。

元のツリーではどのパスでも2つの黒ノードがあるのでした。

6が来る前は。そして、6が赤ならこれは変わりません。

つまり、6を挿入しても赤くすれば4つの条件は全て満たされます。

次に、たとえば8を挿入しましょう。全く同じやり方が使えます。

8を赤とします。同じく、このノードは条件4には参加しません。

なので破られません。さらに言えば、2つの赤ノードは並んでいないので、

条件3も破られていません。

というわけで、これも赤黒木です。実は、この赤黒木を

4つの条件を満たしつつ塗り分けるのは

これだけではありません。たとえば、6と8を黒に変更します。

ただ同時に、7を赤に塗り分けます。これで完璧です。

明らかに最初の3つの不変条件は満たされます。

また、6と8の赤を合併して上に押し上げ、

7を赤にすることで、黒ノードの数は、どんな経路でも

かわりません。6を通ったパスは7を通りますし、

8を通った経路も7を通ります。だから、

これまでと同じく、正確に同じ数の赤と黒のノードが、

どちらの経路でも存在します。つまり、全ての経路が

同じ数の黒ノードを持ち、条件4は満たされます。

ここでは、ごく単純な例だけをお見せしています。挿入の際、

赤黒の性質を守るために大したことは必要ありません。

一般に、もっとたくさんのものを挿入したり削除すると、

4つの不変条件を維持するために大変なことをしなければいけなくなります。

時間が許せば、オプショナルなビデオでそのさわりを説明します。

ところで、赤黒木に足された一見適当な条件の

要点は何でしょうか？　実は4つの不変条件を

全て満たすようにすると、高さが小さくなるというのが

要点です。そして高さが小さくなるので、

全ての操作が速くなるのです。

では、4つの不変条件を満たすと、高さがとても

小さくなることを証明します。実は、考えうる最小値の倍

ほぼlog_2(N)の2倍を超えません。

正式にいえば、任意のNノードの赤黒木では、高さは

O(log N)、より正確には 2log_2(N+1)となります。

証明しましょう。この証明についてはっきりしているのは、

不変条件3と4の果たす役割です。

本質的に、この不変条件が保証するのは、赤黒木は

完全平衡木にある係数の増加を加えたようになります。

どういう意味か見てみましょう。とある考え方から始めます。

ここでは、赤黒木には何もしません。

色のことはいったん忘れてください。二分木の構造だけを考えます。

そして、ツリーの中のルートノードからの経路の長さに

下限があるとします。これをkとしましょう。

kを、たとえば10とでも考えてみてください。あるツリーがあって

ルートからはじめ、左右のどのように経路をたどって

nullポインタまで到達しても、どう選んでも、

少なくともk個のノードはたどることになります。

もしこの仮定が満たされるなら、考えてみてください、

このツリーの上位は完全に埋まっています。このツリーの上位は

完全平衡木になっています。高さk-1の二分木です。

では、k=3となるようなツリーを描いてみます。

ルートからnullポインタまでどのように移動しても、必ず

最低3つのノードを見るということです。つまり上位3階層は

完全に埋まっています。まずルートがあって、

両側に子ノードがあります。孫ノードは全部で4つ。

この考え方を、背理法で証明します。

実際、上位k階層のノードのどれかが欠けていたとすると、

k個のノードをたどる前にnullポインタに到達する経路が

存在します。ここでのポイントは、この下限から、

ツリー内のノード数の下限が、ルートからnullまでの経路の

長さの関数として与えられるということです。ツリーの大きさNは

深さk-1の完全平衡木のノード数、つまり2のk乗-1を

含みます。たとえばk=3なら

2の3乗-1の7です。これはツリーについての基本的な事実で

赤黒木とは関係ありません。ではこれと赤黒木の不変条件を

組み合わせて、なぜ赤黒木が低くなるか考えましょう。

また、前のスライドの結論を振り返りましょう。

ツリーのノード数Nは、少なくとも2のk乗-1はあります。

ここでkは、ルートからnullまでの経路の一番小さい値です。

このことを少し書き換えて、kに対してNに

制約を与えるのではなく、Nからkの上限を決めましょう。

つまり、ルートからのあらゆる経路の長さの最小値は、

log_2(N+1)より大きくなることはありません。

これは単に両辺に1を足して2を底とした対数を取るだけです。

では、これの何がいいんでしょうか？　では赤黒木について

考えましょう。ノード数Nの赤黒木です。

何が言えるでしょうか？　赤黒木と関係なく

あるルートからnullまでの経路のノードの数は、

たかだかlog_2(N+1)です。最善の場合で。全部が黒ノードです。

いくらかは赤ノードですが、最大の場合では、全てが黒ノードです。

つまり、Nノードの赤黒木について次のことが言えます。

ルート-null経路には、最大でもlog_2(N+1)の黒ノードしか含まれない。

これは、証明したことよりは弱い主張です。

証明したのは、log_2(N+1)ノードを必ず持つということですから。

というわけで、経路は確実にlog_2(N+1)個の

黒ノードを持つことがわかりました。では2つの不変条件から

2つのノックアウトパンチを繰り出しましょう。そもそも、

4つの不変条件は何を言っていたでしょうか？　言っていたのは

赤黒木の経路を見た時、ルートからはじめて

失敗した探索を考えました。nullポインタまでたどります。

そして、赤ノードが見えないとして、全然数えないとすると、

経路には対数的な数のノードしかないということです。

もちろん、赤黒木の高さについて考えるときは、すべてのノードを

考えます。赤ノードと黒ノードを。

これまでのところ、黒ノードしか考えないと、うまくいって、

log_2(N+1)個のノードだけしかないということです。

ここで不変条件3がやってきます。

この条件は実は、ツリーでは黒ノードが多数派だと言っています。

もともとは、どんな経路でも赤ノードが並ばないということです。

もし黒ノードの数が少なければ、赤ノードを並べることは

できないので、経路上のノード数も2倍にしかなりません。

最悪の場合で、黒のルートノードがあり、赤ノード、次に黒、次に赤

黒、赤、黒、などとなります。最悪の場合でも赤ノードの数は

黒ノードの数と等しくなります。経路の長さは、赤ノードを

考えた時、倍になります。そして、これはまさしく、

ツリーの高さが対数的になるということです。実際、これは

もしツリーが4つの不変条件を満たすなら、とくに

赤ノードが並ばないというのと、黒ノードの経路上の数が等しい

というなら、ツリーのことは他に何も知らなくても、ツリーは

バランスされるという主張が証明されます。2を底として

完全にバランスされます。また、ポイントとしては、

探索木の操作も対数時間で実行されます。

なぜなら、高さがこうした操作の実行時間を支配するからです。

さて、ある意味では、簡単な部分はお話しました。

探索木が4つの不変条件を満たすなら、それでうまく行く。

高さが小さくなり、操作は速くなることが保証されます。

明らかにこれが、このデータ構造から欲しかったことです。

ただ、このデータ構造を実際に実装しないといけない哀れな者どもは、

データ構造が変化しても不変条件を維持するための労力をかけることになります。

ここでの問題は動的であること、挿入と削除に対応することです。

挿入と削除は4つの不変条件を台なしにするかもしれないので、

コードを書き換えて条件を満たすようにすることで、ツリーを

平衡に保ち、どんな挿入と削除の順番でも高さを保つ必要が

あります。この部分は、このビデオでは扱いません。

操作のどれも明らかに遅くすることなしに実現できます。

これはとても複雑で、面白いアイデアを使います。

有名なアルゴリズムがいくつかあり、教科書に詳しく書いてあります。

もしくは、オープンソースで平衡探索木のコードを探せば、

実装するコードを読むこともできます。

ともあれ、現実的に実現でき、しかも赤黒木は

豊富な操作をサポートするので、

数学アプリケーションでよく見かけます。また同じ理由から、

平衡木はプログラミングツールボックスの一部となっています。