1
00:00:00,000 --> 00:00:03,084
このビデオでは、ただの二分探索は

2
00:00:03,084 --> 00:00:07,035
既にお話しので、次のお話に進みたいと思います。

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

4
00:00:10,067 --> 00:00:13,852
あなたが実際に必要とする探索木です。

5
00:00:13,852 --> 00:00:17,627
それはバランスされたままである事が保証されるアルゴリズムです。それは

6
00:00:17,627 --> 00:00:21,015
高さが対数的であることが保証されているということです。つまり、

7
00:00:21,015 --> 00:00:25,005
二分探索木において私たちが学び、愛した全ての操作について

8
00:00:25,005 --> 00:00:27,012
保持するキーの数に対して対数的に処理されるということです。

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

10
00:00:30,056 --> 00:00:34,075
探索木の全てのノードについて、もし左にいくとしたら、

11
00:00:34,075 --> 00:00:38,060
その先のツリーのデータには元のデータよりも小さいものしかありません。

12
00:00:38,060 --> 00:00:42,025
右に行けば、大きなものしかありません。

13
00:00:42,025 --> 00:00:45,614
また本当に大事なポイントは、あるキーの集合があるとき

14
00:00:45,614 --> 00:00:48,875
そのキーについての正当な探索木はたくさんあることです。

15
00:00:48,875 --> 00:00:50,986
この例として

16
00:00:50,986 --> 00:00:53,532
１，２，３，４，５というキーがあるとします。

17
00:00:53,532 --> 00:00:57,589
一方では、ちゃんとバランスされた探索木があります。高さは

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

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

20
00:01:05,957 --> 00:01:08,936
同じになってしまいます。一般論として、高さについて

21
00:01:08,936 --> 00:01:13,479
指数的な差が生まれます。コストは最良の場合には

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

23
00:01:16,417 --> 00:01:20,148
というわけで、高さについては何にも心配しなくてもよくなるような

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

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

26
00:01:25,589 --> 00:01:28,236
皆さんはもう、うんざりするような線形の高さになるのかと

27
00:01:28,236 --> 00:01:32,309
心配することもなくなります。繰り返しですが、高さが低いことが

28
00:01:32,309 --> 00:01:35,481
なぜそれほど重要なんでしょうか？　なぜなら探索木の

29
00:01:35,481 --> 00:01:38,773
操作の実行時間はすべて、木の高さに依存するからです。

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

31
00:01:43,455 --> 00:01:48,334
どんな場合でも、高さが実行時間を支配します。

32
00:01:48,334 --> 00:01:50,013
そして、探索木についての一番大事なアイデアは

33
00:01:50,013 --> 00:01:54,776
皆さんがすでにお考えの通りのものです。つまり、

34
00:01:54,776 --> 00:01:58,463
高さは保持するものの数の対数よりは決して良くならない

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

36
00:02:02,186 --> 00:02:05,151
倍にしかならず、保持しているすべての数に到達するには

37
00:02:05,151 --> 00:02:07,040
対数量が必要になるからです。

38
00:02:07,040 --> 00:02:11,007
さらに、対数的になったとしたら、どんな場合でも対数的に留まる

39
00:02:11,007 --> 00:02:16,399
ということも仮定しましょう。挿入や削除をしてもです。そうしたら

40
00:02:16,399 --> 00:02:21,012
すべて対数時間で行える豊かな操作群を利用できます。

41
00:02:21,056 --> 00:02:25,048
同じように、保持されるキーの数に対して

42
00:02:25,048 --> 00:02:29,006
平衡探索木には物凄くたくさんの種類があります。

43
00:02:29,006 --> 00:02:33,022
それらは、ほとんどの場合、それほど互いには大きくは違いません。

44
00:02:33,022 --> 00:02:37,092
ここでは、その中で一番有名な、赤黒木についてお話します。

45
00:02:37,092 --> 00:02:40,062
これは70年代には見出されていたものです。

46
00:02:40,096 --> 00:02:44,674
ただ、はじめに知られた平衡二分探索木ではありません。

