バイナリーサーチツリー（BST）- 検索、挿入、削除
このチュートリアルでは、バイナリサーチツリーデータ構造について話し合います。バイナリサーチツリーから値を検索、挿入、削除するための関数を実装します。また、これらの操作を再帰的におよび反復的に実装します。
バイナリーツリー
バイナリサーチツリーには、以下の特性があります。
- All nodes should be such that the left child is always less than the parent node.
- The right child is always greater than the parent node.
以下のセクションでは、再帰的および反復的にBST（二分探索木）での検索、挿入、および削除方法を見ていきます。まず、二分木のデータ構造を作成しましょう。
public class BinaryTree {
public TreeNode root;
public static class TreeNode {
public TreeNode left;
public TreeNode right;
public Object data;
public TreeNode(Object data) {
this.data = data;
left = right = null;
}
}
}
上記の実装は、要素を木に挿入する制限がないため、バイナリサーチツリーではありません。
再帰的にBST探索
以下のJavaプログラムには、再帰的にBST内の値を検索するための関数が含まれています。
public class SearchInsertRemoveFromTree {
public static void main(String[] args) {
/**
* Our Example Binary Search Tree
* 10
* 5 20
* 4 8 15 25
*/
BinaryTree tree = new BinaryTree();
tree.root = new TreeNode(10);
tree.root.left = new TreeNode(5);
tree.root.right = new TreeNode(20);
tree.root.left.left = new TreeNode(4);
tree.root.left.right = new TreeNode(8);
tree.root.right.left = new TreeNode(15);
tree.root.right.right = new TreeNode(25);
System.out.println("Search Value 2 is in tree? " + searchRecursively(tree.root, 2));
System.out.println("Search Value 10 in tree? " + searchRecursively(tree.root, 10));
}
public static boolean searchRecursively(TreeNode root, int value) {
if (root == null)
return false;
if ((int) root.data == value)
return true;
if (value < (int) root.data)
return searchRecursively(root.left, value);
else if (value > (int) root.data)
return searchRecursively(root.right, value);
return false;
}
}
出力は次のようになります。
BSTを反復的に検索する
反復処理で検索する場合は、代わりに次の方法を使用してください。
public static boolean searchIteratively(TreeNode root, int value) {
while (root != null) {
if ((int) root.data == value)
return true;
if (value < (int) root.data)
root = root.left;
else
root = root.right;
}
return false;
}
二分探索木に新しいノードを挿入する方法を見てみましょう。
再帰的にBSTに要素を挿入する。
public static TreeNode insertionRecursive(TreeNode root, int value) {
if (root == null)
return new TreeNode(value);
if (value < (int) root.data) {
root.left = insertionRecursive(root.left, value);
} else if (value > (int) root.data) {
root.right = insertionRecursive(root.right, value);
}
return root;
}
public static void printInorderTraversal(TreeNode root) {
if (root != null) {
printInorderTraversal(root.left);
System.out.print(root.data + " ");
printInorderTraversal(root.right);
}
}
メインメソッドで上記のメソッドを呼び出してください。
tree.root = insertionRecursive(tree.root, 24);
tree.root = insertionRecursive(tree.root, 2);
printInorderTraversal(tree.root);
その木は中間順序の形式で出力されています。
BST（Binary Search Tree）の挿入を反復的な方法で行う。
BSTの木にノードを反復的に挿入するには、2つのポインタを使用して木を走査する必要があります。
public static TreeNode insertionIterative(TreeNode root, int value) {
TreeNode current, parent;
TreeNode tempNode = new TreeNode(value);
if (root == null) {
root = tempNode;
return root;
} else {
current = root;
}
while (true) {
parent = current;
if (value < (int) current.data) {
current = current.left;
if (current == null) {
parent.left = tempNode;
return root;
}
} else if (value > (int) current.data) {
current = current.right;
if (current == null) {
parent.right = tempNode;
return root;
}
}
}
}
要素を再帰的に削除するBST
BSTから要素を削除することは、検索や挿入よりもやや複雑です。なぜなら、BSTのプロパティが保持されるようにする必要があるからです。ノードを削除するためには、まず検索する必要があります。次に、そのノードが子を持っているかどうかを判断する必要があります。
- If no children – Just delete.
- If a single child – Copy that child to the node.
- If two children – Determine the next highest element (inorder successor) in the right subtree. Replace the node to be removed with the inorder successor. Delete the inorder successor duplicate.
ノードの右側の子ノードの中で最小値を見つけることによって、中間次節点を取得することができます。
以下のJavaプログラムは、BSTから要素を削除します。
public static TreeNode deleteRecursively(TreeNode root, int value) {
if (root == null)
return root;
if (value < (int) root.data) {
root.left = deleteRecursively(root.left, value);
} else if (value > (int) root.data) {
root.right = deleteRecursively(root.right, value);
} else {
if (root.left == null) {
return root.right;
} else if (root.right == null)
return root.left;
root.data = inOrderSuccessor(root.right);
root.right = deleteRecursively(root.right, (int) root.data);
}
return root;
}
public static int inOrderSuccessor(TreeNode root) {
int minimum = (int) root.data;
while (root.left != null) {
minimum = (int) root.left.data;
root = root.left;
}
return minimum;
}
メインメソッドで上記の削除メソッドを呼び出してください。
tree.root = deleteRecursively(tree.root, 4);
tree.root = deleteRecursively(tree.root, 20);
printInorderTraversal(tree.root);
出力は：2 5 8 10 15 24 25 です。同じ手順を反復して行いましょう。
BSTを要素を反復的に削除する
public static TreeNode deleteNodeIteratively(TreeNode root, int value) {
TreeNode parent = null, current = root;
boolean hasLeft = false;
if (root == null)
return root;
while (current != null) {
if ((int) current.data == value) {
break;
}
parent = current;
if (value < (int) current.data) {
hasLeft = true;
current = current.left;
} else {
hasLeft = false;
current = current.right;
}
}
if (parent == null) {
return deleteNodeIteratively(current);
}
if (hasLeft) {
parent.left = deleteNodeIteratively(current);
} else {
parent.right = deleteNodeIteratively(current);
}
return root;
}
private static TreeNode deleteNodeIteratively(TreeNode node) {
if (node != null) {
if (node.left == null && node.right == null) {
return null;
}
if (node.left != null && node.right != null) {
TreeNode inOrderSuccessor = deleteInOrderSuccessorDuplicate(node);
node.data = inOrderSuccessor.data;
} else if (node.left != null) {
node = node.left;
} else {
node = node.right;
}
}
return node;
}
private static TreeNode deleteInOrderSuccessorDuplicate(TreeNode node) {
TreeNode parent = node;
node = node.right;
boolean rightChild = node.left == null;
while (node.left != null) {
parent = node;
node = node.left;
}
if (rightChild) {
parent.right = node.right;
} else {
parent.left = node.right;
}
node.right = null;
return node;
}
BST操作の時間計算量はO(h)です。ここで、hは木の高さを表します。
このチュートリアルは終わりです。
弊社のGitHubリポジトリからは、完全なコードとさらに多くのデータ構造とアルゴリズムの例をチェックアウトできます。