さまざまなデータ構造（１２）二分探索木３
こんにちは。前回は二分探索木を取り上げました。今回はプログラムをまとめることにします。
二分探索木のクラス
前回示した手順をクラスとしてまとめました。次のようになります。前回のポイントになっているのは、find・insert・deleteのメソッドです。１２１行目以降は、表示するためのメソッドです。
package data_structure;
public class MyBinarySearchTree {
private MyTreeNode<Integer> root;
public MyBinarySearchTree() {
root = null;
}
public MyTreeNode<Integer> find(Integer element) {
MyTreeNode<Integer> node = root;
while (node != null && node.getElement() != element) {
if (element < node.getElement()) {
node = node.getLeft();
} else {
node = node.getRight();
}
}
return node;
}
public void insert(Integer element) {
if (root == null) {
MyTreeNode<Integer> tmp = new MyTreeNode<Integer>(element, null, null);
root = tmp;
return;
}
insert(root, element);
}
private void insert(MyTreeNode<Integer> node, Integer element) {
if (element < node.getElement()) {
if (node.getLeft() == null) {
MyTreeNode<Integer> tmp = new MyTreeNode<Integer>(element, null, null);
node.setLeft(tmp);
return;
} else {
insert(node.getLeft(), element);
return;
}
} else {
if (node.getRight() == null) {
MyTreeNode<Integer> tmp = new MyTreeNode<Integer>(element, null, null);
node.setRight(tmp);
return;
} else {
insert(node.getRight(), element);
return;
}
}
}
public boolean delete(Integer element) {
if (find(element) == null) {
return false;
}
MyTreeNode<Integer> parent = null;
MyTreeNode<Integer> child = root;
while (child.getElement() != element) {
if (element < child.getElement()) {
parent = child;
child = child.getLeft();
} else {
parent = child;
child = child.getRight();
}
}
if (child.getLeft() == null && child.getRight() == null) {
if (child == root) {
root = null;
return true;
}
if (child == parent.getLeft()) {
parent.setLeft(null);
} else {
parent.setRight(null);
}
return true;
}
if (child.getLeft() == null || child.getRight() == null) {
MyTreeNode<Integer> node;
if (child.getLeft() == null) {
node = child.getRight();
} else {
node = child.getLeft();
}
if (child == root) {
root = node;
} else if (child == parent.getLeft()) {
parent.setLeft(node);
} else {
parent.setRight(node);
}
return true;
}
if (child == root) {
root = child.getLeft();
} else if (parent.getLeft() == child) {
parent.setLeft(child.getLeft());
} else {
parent.setRight(child.getLeft());
}
MyTreeNode<Integer> node = child.getRight();
child = child.getLeft();
while (child.getRight() != null) {
child = child.getRight();
}
child.setRight(node);
return true;
}
public void printPreOrder() {
System.out.println("PreOrder : " + preOrder(root));
}
private static String preOrder(MyTreeNode<Integer> node) {
String result = "" + node.getElement();
if (node.getLeft() != null) {
result += " " + preOrder(node.getLeft());
}
if (node.getRight() != null) {
result += " " + preOrder(node.getRight());
}
return result;
}
public void printInOrder() {
System.out.println("InOrder : " + inOrder(root));
}
private static String inOrder(MyTreeNode<Integer> node) {
String result = "";
if (node.getLeft() != null) {
result += inOrder(node.getLeft());
}
result += " " + node.getElement();
if (node.getRight() != null) {
result += inOrder(node.getRight());
}
return result;
}
public void printPostOrder() {
System.out.println("PostOrder : " + postOrder(root));
}
private static String postOrder(MyTreeNode<Integer> node) {
String result = "";
if (node.getLeft() != null) {
result += postOrder(node.getLeft());
}
if (node.getRight() != null) {
result += postOrder(node.getRight());
}
result += " " + node.getElement();
return result;
}
public void printDepthFirst() {
System.out.println("DepthFirstSearch : " + depthFirst(root));
}
private static String depthFirst(MyTreeNode<Integer> node) {
MyStack<MyTreeNode<Integer>> stack = new MyStack<MyTreeNode<Integer>>();
MyTreeNode<Integer> tmp;
String result = "";
stack.push(node);
while (!stack.empty()) {
tmp = stack.pop();
result += " " + tmp.getElement();
if (tmp.getRight() != null) {
stack.push(tmp.getRight());
}
if (tmp.getLeft() != null) {
stack.push(tmp.getLeft());
}
}
return result;
}
public void printBreadthFirst() {
System.out.println("BreadthFirstSearch : " + breadthFirst(root));
}
private static String breadthFirst(MyTreeNode<Integer> node) {
MyQueue<MyTreeNode<Integer>> queue = new MyQueue<MyTreeNode<Integer>>();
MyTreeNode<Integer> tmp;
String result = "";
queue.offer(node);
while (!queue.isEmpty()) {
tmp = queue.poll();
result += " " + tmp.getElement();
if (tmp.getLeft() != null) {
queue.offer(tmp.getLeft());
}
if (tmp.getRight() != null) {
queue.offer(tmp.getRight());
}
}
return result;
}
public void printTree() {
System.out.println(TreeToString(0, "", root));
}
private static String TreeToString(int n, String direction, MyTreeNode<Integer> node) {
if (node == null) {
return "";
}
String result = "";
result += String.format("%2d", node.getElement());
if (node.getLeft() != null && node.getRight() != null) {
result += "┬";
} else if (node.getRight() != null) {
result += "─";
} else if (node.getLeft() != null) {
result += "┐";
}
if (node.getRight() != null && node.getLeft() != null) {
result += TreeToString(n + 1, direction + "R", node.getRight());
} else if (node.getRight() != null) {
result += TreeToString(n + 1, direction + "r", node.getRight());
}
if (node.getLeft() != null) {
result += "\n";
for (int i = 0; i <= n; i++) {
result += " ";
if (i < n && direction.substring(i, i + 1).equals("R")) {
result += "│";
} else if (i < n) {
result += " ";
}
}
result += "└";
result += TreeToString(n + 1, direction + "L", node.getLeft());
}
return result;
}
}
二分探索木の実行用プログラム
このプログラムでは、はじめに乱数を２０個発生させ、二分探索木に挿入します。挿入する度に、二分探索木を表示します。
次に出来上がった二分探索木を、先行順・中間順・後行順・深さ優先・幅優先で走査します。
その次に、乱数で発生した値が存在するか否かを探索することを５回行います。
その次に、乱数で発生した値を１０回削除します。削除する度に、二分探索木を表示します。
挿入および削除の度に二分探索木を表示しているのは、いずれも操作の様子がわかるようにするためです。
package data_structure;
import java.util.Random;
public class MyBinarySearchTreeExec {
public static void main(String[] args) {
Random random = new Random();
MyBinarySearchTree bst = new MyBinarySearchTree();
int count = 0;
while (count < 20) {
int r = random.nextInt(100);
bst.insert(r);
count++;
}
bst.printPreOrder();
bst.printInOrder();
bst.printPostOrder();
bst.printDepthFirst();
bst.printBreadthFirst();
System.out.println();
for (int i = 0; i < 5; i++) {
int r = random.nextInt(100);
if (bst.find(r) == null) {
System.out.println(r + "はありません");
} else {
System.out.println(r + "はあります");
}
}
count = 0;
while (count < 10) {
int r = random.nextInt(100);
if (bst.delete(r)) {
System.out.println();
System.out.println("Delete " + r);
bst.printTree();
count++;
}
}
}
}
二分探索木を実行した結果
木の表示がフォント幅の関係で崩れてしまっていますが、温かく見てください。見どころはdeleteの一番最初で、rootノードをいきなり削除しています。
Insert 32
32
Insert 28
32┐
└28
Insert 73
32┬73
└28
Insert 0
32┬73
└28┐
└ 0
Insert 90
32┬73─90
└28┐
└ 0
Insert 30
32┬73─90
└28┬30
└ 0
Insert 70
32┬73┬90
│ └70
└28┬30
└ 0
Insert 37
32┬73┬90
│ └70┐
│ └37
└28┬30
└ 0
Insert 43
32┬73┬90
│ └70┐
│ └37─43
└28┬30
└ 0
Insert 89
32┬73┬90┐
│ │ └89
│ └70┐
│ └37─43
└28┬30
└ 0
Insert 78
32┬73┬90┐
│ │ └89┐
│ │ └78
│ └70┐
│ └37─43
└28┬30
└ 0
Insert 59
32┬73┬90┐
│ │ └89┐
│ │ └78
│ └70┐
│ └37─43─59
└28┬30
└ 0
Insert 60
32┬73┬90┐
│ │ └89┐
│ │ └78
│ └70┐
│ └37─43─59─60
└28┬30
└ 0
Insert 49
32┬73┬90┐
│ │ └89┐
│ │ └78
│ └70┐
│ └37─43─59┬60
│ └49
└28┬30
└ 0
Insert 79
32┬73┬90┐
│ │ └89┐
│ │ └78─79
│ └70┐
│ └37─43─59┬60
│ └49
└28┬30
└ 0
Insert 99
32┬73┬90┬99
│ │ └89┐
│ │ └78─79
│ └70┐
│ └37─43─59┬60
│ └49
└28┬30
└ 0
Insert 74
32┬73┬90┬99
│ │ └89┐
│ │ └78┬79
│ │ └74
│ └70┐
│ └37─43─59┬60
│ └49
└28┬30
└ 0
Insert 98
32┬73┬90┬99┐
│ │ │ └98
│ │ └89┐
│ │ └78┬79
│ │ └74
│ └70┐
│ └37─43─59┬60
│ └49
└28┬30
└ 0
Insert 93
32┬73┬90┬99┐
│ │ │ └98┐
│ │ │ └93
│ │ └89┐
│ │ └78┬79
│ │ └74
│ └70┐
│ └37─43─59┬60
│ └49
└28┬30
└ 0
Insert 95
32┬73┬90┬99┐
│ │ │ └98┐
│ │ │ └93─95
│ │ └89┐
│ │ └78┬79
│ │ └74
│ └70┐
│ └37─43─59┬60
│ └49
└28┬30
└ 0
PreOrder : 32 28 0 30 73 70 37 43 59 49 60 90 89 78 74 79 99 98 93 95
InOrder : 0 28 30 32 37 43 49 59 60 70 73 74 78 79 89 90 93 95 98 99
PostOrder : 0 30 28 49 60 59 43 37 70 74 79 78 89 95 93 98 99 90 73 32
DepthFirstSearch : 32 28 0 30 73 70 37 43 59 49 60 90 89 78 74 79 99 98 93 95
BreadthFirstSearch : 32 28 73 0 30 70 90 37 89 99 43 78 98 59 74 79 93 49 60 95
41はありません
38はありません
91はありません
22はありません
8はありません
Delete 32
28┬30─73┬90┬99┐
│ │ │ └98┐
│ │ │ └93─95
│ │ └89┐
│ │ └78┬79
│ │ └74
│ └70┐
│ └37─43─59┬60
│ └49
└ 0
Delete 74
28┬30─73┬90┬99┐
│ │ │ └98┐
│ │ │ └93─95
│ │ └89┐
│ │ └78─79
│ └70┐
│ └37─43─59┬60
│ └49
└ 0
Delete 70
28┬30─73┬90┬99┐
│ │ │ └98┐
│ │ │ └93─95
│ │ └89┐
│ │ └78─79
│ └37─43─59┬60
│ └49
└ 0
Delete 43
28┬30─73┬90┬99┐
│ │ │ └98┐
│ │ │ └93─95
│ │ └89┐
│ │ └78─79
│ └37─59┬60
│ └49
└ 0
Delete 60
28┬30─73┬90┬99┐
│ │ │ └98┐
│ │ │ └93─95
│ │ └89┐
│ │ └78─79
│ └37─59┐
│ └49
└ 0
Delete 49
28┬30─73┬90┬99┐
│ │ │ └98┐
│ │ │ └93─95
│ │ └89┐
│ │ └78─79
│ └37─59
└ 0
Delete 89
28┬30─73┬90┬99┐
│ │ │ └98┐
│ │ │ └93─95
│ │ └78─79
│ └37─59
└ 0
Delete 37
28┬30─73┬90┬99┐
│ │ │ └98┐
│ │ │ └93─95
│ │ └78─79
│ └59
└ 0
Delete 79
28┬30─73┬90┬99┐
│ │ │ └98┐
│ │ │ └93─95
│ │ └78
│ └59
└ 0
Delete 99
28┬30─73┬90┬98┐
│ │ │ └93─95
│ │ └78
│ └59
└ 0
二分探索木の欠点である昇順または降順に近い順序でデータを追加した場合に連結リストのようになってしまう問題を解決しようかどうしようか・・・とりあえず今回はこれでおしまい。それではまた。