Rustで二分探索木かいた
最近C言語勉強してみたりしてアルゴリズムとデータ構造に興味持ってきたんだけど、そういや二分木かいたことないなーと思いRustでやってみた。
「二分探索木」で検索して一番上にレコメンドされたサイトみながらやったけど、正直雰囲気でかいたので自分のこれが二分探索木と呼べるのかいまいち不安だったりする。
実装した機能は３つで、要素の挿入と探索と削除。
ノードの削除について
Node構造体に生えてるdeleteメソッドのことです。insertとかと比べてありえんほど難しくて困った。
どんな実装が一般的なんだろう？自分の実装だと削除するノードをxとすると、
- ノード
x以下の子ノードのデータをリストに保存する。 - ノード
xを子ノード諸共削除する(dropさせる)。 - リストに保存されたデータを全部insertメソッドに投げる。
- 元の状態からノード
xのみが削除された状態になる。
こうすることで大小関係の順序を保ったまま指定の要素のみを削除できた。
ただこの、全部削除して全部insertしなおすのめっちゃ効率悪そう。今更だけども
かいた感想
削除処理むずかしかった
再帰力が高まった気がする。ハノイの塔より好きだ
AVLtreeとBtreeもどんななのかちらっと見たけど難しそう
次はBtreeかいてみたい
