WEBVTT

00:00:00.000 --> 00:00:03.084
このビデオでは、ただの二分探索は

00:00:03.084 --> 00:00:07.035
既にお話しので、次のお話に進みたいと思います。

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

00:00:10.067 --> 00:00:13.852
あなたが実際に必要とする探索木です。

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

00:00:17.627 --> 00:00:21.015
高さが対数的であることが保証されているということです。つまり、

00:00:21.015 --> 00:00:25.005
二分探索木において私たちが学び、愛した全ての操作について

00:00:25.005 --> 00:00:27.012
保持するキーの数に対して対数的に処理されるということです。

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

00:00:30.056 --> 00:00:34.075
探索木の全てのノードについて、もし左にいくとしたら、

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

00:00:38.060 --> 00:00:42.025
右に行けば、大きなものしかありません。

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

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

00:00:48.875 --> 00:00:50.986
この例として

00:00:50.986 --> 00:00:53.532
１，２，３，４，５というキーがあるとします。

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

00:00:57.589 --> 00:01:01.618
２で、1から5までのキーがあります。一方では、無茶苦茶な

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

00:01:05.957 --> 00:01:08.936
同じになってしまいます。一般論として、高さについて

00:01:08.936 --> 00:01:13.479
指数的な差が生まれます。コストは最良の場合には

00:01:13.479 --> 00:01:16.417
対数的と小さいですが、最悪な場合は線形なほど大きくなります。

00:01:16.417 --> 00:01:20.148
というわけで、高さについては何にも心配しなくてもよくなるような

00:01:20.148 --> 00:01:23.621
性質を持つ探索木が望まれます。そういう木はうまくバランスされることが

00:01:23.621 --> 00:01:25.589
わかっています。高さがアルゴリズム的に決まることもわかります

00:01:25.589 --> 00:01:28.236
皆さんはもう、うんざりするような線形の高さになるのかと

00:01:28.236 --> 00:01:32.309
心配することもなくなります。繰り返しですが、高さが低いことが

00:01:32.309 --> 00:01:35.481
なぜそれほど重要なんでしょうか？　なぜなら探索木の

00:01:35.481 --> 00:01:38.773
操作の実行時間はすべて、木の高さに依存するからです。

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

00:01:43.455 --> 00:01:48.334
どんな場合でも、高さが実行時間を支配します。

00:01:48.334 --> 00:01:50.013
そして、探索木についての一番大事なアイデアは

00:01:50.013 --> 00:01:54.776
皆さんがすでにお考えの通りのものです。つまり、

00:01:54.776 --> 00:01:58.463
高さは保持するものの数の対数よりは決して良くならない

00:01:58.463 --> 00:02:02.186
ということです。なぜなら、木は二分されるので、どのレベルでも

00:02:02.186 --> 00:02:05.151
倍にしかならず、保持しているすべての数に到達するには

00:02:05.151 --> 00:02:07.040
対数量が必要になるからです。

00:02:07.040 --> 00:02:11.007
さらに、対数的になったとしたら、どんな場合でも対数的に留まる

00:02:11.007 --> 00:02:16.399
ということも仮定しましょう。挿入や削除をしてもです。そうしたら

00:02:16.399 --> 00:02:21.012
すべて対数時間で行える豊かな操作群を利用できます。

00:02:21.056 --> 00:02:25.048
同じように、保持されるキーの数に対して

00:02:25.048 --> 00:02:29.006
平衡探索木には物凄くたくさんの種類があります。

00:02:29.006 --> 00:02:33.022
それらは、ほとんどの場合、それほど互いには大きくは違いません。

00:02:33.022 --> 00:02:37.092
ここでは、その中で一番有名な、赤黒木についてお話します。

00:02:37.092 --> 00:02:40.062
これは70年代には見出されていたものです。

00:02:40.096 --> 00:02:44.674
ただ、はじめに知られた平衡二分探索木ではありません。

00:02:44.674 --> 00:02:49.000
それはAVL木です。赤黒木とそれほど大きな違いがあるわけでは

00:02:49.000 --> 00:02:51.617
ありませんが、満たす性質が少しことなります。