47
00:02:44,674 --> 00:02:49,000
それはAVL木です。赤黒木とそれほど大きな違いがあるわけでは

48
00:02:49,000 --> 00:02:51,617
ありませんが、満たす性質が少しことなります。

49
00:02:51,617 --> 00:02:55,997
もう一つ知っておくとよいこととしては、スプレー木という

50
00:02:55,997 --> 00:02:58,454
面白いアイディアがSleatorとTarjanによって考え出されました。

51
00:02:58,454 --> 00:03:01,797
赤黒木やAVL木では、挿入や削除のときにしか変化しません。

52
00:03:01,797 --> 00:03:05,725
それは、考えてみると、期待されるような性質だと思います。

53
00:03:05,725 --> 00:03:08,583
スプレー木では、自分自身を変更します。探索の場合でも、

54
00:03:08,583 --> 00:03:11,788
検索だけをしているときでもです。

55
00:03:11,788 --> 00:03:15,738
このため、自己調節木と呼ばれることもあります。

56
00:03:15,738 --> 00:03:20,653
それにとてもシンプルで、驚くような性質を保証します。

57
00:03:20,653 --> 00:03:25,213
また最後には、二分木の枠組みを越えて、

58
00:03:25,213 --> 00:03:28,281
B木とB+木も見ておいたほうがよいでしょう。

59
00:03:28,281 --> 00:03:31,443
B木やB+木はデータベースの実装と深い関係があります。

60
00:03:31,443 --> 00:03:35,499
ここでのアイディアは、あるノードについて唯一のキーではなく

61
00:03:35,499 --> 00:03:39,567
多くのキーを持ち、ノードからは持っているキーの数に応じて

62
00:03:39,567 --> 00:03:44,306
多数の枝が出ます。

63
00:03:44,306 --> 00:03:47,138
二分木の枠組みを超えたデータベースにおける動機は

64
00:03:47,138 --> 00:03:50,668
メモリの階層構造にうまくあった構造を持つことです。

65
00:03:50,668 --> 00:03:53,295
これは非常に重要なことですが、この講義の範囲を越えます。

66
00:03:53,295 --> 00:03:57,316
つまり、ここでお話するのは赤黒木についてで、

67
00:03:57,316 --> 00:04:01,133
もっと学ぶ必要があり、学ぶべき場所がわかれば

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

69
00:04:05,641 --> 00:04:09,169
赤黒木はただの二分探索木と同じです。

70
00:04:09,169 --> 00:04:13,414
ただし、新しく幾つかの不変条件を維持しています。

71
00:04:13,414 --> 00:04:16,356
このビデオではじめに説明するのは、

72
00:04:16,356 --> 00:04:19,775
どんな不変条件があるかということ、またどのようにして

73
00:04:19,775 --> 00:04:22,849
その不変条件から、高さが対数的になることを保証するかです。

74
00:04:22,849 --> 00:04:27,080
時間が許せば、どこかの時点で、補助的なビデオで核心となる

75
00:04:27,080 --> 00:04:31,612
赤黒木の実装がどのようにして、挿入や削除のもとで

76
00:04:31,612 --> 00:04:34,098
こうした不変条件を維持するのか説明するかもしれません。

77
00:04:34,098 --> 00:04:37,676
この話はとても込み入っているので、オプショナルな資料に

78
00:04:37,676 --> 00:04:40,530
するほうがよいと思います。ただし、不変条件とはなにか、

79
00:04:40,530 --> 00:04:44,794
不変条件が高さの制御にどのような役割を持つかということは、

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

81
00:04:47,291 --> 00:04:51,152
では4つの不変条件を書き出します。そのうち重要なものは

82
00:04:51,152 --> 00:04:54,420
後半ふたつ、つまり3つめと4つめによります。

83
00:04:54,420 --> 00:04:57,986
最初の2つの不変条件は、表面的なものです。

84
00:04:57,986 --> 00:05:01,980
最初のものとして、各ノードに、キーに加えて余計に1ビットの

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

86
00:05:06,783 --> 00:05:09,827
決めます。たぶん、なぜ赤と黒なのか、疑問に思うでしょう。

