This article is absolutely dry, eating time of about 8 minutes, it is recommended to fine taste!
primers
Last time I introduced what binary search tree is, but due to the instability of the query efficiency of binary search tree, it is rarely used in the actual scene, so our great predecessors improved the binary search tree and invented AVL tree.
AVL tree is a self-balanced binary search tree, because the absolute value of the height difference between the left and right subtrees of any node of AVL tree is not more than 1, so AVL tree is also called height balanced tree.
AVL tree is essentially a binary search tree with balance conditions, it meets the basic characteristics of binary search tree, so this paper mainly introduces how AVL tree self-balance, that is, to understand its rotation process.
Binary search tree features forget friends can read the previous article: fix binary search tree, 9 map is enough! At the same time, I will give you the basic properties to review again:
-
If its left subtree is not empty, then all nodes in the left subtree are less than the root node.
-
If its right subtree is not empty, then all nodes in the right subtree are greater than the root node.
-
Its left and right subtrees are binary search trees respectively.
Equilibrium condition: The absolute value of the height difference between the left and right subtrees of each node is not more than 1.
The absolute value of the height difference between the left and right subtrees of each node is also called the balance factor.
AVL tree rotation behavior is generally in the process of insertion and deletion, because the rotation in the process of insertion is more simple and intuitive than the rotation in the process of deletion, so I give you a diagram of the AVL tree insertion process.
Insertion process
We start with an empty tree with no nodes, so we can just insert a node from the data, for example, the first data to be inserted is 18.
After the first node is inserted, start inserting the second node, assuming the value is 20.
Insert the third node and the data is 14.
Data of the fourth node is 16. Compare from the root node position and find the corresponding insertion position of 16.
The fifth data to be inserted is 12. Again, start from the root node of the tree and search down to the corresponding position according to the characteristics of the binary search tree.
At this time, a data 11 is inserted. According to the nature of the search tree, it is not difficult for us to find its corresponding insertion position. However, the balance condition of AVL tree cannot be satisfied after the node 11 is inserted.
Now the left subtree of 18 is taller, the right subtree is shorter, so we should do a single right spin, so the single right spin gets the left subtree lifted, the right subtree pulled down, so the left subtree gets shorter, the right subtree gets taller, so after one spin, we’re in equilibrium again.
A simple analysis of the rotation process in the image above: ** Since the left subtree is lifted, 14 becomes the new root node, while 18 is pulled to the position of the right subtree of 14. Since the node 14 originally had a right child node 16, the position of 18 and 16 after rotation conflicts. However, since 16 is less than 18, ** so at this time, according to the characteristics of binary search tree, Adjust 16 to 18 in the left subtree, because of the rotation after 18 left subtree is no nodes of this node, so 16 can directly on the left side of the 18, if the left subtree of the 18 nodes, then also need according to the properties of the binary search tree to compare 16 and 18 in the left subtree node size, until the new location is determined.
Through the above analysis we can know that: if the newly inserted node is inserted into the root node to the left side of the left subtree, needs a right single, we generally will be simple to left, left the first left said is higher left subtree left, second left, said the new node is inserted into the higher to the left of the left subtree.
Analysis over left, left, I think friends is not difficult to launch the right right (first right say is high right subtree is right, the second right is the right of the new node is inserted into the higher right subtree), is a single, left here is not right is the right step by step analysis, because it is symmetrical left and the left. Draw a picture for everyone, smart you can learn at a glance!
Now two kinds of single case has been finished, left right left and right, left two single, but don’t panic, because twin twist simple than your imagination, and similarly, twin twist is two kinds of symmetry, in fact we only have a situation need to analyze, so, come on, make sense of the word, the interview was completely don’t panic!
Twin twist
We assume that the current AVL tree looks like the following figure.
At this time, we insert a new node with data of 15. According to the nature of the search tree, we find the corresponding position of 15 and insert it, as shown in the figure
At this time, we calculated the balance factor of each node again, and found that the balance factor of root node 18 was 2, exceeding 1, which did not meet the balance condition, so it needed to be rotated.
We will just need to be single left, the left and right now this situation together contrast, clever you must have found that the current situation compared to the left to the left, just different from the position of the insertion, left, left is inserted into the node in the left subtree of the left side of the root node 18 higher, and this situation into the current node is on the right side of the 18 higher left subtree root node, We call that the left and right case.
So you’re probably looking at this and thinking, well, this isn’t just like left, left, right. Is it really so? Let’s do a single right spin and see what happens.
Simple analysis of the right monogyration: ** node 14 is lifted up to become the new root node, 18 is pulled down to become the right subtree of the root node, and since the current root node 14 originally has a right subtree 16, the position of 18 and 16 conflict. After comparing the size of 18 and 16, it is found that 18 is larger than 16. According to the nature of the search tree, the subtree with the root node 16 is adjusted to the left subtree of 18. Because the left subtree of 18 is currently empty, the subtree with the root of 16 is directly hung to the left of 18. If the left subtree of 18 is not empty, you need to continue the comparison based on the properties of search trees until an appropriate mount position is found.
Since one right spin doesn’t work, what should we do? The answer is to do a double spin, a double spin can be split into two single spins, and for the current unbalanced condition, we can do a left single spin, then a right single spin, and then we can adjust the tree to be an AVL tree that satisfies the equilibrium condition, so without further ado, I’ll just illustrate it.
Simple analysis of left and right double rotation: Subtree of the dashed frame left first single, 16 lift into a subtree of the new root, with 14 as the root node of the subtree drop-down, adjust to 16 left subtree, now found left subtree is 15, 16 and 14 this tree KeZi conflict, so adjustments according to the rules of the search tree, will be 15 mount to 14 for root section ideas right subtree of a tree, so as to complete a single screw on the left, After that, the whole tree is rotated right once again. Node 16 is lifted up to become the new root node, and node 18 is pulled down to become the right subtree of the root node. Since there was no right subtree at 16 before, the subtree with root node 18 is directly mounted to the right subtree at 16 to complete the right rotation.
Similarly, I will not give you the analysis of the symmetry of the left and right cases, or I will give you the diagram, I believe that you will be smart to see!
So far, I will be four of AVL tree rotation is to introduce again, think of it, in fact not only need to rotate the four conditions, technically there are eight kinds of conditions need to rotate, introduce the situation left left before, for example, we say that the left left is to insert the new node to the root node to the left side of the left subtree, This is actually a segment on the left and there are two kinds of circumstances, but in both cases can synthesize a kind of actual situation, that is, when the new node is inserted into the left can be a father left child node, it can also be a father it right child node, then it is equivalent to two cases, draw a simple picture have a look at it.
Is above, so each new insert node can is it his father left and right child nodes, it depends on the size of the new insert data, such as left 11 is 12-13 is 12 children right, both of which belong to the left, left, that is to say they are essentially the same, all 18 is higher in the node to the left of the left subtree.
So it looks like each of these four rotations can technically be divided into one more case, eight cases.
The latter
Emmm… So it seems that AVL tree does solve the defect of unbalanced binary search tree and makes up for the defect of unstable performance. But if you think about it carefully, the efficiency of AVL tree is not very good. What we say here is not query efficiency, but insert and delete efficiency. Then it takes a lot of time to rotate, and my god, it’s too hard!
But clever predecessors have long as we want to more conducive to actual use of the search tree, in the real scene AVL tree and binary search tree, basically can’t use, we need to tell this type of binary search tree is application, we often believe that informed you must have guessed its name, yes, that’s it, the well-known red and black tree! We’ll take him next time!
I am uneducated, if there is any mistake, but also hope you forgive me, not stingy advice!
Like this article little xia people, welcome to pay attention to the public number Lei Zi’s programming rivers and rivers, practice more martial arts secrets.
One key three even is the contemporary virtue of the Chinese nation!