00:02:51.617 --> 00:02:55.997
もう一つ知っておくとよいこととしては、スプレー木という

00:02:55.997 --> 00:02:58.454
面白いアイディアがSleatorとTarjanによって考え出されました。

00:02:58.454 --> 00:03:01.797
赤黒木やAVL木では、挿入や削除のときにしか変化しません。

00:03:01.797 --> 00:03:05.725
それは、考えてみると、期待されるような性質だと思います。

00:03:05.725 --> 00:03:08.583
スプレー木では、自分自身を変更します。探索の場合でも、

00:03:08.583 --> 00:03:11.788
検索だけをしているときでもです。

00:03:11.788 --> 00:03:15.738
このため、自己調節木と呼ばれることもあります。

00:03:15.738 --> 00:03:20.653
それにとてもシンプルで、驚くような性質を保証します。

00:03:20.653 --> 00:03:25.213
また最後には、二分木の枠組みを越えて、

00:03:25.213 --> 00:03:28.281
B木とB+木も見ておいたほうがよいでしょう。

00:03:28.281 --> 00:03:31.443
B木やB+木はデータベースの実装と深い関係があります。

00:03:31.443 --> 00:03:35.499
ここでのアイディアは、あるノードについて唯一のキーではなく

00:03:35.499 --> 00:03:39.567
多くのキーを持ち、ノードからは持っているキーの数に応じて

00:03:39.567 --> 00:03:44.306
多数の枝が出ます。

00:03:44.306 --> 00:03:47.138
二分木の枠組みを超えたデータベースにおける動機は

00:03:47.138 --> 00:03:50.668
メモリの階層構造にうまくあった構造を持つことです。

00:03:50.668 --> 00:03:53.295
これは非常に重要なことですが、この講義の範囲を越えます。

00:03:53.295 --> 00:03:57.316
つまり、ここでお話するのは赤黒木についてで、

00:03:57.316 --> 00:04:01.133
もっと学ぶ必要があり、学ぶべき場所がわかれば

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

00:04:05.641 --> 00:04:09.169
赤黒木はただの二分探索木と同じです。

00:04:09.169 --> 00:04:13.414
ただし、新しく幾つかの不変条件を維持しています。

00:04:13.414 --> 00:04:16.356
このビデオではじめに説明するのは、

00:04:16.356 --> 00:04:19.775
どんな不変条件があるかということ、またどのようにして

00:04:19.775 --> 00:04:22.849
その不変条件から、高さが対数的になることを保証するかです。

00:04:22.849 --> 00:04:27.080
時間が許せば、どこかの時点で、補助的なビデオで核心となる

00:04:27.080 --> 00:04:31.612
赤黒木の実装がどのようにして、挿入や削除のもとで

00:04:31.612 --> 00:04:34.098
こうした不変条件を維持するのか説明するかもしれません。

00:04:34.098 --> 00:04:37.676
この話はとても込み入っているので、オプショナルな資料に

00:04:37.676 --> 00:04:40.530
するほうがよいと思います。ただし、不変条件とはなにか、

00:04:40.530 --> 00:04:44.794
不変条件が高さの制御にどのような役割を持つかということは、

00:04:44.794 --> 00:04:47.291
あらゆるプログラマが知っておくべきことだと私は思います。

00:04:47.291 --> 00:04:51.152
では4つの不変条件を書き出します。そのうち重要なものは

00:04:51.152 --> 00:04:54.420
後半ふたつ、つまり3つめと4つめによります。

00:04:54.420 --> 00:04:57.986
最初の2つの不変条件は、表面的なものです。

00:04:57.986 --> 00:05:01.980
最初のものとして、各ノードに、キーに加えて余計に1ビットの

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

00:05:06.783 --> 00:05:09.827
決めます。たぶん、なぜ赤と黒なのか、疑問に思うでしょう。

00:05:09.827 --> 00:05:12.464
いや、私も数年前、同じことを同僚のLeo Guibasに

00:05:12.464 --> 00:05:16.076
聞きました。教えてくれたところによると、彼と

00:05:16.076 --> 00:05:20.990
Sedgewick教授がその論文を書き上げたとき、論文誌では

