はじめに
これは、二分木の一つである二分探索木についての記事です。
この記事中の図は以下を用いて作成しました。
visualization
木構造の全般的な説明はこちら
参考：
お気楽Ｃ言語プログラミング超入門 中級編 : 二分探索木
二分探索木とは
ノードが持つ値を「左の子<=親<=右の子」となるように並べた2分木を指します。
操作
最初の状態を以下とします。
これは二分探索木の定義を満たします。
検索
「左の子<=親<=右の子」というルールを使って再帰処理として実装できます。
targetの値を探すときに通るルートをpathとして返します。targetが木構造内に存在しない場合は「NotFound」と返します。
public String search(Node node, int target, String path) {
if(node == null) {
return "NotFound";
}
if(node.value == target) {
return path + "," + node.value;
}
if(node.value > target) {
return search(node.left, target, path + "," + node.value);
}
return search(node.right, target, path + "," + node.value);
}
public static void main(String[] args) {
Node root = new Node(5);
root.left = new Node(3);
root.right = new Node(7);
root.left.left = new Node(1);
root.right.left = new Node(6);
root.right.right = new Node(8);
System.out.println(search(root, 5, "")); // ,5
System.out.println(search(root, 6, "")); // ,5,7,6
System.out.println(search(root, 1, "")); // ,5,3,1
System.out.println(search(root, 5, "")); // NotFound
}
追加
二分探索木のルール（左の子<=親<=右の子）を満たすような位置にノードを追加します。
こちらも再帰処理で実装できます。
newNodeを適切な場所に追加します。渡されたnodeを直接書き換えます。
public Node add(Node node, Node newNode){
if(node == null) {
return newNode;
}
if(node.value == newNode.value) {
// 重複を許さないので何もしない
}
else if(node.value > newNode.value) {
node.left = add(node.left, newNode);
}
else {
node.right = add(node.right, newNode);
}
return node;
}
public void print(Node node, String prefix, boolean isLeft, String label){
if (node == null) {
return;
}
System.out.println(prefix + (isLeft ? "├── " : "└── ") + label + node.value);
String childPrefix = prefix + (isLeft ? "│ " : " ");
print(node.left, childPrefix, true, "L:");
print(node.right, childPrefix, false, "R:");
}
public static void main(String[] args) {
Node root = new Node(5);
root.left = new Node(3);
root.right = new Node(7);
root.left.left = new Node(1);
root.right.left = new Node(6);
root.right.right = new Node(8);
root = add(root, new Node(2));
print(root, "", false, "");
/**
└── 5
├── L:3
│ ├── L:1
│ │ └── R:2
└── R:7
├── L:6
└── R:8
*/
}
削除
二分探索木のルール（左の子<=親<=右の子）に従って対象のノードを探し、削除します。
葉を削除する場合は削除対象のノードをNULLとします。
子を一つのみ持つノード（左の子のみ、もしくは右の子のみ）を削除する場合は、削除対象のノードを子で置き換えます。
子を二つ持つノード（左の子、右の子、どちらも持つノード）の場合、そのまま削除しようとすると二分探索木の構造が崩れます。少し考えましょう。
削除する際、削除対象のノードの子の構造をなるべく変更せずに削除したいです。（子を付け替えるだけにしたい）
削除対象のノードの位置に入ることができる値を考えます。
削除対象のノードは、その右の子の全てのノードよりも値が小さいです。よって、右部分木の最小値は削除対象のノードの位置に入れそうです。
また、削除対象のノードは、その左のこの全てのノードよりも値が大きいです。よって、左部分木の最大値は削除対象のノードの位置に入れそうです。
今回は、右部分木の最小値と入れ替える方向で実装します。
public Node delete(Node node, int target) {
if(node == null) {
return node;
}
if(node.value == target) {
if(node.left == null && node.right == null) {
node = null;
}
else if(node.left == null) {
node = node.right;
}
else if(node.right == null) {
node = node.left;
}
else {
int min = getMin(node.right);
node.right = delete(node.right, min);
node.value = min;
}
}
else if(node.value > target) {
node.left = delete(node.left, target);
} else{
node.right = delete(node.right, target);
}
return node;
}
private int getMin(Node node) {
if(node.left == null) {
return node.value;
}
return getMin(node.left);
}
public static void main(String[] args) {
Node root = new Node(5);
root.left = new Node(3);
root.right = new Node(7);
root.left.left = new Node(1);
root.right.left = new Node(6);
root.right.right = new Node(8);
delete(root, 7);
print(root, "", false, "");
/**
└── 5
├── L:3
│ ├── L:1
└── R:8
├── L:6
*/
}
性能
二分探索木はその形によって性能が大きく変わります。
例えば小さい順に追加する場合、全て右の子として挿入することになるため、辿らなければいけないパスが数に比例して大きくなります。つまり$O(n)$です。（この形はLinkedListの形です）
対して、左右のバランスが取れている場合、たどるべきパスが短くなります（$O(\log{n})$になります）。
よって、この単純な二分探索木ははっきり言って実用に耐える構造ではなく、バランスをとるためにもう少し工夫をしなくてはいけません。
工夫してバランスをとった木構造を、平衡木と呼びます。
おわりに
木構造の出力はチャッピーに書いてもらいました。でもこの出力方法だと、「左」と「右」がわかりにくいですよね。そう伝えるとラベルを出力することを提案してくれました。うーんまあデバッグ用みたいなもんだしこれでいいか、と妥協しました。