バランス木
完全木
BS(Binary Search)木
の判定は、いずれも再帰的呼び出しで
返り値に何（どういう状態）を返すか？
入力として、何（どいういう状態）を渡すか？を考える
バランス木やAVL木は左右の深さの差、とかBS木はmin, maxを親から与えてやるとか
いろいろ。以下のノートのでパッみて思い出せるようになると良いです。
つづいてAVL木とは
ちょっと中級者というか難しそうな印象で今まで触れてこなかったですが
噛み砕いた理解はとっても簡単。
AVLはすべてのノードにおいて、左と右の深さの差が位置以下
というBS木です。BS木の強化バージョンとおぼえましょう。
こうすると、BS木のworst探索時間O(N)がなくなり常にO(NlogN)での探索、挿入、削除が
できるようになります。
AVL木の挿入の基本コンセプトは以下で、4つの場合分けにより、処理がすこし異なるだけですが
基本は挿入の状態によってローテートする。という手順です。
ちなみにAVL の名前は、このアルゴリズム（手順）を考案して論文を書いたソ連の数学者の
ゲオルギー・アデルソン・ヴェルスキーとエフゲニー・ランディスに由来するそうです。
最後は更に玄人なイメージのある
赤黒木です
こちらは、AVL木だとLeft, Rightのパターンや, Right Leftの場合はローテートが二回発生しますが、
赤黒木はそこがなくて、より安定しているそうです。
ここでは、深く理解することはせず、こういう木がよく使われているだな、という
大きなレベルでの理解にとどめておきます。
赤黒木とは、以下のよう条件を満たすBS木です。
以上です