00:05:20.990 --> 00:05:24.793
限られた印刷技術しか使うことができず、出版するには

00:05:24.793 --> 00:05:28.097
限られた種類の色しか使えませんでした。だから単に

00:05:28.097 --> 00:05:32.085
その色を使い、データ構造に赤黒木と名付け、論文でも

00:05:32.085 --> 00:05:36.028
ちゃんと赤と黒の絵を使えたというわけです。残念ながらその後

00:05:36.028 --> 00:05:40.172
混乱があり、そうした印刷技術は結局使えませんでした。なので

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

00:05:44.038 --> 00:05:47.897
これが、このデータ構造がどうしてこのような名前になったか

00:05:48.055 --> 00:05:51.942
という面白い理由です。次に二番目の不変条件ですが、

00:05:51.942 --> 00:05:56.060
探索木のルートノードは常に黒です。赤にはなりません。

00:05:56.060 --> 00:05:58.092
いいですか？　では、表面的な不変条件がわかったところで、

00:05:58.092 --> 00:06:02.045
残りの2つの主要な条件について見てみましょう。

00:06:02.045 --> 00:06:06.023
まずはじめに、赤ノードが並ぶことはありません。

00:06:06.023 --> 00:06:12.820
つまり、赤ノードがツリーにあれば、その子ノードは必ず黒です。

00:06:12.820 --> 00:06:16.011
もうちょっと考えてみればおわかりでしょうが、つまり

00:06:16.011 --> 00:06:20.019
赤ノードがあれば、それは必ず親を持ち、また親は必ず

00:06:20.019 --> 00:06:24.076
黒ノードになります。そういう意味で、ツリーのどこででも

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

00:06:30.079 --> 00:06:37.046
ルートノードから先端まで取ることのできるどんな経路を取っても

00:06:37.046 --> 00:06:41.019
正確に同じ数の黒ノードがなければいけません。

00:06:41.019 --> 00:06:45.956
ルートからの経路という意味を明確にしましょう。考えるべきは

00:06:45.956 --> 00:06:49.371
失敗した探索ですよね？　失敗した探索では、

00:06:49.371 --> 00:06:53.225
ルートからはじめて、大きいか小さいかに応じて

00:06:53.225 --> 00:06:57.154
右か左かに行きます。右か左かにたどっていって、

00:06:57.154 --> 00:07:01.053
nullポインタに到達します。つまり皆さんに考えてみてほしいのは、

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

00:07:04.938 --> 00:07:07.098
そうするなかで、ある数のノードを調べることになります。

00:07:07.098 --> 00:07:11.030
そのうち一部は黒ノードで、一部は赤ノードでしょう。

00:07:11.030 --> 00:07:15.364
そして黒ノードの数を考えてみましょう。赤黒木の条件では、

00:07:15.364 --> 00:07:19.529
定義上、どんな経路をたどってルートから

00:07:19.529 --> 00:07:24.096
nullポインタまでたどっても、たどる黒ノードの数は

00:07:24.096 --> 00:07:27.278
全く同じになる、という条件を満たさないといけません。

00:07:27.278 --> 00:07:31.788
経路によって変わってはいけません。同じルートからは

00:07:31.788 --> 00:07:34.559
完全に同じです。いくつか例を見てみましょう。

00:07:34.559 --> 00:07:38.408
こういうことです。赤黒木がうまくバランスしなければ

00:07:38.408 --> 00:07:42.667
ならないという考え方を示します。

00:07:42.667 --> 00:07:45.745
高さは、基本的には対数的でなければなりません。

00:07:45.745 --> 00:07:49.019
考えてみましょう。一番バランスしてないツリーは何でしょう？

00:07:49.019 --> 00:07:54.123
それは、このような連鎖ですね。つまり、言いたいのは3ノードの

00:07:54.123 --> 00:07:58.393
チェインであっても赤黒木ではないということです。その証明は？

00:07:58.393 --> 00:08:04.965
そういうツリーを仮定します。仮に、キーを１，２，３とします。

00:08:04.965 --> 00:08:08.465
すると問題は、この3つのノードを赤か黒に色をつけ

00:08:08.465 --> 00:08:13.382
4つの不変条件を満たすような方法はあるだろうか、

