Binary search tree, also known as ordered binary search tree, has a characteristic that the node value of the left subtree is smaller than the parent node value, and the node value of the right subtree is larger than the parent node value. Based on such characteristics, when we are looking for a node, we can adopt the idea of binary search to find the node quickly. The expected time complexity is O(log n), but it has the worst case.
For example, if you enter an array [9,7,5,3,1] and insert each node to satisfy the rules of a binary search tree, the binary tree will degenerate into a linear table with O(N) time to find the elements.
In this case, we derive a balanced binary search tree, whose height difference between left and right subtrees of each node is no more than 1, and which can complete the insertion, search and deletion operations in O(log n). There are many analogies of balanced binary search tree species, AVL tree is one of them, but it is the earliest self-balanced binary search tree invented.
An AVL tree is also called a height balanced tree because it has one more feature than a binary search tree: the height difference between the left and right subtrees of any node is at most 1. If you go to the competition in the future, you can change the maximum height difference according to the data, or even make the height difference several times.
Calculate the height and balance factors
The compute height starts from the leaf node, and the default starting height is 1. Then calculate the height of the parent node of the leaf node, compare the height of the left and right subtrees, take the maximum and add 1 to get the height of the node. And so on until you get to the top of the tree.
Calculating the balance factor is the same as calculating the height from the leaf node and then from the parent node. The formula for a node’s balance factor is the height of its left subtree minus the height of its right subtree, or sometimes the other way around.
Nodes with equilibrium factor -1, 0, or 1 are said to be balanced, i.e. the absolute value of the equilibrium factor of the equilibrium node is not expected to be greater than the maximum height difference. Nodes with a balance factor of -2 or 2 are considered unbalanced, meaning that the tree needs to be readjusted. The maximum absolute value of the balance factor cannot exceed the maximum height difference +1, indicating that the balance factor of any node of this number will not appear -3 or 3.
If the height difference is set to a maximum of 2, then the balance factor will appear -3 or 3, and this node is also unbalanced and needs to be rotated. A balance factor of -2, -1, 0, 1 or 2 is said to be balanced.
animation
Algorithm animation video address
Code
Rotate left and rotate right
The unbalanced nodes of AVL tree are divided into left rotation and right rotation, but there are four cases: LL, RR, LR and RL. Where L is left rotation and R is right rotation. How to take which case to use depends on where the node is inserted.
If the node is inserted into a T2 subtree, T1, T2, T3, and T4 all represent a subtree. Insert a node into T2, increase the height of the subtree by 1, and calculate the balance factor of the parent node. If the node is balanced, the height of the node is updated. Then calculate the balance factor of the parent node, then judge whether it is balanced, if it is balanced, update the height, until it is not balanced, then rotate the operation.
As shown in the figure above, node 9 is unbalanced and needs to be rotated. So how do you do that?
The height of the left subtree of node 5 is increased by 1, causing the balance factor of node 5 to change from 0 to 1. In order to change the balance factor of node 5 from 1 to 0, it is expected that the height of the right subtree of node 5 can be increased by 1. Therefore, the right rotation operation is performed on the parent node 9 of node 5 to readjust the balance factor and restore the balance factor of node 5 to 0.
If this is the case, you can’t just rotate right. As you can see below, the insertion of a node occurs in the right subtree of node 3. The balance factor of node 3 changes from 0 to -1, and the height of the left subtree of node 3 should hopefully be higher. So rotate node 3 left.
After the left rotation of node 3, the height and balance factor of the corresponding node are updated. In the figure below, it is found that the balance factor of node 5 changes from -1 to 1. In order to make 1 become 0, it is hoped that the height of the right subtree of node 5 can be higher, so node 9 is rotated right.
The operation of LR rotation is shown in the following figure. The balance factor of node 5 has been restored to 0, and node 9 has become balanced from the initial imbalance.
animation
Algorithm animation video address
Code
Remove nodes
Like binary search tree, the deletion operation of AVL tree can also be divided into the case that the right subtree of the node to be deleted is empty, the left subtree is empty, and the left and right subtrees are not empty.
How to update height and balance factor, and how to adjust unbalanced nodes to balance? Same as inserting a node.
Inserting a node computes the height from the leaf node, then to the parent node to calculate the balance factor based on the height of the left and right subtrees, then updates the height to the last parent node, and then to the vertices of the entire binary tree.
Deleting a node can be considered to include inserting nodes, because deleting a node pulls up a node from the left and right subtrees. Instead of recalculating the height from the leaf nodes, the height is then updated from the left and right subtrees and the balance factor is calculated.
animation
Algorithm animation video address
Code
Long click on the qr code below to follow the public account, “algorithm for all” continue to update the algorithm
