This is the 5th day of my participation in the August More Text Challenge
An overview of
AVL tree is actually evolved from binary search tree. Here we briefly review the concepts related to binary search trees.
For binary search trees we have the following definition
-
The value of any node is greater than the value of all nodes in its left subtreeCopy the code -
The value of any node is less than the value of all nodes in its right subtreeCopy the code
Then we define it recursively, requiring that all the left and right subtrees in the tree are also binary search trees. The graph shows a typical binary search tree.
Problems faced by balanced binary trees:
The biggest characteristic of binary search tree is that it can complete the information query operation within O () complexity in the best case, but it may face the following situation in the worst case:
If the given data information is given in the form of: 2,4,5,7,8,9,11, then the convenient tree will degenerate into a single linked list, which reduces the query efficiency. Therefore, it is necessary to have a mechanism to avoid the degradation of the tree into a single linked list as far as possible. At this time, the concept of AVL tree is proposed.
AVL tree adds a new restriction on the basis of the original binary search tree: that is, the absolute value of the height difference between the left and right subtrees of each node is not more than 1.
When the height difference is greater than 1, we need to perform a rotation operation to prevent the search tree from degenerated into a single linked list. Generally speaking, there are LL,LR,RR,RL and other conditions that lead to imbalance.
Rotation operation
Before we analyze the adjustment, we need to distinguish one concept: RR and LL refer to the situation when the tree is out of balance, not rotated. Many people tend to confuse disequilibrium with rotation, thinking that when LL disequilibrium occurs, they rotate to the left, which is a wrong idea.
The overall rotation is reviewed at the end of the article to reinforce your memory of AVL tree rotation.
All kinds of imbalances
LL situation
When we insert a new node into the left subtree of the left subtree of a node, the tree becomes unbalanced, which is called LL. We need to rotate it to the right to balance it.
When the LL case occurs we need to rebalance the search tree by rotating it right. The rotation process is as follows:
It can be easily seen from the figure that dextral rotation adjustment under the condition of LL imbalance mainly involves the following key steps:
1. Point the left pointer of the unbalanced node to the right subtree of the left subtree of the current node.
2. Promote the left subtree of the current unbalanced node to the parent node, and the unbalanced node to the right subtree.
As shown in the figure, the left subtree B of A is promoted to the parent node, and the information of A as the right subtree node of B is adjusted. \color{blue} As shown in the figure: the left subtree B of A is promoted as the parent node, and the information of A as the right subtree node of B is adjusted. As shown in the figure, the left subtree B of A is promoted to the parent node, and the information of A as the right subtree node of B is adjusted.
The RR situation
When we insert a new node into the right subtree of the right subtree of a node, the tree becomes unbalanced. This case is called LL. We need to rotate it to the left to balance it
Rotation of RR case
1. Point the right pointer of the unbalanced node to the left subtree of the right subtree of the current node.
As shown in the figure, the current unbalanced node is A, and the → pointer points to the left subtree information of node B when adjusting the current unbalanced node is A, the → pointer points to the left subtree information of node B as shown in the figure: The current unbalanced node is A, at this point, the → pointer points to the left subtree information of node B first
2. Promote the right subtree of the current unbalanced node to the parent node, and the unbalanced node to the left subtree node.
As shown in the figure, the right subtree B of A is promoted to the parent node, and the information of A as the left subtree node of B is adjusted. \color{green} As shown in the figure: the right subtree B of A is promoted to the parent node, and the information of A as the left subtree of B is adjusted. As shown in the figure, the right subtree B of A is promoted to the parent node, and the information of A as the left subtree node of B is adjusted.
After the above analysis, we understand the specific operation details of left rotation and right rotation, which are necessary skills to deal with LR and RL cases.
LR situation
LR imbalance occurs when we insert nodes into the right subtree of the left subtree of a node
In this case we need to rotate twice, first through a right spin, then through a left spin.
RL situation
RL imbalance occurs when we insert nodes into the left subtree of the right subtree of a node.
In this case we need to do two rotations, first one left, then one right
The sample code
/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode() {} * TreeNode(int val) { this.val = val; } * TreeNode(int val, TreeNode left, TreeNode right) { * this.val = val; * this.left = left; * this.right = right; *} *} */
public class Solution{
// rotation in LL case
private TreeNode leftleft(TreeNode root) {
TreeNode newRoot = root.left;
root.left = newRoot.right;
newRoot.right = root;
return newRoot;
}
// Rotation in RR
private TreeNode rightright(TreeNode root) {
TreeNode newRoot = root.right;
root.right = newRoot.left;
newRoot.left = root;
return newRoot;
}
// in the case of LR
private TreeNode leftRight(TreeNode root) {
root.left = rightright(root.left);
return leftleft(root);
}
/ / RL
private TreeNode rightleft(TreeNode root) {
root.right = leftleft(root.right);
returnrightright(root); }}Copy the code