00:08:13.382 --> 00:08:17.060
ということです。ノードを赤か黒にわけます。

00:08:17.060 --> 00:08:20.379
条件2から、ルートノードは黒になります。

00:08:20.379 --> 00:08:24.412
2と3の色分けについては、4通りの可能性があります。

00:08:24.412 --> 00:08:27.446
ですが条件3により、3つの可能性しかありません。

00:08:27.446 --> 00:08:30.246
2と3をどちらも赤にしてはいけません。なぜなら、

00:08:30.246 --> 00:08:34.018
2つの赤ノードが連続するからです。そこで2が赤で3が黒、

00:08:34.018 --> 00:08:37.007
2が黒で3が赤、両方とも黒、という可能性があります。

00:08:37.007 --> 00:08:41.069
このどれも同じです。一例として、

00:08:41.069 --> 00:08:44.083
2が赤で3が黒としましょう。

00:08:44.083 --> 00:08:48.491
ここでは条件4が破られています。実は条件4は

00:08:48.491 --> 00:08:53.001
2と3をどのように色分けしても破られます。

00:08:53.001 --> 00:08:56.619
条件4は何だったでしょうか？　どんな失敗する探索でも、

00:08:56.619 --> 00:09:00.006
全く同じ数の黒ノードを通るということです。

00:09:00.006 --> 00:09:03.062
失敗する探索のひとつは、たとえば0です。

00:09:03.062 --> 00:09:07.083
0を探索すると、ルートを見て左に行き、nullポインタに

00:09:07.083 --> 00:09:10.027
到達します。つまり1つの黒ノードに到達します。

00:09:10.027 --> 00:09:12.063
1つです。一方、4を探索したとしましょう。

00:09:12.063 --> 00:09:15.285
ルートからはじめて右へ行き、2に行き、さらに右へ、

00:09:15.285 --> 00:09:19.396
3に行き、さらに右へ、そしてnullポインタに

00:09:19.396 --> 00:09:22.018
到達します。この場合、失敗した探索で

00:09:22.018 --> 00:09:24.060
2つの黒ノードにぶつかります。1と3です。

00:09:24.060 --> 00:09:28.008
つまり不変条件4が破られています。したがって、

00:09:28.008 --> 00:09:30.063
これは赤黒木ではありません。どのように2と3を

00:09:30.063 --> 00:09:34.043
塗り分けてもどれかの不変条件が破られるという確認は

00:09:34.043 --> 00:09:37.003
自分で確認してみてください。両方赤なら条件3が破られます。

00:09:37.003 --> 00:09:39.023
少なくとも1つが赤なら、条件4は破られます。

00:09:39.023 --> 00:09:42.040
つまりこれは赤黒木ではないという例です。

00:09:42.040 --> 00:09:44.410
では赤黒木の例も見てみましょう。

00:09:44.410 --> 00:09:48.014
ある探索木が、実際にノードを赤と黒に塗り分け、

00:09:48.014 --> 00:09:52.016
全ての4つの不変条件が満たされるようなものです。

00:09:52.016 --> 00:09:56.057
赤黒木のとても簡単な例は、完全にバランスした木です。

00:09:56.057 --> 00:09:59.008
たとえば、このように3つのノードがあって、３，５，７のキーがあり

00:09:59.008 --> 00:10:03.049
5がルートになっているとします。

00:10:03.049 --> 00:10:06.022
両側に子ノードがひとつずつあります。

00:10:06.022 --> 00:10:09.040
3と7です。これは赤黒木でしょうか？

00:10:09.040 --> 00:10:11.097
問題は何だったでしょうか？

00:10:11.097 --> 00:10:16.049
この3つのノードを赤か黒に塗り分けて、4つの不変条件を

00:10:16.049 --> 00:10:19.005
全て満たすような方法はあるか？ということです。

00:10:19.075 --> 00:10:24.010
ちょっと考えてみると、そう、たしかにこのノードを塗り分けて

00:10:24.010 --> 00:10:27.061
条件を満たすことができることがわかるでしょう。

00:10:27.061 --> 00:10:31.000
とくに、全部のノードを黒だとしましょう。

