1. Binary search tree
**1. Definition: **Binary search tree, also called binary search tree, or binary sorting tree. Its definition is also relatively simple, it is either an empty tree or a binary tree with the following properties.
2. Properties:
(1) If the left subtree of any node is not empty, then the values of all nodes on the left subtree are less than the value of its root node;
(2) 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;
(3) The left and right subtrees of any node are also binary search trees respectively;
(4) There are no nodes with equal key values.
(5) Perform in-order traversal on the binary search tree to obtain an ordered sequence.
Figure 1 Binary search tree
As shown in the figure above, they are binary search trees in different forms. A binary search tree is a spanning tree for the data to be searched. The value of the left branch is smaller than the value of the right branch. The same idea is used when searching, starting from the root node, entering the right branch if it is larger than the node, and entering the left branch if it is smaller than the node, until the target value is found.
3. Operation: query, insert, delete
**Query:** Similar to binary search
**Insertion:** The insertion algorithm of the binary search tree is relatively simple: if the tree is empty, the root node will be generated first; if the tree is not empty, the parent node will be found according to the search algorithm, and then inserted as a leaf node. If the value already exists, the insertion will fail.
**Delete:** The deletion operation is a little more complicated. There are several situations:
(1) If you delete a leaf node, you can delete it directly; (2) If the deleted element has a child node, the child node can be moved directly to the position of the deleted element; (3) If there are two child nodes, then use in-order traversal to find the successor node of the node to be deleted, and exchange it with the node to be deleted. At this time, the position of the node to be deleted is already a leaf node and can be deleted directly.
As shown below:
Figure 2 Delete
Swap the node to be deleted with the successor node, as shown in the following figure:
Figure 3 Interchange
Delete the element to be deleted, as shown in the figure below:
Figure 4 Deletion of elements to be deleted
[Note] 1. Binary search tree also has another property, that isPerform in-order traversal on the binary search tree to obtain an ordered sequence.
2. The query complexity of the binary search tree is the same as the binary search. The time complexity of both insertion and search is O(logn), but in the worst case there will still be a time complexity of O(n). The reason is that the tree is not balanced when elements are inserted and deleted.
1. Binary balanced tree
**1. Definition: **Balanced binary tree, also known as AVL tree. There are many types of balanced binary trees. The most famous one was proposed by the former Soviet mathematicians Adelse-Velskil and Landis in 1962, and is called the AVL tree.
2. Properties:
It is an empty tree or has the following properties:
(1) The absolute value of the difference between the depths of the left and right subtrees does not exceed 1;
(2) The left and right subtrees are still balanced binary trees.
Balance factor BF = left subtree depth - right subtree depth. The balance factor of each node of a balanced binary tree can only be 1, 0, -1.
[Explanation] Since ordinary binary search trees can easily lose their "balance", in extreme cases, the binary search tree will degenerate into a linear linked list, causing the complexity of insertion and search to drop to O(n). Therefore, this is also the original intention of the balanced binary tree design. So how does a balanced binary tree maintain "balance"? According to the definition, there are two important points. One is that the absolute value of the height difference between the left and right subtrees cannot exceed 1, and the other is that the left and right subtrees are also balanced binary trees.
For example: As shown in the figure below, the left figure is a balanced binary tree with root node 10 and the height difference between the left and right subtrees is 1. In the right figure, although the height difference between the left and right subtrees of the root node is 0, the height difference between the left and right subtrees of the right subtree 15 is 2, which does not meet the definition, so the right figure is not a balanced binary tree.
Figure 5 Comparison of balanced binary trees
It can be seen that the balanced binary tree is a highly balanced binary search tree. Therefore, constructing and maintaining a balanced binary tree is much more complicated than an ordinary binary tree. In the process of building a balanced binary tree, when a new node is to be inserted, check whether the balance of the tree is destroyed due to the insertion. If so, you need to rotate to change the structure of the tree.
3. Preliminary knowledge:
Left-handed：
Figure 6 Left-hand rotation
Right-hand rotation：
Figure 7 Right-hand rotation
Different from the clockwise and counterclockwise transformation method to remember, the above two dynamic diagrams are particularly convenient to remember and understand:
(1) Left rotation is to pull the right branch of the node to the left, the right child node becomes the parent node, and the excess left child node after promotion is transferred to the right child node of the demoted node;
(2) Right rotation is the opposite, pulling the left branch of the node to the right, the left child node becomes the parent node, and the excess right child node after promotion is transferred to the left child node of the demoted node.
(3) That is, left-hand rotation means transforming to the left, and right-hand rotation means transforming to the right. Whether it is left or right rotation, the purpose of rotation is to give the node of one branch with more nodes to the other branch with fewer nodes.
For example, in the picture above, whether a binary tree is balanced or not, in the picture on the left, before the node "19" is inserted, the tree is still a balanced binary tree, but after inserting "19", the left and right subtrees of "15" lose their "balance", so At this time, the "15" node can be rotated left, so that "15" itself transfers the node to "17" as the left tree of "17", so that the left and right subtrees of the "17" node are balanced, while the "15" node has no subtrees, and the left and right are also balanced. As shown below:
Figure 8 Balance
4. Operation: query, insert, delete
**Query:** Similar to binary search
insert:Since when constructing a balanced binary tree, when there areNew node insertionWhen, it will be judged whether it is balanced after insertion, which means that it is balanced before inserting a new node, that is, the absolute value of the height difference will not exceed 1. When a new node is inserted, it may cause the tree to be unbalanced. At this time, adjustments need to be made. There are four possible situations, which are calledLeft left, left and right, right left, right right。
(1) Left-left means that in the original balanced binary tree, a new node is inserted under the left sub-tree of the node's left sub-tree;
(2) The left and right means that in the original balanced binary tree, a new node is inserted under the right subtree of the node's left subtree;
(3) The right and left means that in the original balanced binary tree, a new node is inserted under the left subtree of the node's right subtree;
(4) Right and right means that in the original balanced binary tree, a new node is inserted under the right subtree of the node's right subtree.
How to adjust the balance of the tree after inserting:
Left-left adjustment is actually relatively simple, you only need to rotate the node right;
Right and left are the same as left and right, only one rotation is needed to balance the tree, left rotation;
The same goes for the left and right sides, which require two rotations to balance the tree.
Zuozuo：
Figure 9 Left and right adjustment
**Left Left:** means that on the original balanced binary tree, a new node is inserted under the left subtree of the node's left subtree, resulting in a height difference of 2 between the left and right subtrees of the node. As shown above, the left subtree of node "10" is "7", and the left subtree of node "4" is inserted. Node "5" or "3" is inserted, causing imbalance.
**Left and left adjustment:** In fact, it is relatively simple. You only need to rotate the node to the right. As shown in the figure below, rotate the node "10" to the right:
Figure 10 Right-hand rotation
about：
Figure 11 Left and right rotation
**Left and right:** means that on the original balanced binary tree, a new node is inserted under the right subtree of the node's left subtree, resulting in a height difference of 2 between the node's left and right subtrees. As shown above, the left subtree of node "11" is "7", and the right subtree of node "9", the insertion of node "10" or "8" causes imbalance.
**Left and right adjustment:** You cannot complete the adjustment with one rotation like Zuo Zuo. We might as well try to make the left and right right-rotate the "11" node like the left and right. The result is as follows. The binary tree in the right picture is still unbalanced, and the right picture is the right and left that we will talk about next. That is, the left and right are mirror images of each other, and the left and right are also mirror images of each other.
Figure 12 Imbalance
The right and left are the same as the left and right. They only need to rotate once to adjust the balance of the tree. The left and right are the same as the right and left. They need to rotate twice to adjust the balance of the tree., so, first of all, the adjustment in the above picture is wrong. The correct adjustment method is to rotate the left and right for the first time, adjust the left and right to left and right first, and then adjust the left and right to make the binary tree balanced.
That is, first perform a left-turn on the node "7" in the above figure, so that the binary tree becomes left-left, and then perform a right-turn on the "11" node. At this time, the adjustment of the binary tree is completed, as shown below:
Figure 13 Balance
right left：
Figure 14 right and left
**Right and left:** In the original balanced binary tree, a new node is inserted under the left subtree of the right subtree of the node, resulting in a height difference of 2 between the left and right subtrees of the node. As shown above, the right subtree of node "11" is "15", and the left subtree of node "13" is inserted. Node "12" or "14" is inserted, causing imbalance.
**Right-left adjustment:** Right-left and left-right are actually mirror images of each other, so the adjustment process is reversed. First, rotate the node "15" right to make the binary tree become right-right, and then rotate the node "11" left. At this time, the adjustment of the binary tree is completed, as shown below:
Figure 15 Right and left adjustment
right right：
Figure 16 Right-right adjustment
**Right and right:** means that on the original balanced binary tree, a new node is inserted under the right subtree of the node's right subtree, resulting in a height difference of 2 between the left and right subtrees of the node. As shown above, the right subtree of node "11" is "13", and the left subtree of node "15" is inserted into node "14" or "19", causing imbalance.
**Right-right adjustment:** You only need to rotate the node left once to adjust the balance. As shown in the figure below, rotate the node "11" left.
Figure 17 Right-right adjustment
**Delete:** Deleting a binary tree node can be summed up in two judgments:
①.What type of node is being deleted?
②. Will deletion of nodes cause imbalance?
There are three types of nodes:
①.Leaf node;
②.Only the left subtree or only the right subtree;
③. There is both a left subtree and a right subtree.
Adjustments after deletion:
For these three node types, judgment 2) is introduced, sodeal withThe ideas are:
(1) When the deleted node is a leaf node, delete the node, and then start from the parent node to determine whether it is unbalanced. If there is no imbalance, then determine whether the parent node of the parent node is unbalanced, until the root node. If no imbalance is found at the root node, it is said that the tree is balanced at this time; if an imbalance is found in the intermediate process, determine what type of imbalance it is (left-left, left-right, right-left, right-right), and then make adjustments.
(2) The deleted node has only a left subtree or a right subtree. In this case, there is actually one more step than deleting a leaf node, which is to delete the node, and then replace the original node with only one left subtree or right subtree. The following steps are the same. Starting from the parent node, determine whether it is unbalanced. If there is no imbalance, then determine whether the parent node of the parent node is unbalanced, until the root node. If an imbalance is found in the intermediate process, adjustments will be made according to the type of imbalance.
(3) The deleted node has both a left subtree and a right subtree. This situation has one more step than the above, which is in-order traversal. It can find the predecessor or successor of the node to be deleted, and then swap positions with the node to be deleted, and then delete the node to be deleted. The following steps are the same. Determine whether there is an imbalance, and then make adjustments according to the type of imbalance.
【Summary】 Finally, to summarize, a balanced binary tree is a highly balanced binary tree, so the time complexity of the query is O(logN). When inserting, as mentioned above, there are 4 imbalance situations: left-left, left-right, right-left, right-right. That is, once a new node is inserted and the imbalance needs to be adjusted, it only needs to be rotated 2 times at most, so the insertion complexity is O(1) , but the balanced binary tree is not perfect, and it also has shortcomings. As can be seen from the deletion processing ideas above, when deleting a node, it may be due to imbalance, which leads to the need to start from the parent node of the deleted node and continuously backtrack to the root node. If the balanced binary tree is very high, then many nodes must be judged in the middle.