2分探索木の削除アルゴリズム
２分探索木のアルゴリズム実装課題で悩んでいます。
追加、探索までは実装でき、テストもokだったのですが、削除だけうまくいきません。
実装したい削除メソッドの構造は、
- (a),(b),(c)で場合分けして削除する
(a)削除するkeyの節点が葉
(b)削除するkeyの節点が１つのみ子を持つ
(c)削除するkeyの節点が２つの子を持つ - 探索メソッドと同様削除する値を探索し、探索が失敗した場合エラーメッセージ
場合分けしたところまでは良いものの、実際に値を削除する方法がわかりません
削除したいノード=nullをしても値は削除されません
public class BinarySearchTree {
private Node root = null; // 根
private class Node {
private int key; // key
private Node left; // 左の子
private Node right; // 右の子
private Node(int key) {
this.key = key;
left = null;
right = null;
}
public String toString() {
return String.format("<%s(%d)%s>", (left == null ? "/" :
left), key, (right == null ? "/" : right));
}
}
public void add(int x) {
Node v = root; // 探索中のノードを指すカーソル
Node p = null; // 探索中のノードの親を指すカーソル
boolean isLeft = true; // ノードpの左の子を参照したならtrue, 右の子を参照したならfalse
Node nn = new Node(x); // 新たに追加するkey値をもつノード
while (v != null) { //葉に到達していないことを表す
if (x < v.key) {
p = v;
isLeft = true;
v = v.left;
}else{
p = v;
isLeft = false;
v = v.right;
}
}
if (v == root) root = nn;
else if (isLeft) p.left = nn;
else p.right = nn;
}
//課題追加部分:探索アルゴリズム
//探索が成功すれば真を、失敗すれば偽を返す
public boolean search(int x){
Node v = root; // 探索中のノードを指すカーソル
boolean ret = false; //探索成功の可否の判定値
while(v != null && !ret){ //１つ目の条件は葉に到達していないことを表す
if(x<v.key) v = v.left; //keyが探索する値よりも大きい場合、左の子へ移動
else if(x>v.key) v= v.right; //keyが探索する値よりも小さい場合、右の子へ移動
else ret =true; //探索する値が見つかった時
}
return ret;
}
//質問部分！！！！
//課題追加部分:削除アルゴリズム
//削除するkeyの節点によって(a),(b),(c)で場合分けする
public void delete(int x){
Node v = root;
boolean ret = false;
while(v != null && !ret){
if(x<v.key) v = v.left;
else if(x>v.key) v= v.right;
else {
ret = true;
if(v.left==null&&v.right==null){ //(a)削除するkeyの節点が葉
v = null;
}
else if(v.left==null||v.right==null){ //(b)削除するkeyの節点が１つのみ子を持つ
}
else{ //(c)削除するkeyの節点が２つの子を持つ
}
}
}
if(ret) System.out.println( x + "を削除しました.");
else System.out.println("削除したいkeyが見つかりません.");
}
public String toString() {
return String.format("%s",(this.root==null ? "/" :this.root));
}
public static void main(String[] args) {
// TODO 自動生成されたメソッド・スタブ
BinarySearchTree bst = new BinarySearchTree();
System.out.println(bst);
System.out.println("50,31,81,15,41,62,92,3,28,33,53,74,85を順に追加:");
bst.add(50);
System.out.println(bst);
bst.add(31);
System.out.println(bst);
bst.add(81);
System.out.println(bst);
bst.add(15);
System.out.println(bst);
bst.add(41);
System.out.println(bst);
bst.add(62);
System.out.println(bst);
bst.add(92);
System.out.println(bst);
bst.add(3);
System.out.println(bst);
bst.add(28);
System.out.println(bst);
bst.add(33);
System.out.println(bst);
bst.add(53);
System.out.println(bst);
bst.add(74);
System.out.println(bst);
bst.add(85);
System.out.println(bst);
//追加課題部分テスト:探索アルゴリズム
System.out.println("3の探索結果:" + bst.search(3)); //探索成功
System.out.println("11の探索結果:" + bst.search(11)); //探索失敗
//追加課題部分テスト:削除アルゴリズム
bst.delete(3); //(a)の場合
System.out.println(bst);
/*
bst.delete(5); //(b)の場合
System.out.println(bst);
bst.delete(81); //(c)の場合
System.out.println(bst);
bst.delete(91); //削除するkeyが存在しない場合
*/
}
}
mainメソッドbst.delete(3);の実行結果