00:10:31.036 --> 00:10:34.048
条件1は満たされます。すべてのノードには色がついています。

00:10:34.048 --> 00:10:37.095
条件2も満たされます。ルートノードは黒です。

00:10:37.095 --> 00:10:41.076
条件3も満たされます。赤ノードはないので、

00:10:41.076 --> 00:10:45.019
赤ノードが並ぶこともありません。そして、考えてみると、

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

00:10:48.073 --> 00:10:52.098
どういう探索で失敗しても、必ず2つの黒ノードを

00:10:52.098 --> 00:10:55.043
通過します。たとえば1を検索すると、

00:10:55.043 --> 00:10:59.002
3と5を通ります。6を検索すれば、

00:10:59.002 --> 00:11:01.909
5と7を通ります。つまり、ルートからのあらゆる経路は正確に

00:11:01.909 --> 00:11:05.077
2つの黒ノードを持ち、第4の不変条件も満たされます。

00:11:05.077 --> 00:11:08.046
素晴らしい。ですがもちろん、二分探索木のポイントは、

00:11:08.046 --> 00:11:11.033
動的にしたいということです。

00:11:11.033 --> 00:11:13.068
挿入や削除に対応できないといけません。

00:11:13.068 --> 00:11:17.047
挿入や削除のたびに、赤黒木に新しいノードができます。

00:11:17.047 --> 00:11:19.290
たとえば挿入の場合、新しいノードができて

00:11:19.290 --> 00:11:23.279
色を決めねばなりません。すると突然、4つの不変条件の

00:11:23.279 --> 00:11:25.485
どれも破られないか心配になってきますね。

00:11:25.485 --> 00:11:28.952
では、あまり大変なことをしなくても挿入できるような、

00:11:28.952 --> 00:11:32.056
簡単な場合を見てみます。またの機会に、オプショナルなビデオで

00:11:32.056 --> 00:11:35.998
ツリーの回転によって、もっと根本的な探索木の再構築を

00:11:35.998 --> 00:11:40.540
行い、4つの不変条件を維持してバランスした状態を保つための

00:11:40.699 --> 00:11:44.164
解説をします。では、ここに赤黒木があって、全部のノードが黒

00:11:44.164 --> 00:11:48.367
だとします。そして例えば6を挿入します。

00:11:48.367 --> 00:11:51.054
ここに。ここでもし、これを黒にすると、

00:11:51.054 --> 00:11:55.033
もう赤黒木ではありません。なぜなら、たとえば5.5を探索すると、

00:11:55.033 --> 00:11:59.622
3つの黒ノードに遭遇することになるからです。

00:11:59.622 --> 00:12:03.462
ここで1を探索すると、2つの黒ノードにしか遭遇しません。

00:12:03.462 --> 00:12:05.706
だからこれではうまく行きません。

00:12:05.706 --> 00:12:09.969
ですが6を黒にするかわりに、赤にするとうまくいきます。

00:12:09.969 --> 00:12:13.544
この場合、6は条件4からは無関係になります。

00:12:13.544 --> 00:12:16.406
ルートからのどのパスにもあらわれません。

00:12:16.406 --> 00:12:20.858
元のツリーではどのパスでも2つの黒ノードがあるのでした。

00:12:20.858 --> 00:12:24.275
6が来る前は。そして、6が赤ならこれは変わりません。

00:12:24.275 --> 00:12:28.993
つまり、6を挿入しても赤くすれば4つの条件は全て満たされます。

00:12:28.993 --> 00:12:33.209
次に、たとえば8を挿入しましょう。全く同じやり方が使えます。

00:12:33.209 --> 00:12:37.142
8を赤とします。同じく、このノードは条件4には参加しません。

00:12:37.142 --> 00:12:42.021
なので破られません。さらに言えば、2つの赤ノードは並んでいないので、

00:12:42.021 --> 00:12:45.073
条件3も破られていません。

00:12:45.073 --> 00:12:50.042
というわけで、これも赤黒木です。実は、この赤黒木を

00:12:50.042 --> 00:12:54.092
4つの条件を満たしつつ塗り分けるのは

00:12:54.092 --> 00:12:57.082
これだけではありません。たとえば、6と8を黒に変更します。