87
00:05:09,827 --> 00:05:12,464
いや、私も数年前、同じことを同僚のLeo Guibasに

88
00:05:12,464 --> 00:05:16,076
聞きました。教えてくれたところによると、彼と

89
00:05:16,076 --> 00:05:20,990
Sedgewick教授がその論文を書き上げたとき、論文誌では

90
00:05:20,990 --> 00:05:24,793
限られた印刷技術しか使うことができず、出版するには

91
00:05:24,793 --> 00:05:28,097
限られた種類の色しか使えませんでした。だから単に

92
00:05:28,097 --> 00:05:32,085
その色を使い、データ構造に赤黒木と名付け、論文でも

93
00:05:32,085 --> 00:05:36,028
ちゃんと赤と黒の絵を使えたというわけです。残念ながらその後

94
00:05:36,028 --> 00:05:40,172
混乱があり、そうした印刷技術は結局使えませんでした。なので

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

96
00:05:44,038 --> 00:05:47,897
これが、このデータ構造がどうしてこのような名前になったか

97
00:05:48,055 --> 00:05:51,942
という面白い理由です。次に二番目の不変条件ですが、

98
00:05:51,942 --> 00:05:56,060
探索木のルートノードは常に黒です。赤にはなりません。

99
00:05:56,060 --> 00:05:58,092
いいですか？　では、表面的な不変条件がわかったところで、

100
00:05:58,092 --> 00:06:02,045
残りの2つの主要な条件について見てみましょう。

101
00:06:02,045 --> 00:06:06,023
まずはじめに、赤ノードが並ぶことはありません。

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

103
00:06:12,820 --> 00:06:16,011
もうちょっと考えてみればおわかりでしょうが、つまり

104
00:06:16,011 --> 00:06:20,019
赤ノードがあれば、それは必ず親を持ち、また親は必ず

105
00:06:20,019 --> 00:06:24,076
黒ノードになります。そういう意味で、ツリーのどこででも

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

107
00:06:30,079 --> 00:06:37,046
ルートノードから先端まで取ることのできるどんな経路を取っても

108
00:06:37,046 --> 00:06:41,019
正確に同じ数の黒ノードがなければいけません。

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

110
00:06:45,956 --> 00:06:49,371
失敗した探索ですよね？　失敗した探索では、

111
00:06:49,371 --> 00:06:53,225
ルートからはじめて、大きいか小さいかに応じて

112
00:06:53,225 --> 00:06:57,154
右か左かに行きます。右か左かにたどっていって、

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

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

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

116
00:07:07,098 --> 00:07:11,030
そのうち一部は黒ノードで、一部は赤ノードでしょう。

117
00:07:11,030 --> 00:07:15,364
そして黒ノードの数を考えてみましょう。赤黒木の条件では、

118
00:07:15,364 --> 00:07:19,529
定義上、どんな経路をたどってルートから

119
00:07:19,529 --> 00:07:24,096
nullポインタまでたどっても、たどる黒ノードの数は

120
00:07:24,096 --> 00:07:27,278
全く同じになる、という条件を満たさないといけません。

121
00:07:27,278 --> 00:07:31,788
経路によって変わってはいけません。同じルートからは

122
00:07:31,788 --> 00:07:34,559
完全に同じです。いくつか例を見てみましょう。

123
00:07:34,559 --> 00:07:38,408
こういうことです。赤黒木がうまくバランスしなければ

124
00:07:38,408 --> 00:07:42,667
ならないという考え方を示します。

125
00:07:42,667 --> 00:07:45,745
高さは、基本的には対数的でなければなりません。

126
00:07:45,745 --> 00:07:49,019
考えてみましょう。一番バランスしてないツリーは何でしょう？

127
00:07:49,019 --> 00:07:54,123
それは、このような連鎖ですね。つまり、言いたいのは3ノードの

128
00:07:54,123 --> 00:07:58,393
チェインであっても赤黒木ではないということです。その証明は？

129
00:07:58,393 --> 00:08:04,965
そういうツリーを仮定します。仮に、キーを１，２，３とします。

