“This is the 13th day of my participation in the Gwen Challenge in November. Check out the details: The Last Gwen Challenge in 2021”
Binary search tree
A binary search tree must be a binary tree. If the left and right subtrees of the binary search tree exist, the left and right subtrees of the node in the binary search tree are both smaller than the value of the node, and the right subtrees are also smaller than the node
The following is an example:
For example, the time complexity of searching for the corresponding value in the figure above is O(log2(n)), but the insertion of various segments of the binary search tree may degenerate into a linked list. For example, if 17, 20, 30 and 45 are inserted in the figure above, the following figure will be generated
If you keep doing this, and then you look up the value, the time is going to be zeroO(n), so the balanced binary tree is introduced
AVL Tree(Balanced binary Tree)
Balanced binary search trees: the absolute value of the difference between the depth of the left and right subtrees cannot exceed 1. For example, the depth of the right subtree is 4, and the depth of the left subtree is 3 or 5.
If we insert -1, -3 in the first picture, it becomes the following
In the figure above, we can see that node 1(left subtree of the first unbalance) has a depth of 2, the right subtree has a depth of 0, and the depth difference is 2. This type of imbalance is generally called LL (the node causing the imbalance is -3, left of the left subtree). So we need to adjust, right rotation, to the picture below
If we insert 7,9 in the first picture, it becomes the following
In the figure above, we can see that the depth of the left subtree of node 6(the first imbalance) is 0, the depth of the right subtree is 2, and the depth difference is 2. This type of imbalance is generally called RR (the node causing the imbalance is 9, the right side of the right subtree). So we need to adjust, which is left rotation, to the following figure
If we insert -1, 0 in the first picture, it becomes the following
In the figure above, we can see that the depth of the left subtree of node 1(the first unbalance) is 2, the depth of the right subtree is 0, and the depth difference is 2, which is generally called LR (the node causing the unbalance is 0, on the right side of the left subtree) type imbalance. Therefore, we need to adjust, that is, first the leaf node rotates left around the middle node, then the unbalanced node rotates right around the middle node after the last rotation, as shown in the following figure
If we insert 9,7 in the first picture, it becomes the following
In the figure above, we can see that the depth of the left subtree of node 6(the first imbalance) is 0, the depth of the right subtree is 2, and the depth difference is 2, which is generally called RL (the node causing the imbalance is 9, the left of the right subtree) type imbalance. Therefore, we need to adjust, namely, first the leaf node rotates right around the middle node, then the unbalanced node rotates left around the middle node after the last rotation, as shown in the following figure
These processes are LL (dextral), RR(left), LR (left), RL (right)
The binary balanced tree can keep the search at O(log2(n)), but if you insert too much, you may cause multiple balance adjustments, which is also very time-consuming.