00:12:57.082 --> 00:13:02.001
ただ同時に、7を赤に塗り分けます。これで完璧です。

00:13:02.001 --> 00:13:05.000
明らかに最初の3つの不変条件は満たされます。

00:13:05.000 --> 00:13:09.009
また、6と8の赤を合併して上に押し上げ、

00:13:09.009 --> 00:13:13.035
7を赤にすることで、黒ノードの数は、どんな経路でも

00:13:13.035 --> 00:13:16.044
かわりません。6を通ったパスは7を通りますし、

00:13:16.044 --> 00:13:20.070
8を通った経路も7を通ります。だから、

00:13:20.070 --> 00:13:24.923
これまでと同じく、正確に同じ数の赤と黒のノードが、

00:13:24.923 --> 00:13:28.077
どちらの経路でも存在します。つまり、全ての経路が

00:13:28.077 --> 00:13:30.835
同じ数の黒ノードを持ち、条件4は満たされます。

00:13:30.835 --> 00:13:36.595
ここでは、ごく単純な例だけをお見せしています。挿入の際、

00:13:36.595 --> 00:13:39.895
赤黒の性質を守るために大したことは必要ありません。

00:13:39.895 --> 00:13:44.459
一般に、もっとたくさんのものを挿入したり削除すると、

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

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

00:13:52.807 --> 00:13:57.748
ところで、赤黒木に足された一見適当な条件の

00:13:57.748 --> 00:14:00.478
要点は何でしょうか？　実は4つの不変条件を

00:14:00.478 --> 00:14:05.475
全て満たすようにすると、高さが小さくなるというのが

00:14:05.475 --> 00:14:07.839
要点です。そして高さが小さくなるので、

00:14:07.839 --> 00:14:10.098
全ての操作が速くなるのです。

00:14:10.098 --> 00:14:15.695
では、4つの不変条件を満たすと、高さがとても

00:14:15.695 --> 00:14:20.030
小さくなることを証明します。実は、考えうる最小値の倍

00:14:20.030 --> 00:14:24.040
ほぼlog_2(N)の2倍を超えません。

00:14:24.040 --> 00:14:31.003
正式にいえば、任意のNノードの赤黒木では、高さは

00:14:31.003 --> 00:14:36.884
O(log N)、より正確には 2log_2(N+1)となります。

00:14:36.886 --> 00:14:41.723
証明しましょう。この証明についてはっきりしているのは、

00:14:41.723 --> 00:14:46.089
不変条件3と4の果たす役割です。

00:14:46.089 --> 00:14:51.914
本質的に、この不変条件が保証するのは、赤黒木は

00:14:51.914 --> 00:14:57.010
完全平衡木にある係数の増加を加えたようになります。

00:14:57.010 --> 00:15:01.010
どういう意味か見てみましょう。とある考え方から始めます。

00:15:01.010 --> 00:15:03.083
ここでは、赤黒木には何もしません。

00:15:03.083 --> 00:15:08.006
色のことはいったん忘れてください。二分木の構造だけを考えます。

00:15:08.006 --> 00:15:10.059
そして、ツリーの中のルートノードからの経路の長さに

00:15:10.059 --> 00:15:14.082
下限があるとします。これをkとしましょう。

00:15:14.082 --> 00:15:18.079
kを、たとえば10とでも考えてみてください。あるツリーがあって

00:15:18.079 --> 00:15:22.097
ルートからはじめ、左右のどのように経路をたどって

00:15:22.097 --> 00:15:26.079
nullポインタまで到達しても、どう選んでも、

00:15:26.079 --> 00:15:29.032
少なくともk個のノードはたどることになります。

00:15:29.032 --> 00:15:34.069
もしこの仮定が満たされるなら、考えてみてください、

00:15:34.069 --> 00:15:39.032
このツリーの上位は完全に埋まっています。このツリーの上位は

00:15:39.032 --> 00:15:43.060
完全平衡木になっています。高さk-1の二分木です。

00:15:43.062 --> 00:15:46.028
では、k=3となるようなツリーを描いてみます。

00:15:46.033 --> 00:15:50.083
ルートからnullポインタまでどのように移動しても、必ず

