みんなのデータ構造（紙書籍+電子書籍） – 技術書出版と販売のラムダノート
これまでのメモ
- 「みんなのデータ構造」学習メモ：2.1 ArrayStack
- 「みんなのデータ構造」学習メモ：2.3 ArrayQueue
- 「みんなのデータ構造」学習メモ：2.4 ArrayDeque
- 「みんなのデータ構造」学習メモ：3.1 SLList 単方向連結リスト
- 「みんなのデータ構造」学習メモ：3.2 DLList 双方向連結リスト
- 「みんなのデータ構造」学習メモ：5.1 ChainedHashTable, 5.2 LinearHashTable
- 「みんなのデータ構造」学習メモ：6.1 BinaryTree 二分木
二分木の続き。
TypeScript によるソースコード
https://github.com/zaki-yama/open-data-structures-typescript/blob/master/src/BinarySearchTree.ts
用語
- 二分探索木の性質：あるノード
uに対し、u.left以下の部分木はすべてu.xより小さいu.right以下の部分技はすべてu.xより大きい
その木構造が探索木として機能するために、あるノードのキーは、そのノードの左の子ノードのキーよりは常に大きく、逆に右の子ノードのキーよりは常に小さい性質が必要である
本書では言及されてなかったけど、二分木と関係なく探索木という用語があって、両方の性質を満たすものを二分探索木と呼ぶ、という理解。
先にまとめ
二分探索木は SSet （順序づけられた Set）インターフェースの実装。
add(x), remove(x), find(x) の実行時間は である。
二分探索木は木の形状に関して制約がないため、アンバランス（たとえば、ほとんどのノードが子を1つだけ持つ鎖のような形）かもしれないという問題がある。
二分探索木の探索・追加・削除
6.2.1 探索(find)
根 r からノードを順にたどって x を探す。ノード u を訪問しているとき、以下の3つの場合がありうる。
x < u.xならu.leftに進むx > u.xならu.rightに進むx = u.xなら値がxであるノードuを見つけた
3 つめのケースになるか、u = null になった（= 見つからなかった）ら探索は終了。
6.2.2 追加(add)
値 x を追加するには、まず x を検索する。このとき、最後に訪問したノード p を保持しておき、x が見つからなかった場合はノード p の子である葉として、x を保存する。
6.2.3 削除(remove)
削除するノードの子が
- 0個のとき：葉なので、そのままノードを削除すればいい
- 1個のとき：削除するノードの親と子をつなぎ合わせる
- 2個のとき：
u.rightを根とする部分木の中で最小の値を持つノードwを見つけ、uがあった場所に挿入する
2個のときがちょっと複雑。ロジックとしては、 u.right にアクセスしてその後ひたすら左の子が存在しなくなるまでたどっていけばいい（一番左が最小なので）。
