Javaで二分探索木クラス作成
(12/24追記：deleteのコードに一部誤りがありました。すいませんでした。)
いやあ、更新空いた空いた。
このままだと本気で何も書かなくなりそうなので、データ構造の練習をしてみることにした。
それにしても、大学でCを使うのを強制されてるせいかJavaとC++がまあ便利に思えてくる。Javaなんかメモリの解放を言語側がしてくれる仕様とか……どんだけ至れり尽くせりだ。
とまあそんなわけで、まずは初歩的なモンから作ってみようと言うことで。挿入・探索・削除を備えた基本的な二分探索木クラスを制作。
ちなみに、実はもともとある平衡二分探索木を制作していて、今はその途中段階なんです（；・ω・）。今後の更新で完成したら公開するつもりですが。
以前、二分探索木は１５パズルあたりで使ってるけど、アレよりはもう少しわかりやすく、使いたければ別のプログラムで応用して汎用的に使えるようなクラスを書いてみた
。勿論、ジェネリクスを使ってどんなクラスも値に持てるようにした。
せっかくなので久々に解説風に。……っつってもこんな基本的な構造をいちいち覚書にかく必要はないと思うけど。
まずは持っているデータ及びコンストラクタはこんな感じ。
ちなみにクラス名はBinarySearchTree
public int key; public T value; public BinarySearchTree<T> left; public BinarySearchTree<T> right; public BinarySearchTree<T> parent; //コンストラクタ：木を作成 BinarySearchTree(){ this.value = null; this.key = 0; this.left = null; this.right = null; this.parent = null; } //コンストラクタ：ノードを作成 BinarySearchTree(int key,T value,BinarySearchTree<T> p){ this.value = value; this.key = key; this.left = null; this.right = null; this.parent = p; }
| データ型 | 要素名 | 意味 |
|---|---|---|
| int | key | キー値 |
| T | value | データ |
| BinarySearchTree |
left | 左の子（キー値小） |
| BinarySearchTree |
right | 右の子（キー値大） |
| BinarySearchTree |
parent | 親 |
……全く関係ないけど、「ようそめい」の変換で一発目に出るのが「ヨウ素名」ってどういうことよ。
それはさておき、二分探索木なのでキー・データに加え左右の子へのポインタを各ノードに持たせる。親のノードへのポインタを持たせるか少々迷ったけど、今後これをベースに平衡二分探索木を書いていくことを考え、また削除のときに多少簡単になるので持たせることにした。
コンストラクタについては特に言うことも無い。あ、もちろん最初に木自体を作るコンストラクタのキー値０には特に意味がない。nullにしたらコンパイラに怒られたんでさしあたり入れといただけです。
次に挿入操作。
//木に挿入 public void insert(int key,T value){ if(this.parent == null && this.value == null){ //根が空の場合 this.value = value; this.key = key; return; }else if(this.key > key){ //左に挿入 if(this.left == null){ //左に子がない this.left = new BinarySearchTree<T>(key,value,this); }else { //左に部分木あり this.left.insert(key,value); } }else if(this.key < key){ //右に挿入 if(this.right == null){ //右に子がない this.right = new BinarySearchTree<T>(key,value,this); }else { //右に部分木あり this.right.insert(key,value); } }else{ //既存のキーの場合：上書きする this.value = value; } return; }
挿入するキーが
(1)ノードのキーより小さい
→左に子があれば左の子で再帰呼び出し。無ければその場に挿入
(2)ノードのキーより大きい
→右に子があれば右の子で再帰呼び出し。無ければその場に挿入
(3)ノードのキーと同じ
→データだけ上書き
・左の部分木に入っている全てのキーが親ノードのキーより小さい
・右の部分木に入っている全てのキーが親ノードのキーより大きい
という条件が常に保存されるように挿入していく。
例えば
にキー１を挿入すると
となる。
次に検索。唯一のクエリ。
//キーを指定して検索 public BinarySearchTree<T> search(int key){ if(this.key == key && this.value != null)return this; if(this.key > key && this.left != null)return this.left.search(key); if(this.key < key && this.right != null)return this.right.search(key); return null; }
検索するキーが
(1)ノードのキーより小さい
→左に子があれば左の子で再帰呼び出し。
(2)ノードのキーより大きい
→右に子があれば右の子で再帰呼び出し。
(3)ノードのキーと同じ
→ノードのポインタを返す
再帰呼び出し後も見つからなければnullを返す
挿入操作および、その他もろもろの操作で保存している条件のおかげで、上のような超単純なアルゴリズムで検索が可能になるわけです。
次に削除……が意外とめんどい。
最初は「最小のノードを削除する関数」次にメインの「指定されたキーを持つノードを削除する関数」
//最小の値を削除 //木から切り取るだけなので、この関数から返ったノードへのアドレスを呼び出し側で受けることで削除したノードへのアクセスが可能 //なお、削除操作での使用を想定しているため、削除ノードが根だった場合を考慮していない public BinarySearchTree<T> extractMin(){ if(this.left == null){ //左に子を持たない場合：これが最小ノードなので、削除 if(this.right == null){ //孤立した（子がない）場合：削除ノードを切り離す if(this.parent.left == this){ this.parent.left = null; }else { this.parent.right = null; } }else{ //右に子を持つ場合：このノードの代わりに右の子を親の子とする if(this.parent.left == this){ this.parent.left = this.right; }else { this.parent.right = this.right; } this.right.parent = this.parent; } return this; }else{ //左に子を持つ場合：左の部分木の最小ノードを取り除く return this.left.extractMin(); } } //キーを指定して削除 //削除の成功・失敗を返す public boolean delete(int key){ BinarySearchTree<T> del = this.search(key); //削除するノードが見つからなかった場合 if(del == null)return false; //削除 if(del.left == null && del.right == null){ if(del.parent != null){ //子が根ではなく、両方とも子がない場合：削除ノードを切り離す if(del.parent.left == del){ del.parent.left = null; }else { del.parent.right = null; } }else{ //子が根であり、両方とも子がない場合：キーと値を削除する del.key = 0; del.value = null; } }else if(del.left == null){ if(del.parent != null){ //子が根ではなく、左にのみ子がない場合：このノードの代わりに右の子を親の子とする if(del.parent.left == del){ del.parent.left = del.right; }else { del.parent.right = del.right; } del.right.parent = del.parent; }else{ //子が根であり、左にのみ子がない場合：右のノードのデータを根に入れ、右のノードの子を受け継ぐ del.key = del.right.key; del.value = del.right.value; del.left = del.right.left; del.right = del.right.right; if(del.right != null)del.right.parent = del; if(del.left != null)del.left.parent = del; } }else if(del.right == null){ if(del.parent != null){ //子が根ではなく、右にのみ子がない場合：このノードの代わりに左の子を親の子とする if(del.parent.left == del){ del.parent.left = del.left; }else { del.parent.right = del.left; } del.left.parent = del.parent; }else{ //子が根であり、右にのみ子がない場合：左のノードのデータを根に入れ、左のノードの子を受け継ぐ del.key = del.left.key; del.value = del.left.value; del.right = del.left.right; del.left = del.left.left; if(del.right != null)del.right.parent = del; if(del.left != null)del.left.parent = del; } }else{ //両方に子を持つ場合：右の最小の子とデータを入れ替え、右の最小の子を切り離す BinarySearchTree<T> min = del.right.extractMin(); del.key = min.key; del.value = min.value; } return true; }
削除するキーで木を探索
→ノードを削除
と、簡単な操作なのですが削除の段階で何でこんなに場合分けが多いのorz
ていうか、削除ノードが根だった場合が厄介なのよ（´・ω・）
削除の手順をまとめると
削除するノードDが
(1)子を持たない
(1-I)根でない
Dを木から切り離す
(1-II)根である
キー・データをリセット(2)左の子のみもつ
(2-I)根でない
(2-I-i)Dが親の左の子
Dの左の子をDの親の左の子にする
Dの左の子の親をDの親にする
(2-I-ii)削除ノードが親の右の子
Dの左の子をDの親の右の子にする
Dの左の子の親をDの親にする
(2-II)根である
Dのキー・データ・左右の子をDの左の子のものと入れ替える
(3)右の子のみもつ
((3-I)根でない
(3-I-i)Dが親の左の子
Dの右の子をDの親の左の子にする
Dの右の子の親をDの親にする
(3-I-ii)削除ノードが親の右の子
Dの右の子をDの親の右の子にする
Dの右の子の親をDの親にする
(3-II)根である
Dのキー・データ・左右の子をDの右の子のものと入れ替える
(4)左右に子を持つ
Dの右の子の最小のノードを木から切り離し、Dのキー・データをその削除した最小ノードのものと入れ替える。
……うぜぇ（；´Д`）
根か否かがかなり面倒さに強くかかわっている。
根には空のノードを入れておいて、その左右の子が実質上の根を指すようにする……とかすれば回避できないかな。まあいいや。
とりあえずこれでおわり。印刷とかもあるけど基本操作はこれで全部の筈。
これを一つのクラス(class BinarySearchTree
使用例。
public static void main(String args[]){ int count = 0; BinarySearchTree<String> st = new BinarySearchTree<String>(); st.insert(5,"five"); st.insert(2,"two"); st.insert(4,"four"); st.insert(9,"nine"); st.insert(0,"zero"); st.insert(1,"one"); st.insert(7,"seven"); st.insert(6,"six"); st.insert(3,"three"); st.insert(10,"ten"); st.insert(11,"eleven"); st.delete(5); st.delete(7); st.delete(9); st.delete(10); st.delete(11); st.delete(6); }
上の例だと木の形はこんな風に変わる。
さて、とりあえず書いたけど、自分の中じゃ完成ではない。
勿論二分探索木としてはこれで十分完成だとは思うけど、もうちょっと進んだ平衡二分探索木をいくつか書いてみようと思ってます。
次回更新はなるべく空かないように頑張ります……
それでは！（・ω・）ﾉｼ
