これはなに

AVL木を実装して記事を書こうとしているんですが，うまくいかないので前提知識であるところの二分探索木(Binary Search Tree)についてまとめることにしました．

前提知識

木
Haskellの基本的な文法

二分探索木とは

二分探索木とは各節点のデータが全順序集合の要素である二分木であって，以下の条件を満たすものです．

二分探索木条件: 葉を除く任意の節点に対してその節点のデータは，
① その節点の左部分木の任意のデータよりも大きく
② その節点の右部分木の任意のデータよりも小さい

以下が二分探索木の例です．

f:id:iKanago:20200414135902p:plain

たとえば根のデータは4ですが，左部分木中のどのデータも4より小さいですし，右部分木中のどのデータも4より大きいです．他の節点についても同様のことが成り立つので確かめてみてください．

実装

再帰的なデータ構造を実装するならやっぱりHaskellです．教科書に載っているC言語の長々としたコードが異常に短くなって気持ちいいです．
コードはここに公開しています:

github.com

定義

二分探索木をHaskellのデータ型として以下のように定義します．

Nilは空の木を表します．Node a (BinaryTree a) (BinaryTree a)は型引数aで指定した型のデータを持つ部分木で，第2引数のBinaryTree aは左部分木，第3引数のBinaryTree aは右部分木を表します．

挿入

データの挿入は再帰的に以下のように定義します．

再帰的に葉の方向に潜りながら注目する節点を移動していきます．
2行目: 再帰の基底部です．
3行目: 挿入するデータxと注目している節点のデータaが等しいときです．二分探索木はデータの重複を認めないので，もとの節点をそのまま返します．
4行目: 挿入するデータxの方が小さいときです．このデータは今見ている節点の左部分木に挿入されるので，lhsのあった場所にinsert x lhsで返ってきた木を付け替えます．
このまま行くところまで行くとじきにNilへたどり着くので，そこにデータを挿入して(2行目)今度は再帰をさかのぼります．
5行目: 挿入するデータxの方が大きいときです．4行目と左右対称な動作をします．

挿入の時間計算量の平均値は $\mathcal{O}(\log n)$ です．動的配列への挿入などに比べると速いですね．

探索

最小値

最小値の探索はとても簡単です．

より小さい値は各節点の左部分木に存在するので左側に潜りながら探索します．左部分木がNilであるような節点にたどり着くと，そこにあるデータが最小値です．
最大値の探索も同様に右側に潜っていくとできます．

データを指定した探索

あるデータが存在するかを探索するのは挿入とほぼ同じプロセスで，BinaryTree aを返すかBoolを返すかの違いしかありません．

3行目: 探索するデータxと注目する節点のデータaが等しい場合，つまり目的のデータが存在しているときで，Trueを返します．
4・5行目: 探索するデータxと注目する節点のデータaの大小に応じて左部分木または右部分木に潜っていきます．潜っていっても目的のデータにぶつからない場合はそのうちNilにたどり着くので，2行目に定義されているようにFalseを返します．

探索の時間計算量の平均値も挿入と同様に $\mathcal{O}(\log n)$ です．

削除

実装は以下の通りです．

要素の削除は今までの操作よりは少し複雑です．
4，5行目: 挿入と同じ要領で，削除対象のデータが含まれるであろう部分木へ潜っていきます．
2行目: 削除対象のデータを持つ節点が見つからないままNilに到達した場合，Nilを返します．
6行目: 削除対象のデータが見つかりました．しかし単純にその節点を削除すると二分木がこわれてしまいます．ここでは削除する節点に対して，補助関数delete'を適用します．

削除対象の節点が1つ以下の子を持つ場合

葉である場合，子を持たないのでそのまま削除する
子を一つ持つ場合，削除する節点があった場所にその子を根とする部分木を付け替える

これらの処理をdelete'関数でどう実装しているかを見てみます． 1行目: 左部分木がNilのときは右部分木もNilのときはNilを，そうでなければ右部分木を削除対象の節点のあった場所へ移動させればよいです．まとめてrhsを返すことでこの2つの場合を表現できます．
2行目: 右部分木のみがNilの場合です． lhsを返します．

削除対象の節点が2つの子を持つ場合

このときは削除する節点がある場所へ

右部分木の最大データの節点
左部分木の最小データの節点

を代わりに移してやります．今回は右部分木の最大データの節点を移動させるようにしました．
図3の右側の期において，データ5を持つ節点を消す場合はデータ9を持つ節点を移動させます．このとき，操作後も二分探索木条件を満たしていることを確認してください．

f:id:iKanago:20200414162752p:plain — 図3: 節点の削除と移動

delete'関数の3，4行目を見てください．まずminInSubTreeを削除対象の節点の右部分木の最小値とします．そしてminInSubTreeをデータに持ち，「delete minInSubTree rhsによってminInSubTreeを右部分木から削除した部分木」を右部分木として持つ節点を返します．

削除の時間計算量の平均も他の操作と同様に $\mathcal{O}(\log n)$ です．

平衡二分木へ

ここまで二分探索木に関する基本的な操作を見てきました．挿入，探索，削除のいずれも平均時間計算量は $\mathcal{O}(\log n)$ なのですが，最悪時間計算量は $\mathcal{O}(n)$ になってしまいます．

どういう状況でそうなるのかというと，ほぼソートされた配列を前の要素から順に挿入していき，下の図4のように高さが偏った木ができてしまったときです．

f:id:iKanago:20200414220151p:plain — 図4: 偏った二分探索図

これを解決するのが平衡二分木です．二分探索木は値の順序関係のみを見て構築します．一方，平衡二分木はこれに加えて木が平衡を保つようにいくつかの制約を加えて，高さが $\mathcal{O}(\log n)$ になるように工夫したものです．次はその一種であるAVL木に関する記事を書こうと思います．