00:15:50.083 --> 00:15:54.098
最低3つのノードを見るということです。つまり上位3階層は

00:15:54.098 --> 00:15:57.087
完全に埋まっています。まずルートがあって、

00:15:57.087 --> 00:16:01.074
両側に子ノードがあります。孫ノードは全部で4つ。

00:16:01.074 --> 00:16:04.083
この考え方を、背理法で証明します。

00:16:04.083 --> 00:16:08.019
実際、上位k階層のノードのどれかが欠けていたとすると、

00:16:08.019 --> 00:16:13.016
k個のノードをたどる前にnullポインタに到達する経路が

00:16:13.016 --> 00:16:18.045
存在します。ここでのポイントは、この下限から、

00:16:18.045 --> 00:16:23.086
ツリー内のノード数の下限が、ルートからnullまでの経路の

00:16:23.086 --> 00:16:28.086
長さの関数として与えられるということです。ツリーの大きさNは

00:16:28.086 --> 00:16:34.315
深さk-1の完全平衡木のノード数、つまり2のk乗-1を

00:16:34.315 --> 00:16:40.094
含みます。たとえばk=3なら

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

00:16:45.346 --> 00:16:49.553
赤黒木とは関係ありません。ではこれと赤黒木の不変条件を

00:16:49.553 --> 00:16:54.740
組み合わせて、なぜ赤黒木が低くなるか考えましょう。

00:16:54.740 --> 00:16:58.828
また、前のスライドの結論を振り返りましょう。

00:16:58.828 --> 00:17:04.407
ツリーのノード数Nは、少なくとも2のk乗-1はあります。

00:17:04.407 --> 00:17:08.932
ここでkは、ルートからnullまでの経路の一番小さい値です。

00:17:08.932 --> 00:17:13.503
このことを少し書き換えて、kに対してNに

00:17:13.503 --> 00:17:18.366
制約を与えるのではなく、Nからkの上限を決めましょう。

00:17:18.366 --> 00:17:23.481
つまり、ルートからのあらゆる経路の長さの最小値は、

00:17:23.481 --> 00:17:26.803
log_2(N+1)より大きくなることはありません。

00:17:26.804 --> 00:17:31.243
これは単に両辺に1を足して2を底とした対数を取るだけです。

00:17:31.243 --> 00:17:35.355
では、これの何がいいんでしょうか？　では赤黒木について

00:17:35.355 --> 00:17:38.022
考えましょう。ノード数Nの赤黒木です。

00:17:38.022 --> 00:17:42.208
何が言えるでしょうか？　赤黒木と関係なく

00:17:42.208 --> 00:17:48.156
あるルートからnullまでの経路のノードの数は、

00:17:48.156 --> 00:17:52.622
たかだかlog_2(N+1)です。最善の場合で。全部が黒ノードです。

00:17:52.622 --> 00:17:57.236
いくらかは赤ノードですが、最大の場合では、全てが黒ノードです。

00:17:57.236 --> 00:18:00.065
つまり、Nノードの赤黒木について次のことが言えます。

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

00:18:06.176 --> 00:18:10.747
これは、証明したことよりは弱い主張です。

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

00:18:15.500 --> 00:18:18.339
というわけで、経路は確実にlog_2(N+1)個の

00:18:18.339 --> 00:18:21.878
黒ノードを持つことがわかりました。では2つの不変条件から

00:18:21.878 --> 00:18:25.742
2つのノックアウトパンチを繰り出しましょう。そもそも、

00:18:25.742 --> 00:18:29.167
4つの不変条件は何を言っていたでしょうか？　言っていたのは

00:18:29.167 --> 00:18:33.014
赤黒木の経路を見た時、ルートからはじめて

00:18:33.014 --> 00:18:35.380
失敗した探索を考えました。nullポインタまでたどります。

00:18:35.380 --> 00:18:39.093
そして、赤ノードが見えないとして、全然数えないとすると、

00:18:39.093 --> 00:18:43.033
経路には対数的な数のノードしかないということです。

00:18:43.033 --> 00:18:47.054
もちろん、赤黒木の高さについて考えるときは、すべてのノードを