130
00:08:04,965 --> 00:08:08,465
すると問題は、この3つのノードを赤か黒に色をつけ

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

132
00:08:13,382 --> 00:08:17,060
ということです。ノードを赤か黒にわけます。

133
00:08:17,060 --> 00:08:20,379
条件2から、ルートノードは黒になります。

134
00:08:20,379 --> 00:08:24,412
2と3の色分けについては、4通りの可能性があります。

135
00:08:24,412 --> 00:08:27,446
ですが条件3により、3つの可能性しかありません。

136
00:08:27,446 --> 00:08:30,246
2と3をどちらも赤にしてはいけません。なぜなら、

137
00:08:30,246 --> 00:08:34,018
2つの赤ノードが連続するからです。そこで2が赤で3が黒、

138
00:08:34,018 --> 00:08:37,007
2が黒で3が赤、両方とも黒、という可能性があります。

139
00:08:37,007 --> 00:08:41,069
このどれも同じです。一例として、

140
00:08:41,069 --> 00:08:44,083
2が赤で3が黒としましょう。

141
00:08:44,083 --> 00:08:48,491
ここでは条件4が破られています。実は条件4は

142
00:08:48,491 --> 00:08:53,001
2と3をどのように色分けしても破られます。

143
00:08:53,001 --> 00:08:56,619
条件4は何だったでしょうか？　どんな失敗する探索でも、

144
00:08:56,619 --> 00:09:00,006
全く同じ数の黒ノードを通るということです。

145
00:09:00,006 --> 00:09:03,062
失敗する探索のひとつは、たとえば0です。

146
00:09:03,062 --> 00:09:07,083
0を探索すると、ルートを見て左に行き、nullポインタに

147
00:09:07,083 --> 00:09:10,027
到達します。つまり1つの黒ノードに到達します。

148
00:09:10,027 --> 00:09:12,063
1つです。一方、4を探索したとしましょう。

149
00:09:12,063 --> 00:09:15,285
ルートからはじめて右へ行き、2に行き、さらに右へ、

150
00:09:15,285 --> 00:09:19,396
3に行き、さらに右へ、そしてnullポインタに

151
00:09:19,396 --> 00:09:22,018
到達します。この場合、失敗した探索で

152
00:09:22,018 --> 00:09:24,060
2つの黒ノードにぶつかります。1と3です。

153
00:09:24,060 --> 00:09:28,008
つまり不変条件4が破られています。したがって、

154
00:09:28,008 --> 00:09:30,063
これは赤黒木ではありません。どのように2と3を

155
00:09:30,063 --> 00:09:34,043
塗り分けてもどれかの不変条件が破られるという確認は

156
00:09:34,043 --> 00:09:37,003
自分で確認してみてください。両方赤なら条件3が破られます。

157
00:09:37,003 --> 00:09:39,023
少なくとも1つが赤なら、条件4は破られます。

158
00:09:39,023 --> 00:09:42,040
つまりこれは赤黒木ではないという例です。

159
00:09:42,040 --> 00:09:44,410
では赤黒木の例も見てみましょう。

160
00:09:44,410 --> 00:09:48,014
ある探索木が、実際にノードを赤と黒に塗り分け、

161
00:09:48,014 --> 00:09:52,016
全ての4つの不変条件が満たされるようなものです。

162
00:09:52,016 --> 00:09:56,057
赤黒木のとても簡単な例は、完全にバランスした木です。

163
00:09:56,057 --> 00:09:59,008
たとえば、このように3つのノードがあって、３，５，７のキーがあり

164
00:09:59,008 --> 00:10:03,049
5がルートになっているとします。

165
00:10:03,049 --> 00:10:06,022
両側に子ノードがひとつずつあります。

166
00:10:06,022 --> 00:10:09,040
3と7です。これは赤黒木でしょうか？

167
00:10:09,040 --> 00:10:11,097
問題は何だったでしょうか？

168
00:10:11,097 --> 00:10:16,049
この3つのノードを赤か黒に塗り分けて、4つの不変条件を

