GitHub source code sharing
Wechat search: code nong StayUp
Home address: goZhuyinglong.github. IO
Source: github.com/gozhuyinglo…
1. The AVL tree
AVL (Adelson-Velskii and Landis) trees are binary search trees with equilibrium conditions, also known as balanced binary trees. The height difference between two subtrees of any node in AVL tree is at most 1, so it is also called height balanced tree.
As can be clearly seen in the figure below, the height of the left subtree of the root node of the tree on the left is 3 and the height of the right subtree is 2, which conforms to the characteristics of AVL trees. The height of the left subtree of the root node on the right is 3 and that of the right subtree is 1, which does not conform to the characteristics of AVL trees. So the tree on the left is an AVL tree and the tree on the right is not an AVL tree.
So how do you strike this balance?
The answer is to maintain balance by making simple corrections to the tree, called rotations, as nodes are inserted or removed.
2. Rotation
The rotation is divided into single rotation and double rotation.
- Single rotation is used when the height difference between the left and right subtrees is greater than 1 and the highest leaf node is “outside”.
- Double rotation is used when the height difference between the left and right subtrees is more than 1 and the highest leaf node is “inside”.
And single rotation is divided into:
- Left rotation, that is, left rotation. Left rotation is performed when the height of the right subtree is greater than that of the left subtree.
- Right rotation, that is, right rotation. When the height of the left subtree is greater than that of the right subtree, the right rotation is performed.
Double rotation is divided into:
- Left-right double rotation, that is, first to the left (left child node) and then to the right. Left-right double rotation is required when the height of the left subtree is the same as the height of the right subtree and the highest leaf node of the left subtree is the right child of its parent.
- Right-left double rotation, that is, first to the right (right child node) and then to the left. When the height of the right subtree is the same as that of the left subtree, and the highest leaf node of the right subtree is the left child of its parent, then right-left double rotation is required.
These nouns and concepts are not easy to understand, so let’s introduce them one by one through legends.
3. Rotate left
Look at the tree on the left in the figure below. This tree is a binary lookup tree, but does it meet AVL’s characteristics? It can be found that the height of the left subtree of the root node is 1, while the height of the right subtree is 3, so there are no AVL trees.
After observation, the right subtree is higher than the left subtree, and the highest leaf node is also on the right, so we use left rotation for balance.
Detailed rotation process:
- Copy the root node 4 into a new node with its left child 3 unchanged and its right child pointing to 5 (the left child of the right child of the original root node).
- If the left child of the right child of the original root node 6 points to the new node 4 and its right child remains unchanged at 7, 6 becomes the new root node.
Since the right subtree is higher than the left subtree, move the root 4 to the left and down, and move the right child node 6 to the up to become the new root, thus balancing the height of the left and right subtrees. Repeat the exercise several times using the picture above.
4. Right
Right rotation and left rotation are exactly symmetric. See the tree on the left in the figure below. The left subtree height of the binary search tree is 3 and the right subtree height is 1, which does not meet the AVL tree rotation.
Since the left subtree is higher than the right and the highest leaf node is on the left, we use the right rotation.
Detailed rotation process:
- Copy root node 7 into a new node whose right child remains 9 and whose left child points to 5 (that is, the right child of the left child of the original root node).
- Upgrade the left node of the original root node to the new root node, that is, its left subtree of 3 remains unchanged, and the right child node points to the new root node 7.
Left rotation and right rotation must be understood, or the following double rotation is more prone to vertigo!
5. Double rotation
Before introducing double rotation, take a look at the figure below. The height of the left subtree of the root node is 3 and the height of the right subtree is 9. Then, we first use the right rotation to see if the effect of balance can be achieved.
Observing the effect of right rotation does not satisfy the AVL tree characteristics. This requires the use of double rotations.
We use left-right rotation to balance the tree in the image above, first left, then right, but with a different balance point, as shown below.
Detailed rotation process:
- First, rotate the left subtree (5 nodes) of the root node to the left, and lower the height of its (5 nodes) right subtree.
- Rotate the root node to the right to achieve balance.
So in reverse, the detailed process of right-left double rotation:
- First, rotate the right subtree of the root node to lower the height of the right subtree.
- Rotate the root node to the left.
6. Code implementation
The realization of AVL tree is to add balance operation on the basis of binary search tree.
6.1 Finding the Node Height
Add height, leftHeight, and rightHeight to the Node class. If the Node is empty, the height is 0.
// The current node height
public int height(a) {
return Math.max(left == null ? 0 : left.height(), right == null ? 0 : right.height()) + 1;
}
// Height of left child node
public int leftHeight(a) {
if (left == null) {
return 0;
}
return left.height();
}
// Height of the right child node
public int rightHeight(a) {
if (right == null) {
return 0;
}
return right.height();
}
Copy the code6.2 left rotation
Add left rotation method leftRotate to the Node class.
public void leftRotate(a) {
// Move the current node down to the left to become the new left node
Node newLeftNode = new Node(element);
newLeftNode.left = left;
// Set the right child to the left subtree of the right subtree of the original root node
newLeftNode.right = right.left;
// Move the right node up to become the new root (current node)
element = right.element;
// Set the left child to the new left child (the original root)
left = newLeftNode;
right = right.right;
}
Copy the code6.3 right
Add right rotation method rightRotate to Node class.
public void rightRotate(a) {
// Move the current node down to the right to become the new right child node
Node newRightNode = new Node(element);
// Point the left child to the right child of the left subtree of the original root node
newRightNode.left = left.right;
newRightNode.right = right;
// Move the left child node up to become the new root (the current node)
element = left.element;
left = left.left;
// Set the right child node to the new right child node (the original root)
right = newRightNode;
}
Copy the code6.4 Balancing Method
Add the balance method to the AVLTree class to determine if a single or double rotation is required.
public void balance(Node node) {
if (node == null) {
return;
}
if (node.leftHeight() - node.rightHeight() > 1) {
if (node.left.rightHeight() > node.left.leftHeight()) {
node.left.leftRotate();
}
node.rightRotate();
} else if (node.rightHeight() - node.leftHeight() > 1) {
if(node.right.leftHeight() > node.right.rightHeight()) { node.right.rightHeight(); } node.leftRotate(); }}Copy the code6.5 Adding a Node
Add a node method to AVLTree class. When a node is added, call the balance method to maintain balance.
private void add(Node node, int element) {
if (node.compareTo(element) < 0) {
if (node.left == null) {
node.left = new Node(element);
} else{ add(node.left, element); }}else if (node.compareTo(element) > 0) {
if (node.right == null) {
node.right = new Node(element);
} else {
add(node.right, element);
}
}
balance(node);
}
Copy the code6.6 Deleting a Node
Add delete node method in AVLTree class. After deleting a node, call balance method to maintain balance.
private void remove(Node parentNode, Node node, int element) {
if (node == null) {
return;
}
// Find the target element first
int compareResult = node.compareTo(element);
if (compareResult < 0) {
remove(node, node.left, element);
} else if (compareResult > 0) {
remove(node, node.right, element);
} else {
// Find the target element and determine whether the node is the left or right child of the parent node
boolean isLeftOfParent = false;
if(parentNode.left ! =null && parentNode.left.compareTo(element) == 0) {
isLeftOfParent = true;
}
// Delete the target element
if (node.left == null && node.right == null) { // (1) Target element is leaf node, delete directly
if (isLeftOfParent) {
parentNode.left = null;
} else {
parentNode.right = null; }}else if(node.left ! =null&& node.right ! =null) { // (2) The target element has both left and right subtrees
// Find the right subtree minimum (leaf node) and delete it
Node minNode = findMin(node.right);
remove(minNode.element);
// Replace the minimum value with the target node to be deleted
minNode.left = node.left;
minNode.right = node.right;
if (isLeftOfParent) {
parentNode.left = minNode;
} else{ parentNode.right = minNode; }}else { // (3) The target element has only left or right subtrees
if(isLeftOfParent) { parentNode.left = node.left ! =null ? node.left : node.right;
} else{ parentNode.right = node.left ! =null ? node.left : node.right;
}
}
}
balance(node);
}
Copy the code6.7 Complete Code
Due to the length of the complete code, it is not shown here. It can be accessed through GitHub at the following address:
Github.com/gozhuyinglo…
7. To summarize
AVL tree is a binary search tree whose absolute value of the balance factor (the height difference between the left and right subtrees) is less than 1, which can be balanced by single rotation or double rotation.