Java implements graphic details of searching, inserting, deleting, and traversing binary search trees

This article mainly introduces the Java implementation of search, insertion, deletion, traversal, etc. of a binary search tree. It has a very good reference value. Let’s take a look at it with the editor.

Recently I want to read about the specific implementation of HashMap in JDK1.8, but because the implementation of HashMap uses red-black trees, so I think it is necessary to review the relevant knowledge of red-black trees first, so I wrote this essay memo. Please point out if there are any mistakes~

To learn red-black trees, I think it is necessary to start with binary search trees To start learning, this essay mainly introduces Java to implement search, insertion, deletion, traversal, etc. of a binary search tree.

The binary search tree must meet the following four conditions:

If the left subtree of any node is not empty, then the values ​​of all nodes on the left subtree are equal Less than the value of its root node;

If the right subtree of any node is not empty, then the values ​​of all nodes on the right subtree are greater than the value of its root node;

The left and right subtrees of any node are also binary search trees respectively;

There are no nodes with equal key values.

Binary search tree example:

Figure 1

Next Based on Figure 1, we introduce the related operations of binary search tree.

First of all, there should be a class related to the node object, named Node.

class Node {
 int key;
 int value;
 Node leftChild;
 Node rightChild;
 public Node(int key, int value) {
 this.key = key;
 this.value = value;
 }
 public void displayNode() {
 }
}

The Node class contains the key value, which is used to determine the corresponding position of the node in the tree. The value value represents the content to be stored, and also contains points to the left and right child nodes. of two references.

Next, let’s look at the corresponding class of the search tree:

class Tree {
 Node root;//保存树的根
 public Node find(int key) {//查找指定节点
 }
 public void insert(int key, int value) {//插入节点
 }
 public boolean delete(int key) {//删除指定节点
 }
 private Node getDirectPostNode(Node delNode) {//得到待删除节点的直接后继节点
 }
 public void preOrder(Node rootNode) {//先序遍历树
 }
 public void inOrder(Node rootNode) {//中序遍历树
 }
 public void postOrder(Node rootNode) {//后序遍历树
 }
}

The framework of the class represents the tree, including search, insertion, traversal, and deletion The corresponding methods, among which the node deletion operation is the most complicated, will be introduced one by one next.

1. Find a node

Due to the particularity of the definition of binary search tree, it only needs to be compared from the root based on the input key value. If it is less than The key value of the root is compared with the left subtree of the root, and the key value greater than the root is compared with the right subtree of the root, and so on. If found, the corresponding node is returned, otherwise null is returned.

public Node find(int key) {
 Node currentNode = root;
 while (currentNode != null && currentNode.key != key) {
 if (key < currentNode.key) {
 currentNode = currentNode.leftChild;
 } else {
 currentNode = currentNode.rightChild;
 }
 }
 return currentNode;
}

2. Inserting nodes

is similar to the search operation. Due to the particularity of the binary search tree, it needs to be The inserted node also needs to be compared starting from the root node. If it is smaller than the root node, it will be compared with the left subtree of the root node. Otherwise, it will be compared with the right subtree. Until the left subtree is empty or the right subtree is empty, insert it into the corresponding node. For empty positions, during the comparison process, you must pay attention to saving the information of the parent node and whether the position to be inserted is the left subtree or the right subtree of the parent node, so that it can be inserted into the correct position.

public void insert(int key, int value) {
 if (root == null) {
 root = new Node(key, value);
 return;
 }
 Node currentNode = root;
 Node parentNode = root;
 boolean isLeftChild = true;
 while (currentNode != null) {
 parentNode = currentNode;
 if (key < currentNode.key) {
 currentNode = currentNode.leftChild;
 isLeftChild = true;
 } else {
 currentNode = currentNode.rightChild;
 isLeftChild = false;
 }
 }
 Node newNode = new Node(key, value);
 if (isLeftChild) {
 parentNode.leftChild = newNode;
 } else {
 parentNode.rightChild = newNode;
 }
}

3. Traversing a binary search tree

The traversal operation is exactly the same as traversing an ordinary binary tree and will not be described in detail. .

public void preOrder(Node rootNode) {
 if (rootNode != null) {
 System.out.println(rootNode.key + " " + rootNode.value);
 preOrder(rootNode.leftChild);
 preOrder(rootNode.rightChild);
 }
 }
public void inOrder(Node rootNode) {
 if (rootNode != null) {
 inOrder(rootNode.leftChild);
 System.out.println(rootNode.key + " " + rootNode.value);
 inOrder(rootNode.rightChild);
 }
 }
public void postOrder(Node rootNode) {
 if (rootNode != null) {
 postOrder(rootNode.leftChild);
 postOrder(rootNode.rightChild);
 System.out.println(rootNode.key + " " + rootNode.value);
 }
 }