169
00:10:16,049 --> 00:10:19,005
全て満たすような方法はあるか？ということです。

170
00:10:19,075 --> 00:10:24,010
ちょっと考えてみると、そう、たしかにこのノードを塗り分けて

171
00:10:24,010 --> 00:10:27,061
条件を満たすことができることがわかるでしょう。

172
00:10:27,061 --> 00:10:31,000
とくに、全部のノードを黒だとしましょう。

173
00:10:31,036 --> 00:10:34,048
条件1は満たされます。すべてのノードには色がついています。

174
00:10:34,048 --> 00:10:37,095
条件2も満たされます。ルートノードは黒です。

175
00:10:37,095 --> 00:10:41,076
条件3も満たされます。赤ノードはないので、

176
00:10:41,076 --> 00:10:45,019
赤ノードが並ぶこともありません。そして、考えてみると、

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

178
00:10:48,073 --> 00:10:52,098
どういう探索で失敗しても、必ず2つの黒ノードを

179
00:10:52,098 --> 00:10:55,043
通過します。たとえば1を検索すると、

180
00:10:55,043 --> 00:10:59,002
3と5を通ります。6を検索すれば、

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

182
00:11:01,909 --> 00:11:05,077
2つの黒ノードを持ち、第4の不変条件も満たされます。

183
00:11:05,077 --> 00:11:08,046
素晴らしい。ですがもちろん、二分探索木のポイントは、

184
00:11:08,046 --> 00:11:11,033
動的にしたいということです。

185
00:11:11,033 --> 00:11:13,068
挿入や削除に対応できないといけません。

186
00:11:13,068 --> 00:11:17,047
挿入や削除のたびに、赤黒木に新しいノードができます。

187
00:11:17,047 --> 00:11:19,290
たとえば挿入の場合、新しいノードができて

188
00:11:19,290 --> 00:11:23,279
色を決めねばなりません。すると突然、4つの不変条件の

189
00:11:23,279 --> 00:11:25,485
どれも破られないか心配になってきますね。

190
00:11:25,485 --> 00:11:28,952
では、あまり大変なことをしなくても挿入できるような、

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

192
00:11:32,056 --> 00:11:35,998
ツリーの回転によって、もっと根本的な探索木の再構築を

193
00:11:35,998 --> 00:11:40,540
行い、4つの不変条件を維持してバランスした状態を保つための

194
00:11:40,699 --> 00:11:44,164
解説をします。では、ここに赤黒木があって、全部のノードが黒

195
00:11:44,164 --> 00:11:48,367
だとします。そして例えば6を挿入します。

196
00:11:48,367 --> 00:11:51,054
ここに。ここでもし、これを黒にすると、

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

198
00:11:55,033 --> 00:11:59,622
3つの黒ノードに遭遇することになるからです。

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

200
00:12:03,462 --> 00:12:05,706
だからこれではうまく行きません。

201
00:12:05,706 --> 00:12:09,969
ですが6を黒にするかわりに、赤にするとうまくいきます。

202
00:12:09,969 --> 00:12:13,544
この場合、6は条件4からは無関係になります。

203
00:12:13,544 --> 00:12:16,406
ルートからのどのパスにもあらわれません。

204
00:12:16,406 --> 00:12:20,858
元のツリーではどのパスでも2つの黒ノードがあるのでした。

205
00:12:20,858 --> 00:12:24,275
6が来る前は。そして、6が赤ならこれは変わりません。

206
00:12:24,275 --> 00:12:28,993
つまり、6を挿入しても赤くすれば4つの条件は全て満たされます。

207
00:12:28,993 --> 00:12:33,209
次に、たとえば8を挿入しましょう。全く同じやり方が使えます。

208
00:12:33,209 --> 00:12:37,142
8を赤とします。同じく、このノードは条件4には参加しません。

209
00:12:37,142 --> 00:12:42,021
なので破られません。さらに言えば、2つの赤ノードは並んでいないので、

210
00:12:42,021 --> 00:12:45,073
条件3も破られていません。

