One: What is AVL tree?
In my last article, binary search trees and binary Search methods, I described binary search trees as data structures in detail. The biggest problem with binary search trees is that they are not a balanced binary tree.
In the extreme case of given data, such as adding elements from an incrementing array to a binary search tree, the binary search tree is reduced to a linked list.
To solve this problem of binary search trees, two former Soviet computer scientists Georgy Adelson-Velsky and Evgenii Landis invented a self-balancing binary search tree. This data structure is named after the initials of the two scientists, namely: AVL tree.
So let’s review again what is a balanced binary tree?
First, the balanced binary tree must be a binary search tree. It is either an empty tree, or the absolute value of the difference between the height of the left subtree and the height of the right subtree (alias: balance factor) is no more than 1, and both the left and right subtrees of a balanced binary tree are balanced binary trees.
Next, we will explore how AVL tree, a data structure, can be self-balanced on the basis of binary search trees.
Two: realization of AVL tree
1. Node height and balance factor
How are AVL trees self-balanced?
If AVL wants to satisfy this property of balanced binary tree, it must ensure that the absolute value of balance factor of all nodes does not exceed 1. Therefore, THE AVL tree can maintain self-balance, which is actually to adjust the structure of the tree by detecting the balance factor of nodes when the structure of the tree changes (adding or deleting nodes to the AVL).
The node of the AVL tree must be able to represent the height of the current node in addition to storing the references of the left and right children and its own value.
Therefore, the Node class of AVL tree is designed as follows:
public class Node<E extends Comparable<E>> {
public E e;
public Node left;
public Node right;
public int height;
public Node(E e) {
this.e = e;
left = null;
right = null;
height = 1; }}Copy the codeThen, in our AVLTree class, we can design two methods.
The first method is to get the height of the current node:
/** * Returns the height of node **@param node
* @return* /
private int getHeight(Node node) {
if (node == null)
return 0;
return node.height;
}
Copy the codeThe second is to get the balance factor of the current node: getBalanceFactor:
/** * Get the balance factor of node **@param node
* @return* /
private int getBalanceFactor(Node node) {
if (node == null)
return 0;
return getHeight(node.left) - getHeight(node.right);
}
Copy the code2. Add elements to the AVL tree
Let’s start by reviewing the logic for adding elements to a binary search tree:
If the root node of the current binary search tree is empty, the newly inserted node becomes the root node.
If the root node of the current binary search tree is not empty, the root is used as the node for the current comparison: the newly inserted node is compared with the current node; If the value is smaller than the current node, “go left”, if the value is larger than the current node, “go right”, and then let the node at the next level continue as the current comparison node until it reaches the insertion position.
The following figure shows the process of adding node “28” to the current binary search tree:
The Java code is as follows:
/ * * *@paramE adds a new element */ to the binary search tree
public void add(E e) {
root = add(e, root);
}
/ * * *@paramE searches the binary tree for the newly inserted node *@paramNode Node of the current comparison *@returnReturns the root node of the binary search tree */
private Node add(E e, Node node) {
if (node == null) {
size++;
return new Node(e);
}
if (e.compareTo((E) node.e) < 0) {
node.left = add(e, node.left);
} else if (e.compareTo((E) node.e) > 0) {
node.right = add(e, node.right);
}
return node;
}
Copy the codeAdding elements to an AVL tree is not so simple.
For adding a node to an AVL tree, in addition to ensuring the property of a binary search tree (each node of the binary search tree is greater than all the nodes of the left subtree and less than all the nodes of the right subtree), we also ensure that the property of a balanced binary tree is maintained.
Let’s think about it. If the current AVL tree is balanced, what would make the AVL tree unbalanced? In fact, there are no more than the following four:
The first case: the inserted element is to the left of the left subtree of the unbalanced node
We inserted element “4” into the current AVL tree, causing the balance factor of node “12” to be changed to 2, resulting in an imbalance.
This happens when the balance factor of the current node (” 12 “) is greater than 1 and the balance factor of the left subtree of the current node is greater than or equal to 0. The expression can be expressed as:
getBalanceFactor(node) > 1 && getBalanceFactor(node.left) >= 0
Copy the codeThe second case: the inserted element is to the right of the right subtree of the unbalanced node
We inserted element “18” into the current AVL tree, causing the balance factor of node “12” to change to -2, resulting in an imbalance.
This happens when the balance factor of the current node (” 12 “) is less than -1 and the balance factor of the right subtree of the current node is less than or equal to 0. The expression can be expressed as:
getBalanceFactor(node) < -1 && getBalanceFactor(node.right) <= 0
Copy the codeThird case: the inserted element is to the right of the left subtree of the unbalanced node
We inserted element “10” into the current AVL tree, causing the balance factor of node “12” to change to 2, resulting in an imbalance.
This happens when the balance factor of the current node (” 12 “) is greater than 1 and the balance factor of the left subtree of the current node is less than 0. The expression can be expressed as follows:
getBalanceFactor(node) > 1 && getBalanceFactor(node.left) < 0
Copy the codeFourth case: the inserted element is to the left of the right subtree of the unbalanced node
We inserted element “14” into the current AVL tree, causing the balance factor of node “12” to change to -2, resulting in an imbalance.
This happens when the balance factor of the current node (” 12 “) is less than -1 and the balance factor of the right subtree of the current node is greater than 0. The expression can be expressed as follows:
getBalanceFactor(node) < -1 && getBalanceFactor(node.right) > 0
Copy the codeLeft and right rotation
We already know that adding elements to an AVL tree can lead to an imbalance in these four situations, so how do we balance the structure of the current tree?
For the first case, we need to use the dextral operation:
The dextral operation is shown in the figure above. The so-called right-handed rotation refers to rotating the unbalanced node “Y” clockwise so that the structure on the left in the figure above becomes the structure on the right. In this case, the tree on the right satisfies the properties of both binary search tree and balanced binary tree.
The proof is as follows:
The structure on the left is a binary search tree, which satisfies T1
Let the maximum height of T1T1T1 and T2T2T2 be HHH, so the height of node ZZZ is H + 1H + 1H +1. Node XXX is also balanced, and its balance factor is greater than or equal to 0 and less than or equal to 1. Therefore, the height of T3T3T3 is either H + 1H + 1H +1 or HHH, and the height of XXX is expressed as H +2h+2h+2; Yyy node is unbalanced, and its balance factor must be 2, so the height of T4T4T4 is HHH.
Then, after the structure on the left becomes the structure on the right through dextral operation, the height of ZZZ is H + 1H + 1H +1, the height of YYy is H +2h+ 2H +2, and the height difference between the left and right subtrees of XXX is 1. Therefore, it can be proved that the structure on the right is not only a binary search tree through dextral operation, It’s also a balanced binary tree.
The Java code for the right-handed operation is as follows:
/ right: * * * * * * y x x T4 z / \ \ * y * / \ = = = = = = = = > / \ \ * z T3 T1 T2, T3, T4 * \ * T1 / T2 * /
private Node rightRotate(Node y){
Node x = y.left;
Node T3 = x.right;
x.right = y;
y.left = T3;
/ / update the height
y.height = Math.max(getHeight(y.left),getHeight(y.right)) + 1;
x.height = Math.max(getHeight(x.left),getHeight(x.right)) + 1;
return x;
}
Copy the codeSimilarly, for the second case, we need to use the left-handed operation:
The left-handed operation is shown in the figure above. The so-called left-handedness refers to rotating the unbalanced node “Y” counterclockwise so that the structure on the left in the figure above becomes the structure on the right. In this case, the tree on the right satisfies the properties of both binary search tree and balanced binary tree.
Left-handedness proves to be the same as right-handedness, and I won’t go over it.
The left-handed Java code looks like this:
/ left-handed: * * * * * * x/y \ / * / \ \ * T4 x y z = = = = = = = = > / \ \ * T3, T4 T3 T1 T2 * z \ * T1 / T2 * /
private Node leftRotate(Node y){
Node x = y.right;
Node T3 = x.left;
x.left = y;
y.right = T3;
/ / update the height
y.height = Math.max(getHeight(y.left),getHeight(y.right)) + 1;
x.height = Math.max(getHeight(x.left),getHeight(x.right)) + 1;
return x;
}
Copy the codeFor the third case, we need to rotate the left child of the unbalanced node to the left first, and then rotate the unbalanced node to the right, so that the structure of the whole tree meets the properties of both binary search tree and balanced binary tree:
Similarly, for the fourth case, we need to rotate the right child of the unbalanced node node once, and then rotate the unbalanced node node node to the left, as shown in the diagram below:
The complete code for adding elements to the AVL tree
Through the above analysis, we have already known which situations will cause the AVL tree to be unbalanced when adding elements to the AVL tree, and how to solve these unbalanced situations.
The Java code for adding elements to the AVL tree looks like this:
/ * * *@paramE Adds a new element to AVL */
public void add(E e) {
root = add(e, root);
}
/ * * *@paramE Newly inserted node * into AVL@paramNode Node of the current comparison *@returnReturns the root of AVL */
private Node add(E e, Node node) {
if (node == null) {
size++;
return new Node(e);
}
if (e.compareTo((E) node.e) < 0) {
node.left = add(e, node.left);
} else if (e.compareTo((E) node.e) > 0) {
node.right = add(e, node.right);
}
/ / update the height
node.height = 1 + Math.max(getHeight(node.left), getHeight(node.right));
// Calculate the balance factor
int balanceFactor = getBalanceFactor(node);
// Balance maintenance
// LL
if (balanceFactor > 1 && getBalanceFactor(node.left) >= 0)
return rightRotate(node);
// RR
if(balanceFactor < -1 && getBalanceFactor(node.right) <= 0)
return leftRotate(node);
// LR
if(balanceFactor > 1 && getBalanceFactor(node.left) < 0) {
node.left = leftRotate(node.left);
return rightRotate(node);
}
// RL
if(balanceFactor < -1 && getBalanceFactor(node.right) > 0) {
node.right = rightRotate(node.right);
return leftRotate(node);
}
return node;
}
Copy the code3. Delete elements from the AVL tree
In addition to add elements to the AVL tree will lead to changes in the structure of the tree, remove elements also makes the structure change of the AVL tree, as long as it is a tree structure changes, it may appear uneven node, so delete node in a binary search tree, on the basis of the code, we can realize the balance will be amended.
Let’s review the operation of removing a node from a binary search tree:
Removing an element from a binary search tree falls into the following categories:
In the first case, we delete only the left subtree and no right subtree.
Then we just need to replace the deleted node with the left child of the deleted node.
In the second case, we delete only the right subtree and no left subtree.
All we need to do is replace the deleted node with the child to the right.
The third case is that the node we delete has both left and right subtrees.
In this case, we use the Hibbard Deletion algorithm. If we want to delete a node that has both left and right subtrees, we first need to find the successors of the node to be deleted.
For a binary search tree, the successor node of the node to be deleted is the “leftmost” node in the right subtree of the node. The deletion operation is completed by replacing the successor node with the node to be deleted.
The complete Java code for removing an element from a binary search tree is as follows:
public void remove(E e) {
root = remove(e, root);
}
private Node remove(E e, Node node) {
if (node == null) {
return null;
}
if (e.compareTo((E) node.e) < 0) {
node.left = remove(e, node.left);
return node;
} else if (e.compareTo((E) node.e) > 0) {
node.right = remove(e, node.right);
return node;
} else {
if (node.left == null) {
Node rightNode = node.right;
node.right = null;
size--;
return rightNode;
}
if (node.right == null) {
Node leftNode = node.left;
node.left = null;
size--;
return leftNode;
}
// Hibbard Deletion
Node successor = minimum(node.right);
Node right = removeMin(node.right);
Node left = node.left;
successor.left = left;
successor.right = right;
node.left = null;
node.right = null;
returnsuccessor; }}Copy the codeFor the method of deleting nodes in AVL tree, we only need to add the self-balancing part to the method of deleting nodes in binary search tree. This section is essentially the same as adding elements to an AVL tree to maintain self-balance.
The Java code for deleting a node from the AVL tree is as follows:
public void remove(E e) {
root = remove(e, root);
}
private Node remove(E e, Node node) {
if (node == null)
return null;
Node retNode;
if (e.compareTo((E) node.e) < 0) {
node.left = remove(e, node.left);
retNode = node;
} else if (e.compareTo((E) node.e) > 0) {
node.right = remove(e, node.right);
retNode = node;
} else {
// The left subtree of the node to be deleted is empty
if (node.left == null) {
Node rightNode = node.right;
node.right = null;
size--;
retNode = rightNode;
}
// The right subtree of the node to be deleted is empty
else if (node.right == null) {
Node leftNode = node.left;
node.left = null;
size--;
retNode = leftNode;
}
// The left and right subtrees of the node to be deleted are not empty
else {// Hibbard Deletion
Node successor = minimum(node.right);
Node right = remove((E) node.right, successor);
Node left = node.left;
successor.left = left;
successor.right = right;
node.left = null;
node.right = null; retNode = successor; }}if(retNode == null)
return null;
/ / update the height
retNode.height = 1 + Math.max(getHeight(retNode.left), getHeight(retNode.right));
// Calculate the balance factor
int balanceFactor = getBalanceFactor(retNode);
// Balance maintenance
// LL
if (balanceFactor > 1 && getBalanceFactor(retNode.left) >= 0)
return rightRotate(retNode);
// RR
if(balanceFactor < -1 && getBalanceFactor(retNode.right) <= 0)
return leftRotate(retNode);
// LR
if(balanceFactor > 1 && getBalanceFactor(retNode.left) < 0) {
retNode.left = leftRotate(retNode.left);
return rightRotate(retNode);
}
// RL
if(balanceFactor < -1 && getBalanceFactor(retNode.right) > 0) {
retNode.right = rightRotate(retNode.right);
return leftRotate(retNode);
}
return retNode;
}
Copy the codeThree: AVL tree and binary search tree performance test
Before completing the AVL tree performance test, we need two verification methods, the first is to verify that the current AVL tree meets the characteristics of binary search tree, the second is to verify that the current AVL tree is a balanced binary tree.
The implementation of these two methods is also very simple:
/** * Verify that the current AVL tree meets the binary search tree feature **@return* /
public boolean isBST(a) {
ArrayList<E> list = new ArrayList<>();
inOrder(root, list);
for (int i = 1; i < list.size(); i++)
if (list.get(i - 1).compareTo(list.get(i)) > 0)
return false;
return true;
}
/ * * *@paramNode traverses the AVL */ root of node
private void inOrder(Node node, List<E> list) {
if (node == null) {
return;
}
inOrder(node.left, list);
list.add((E) node.e);
inOrder(node.right, list);
}
/** * Verify that the current binary tree is a balanced binary tree **@return* /
public boolean isBalanced(a) {
return isBalanced(root);
}
/** * Verify that the current binary tree is a balanced binary tree **@param node
* @return* /
private boolean isBalanced(Node node) {
if (node == null)
return true;
int balanceFactor = getBalanceFactor(node);
if (Math.abs(balanceFactor) > 1)
return false;
return isBalanced(node.left) && isBalanced(node.right);
}
Copy the codeOur performance test code is as follows:
class AVLTreeTest {
@Test
void AVLAndBSTPerformanceTest(a) {
int[] testArr = new int[20000];
for (int i = 0; i < testArr.length; i++)
testArr[i] = i;
testBst(testArr);
testAvl(testArr);
}
@Test
void AVLTest(a){
AVLTree<Integer> avl = new AVLTree<>();
for (int i = 0; i < 1000; i++){
avl.add(i);
if(! avl.isBalanced() || ! avl.isBST())throw new RuntimeException("error!");
}
for(int i = 0; i < 1000; i++){
avl.remove(i);
if(! avl.isBalanced() || ! avl.isBST())throw new RuntimeException("error!");
}
System.out.println("correct!");
}
private void testBst(int[] testArr) {
BST<Integer> bst = new BST<>();
long start = System.nanoTime();
for (int i = 0; i < testArr.length; i++)
bst.add(i);
for (int i = 0; i < testArr.length; i++)
if(! bst.contains(i))throw new RuntimeException("error");
long end = System.nanoTime();
System.out.println("BST : " + (end - start) / 1000000000.0 + " s");
}
private void testAvl(int[] testArr) {
AVLTree<Integer> avl = new AVLTree<>();
long start = System.nanoTime();
for (int i = 0; i < testArr.length; i++)
avl.add(i);
for (int i = 0; i < testArr.length; i++)
if(! avl.contains(i))throw new RuntimeException("error");
long end = System.nanoTime();
System.out.println("AVL : " + (end - start) / 1000000000.0 + " s"); }}Copy the codeOur performance test was very simple. We first initialized a monotonically increasing array with a capacity of 20000, and then added all the elements of the array to the binary search tree and AVL tree in turn. After all the elements were added, we executed the query operation in turn.
Since the array is monotonically increasing, our binary search tree degenerates into a linked list, and the time complexity of adding and querying elements is O(N2)O(N^2)O(N2). The AVL tree is O(logN)O(logN)O(logN) O(logN) because of its self-balancing property.
On my computer, the result of the AVLAndBSTPerformanceTest unit test is:
BST : 1.935773389 s
AVL : 0.018965793 s
Copy the codeAs we can see, the difference is huge.
Four:
In this article, I introduced AVL trees as data structures and how AVL trees are self-balancing by left-handed and right-handed rotation. In addition, a small test was performed to verify the performance difference between AVL tree and binary search tree under extreme data conditions.
AVL tree is the first self-balanced binary search tree invented in computer science. In addition to AVL, there are many excellent data structures such as balanced binary search tree. I look forward to studying and learning with you in the following articles.
The code used in this article is in:
Github.com/jinrunheng/…
Ok, so far, this article I will introduce the end ~ welcome to pay attention to my public number [kim_talk], here I hope you can harvest more knowledge, we see you next issue!