Recently, I feel the importance of basic knowledge ability more and more. It was all about catching up, doing business logic, avoiding the fact that you had a weak foundation. A recent determination was made to strengthen previously weak foundations. Start with the contents of your hitherto paradoxical search tree.Copy the codeIn our life, we often use the function of search. In the case of our small amount of data, we can use every time to traverse all the data to query our target data. As the amount of data increases, our way of traversing becomes a bit inadequate; You can also sort the data, using a more efficient binary lookup, but the array will behave very slowly when inserting or deleting data. So we can combine the efficiency of binary search query + the efficiency of linked list addition and deletion to achieve efficient search (symbol table)
Here I’ll list some tree content definitions (all the rest of the code is implemented in the Java language)
-
A tree is made up of nodes, each of which has a parent (the root node has no parent)
-
Nodes can contain links to non-existent NULL or other real nodes
-
Each node can contain multiple sub-links, and the number of sub-links is called degree. The degree of a tree is the largest degree of all the child nodes (the tree of degree 2 is called a binary tree, the tree of degree 3 is called a trigeminal tree, etc.). As shown in figure 1 to 3
-
Leaf node: nodes B, C, and D, as shown in Figure 1, have no child nodes
-
Parent node: A node with A child tree is the parent of the root node of its child tree. A node in Figure 1 is the parent of B, C, and D nodes
-
Child node: If node A is the parent of node B, then B is the child node of A, and the child node can also be the child node. In Figure 3, node A is the parent node of B, C, and D, and the child node of node H
-
Sibling nodes: nodes with the same parent are siblings B, C, and D of Fig-1
Binary search tree
define
-
Each node points to only one parent node and contains a maximum of two child links, left and right
-
The Key of the left child node is smaller than that of the parent node, and the Key of the right child node is larger than that of the parent node, as shown in Figure 4
Public class TreeNode<T extends Comparable<T>>{T data; TreeNode<T> left; TreeNode<T> right; int size; } public class BinarySearchTree<T extends Comparable<T>> {private TreeNode<T> root; }Copy the codeTo find the
Public TreeNode<T> find(T element, TreeNode<T> node){if (objects.isnull (node)) {return null; } T val = node.data; int res = val.compareTo(element); If (res == 0) {return node; } if (res < 0) {return find(element, node.getright ()); } return find(element, node.getLeft()); // The value of the node is greater than the value of the query, recursive left}Copy the codeQuery extreme values (Max/min)
Depending on the nature of finding binary trees, extreme values exist in leaf nodes or parent nodes that contain only one child node
If there is no left node, the current node is considered to be the smallest. Example: Public TreeNode<T> findMin(TreeNode<T> node){if (objects.isnull (node.getLeft())) {return node; } return findMin(node.getLeft()); }// Query the maximum value all the way to the right, if no right node, Public TreeNode<T> findMax(TreeNode<T> node){if (objects.isnull (node.getright ())) {return node; } return findMax(node.getRight()); }Copy the codeinsert
Figure 7 shows the situation of inserting Z as the right child node of F (the situation of inserting Z into the left child node is similar and no longer redundant)
Figure 8 shows the existence of the inserted node.
Public void add(T element) {if (element == null) {throw new RuntimeException(" Data cannot be null "); } TreeNode<T> node = new TreeNode<>(); node.data = element; if (Objects.isNull(root)) { root = node; return; } addImpl(root, node); }private void addImpl(TreeNode<T> root, TreeNode<T> node) { T val = root.data; T element = node.data; int sub = element.compareTo(val); If (sub == 0) {return; TreeNode<T> right = root.getright (); TreeNode<T> right = root.getright (); TreeNode<T> right = root.getright (); if (Objects.isNull(right)) { root.setRight(node); return; } addImpl(right, node); TreeNode<T> left = root.getleft (); TreeNode<T> left = root.getleft (); if (Objects.isNull(left)) { root.setLeft(node); return; } addImpl(root.getLeft(), node); }}Copy the codedelete
Due to the complexity of node deletion, let’s first take a look at the deletion maximum (minimum) to prepare for node deletion
Delete minimum
Due to the characteristic two of binary search tree (the Key of the left child node is smaller than the parent node and the Key of the right child node is larger than the parent node), the minimum value node is either a leaf node or contains the right child node
-
Minimum nodes are leaf nodes that can be removed directly
-
The minimum node has a right child, which is replaced by the parent (if the left child is also included, the current node is non-minimum)
Private TreeNode<T> deleteMin(TreeNode<T> node) {if (objects.isnull (node.getLeft())) {// There is no left child, Return node.getright (); } TreeNode<T> min = deleteMin(node.getLeft()); // Recursive left subtree node.setleft (min); return node; }Copy the codeDelete maximum value
This is similar to deleting the minimum. It just recurses to the right subtree
-
Maximum nodes are leaf nodes and can be removed directly
-
The maximum node has a left child. Replace the left child with the parent (if the right child is also included, the current node is not the maximum)
// Remove the maximum number of nodes. Public TreeNode<T> deleteMax(TreeNode<T> node) {if (objects.isnull (node.getright ())) {return node.getLeft(); } TreeNode<T> max = deleteMax(node.getRight()); node.setRight(max); return node; }Copy the codeRemove nodes
We summarize the case of node deletion as follows
-
The node to be deleted is a leaf node and can be removed directly
-
The deleted node contains only one child node (left child node or right child node). We need to replace the child node with the parent node
-
The deleted node contains two child nodes. If node E is removed directly, child nodes D and F will be lost. We need to switch our thinking from the case with two child nodes to the two cases above. Here’s how to do it. (T. Gibbard 1962)
-
We replace the deleted node with the value of the precursor node (successor node), and then delete the precursor node (successor node)
-
Precursor node: the maximum value in the left subtree of the current node
-
Successor node: The minimum value in the right subtree of the current node
Public TreeNode<T> delete(T element, TreeNode<T> node){if (objects.isnull (node)) {return null; } T val = node.data; int res = val.compareTo(element); TreeNode<T> rNode = delete(element, node.getright ()); if (res < 0) {TreeNode<T> rNode = delete(element, node.getright ()); node.setRight(rNode); } else if (res > 0) {TreeNode<T> lNode = delete(element, node.getLeft()); node.setLeft(lNode); If (objects.isnull (node.getLeft()))) {return node.getright ();} else {//node contains a child node and replaces the parent node with a child node. } if (Objects.isNull(node.getRight())) { return node.getLeft(); TreeNode<T> TMP = node; node = findMin(node.getRight()); TreeNode<T> rNode = deleteMin(tmp.getRight()); node.setRight(rNode); node.setLeft(tmp.getLeft()); } return node; }Copy the codeSo far, we have completed the binary search tree to increase, query, delete the method. We found that binary search trees were not difficult to implement and worked well in most scenarios. The performance of binary search trees is also intolerable in extreme cases.
Later we will describe an initialization that will run logarithmic in any scenario (next preview ** balanced lookup tree **)
A series of
The Inner Workings of programmers: Searching binary Trees
The Inner Workings of programmers — AVL Tree
This article is sorted out in my spare time, it is inevitable that there will be logical errors and typographical errors, please understand, and welcome you to leave a message and share with me!
More highlights: Follow us