211
00:12:45,073 --> 00:12:50,042
というわけで、これも赤黒木です。実は、この赤黒木を

212
00:12:50,042 --> 00:12:54,092
4つの条件を満たしつつ塗り分けるのは

213
00:12:54,092 --> 00:12:57,082
これだけではありません。たとえば、6と8を黒に変更します。

214
00:12:57,082 --> 00:13:02,001
ただ同時に、7を赤に塗り分けます。これで完璧です。

215
00:13:02,001 --> 00:13:05,000
明らかに最初の3つの不変条件は満たされます。

216
00:13:05,000 --> 00:13:09,009
また、6と8の赤を合併して上に押し上げ、

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

218
00:13:13,035 --> 00:13:16,044
かわりません。6を通ったパスは7を通りますし、

219
00:13:16,044 --> 00:13:20,070
8を通った経路も7を通ります。だから、

220
00:13:20,070 --> 00:13:24,923
これまでと同じく、正確に同じ数の赤と黒のノードが、

221
00:13:24,923 --> 00:13:28,077
どちらの経路でも存在します。つまり、全ての経路が

222
00:13:28,077 --> 00:13:30,835
同じ数の黒ノードを持ち、条件4は満たされます。

223
00:13:30,835 --> 00:13:36,595
ここでは、ごく単純な例だけをお見せしています。挿入の際、

224
00:13:36,595 --> 00:13:39,895
赤黒の性質を守るために大したことは必要ありません。

225
00:13:39,895 --> 00:13:44,459
一般に、もっとたくさんのものを挿入したり削除すると、

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

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

228
00:13:52,807 --> 00:13:57,748
ところで、赤黒木に足された一見適当な条件の

229
00:13:57,748 --> 00:14:00,478
要点は何でしょうか？　実は4つの不変条件を

230
00:14:00,478 --> 00:14:05,475
全て満たすようにすると、高さが小さくなるというのが

231
00:14:05,475 --> 00:14:07,839
要点です。そして高さが小さくなるので、

232
00:14:07,839 --> 00:14:10,098
全ての操作が速くなるのです。

233
00:14:10,098 --> 00:14:15,695
では、4つの不変条件を満たすと、高さがとても

234
00:14:15,695 --> 00:14:20,030
小さくなることを証明します。実は、考えうる最小値の倍

235
00:14:20,030 --> 00:14:24,040
ほぼlog_2(N)の2倍を超えません。

236
00:14:24,040 --> 00:14:31,003
正式にいえば、任意のNノードの赤黒木では、高さは

237
00:14:31,003 --> 00:14:36,884
O(log N)、より正確には 2log_2(N+1)となります。

238
00:14:36,886 --> 00:14:41,723
証明しましょう。この証明についてはっきりしているのは、

239
00:14:41,723 --> 00:14:46,089
不変条件3と4の果たす役割です。

240
00:14:46,089 --> 00:14:51,914
本質的に、この不変条件が保証するのは、赤黒木は

241
00:14:51,914 --> 00:14:57,010
完全平衡木にある係数の増加を加えたようになります。

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

243
00:15:01,010 --> 00:15:03,083
ここでは、赤黒木には何もしません。

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

245
00:15:08,006 --> 00:15:10,059
そして、ツリーの中のルートノードからの経路の長さに

246
00:15:10,059 --> 00:15:14,082
下限があるとします。これをkとしましょう。

247
00:15:14,082 --> 00:15:18,079
kを、たとえば10とでも考えてみてください。あるツリーがあって

248
00:15:18,079 --> 00:15:22,097
ルートからはじめ、左右のどのように経路をたどって

249
00:15:22,097 --> 00:15:26,079
nullポインタまで到達しても、どう選んでも、

250
00:15:26,079 --> 00:15:29,032
少なくともk個のノードはたどることになります。

251
00:15:29,032 --> 00:15:34,069
もしこの仮定が満たされるなら、考えてみてください、

252
00:15:34,069 --> 00:15:39,032
このツリーの上位は完全に埋まっています。このツリーの上位は

