Remember the problem we left behind in the previous post? Let's briefly review it again, now there is an empty binary lookup tree, we insert 1, 2, 3, 4, 5, five nodes, so what does the resulting tree look like? This is not difficult to imagine, the binary tree is as follows:
The height of the tree is 4, and there is no difference in the data structure from a linked table, and the lookup performance is the same as a linked table. What if we change the structure of the tree? For example, change to the following tree structure.
Then the height of the tree becomes 3, and it is also a binary lookup tree, the lower the height of the tree, the higher the lookup performance, which is our ideal data structure. If you want the height of the tree to be as low as possible, then the height difference between the left and right subtrees can't be too different. This brings us to our topic todayAVL balanced binary treeThe AVL balanced binary tree is defined as any node whose left and right subtrees cannot differ in height by more than 1. This ensures that the height of the tree is kept to a minimum, so that our lookup performance is also optimal. So how do we ensure the nature of the AVL balanced binary tree when the tree changes (i.e., when nodes are added or deleted)? We analyze each case below.
single-rotation left-left (physics)
Let's take a look at the following examples, each of the following examples is the most complex case and completely covers the simple case, so if we have implemented the most complex case in code, then the simple case will be covered as well. Look at the following diagram
In the above figure, the original tree with k1 as the root node is an AVL balanced binary tree, at this point, we insert node 2 into the tree, according to the nature of the binary lookup tree, the final node 2 is inserted in the above figure. After inserting the node, we analyze each node to see if the node still meets the nature of AVL balanced binary tree. Let's look at node 3, after inserting node 2, the height of the left subtree of node 3 is 0, because there is only one node 2. Then look at the right subtree of node 3, the right subtree is empty, then the height of -1.Here we standardize that if the node is empty, then the height is -1. The height of the left and right subtrees of node 3 is 1, which satisfies the nature of AVL balanced binary tree, similarly we look at node k2, the height of the left subtree is 1, the height of the right subtree is 0 and the difference in height is 1, which also satisfies the AVL balanced binary tree. Then look at node k1, the height of the left child tree k2 is 2, the height of the right child tree is 0, the difference is 2, so at node k1 does not satisfy the nature of the AVL balanced binary tree, we have to make adjustments, so that k1 as the root node of the tree into an AVL balanced binary tree, how do we do it?
Since the height of the left subtree is higher, we have to rotate the tree a little bit, using k2 as the root node and k1 as the right child node of k2, and the rotation is shown in the figure:
After rotation, the new tree with k2 as the root node is an AVL balanced binary tree. Here we are going toPay special attention to the location of node 5, its original position is the right subtree of k2, and k2 is the left subtree of k1, according to the nature of the binary lookup tree, the value in the right subtree of k2 is greater than k2 and less than k1. After rotation, k2 becomes the root node, k1 becomes the right subtree of k2, then the original right subtree of k2 (node 5), becomes the left subtree of k1. Then the tree is still greater than k2 and less than k1 according to the nature of binary lookup tree, no change, which is in line with our expectations. With the above rotation, the new tree we get is an AVL balanced binary tree.
We summarize the important points to prepare for coding:
- The left subtree of k1 is found to have a height greater than 1 than the right subtree;
- The height of the left subtree k2 of k1 is found to be greater than the height of the right subtree of k2, which is called theLeft-left scenario. To do a single rotation on the left side.
- Use k2 as a node of the new tree, the right subtree of k2 is changed to k1, and the left subtree of k1 is changed to the right subtree of k2.
- Update the heights of k1 and k2.
Completing the above, we get a new AVL balanced binary tree. Let's move on to the specific coding.
/**
* binary tree node
* @param <T>
*/
public class BinaryNode<T extends Comparable<T>> {
//Node data
@Setter@Getter
private T element;
//left child node (math.)
@Setter@Getter
private BinaryNode<T> left;
//right child node (math.)
@Setter@Getter
private BinaryNode<T> right;
//Node height
@Setter@Getter
private Integer height;
//constructor
public BinaryNode(T element) {
if (element == null) {
throw new RuntimeException("binary tree node元素不能为空");
}
= element;
= 0;
}
}
We're remodeling now.BinaryNodeclass and add the height attribute to the class, which defaults to 0.
/**
* binary lookup tree
*/
public class BinarySearchTree<T extends Comparable<T>> {
……
/**
* inserted element
*
* @param element
*/
public void insert(T element) {
root = insert(root, element);
}
private BinaryNode<T> insert(BinaryNode<T> tree, T element) {
if (tree == null) {
tree = new BinaryNode<>(element);
} else {
int compareResult = (());
if (compareResult > 0) {
(insert((), element));
}
if (compareResult < 0) {
(insert((), element));
}
}
return balance(tree);
}
/**
* balancing node
* @param tree
*/
private BinaryNode<T> balance(BinaryNode<T> tree) {
if (tree == null) {
return null;
}
Integer leftHeight = height(());
Integer rightHeight = height(());
if (leftHeight - rightHeight > 1) {
//unorthodox-unorthodox情形，rotary
if (height(().getLeft()) >= height(().getRight())) {
tree = rotateWithLeftChild(tree);
}
}
//Height of the current node = Highest child node + 1
((leftHeight,rightHeight) + 1);
return tree;
}
/**
* Height of nodes
* @param node
* @return
*/
public Integer height(BinaryNode node) {
return node == null?-1:();
}
/**
* unorthodox侧rotary
* @param k1
*/
private BinaryNode<T> rotateWithLeftChild(BinaryNode<T> k1) {
BinaryNode<T> k2 = ();
(());
(k1);
((height(()),height(()))+1);
((height(()),height(()))+1);
return k2;
}
……
}
We'll be back in theBinarySearchTreeAdd the height method to the class to get the height of the node and return -1 if the node is empty. since theinsertAfter that, the tree may rotate and the nodes will change, so here, theinsertmethods are transformed so that they will have return values. In the firstinsertmethod, call the secondinsertmethod and uses root to pick up the return value of the second insert method, indicating that the root node of the entire tree may be subject to rotational change. Also in the second insert method, the recursive call gives the return value to the left or right child of the current node, depending on the conditions. After the node insertion is complete, we uniformly callbalancemethod, if the node does not satisfy the balance condition, we have to rotate it accordingly and finally update the height of the node in question, thisbalanceMethods are the ones we're focusing on today.
After entering the BALANCE method, we get the heights of the left and right subtrees respectively, if the height of the left subtree is greater than 1 than the height of the right subtree, it means that the balance condition is not satisfied, and needs to be rotated. Then we judge the height of the left subtree of the left subtree and the right subtree of the left subtree, if it is greater than, it means that it isLeft-left scenario, requires a single rotation on the left side. It's rather roundabout here, so read a few more to deepen your understanding. We pass the subtree with the current node as the root node into therotateWithLeftChildIn the method, the variable is named k1 in order to correspond to the graph above. then the corresponding k2 is the left subtree of k1, and then a rotation is performed, where the left subtree of k1 is set to the right subtree of k2, and the right subtree of k2 is set to k1, and then the heights of k1 and k2 are re-calculated, and finally k2 is returned as the root of the new subtree. In this wayLeft-left scenarioThe single rotation is realized. We can read the code a few more times to deepen our understanding.
right-right single rotation
The opposite of left-left isRight-right scenario, we look at the chart below:
Our insertion of node 6 results in an unbalanced subtree with k1 as the root node, which needs to be rotated, and the rotation is perfectly symmetric with the left-left case, summarizing the operation as follows:
- The right subtree of k1 is found to have a height greater than 1 than the left subtree;
- The height of the right subtree k2 of k1 is found to be greater than the height of the left subtree of k2, a condition calledRight-right scenario. To do a single rotation on the right side.
- Use k2 as a node of the new tree, the left subtree of k2 is changed to k1, and the right subtree of k1 is changed to the left subtree of k2.
- Update the heights of k1 and k2.
After rotating, it is shown below:
We coded it as we did above.
/**
* balancing node
* @param tree
*/
private BinaryNode<T> balance(BinaryNode<T> tree) {
if (tree == null) {
return null;
}
Integer leftHeight = height(());
Integer rightHeight = height(());
if (leftHeight - rightHeight > 1) {
//unorthodox-unorthodox情形，rotary
if (height(().getLeft()) >= height(().getRight())) {
tree = rotateWithLeftChild(tree);
}
} else if (rightHeight - leftHeight > 1){
//right (-hand)-right (-hand)情形，rotary
if (height(().getRight()) >= height(().getLeft())) {
tree = rotateWithRightChild(tree);
}
}
//Height of the current node = Highest child node + 1
((leftHeight,rightHeight) + 1);
return tree;
}
/**
* right (-hand)侧rotary
* @param k1
* @return
*/
private BinaryNode<T> rotateWithRightChild(BinaryNode<T> k1) {
BinaryNode<T> k2 = ();
(());
(k1);
((height(()),height(()))+1);
((height(()),height(()))+1);
return k2;
}
In the balance method, we added theRight-right scenariojudgment and then call therotateWithRightChildmethod, in which the names of the variables are still called k1 and k2 in order to correspond to the above figure. k1's right node is set to k2's left node, and k2's left node is set to k1, and then the height is updated, and finally the new root node, k2, is returned.
Double rotation left and right
Let's look at the double rotation scenario as shown below:
Our new insertion of node 3 results in a subtree with k1 as the root node that does not satisfy the balance condition, so let's start with the previous single rotation on the left side to see if we can satisfy it, as shown below:
After the rotation, the new tree with k2 as the root node has a right subtree with a height greater than 1 than that of the left subtree.It also does not satisfy the equilibrium condition, so this option does not work. So how do we do it? We can only satisfy the equilibrium condition by making k3 the new root node, to move k3 to the root node we need to rotate it twice, the first time we first perform a right rotation at the k2 node, and rotate k3 to the position of the left child node of k1 as shown in the figure:
Then a left rotation is performed at position k1 to move k3 to the root node, as shown in Fig:
This satisfies the balance condition, careful partners may have noticed that the original k3 do node hangs onto the right node of k2, the original k3 right node scrapes onto the left node of k1. These details do not need our special treatment, because in the left rotation right rotation method has been dealt with, we then summarize the specific details:
- After inserting the node, it is found that the left subtree of k1 has a height greater than 1 than the right subtree;
- It is found that the left subtree of k1, k2, and the right subtree of k2 are higher than the left subtree of k2, which is
Left-right scenario, requires double rotation. - Rotate the left subtree k2 of k1 to the right;
- Rotate k1 to the left;
We coded the realization
/**
* balancing node
* @param tree
*/
private BinaryNode<T> balance(BinaryNode<T> tree) {
if (tree == null) {
return null;
}
Integer leftHeight = height(());
Integer rightHeight = height(());
if (leftHeight - rightHeight > 1) {
//unorthodox-unorthodox情形，rotary
if (height(().getLeft()) >= height(().getRight())) {
tree = rotateWithLeftChild(tree);
} else {// unorthodox-right scenario，dual-rotation
tree = doubleWithLeftChild(tree);
}
} else if (rightHeight - leftHeight > 1){
//right (-hand)-right scenario，rotary
if (height(().getRight()) >= height(().getLeft())) {
tree = rotateWithRightChild(tree);
}
}
//Height of the current node = Highest child node + 1
((leftHeight,rightHeight) + 1);
return tree;
}
/**
* unorthodox侧dual-rotation
* @param k1
* @return
*/
private BinaryNode<T> doubleWithLeftChild(BinaryNode<T> k1) {
(rotateWithRightChild(()));
return rotateWithLeftChild(k1);
}
In our balance method, we addLeft-right scenariojudgment and then call thedoubleWithLeftChildmethod, in which we follow the steps summarized earlier, first we perform a right rotation of the left node of k1, then we perform a left rotation of k1, and finally we return the new root node, which is rotated to achieve the condition of equilibrium.
Right-left double rotation
Finally, we turn to the symmetry with the left-right caseRight-left scenario, the initial structure of the tree is shown below:
The insertion of node 8 causes the height of the right subtree of node k1 to be greater than the height of the left subtree by more than one, while the left subtree of k2 is taller than the right subtree, which isRight-left scenario. At this point, we need to first do a left rotation at the k2 node, which is rotated as shown in Fig:
Then another right rotation is done at the k1 node, and the rotation is shown in Fig:
Let's summarize the operation of the right-left case with reference to the left-right case above:
- After inserting the node, it is found that the right subtree of k1 has a height greater than 1 than the left subtree;
- It is found that the right subtree of k1, k2, and the left subtree of k2 are taller than the right subtree of k2, which is
Right-left scenario, requires double rotation. - Rotate the right subtree k2 of k1 to the left;
- Rotate k1 to the right;
Then we code the implementation:
/**
* balancing node
* @param tree
*/
private BinaryNode<T> balance(BinaryNode<T> tree) {
if (tree == null) {
return null;
}
Integer leftHeight = height(());
Integer rightHeight = height(());
if (leftHeight - rightHeight > 1) {
//unorthodox-unorthodox情形，rotary
if (height(().getLeft()) >= height(().getRight())) {
tree = rotateWithLeftChild(tree);
} else {// unorthodox-right scenario，dual-rotation
tree = doubleWithLeftChild(tree);
}
} else if (rightHeight - leftHeight > 1){
//right (-hand)-right scenario，rotary
if (height(().getRight()) >= height(().getLeft())) {
tree = rotateWithRightChild(tree);
} else {//right (-hand)-unorthodox情形，dual-rotation
tree = doubleWithRightChild(tree);
}
}
//Height of the current node = Highest child node + 1
((leftHeight,rightHeight) + 1);
return tree;
}
/**
* right (-hand)侧dual-rotation
* @param k1
* @return
*/
private BinaryNode<T> doubleWithRightChild(BinaryNode<T> k1) {
(rotateWithLeftChild(()));
return rotateWithLeftChild(k1);
}
Since the left-right single-rotation method has already been implemented before, the double-rotation implementation, which we can just call directly, first performs a left-rotation of the right node of k1, then a right-rotation of k1, and finally returns the new root node. Since the height of the node is being handled in the left and right single rotation methods, no special handling is needed here.
Delete nodes
Like insertion of nodes, deletion of nodes also causes imbalance in the tree, similarly, after deletion of nodes, we call the balance method to rebalance the tree. remove transformation method is as follows:
/**
* Delete element
* @param element
*/
public void remove(T element) {
root = remove(root, element);
}
private BinaryNode<T> remove(BinaryNode<T> tree, T element) {
if (tree == null) {
return null;
}
int compareResult = (());
if (compareResult > 0) {
(remove((), element));
} else if (compareResult < 0) {
(remove((), element));
}
if (() != null && () != null) {
(findMin(()));
(remove((), ()));
} else {
tree = () != null ? () : ();
}
return balance(tree);
}
Similarly, the remove method causes a change in the root node of the subtree, so the second remove method is augmented with a return value, and the current node is overwritten with the return value when the second remove method is called.
summarize
Well, the operation of AVL balanced binary tree is fully realized, it solves the problem of unbalanced tree, making the query efficiency greatly improved. Partners have questions, welcome to the comment section message ~~