00:18:47.054 --> 00:18:49.730
考えます。赤ノードと黒ノードを。

00:18:49.730 --> 00:18:54.169
これまでのところ、黒ノードしか考えないと、うまくいって、

00:18:54.169 --> 00:18:56.734
log_2(N+1)個のノードだけしかないということです。

00:18:56.734 --> 00:18:59.048
ここで不変条件3がやってきます。

00:18:59.048 --> 00:19:04.021
この条件は実は、ツリーでは黒ノードが多数派だと言っています。

00:19:04.021 --> 00:19:08.033
もともとは、どんな経路でも赤ノードが並ばないということです。

00:19:08.033 --> 00:19:12.096
もし黒ノードの数が少なければ、赤ノードを並べることは

00:19:12.096 --> 00:19:17.042
できないので、経路上のノード数も2倍にしかなりません。

00:19:17.042 --> 00:19:21.070
最悪の場合で、黒のルートノードがあり、赤ノード、次に黒、次に赤

00:19:21.070 --> 00:19:26.015
黒、赤、黒、などとなります。最悪の場合でも赤ノードの数は

00:19:26.015 --> 00:19:30.089
黒ノードの数と等しくなります。経路の長さは、赤ノードを

00:19:30.089 --> 00:19:35.035
考えた時、倍になります。そして、これはまさしく、

00:19:35.035 --> 00:19:39.001
ツリーの高さが対数的になるということです。実際、これは

00:19:39.001 --> 00:19:43.046
もしツリーが4つの不変条件を満たすなら、とくに

00:19:43.046 --> 00:19:47.085
赤ノードが並ばないというのと、黒ノードの経路上の数が等しい

00:19:47.085 --> 00:19:51.056
というなら、ツリーのことは他に何も知らなくても、ツリーは

00:19:51.056 --> 00:19:54.026
バランスされるという主張が証明されます。2を底として

00:19:54.026 --> 00:19:56.022
完全にバランスされます。また、ポイントとしては、

00:19:56.022 --> 00:19:59.827
探索木の操作も対数時間で実行されます。

00:19:59.827 --> 00:20:04.043
なぜなら、高さがこうした操作の実行時間を支配するからです。

00:20:04.085 --> 00:20:08.633
さて、ある意味では、簡単な部分はお話しました。

00:20:08.633 --> 00:20:12.192
探索木が4つの不変条件を満たすなら、それでうまく行く。

00:20:12.192 --> 00:20:15.992
高さが小さくなり、操作は速くなることが保証されます。

00:20:15.992 --> 00:20:18.992
明らかにこれが、このデータ構造から欲しかったことです。

00:20:18.992 --> 00:20:22.980
ただ、このデータ構造を実際に実装しないといけない哀れな者どもは、

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

00:20:26.751 --> 00:20:31.084
ここでの問題は動的であること、挿入と削除に対応することです。

00:20:31.084 --> 00:20:35.661
挿入と削除は4つの不変条件を台なしにするかもしれないので、

00:20:35.661 --> 00:20:40.025
コードを書き換えて条件を満たすようにすることで、ツリーを

00:20:40.025 --> 00:20:44.384
平衡に保ち、どんな挿入と削除の順番でも高さを保つ必要が

00:20:44.384 --> 00:20:46.774
あります。この部分は、このビデオでは扱いません。

00:20:46.774 --> 00:20:49.023
操作のどれも明らかに遅くすることなしに実現できます。

00:20:49.023 --> 00:20:53.048
これはとても複雑で、面白いアイデアを使います。

00:20:53.048 --> 00:20:57.050
有名なアルゴリズムがいくつかあり、教科書に詳しく書いてあります。

00:20:57.050 --> 00:21:00.068
もしくは、オープンソースで平衡探索木のコードを探せば、

00:21:00.068 --> 00:21:02.608
実装するコードを読むこともできます。

00:21:02.608 --> 00:21:07.147
ともあれ、現実的に実現でき、しかも赤黒木は

00:21:07.147 --> 00:21:11.512
豊富な操作をサポートするので、

00:21:11.512 --> 00:21:15.276
数学アプリケーションでよく見かけます。また同じ理由から、

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