253
00:15:39,032 --> 00:15:43,060
完全平衡木になっています。高さk-1の二分木です。

254
00:15:43,062 --> 00:15:46,028
では、k=3となるようなツリーを描いてみます。

255
00:15:46,033 --> 00:15:50,083
ルートからnullポインタまでどのように移動しても、必ず

256
00:15:50,083 --> 00:15:54,098
最低3つのノードを見るということです。つまり上位3階層は

257
00:15:54,098 --> 00:15:57,087
完全に埋まっています。まずルートがあって、

258
00:15:57,087 --> 00:16:01,074
両側に子ノードがあります。孫ノードは全部で4つ。

259
00:16:01,074 --> 00:16:04,083
この考え方を、背理法で証明します。

260
00:16:04,083 --> 00:16:08,019
実際、上位k階層のノードのどれかが欠けていたとすると、

261
00:16:08,019 --> 00:16:13,016
k個のノードをたどる前にnullポインタに到達する経路が

262
00:16:13,016 --> 00:16:18,045
存在します。ここでのポイントは、この下限から、

263
00:16:18,045 --> 00:16:23,086
ツリー内のノード数の下限が、ルートからnullまでの経路の

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

265
00:16:28,086 --> 00:16:34,315
深さk-1の完全平衡木のノード数、つまり2のk乗-1を

266
00:16:34,315 --> 00:16:40,094
含みます。たとえばk=3なら

267
00:16:40,094 --> 00:16:45,346
2の3乗-1の7です。これはツリーについての基本的な事実で

268
00:16:45,346 --> 00:16:49,553
赤黒木とは関係ありません。ではこれと赤黒木の不変条件を

269
00:16:49,553 --> 00:16:54,740
組み合わせて、なぜ赤黒木が低くなるか考えましょう。

270
00:16:54,740 --> 00:16:58,828
また、前のスライドの結論を振り返りましょう。

271
00:16:58,828 --> 00:17:04,407
ツリーのノード数Nは、少なくとも2のk乗-1はあります。

272
00:17:04,407 --> 00:17:08,932
ここでkは、ルートからnullまでの経路の一番小さい値です。

273
00:17:08,932 --> 00:17:13,503
このことを少し書き換えて、kに対してNに

274
00:17:13,503 --> 00:17:18,366
制約を与えるのではなく、Nからkの上限を決めましょう。

275
00:17:18,366 --> 00:17:23,481
つまり、ルートからのあらゆる経路の長さの最小値は、

276
00:17:23,481 --> 00:17:26,803
log_2(N+1)より大きくなることはありません。

277
00:17:26,804 --> 00:17:31,243
これは単に両辺に1を足して2を底とした対数を取るだけです。

278
00:17:31,243 --> 00:17:35,355
では、これの何がいいんでしょうか？　では赤黒木について

279
00:17:35,355 --> 00:17:38,022
考えましょう。ノード数Nの赤黒木です。

280
00:17:38,022 --> 00:17:42,208
何が言えるでしょうか？　赤黒木と関係なく

281
00:17:42,208 --> 00:17:48,156
あるルートからnullまでの経路のノードの数は、

282
00:17:48,156 --> 00:17:52,622
たかだかlog_2(N+1)です。最善の場合で。全部が黒ノードです。

283
00:17:52,622 --> 00:17:57,236
いくらかは赤ノードですが、最大の場合では、全てが黒ノードです。

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

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

286
00:18:06,176 --> 00:18:10,747
これは、証明したことよりは弱い主張です。

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

288
00:18:15,500 --> 00:18:18,339
というわけで、経路は確実にlog_2(N+1)個の

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

290
00:18:21,878 --> 00:18:25,742
2つのノックアウトパンチを繰り出しましょう。そもそも、

291
00:18:25,742 --> 00:18:29,167
4つの不変条件は何を言っていたでしょうか？　言っていたのは

292
00:18:29,167 --> 00:18:33,014
赤黒木の経路を見た時、ルートからはじめて

293
00:18:33,014 --> 00:18:35,380
失敗した探索を考えました。nullポインタまでたどります。

