AVL木かいた
以前プレーンな二分探索木をかいたことがあって、今回もそんな感じ。
totechite.hatenablog.com
AVL構造体にinsert
, search
, delete
メソッドが生えてて、それぞれNode構造体の要素の挿入と探索と削除処理のインターフェースになるみたいな雰囲気。
なおこの実装にkeyはあるけれどデータを保存するvalueはない。
実際利用する上ではノードの値としてkeyとvalueがあるものだと思う。
しかし今回はAVL木の肝らしいノードの回転操作の学習が目的なのと、その回転操作においてvalueは注目されないため、シンプルさを優先してvalueを省略した。
回転操作について
rotate_l
, rotate_r
合わせて8か所もデータコピーしてしまい、もう少し抑えたかったお気持ち。
直線的な偏り?(left:2,right:0みたいなの)の修正が比較的かんたんで足掛かりになった。
他の人の実装みるとフラグで回転の発火を管理してるものがあった。
他人のコードは十人十色で読むの面白い
感想とか
再帰多用すると10分後には挙動忘れるのでちゃんとコメント書こうと反省した。
次こそBツリーやる