4. Delete the specified node.

The operation of deleting nodes in a binary search tree is complicated and can be divided into the following three situations.

1. The node to be deleted is a leaf node and can be deleted directly.

public boolean delete(int key) {
 Node currentNode = root;//用来保存待删除节点
 Node parentNode = root;//用来保存待删除节点的父亲节点
 boolean isLeftChild = true;//用来确定待删除节点是父亲节点的左孩子还是右孩子
 while (currentNode != null && currentNode.key != key) {
 parentNode = currentNode;
 if (key < currentNode.key) {
 currentNode = currentNode.leftChild;
 isLeftChild = true;
 } else {
 currentNode = currentNode.rightChild;
 isLeftChild = false;
 }
 }
 if (currentNode == null) {
 return false;
 }
 if (currentNode.leftChild == null && currentNode.rightChild == null) {//要删除的节点为叶子节点
 if (currentNode == root)
 root = null;
 else if (isLeftChild)
 parentNode.leftChild = null;
 else
 parentNode.rightChild = null;
 } 
 ......
 }

2. The node to be deleted has only one child node

For example, to delete the node with key value 11 in Figure 1, you only need to point the left child of the node with key value 13 to the node with key value 12 to delete the node with key value 11.

The code obtained from the above analysis is as follows (followed by the ellipsis of the above delete method):

else if (currentNode.rightChild == null) {//要删除的节点只有左孩子
 if (currentNode == root)
 root = currentNode.leftChild;
 else if (isLeftChild)
 parentNode.leftChild = currentNode.leftChild;
 else
 parentNode.rightChild = currentNode.leftChild;
 } else if (currentNode.leftChild == null) {//要删除的节点只有右孩子
 if (currentNode == root)
 root = currentNode.rightChild;
 else if (isLeftChild)
 parentNode.leftChild = currentNode.rightChild;
 else
 parentNode.rightChild = currentNode.rightChild;
 } 
 ......

3. Wait Deleting a node has both left and right children.

For example, if you delete the node with the key value 10 in Figure 1, you need to replace the node with the key value 10 with the in-order successor node (node ​​11). node, and delete the in-order successor node of the node with a key value of 10. According to the relevant rules of in-order traversal, the direct in-order successor node of the node with a key value of 10 must be the node with the smallest key value in its right subtree. Therefore, the in-order successor node must not contain child nodes or only contain one right child. Deleting the in-order successor node belongs to the situations described in 1 and 2 above. In Figure 1, the direct in-order successor node of the node with key value 10 is 11, and node 11 contains a right child 12.

So deleting the node with a key value of 10 in Figure 1 is divided into the following steps:

a. Find the direct in-order successor node of the node with a key value of 10 (That is, the node 11 with the smallest value in its right subtree), and delete this direct in-order successor node.

private Node getDirectPostNode(Node delNode) {//方法作用为得到待删除节点的直接后继节点
 Node parentNode = delNode;//用来保存待删除节点的直接后继节点的父亲节点
 Node direcrPostNode = delNode;//用来保存待删除节点的直接后继节点
 Node currentNode = delNode.rightChild;
 while (currentNode != null) {
 parentNode = direcrPostNode;
 direcrPostNode = currentNode;
 currentNode = currentNode.leftChild;
 }
 if (direcrPostNode != delNode.rightChild) {//从树中删除此直接后继节点
 parentNode.leftChild = direcrPostNode.rightChild;
 direcrPostNode.rightChild = null;
 }
 return direcrPostNode;//返回此直接后继节点
}

#b. Assign the key and value of the successor node to the key of the node to be deleted. value value. (Following the ellipsis code in case 2)

##

else { //要删除的节点既有左孩子又有右孩子
 //思路：用待删除节点右子树中的key值最小节点的值来替代要删除的节点的值,然后删除右子树中key值最小的节点
 //右子树key最小的节点一定不含左子树,所以删除这个key最小的节点一定是属于叶子节点或者只有右子树的节点
 Node directPostNode = getDirectPostNode(currentNode);
 currentNode.key = directPostNode.key;
 currentNode.value = directPostNode.value;
}

The operation of deleting the specified node ends.

Finally, the complete code and simple test code and test results are given:

class Node {
 int key;
 int value;
 Node leftChild;
 Node rightChild;
 public Node(int key, int value) {
 this.key = key;
 this.value = value;
 }
 public void displayNode() {
 }
}
class Tree {
 Node root;
 public Node find(int key) {
 Node currentNode = root;
 while (currentNode != null && currentNode.key != key) {
 if (key < currentNode.key) {
 currentNode = currentNode.leftChild;
 } else {
 currentNode = currentNode.rightChild;
 }
 }
 return currentNode;
 }
 public void insert(int key, int value) {
 if (root == null) {
 root = new Node(key, value);
 return;
 }
 Node currentNode = root;
 Node parentNode = root;
 boolean isLeftChild = true;
 while (currentNode != null) {
 parentNode = currentNode;
 if (key < currentNode.key) {
 currentNode = currentNode.leftChild;
 isLeftChild = true;
 } else {
 currentNode = currentNode.rightChild;
 isLeftChild = false;
 }
 }
 Node newNode = new Node(key, value);
 if (isLeftChild) {
 parentNode.leftChild = newNode;
 } else {
 parentNode.rightChild = newNode;
 }
 }
 public boolean delete(int key) {
 Node currentNode = root;
 Node parentNode = root;
 boolean isLeftChild = true;
 while (currentNode != null && currentNode.key != key) {
 parentNode = currentNode;
 if (key < currentNode.key) {
 currentNode = currentNode.leftChild;
 isLeftChild = true;
 } else {
 currentNode = currentNode.rightChild;
 isLeftChild = false;
 }
 }
 if (currentNode == null) {
 return false;
 }
 if (currentNode.leftChild == null && currentNode.rightChild == null) {
 //要删除的节点为叶子节点
 if (currentNode == root)
 root = null;
 else if (isLeftChild)
 parentNode.leftChild = null;
 else
 parentNode.rightChild = null;
 } else if (currentNode.rightChild == null) {//要删除的节点只有左孩子
 if (currentNode == root)
 root = currentNode.leftChild;
 else if (isLeftChild)
 parentNode.leftChild = currentNode.leftChild;
 else
 parentNode.rightChild = currentNode.leftChild;
 } else if (currentNode.leftChild == null) {//要删除的节点只有右孩子
 if (currentNode == root)
 root = currentNode.rightChild;
 else if (isLeftChild)
 parentNode.leftChild = currentNode.rightChild;
 else
 parentNode.rightChild = currentNode.rightChild;
 } else { //要删除的节点既有左孩子又有右孩子
 //思路：用待删除节点右子树中的key值最小节点的值来替代要删除的节点的值,然后删除右子树中key值最小的节点
 //右子树key最小的节点一定不含左子树,所以删除这个key最小的节点一定是属于叶子节点或者只有右子树的节点
 Node directPostNode = getDirectPostNode(currentNode);
 currentNode.key = directPostNode.key;
 currentNode.value = directPostNode.value;
 }
 return true;
 }
 private Node getDirectPostNode(Node delNode) {//方法作用为得到待删除节点的直接后继节点
 Node parentNode = delNode;//用来保存待删除节点的直接后继节点的父亲节点
 Node direcrPostNode = delNode;//用来保存待删除节点的直接后继节点
 Node currentNode = delNode.rightChild;
 while (currentNode != null) {
 parentNode = direcrPostNode;
 direcrPostNode = currentNode;
 currentNode = currentNode.leftChild;
 }
 if (direcrPostNode != delNode.rightChild) {//从树中删除此直接后继节点
 parentNode.leftChild = direcrPostNode.rightChild;
 direcrPostNode.rightChild = null;
 }
 return direcrPostNode;//返回此直接后继节点
 }
 public void preOrder(Node rootNode) {
 if (rootNode != null) {
 System.out.println(rootNode.key + " " + rootNode.value);
 preOrder(rootNode.leftChild);
 preOrder(rootNode.rightChild);
 }
 }
 public void inOrder(Node rootNode) {
 if (rootNode != null) {
 inOrder(rootNode.leftChild);
 System.out.println("key: " + rootNode.key + " " + "value: " + rootNode.value);
 inOrder(rootNode.rightChild);
 }
 }
 public void postOrder(Node rootNode) {
 if (rootNode != null) {
 postOrder(rootNode.leftChild);
 postOrder(rootNode.rightChild);
 System.out.println(rootNode.key + " " + rootNode.value);
 }
 }
}
public class BinarySearchTreeApp {
 public static void main(String[] args) {
 Tree tree = new Tree();
 tree.insert(6, 6);//插入操作,构造图一所示的二叉树
 tree.insert(3, 3);
 tree.insert(14, 14);
 tree.insert(16, 16);
 tree.insert(10, 10);
 tree.insert(9, 9);
 tree.insert(13, 13);
 tree.insert(11, 11);
 tree.insert(12, 12);
 System.out.println("删除前遍历结果");
 tree.inOrder(tree.root);//中序遍历操作
 System.out.println("删除节点10之后遍历结果");
 tree.delete(10);//删除操作
 tree.inOrder(tree.root);
 }
}

Test results:

The above is the graphic and text details of Java’s implementation of binary search tree search, insertion, deletion, and traversal. Please pay attention to more related content. PHP Chinese website (www.php.cn)!