294
00:18:35,380 --> 00:18:39,093
そして、赤ノードが見えないとして、全然数えないとすると、

295
00:18:39,093 --> 00:18:43,033
経路には対数的な数のノードしかないということです。

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

297
00:18:47,054 --> 00:18:49,730
考えます。赤ノードと黒ノードを。

298
00:18:49,730 --> 00:18:54,169
これまでのところ、黒ノードしか考えないと、うまくいって、

299
00:18:54,169 --> 00:18:56,734
log_2(N+1)個のノードだけしかないということです。

300
00:18:56,734 --> 00:18:59,048
ここで不変条件3がやってきます。

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

302
00:19:04,021 --> 00:19:08,033
もともとは、どんな経路でも赤ノードが並ばないということです。

303
00:19:08,033 --> 00:19:12,096
もし黒ノードの数が少なければ、赤ノードを並べることは

304
00:19:12,096 --> 00:19:17,042
できないので、経路上のノード数も2倍にしかなりません。

305
00:19:17,042 --> 00:19:21,070
最悪の場合で、黒のルートノードがあり、赤ノード、次に黒、次に赤

306
00:19:21,070 --> 00:19:26,015
黒、赤、黒、などとなります。最悪の場合でも赤ノードの数は

307
00:19:26,015 --> 00:19:30,089
黒ノードの数と等しくなります。経路の長さは、赤ノードを

308
00:19:30,089 --> 00:19:35,035
考えた時、倍になります。そして、これはまさしく、

309
00:19:35,035 --> 00:19:39,001
ツリーの高さが対数的になるということです。実際、これは

310
00:19:39,001 --> 00:19:43,046
もしツリーが4つの不変条件を満たすなら、とくに

311
00:19:43,046 --> 00:19:47,085
赤ノードが並ばないというのと、黒ノードの経路上の数が等しい

312
00:19:47,085 --> 00:19:51,056
というなら、ツリーのことは他に何も知らなくても、ツリーは

313
00:19:51,056 --> 00:19:54,026
バランスされるという主張が証明されます。2を底として

314
00:19:54,026 --> 00:19:56,022
完全にバランスされます。また、ポイントとしては、

315
00:19:56,022 --> 00:19:59,827
探索木の操作も対数時間で実行されます。

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

317
00:20:04,085 --> 00:20:08,633
さて、ある意味では、簡単な部分はお話しました。

318
00:20:08,633 --> 00:20:12,192
探索木が4つの不変条件を満たすなら、それでうまく行く。

319
00:20:12,192 --> 00:20:15,992
高さが小さくなり、操作は速くなることが保証されます。

320
00:20:15,992 --> 00:20:18,992
明らかにこれが、このデータ構造から欲しかったことです。

321
00:20:18,992 --> 00:20:22,980
ただ、このデータ構造を実際に実装しないといけない哀れな者どもは、

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

323
00:20:26,751 --> 00:20:31,084
ここでの問題は動的であること、挿入と削除に対応することです。

324
00:20:31,084 --> 00:20:35,661
挿入と削除は4つの不変条件を台なしにするかもしれないので、

325
00:20:35,661 --> 00:20:40,025
コードを書き換えて条件を満たすようにすることで、ツリーを

326
00:20:40,025 --> 00:20:44,384
平衡に保ち、どんな挿入と削除の順番でも高さを保つ必要が

327
00:20:44,384 --> 00:20:46,774
あります。この部分は、このビデオでは扱いません。

328
00:20:46,774 --> 00:20:49,023
操作のどれも明らかに遅くすることなしに実現できます。

329
00:20:49,023 --> 00:20:53,048
これはとても複雑で、面白いアイデアを使います。

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

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

332
00:21:00,068 --> 00:21:02,608
実装するコードを読むこともできます。

333
00:21:02,608 --> 00:21:07,147
ともあれ、現実的に実現でき、しかも赤黒木は

334
00:21:07,147 --> 00:21:11,512
豊富な操作をサポートするので、

335
00:21:11,512 --> 00:21:15,276
数学アプリケーションでよく見かけます。また同じ理由から、

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