Self – balanced tree for the classical problem of tree structure
One problem with BST trees is that depending on the number of nodes you add, one edge of the tree can be very deep; That is, one branch of the tree has many layers, while the others have only a few, as shown in the figure below
This can cause performance problems when a node needs to be added, removed, and searched on an edge.
To solve this problem, there is a tree called the Adelson-Velski-Landi tree (AVL tree).
AVL tree is a self-balanced binary search tree, meaning that the height difference between the left and right subtrees of any node is at most 1.
Get the basics straight
Height of node
As shown above:
There is no other child node on the left of root node 3 except one child node 2, which is also a leaf node, so the height of the left subtree is 0.
There is a child node 6 on the right of root node 3, and a leaf node 4 on the left of child node 5, so the height of node 4 is 0 and that of node 5 is 1.
There is a child node 7 to the right of node 6, and there are no other children below node 7, so node 7 is also a leaf node, so the height of node 7 is also 0.
As the parent node of node 5 and node 7, the height of node 6 must be the highest on the left and right sides. Therefore, the height of node 6 must be increased by 1 above that of node 5, that is, the height of node 6 is 2.
Root node 3 is the parent of nodes 2 and 6, and the height of node 3 is the highest on the left and right sides. Therefore, the height of root node 3 must be increased by 1 above the height of node 6, that is, the height of root node 3 is 3.
Balance factor
In AVL tree, the difference between the right subtree height (HR) and the left subtree height (HL) needs to be calculated for each node, and the value (HR-HL) should be 0, 1 or -1, as shown below:
If the result is not one of these three values, the AVL tree needs to be balanced. That’s the idea of an equilibrium factor.
Balance operation
After adding or removing nodes to an AVL tree, the tree is calculated and verified to be balanced. When inserting a node into the AVL tree, the balancing operation of single rotation or double rotation can be performed, corresponding to four scenarios respectively:
Scene 1:
Left left (LL) : Single rotation to the right
At this point, it can be subdivided into two situations:
Case 1:
The lower right of the left child node of the node has no child node and the left is biased, as shown in the figure below:
The left child node of root node 3 has child node 1 on the left side of node 2, but there is no child node on the right side of node 2. In this case, node 2 is regarded as the new root node, and node 3 becomes the right child node of the new root node 2 to maintain balance
Situation 2:
The left side of the left child node of the node is too heavy, and there are child nodes on the right side of the left child node, as shown in the figure below:
The left subtree 30 of root node 50 is biased, and the left sub-node 10 of the left sub-tree 30 also has child node 5 at the lower left of the left sub-node 10, while the right sub-node 40 of the left sub-tree 30 has no child node and is itself a leaf node. Here’s the balance:
The first step is to separate the left subtree 30 from the root node 50, as shown below:
The second step is to extract the right child node 40 below node 30 and transplant it to the left of node 50 to become the left child node of node 50, as shown in the figure below:
In the third step, the system of node 50 is transplanted to the right side of node 30 as a whole and becomes the right subtree of node 30, so as to complete the balance, as shown in the figure below:
To sum up, LL is used when the height of the left child node of the node is greater than that of the right child node, and the left child node is also balanced or the left is heavier.
Scene 2:
Right-right (RR) : Single rotation to the left
At this point, it can be subdivided into two situations:
Case 1:
The lower left side of the right child node has no child node and the right side is heavy, as shown in the figure below:
There is child node 3 on the right of child node 2 of root node 1, but there is no child node on the left of node 2. In this case, node 2 is regarded as the new root node and node 1 becomes the left child node of the new root node 2 to maintain balance
Situation 2:
The right child node of the node is heavy on the right, and the left child node of the right child node has child nodes, as shown in the figure below:
The right subtree 70 of the root node 50 is heavy, and the right sub-node 80 of the right sub-tree 70 also has child node 90 at the lower right of the right sub-node 80, while the left sub-node 60 of the right sub-tree 70 has no child node and is itself a leaf node. Here’s the balance:
The first step is to separate the right subtree 70 from the root node 50, as shown below:
The second step is to extract the left child node 60 below node 70 and transplant it to the right of node 50 to become the right child node of node 50, as shown in the figure below:
In the third step, the system of node 50 is transplanted to the left of node 70 as a whole to become the left subtree of node 70, so as to complete the balance, as shown in the figure below:
To sum up, an RR is used when the height of the child node on the right is larger than that of the child node on the left, and the child node on the right is balanced or the child node on the right is heavy.
Scenario 3:
Left and right (LR) : double rotation to the right (first LL single rotation to the right, then RR single rotation to the left)
At this point, it can be subdivided into two situations:
Case 1:
The node is biased to the left, and the right child node of the left child node is balanced, as shown in the figure below:
The root node 3 is biased to the left, and the left child node 1 is biased to the right. There are no children under the right child node 2 of the left child node 1, so the lower part of node 2 is balanced. However, nodes 3, 1 and 2 are unbalanced on the whole.
In the first step, node 2 is replaced by node 1 from its original position, and node 1 becomes the left child node of node 2, thus becoming case 1 in the previous scenario 1 (left to left), as shown below:
In the second step, as in case 1 of the previous scenario 1 (left to left), the root node 3 is single-rotated to the right and becomes the right child node of node 2 to maintain balance, as shown in the figure below:
The flow chart is as follows:
Situation 2:
The left subtree of the node is biased, the right of the left subtree is biased, and the lower part of the right sub-node of the left subtree is unbalanced, as shown in the figure below:
The left subtree of the root node 50 is heavy, and only the left side below the right sub-node 40 of the left sub-node 30 has the sub-node 35. Therefore, the sub-node 40 is unbalanced at this time, and the whole sub-node is also unbalanced. If balance is needed at this time:
The first step is to separate the root node 50 from the left subtree, as shown in the figure below:
The second step is to replace the left child node 35 of node 40 to the original position of node 40. At this point, node 35 becomes the new child node on the right of node 30, and then node 40 becomes the parent node of node 30, as shown in the figure below:
Third step, tied node 40 a whole as a root node 50 left subtree, so it has now become a scene before a left (left) in the case of 1 (I know step directly tied 50 a node into the right side of the node 40 subtrees can balance directly, but getting back to the scene in the case of 1 is advantageous to the reuse of code level), as shown in the figure below:
The fourth step is to rotate the whole system of root node 50 and its child node 70 to the right as the right subtree of node 40, as shown in the figure below:
The overall process is as follows:
LR usage scenario: The height of the left child node of a node is larger than that of the right child node, and the right side of the left child node is heavier.
Scene 4:
RL: Double rotation to the left (first RR single rotation to the left, then LL single rotation to the right)
At this point, it can be subdivided into two situations:
Case 1:
The node is right-biased, and the left child node of the right child node is balanced, as shown in the figure below:
The root node 1 is biased to the right, and the right child node 3 is biased to the left. The left child node 2 of the right child node 3 has no child node below it, so the lower part of node 2 is balanced, but nodes 1, 3 and 2 are unbalanced on the whole. If balance is needed at this time:
The first step is to replace node 2 with node 3 and make node 3 the right child node of node 2, thus becoming case 1 in previous scenario 2 (right and right), as shown below:
In the second step, as in case 1 in scenario 2 (right and right), the root node 1 is single-rotated to the left and becomes the left child node of node 2 to maintain balance, as shown in the figure below:
The flow chart is as follows:
Situation 2:
The right subtree of the node is biased, the left of the right subtree is biased, and the lower part of the left child node of the right subtree is unbalanced, as shown in the figure below:
The right subtree of the root node 70 is heavy, and only the right side below the left child node 72 of the right child node 80 has child node 75. Therefore, the child node 72 is unbalanced at this time, and the whole child node is also unbalanced. If balance is needed at this time:
The first step is to separate the root node 70 from the right subtree, as shown in the figure below:
The second step is to replace the child node 75 on the right of node 72 to the original position of node 72. At this point, node 75 becomes the new child node on the left of node 80, and then node 72 becomes the parent node of node 80, as shown in the figure below:
The third step, the node will be 72 this is the right of the whole as a root node 70 subtree, so it has now become a scene before 2 (right) in the case of 1 (I know step on node 70 directly to the department to become 72 nodes can directly balance left subtree, but getting back to the scene. In the case of 1 is advantageous to the reuse of code level), as shown in the figure below:
The fourth step is to rotate the whole system of root node 70 and its child node 50 to the left as the left subtree of node 72, as shown in the figure below:
The overall process is as follows:
Self-realization of self-balanced binary trees
Since the AVL tree is a BST tree, we can extend the BST class we wrote by overriding the methods used to keep the AVL tree balanced, namely the INSERT, insertNode, and removeNode methods. All other BST methods will be inherited by the AVLTree class.
(If you can’t read the code, it doesn’t matter, please be sure to understand the transformation in the diagram first! It took a whole morning to make these pictures, and I don’t know if other friends can understand them.
// Copy the binary search tree directly from the tree:
// Each place in the tree where data is stored is called an element node, so create a class for that node
class Node{
constructor(key){ // The key in the tree is not like the index in the stack or queue. The key in the tree directly corresponds to the data value stored by the node
this.key = key // Storage node value
this.left = null // Index points to the left child node, like a bidirectional list. Lists are up and down structures (pointer fields point up and down) and trees are left and right structures (pointer fields point left and right).
this.right = null // Index to the right child node}}// Binary search tree class
class BinarySearchTree{
constructor(){
this.root = null // The root node of the binary tree. The default value is null
}
insert(key){ // Insert new values into the binary tree
if(!this.root){ // If the root node has no value, it is inserted into the root node of the binary tree
this.root = new Node(key)
}else{ // If the root node already has a value, make a judgment and compare the value of the inserted child node with the value of the parent node to determine the left child node or the right child node
this.insertNode(this.root,key) // this.root because every time a new value is inserted, the root node is used to compare the size and insert the value}}// The insertNode method is intended to be called recursively when there is already a lot of data
insertNode(node,key){ // Insert a value into a node. Node represents the parent node, and key represents the value of the child node. The value of the child node is compared with the value of the parent node
if(key < node.key){ // If the value to be inserted is smaller than the value of the parent node, insert the left side
If there is already a child node to the left of the parent node (because it is not possible to insert children of the root node every time, in case there are many layers), then determine
if(node.left){ // There are already children to the left of the parent node, so the value to be inserted will be the children of that child node (not sure how many layers, so recurse).
this.insertNode(node.left,key) // Recursively calls a method to insert values into a node, this time comparing the value of the left child node to the value to be inserted
}else{ // If there are no children to the left of the parent node, insert the child node directly into the parent node
node.left = new Node(key)
}
}else{ // If greater than or equal to is inserted on the right side, the right child node is also evaluated recursively
if(node.right){ // There are already children to the right of the parent node, so the value to be inserted will be the children of that child node (not sure how many layers, so recurse).
this.insertNode(node.right,key) // Recursively calls a method to insert values into a node, this time comparing the value of the right child node to the value to be inserted
}else{ // If there are no children to the right of the parent node, insert them as children of the parent node
node.right = new Node(key)
}
}
}
min(){ // Query the minimum value of the entire binary tree, also requires a recursive method, because there is no way to know which node is the minimum value
return this.minNode(this.root) // Returns the return value of the function method that recursively evaluates to find the minimum value starting at the root node
}
// The minNode method is the same as the minNode method. The minNode method is the same as the minNode method.
minNode(node){ // Determine recursively how to find the minimum value starting from a specified node. Node represents the node passed in
let current = node // Save the current node passed each time in a variable
while(current && current.left){ // If the current node has a value and the children to the left of the current node also have a value, there is a smaller value
current = current.left // Change the left child node to the current node to continue the loop comparison
}
// If there are no children on the left, the current node is the minimum node
return current
}
max(){ // Query the maximum value of the entire binary tree, also requires a recursive method, because there is no way to know which node is the minimum value
return this.maxNode(this.root) // Returns the return value of the function method that recursively evaluates to find the minimum value starting at the root node
}
// The Max method is different from the maxNode method. The Max method looks for the maximum value of the entire tree, and the Max method looks for the maximum value of the tree from a node down.
maxNode(node){ // Determine recursively how to find the maximum value starting from a specified node. Node represents the node passed in
let current = node // Save the current node passed each time in a variable
while(current && current.right){ // If the current node has a value and the child nodes to the right of the current node have a value, there is a larger value
current = current.right // Change the right child node to the current node and continue the loop comparison
}
If there is no child node on the right, the current node is the node with the maximum value
return current
}
// middle order traversal
inOrderTraverse(cb){ // Receives a callback function that iterates through the sort order
this.inOrderTraverseNode(this.root,cb) // Start from the root node to iterate through the sort
}
inOrderTraverseNode(node,cb){ // Order traversal recursive method
if(node){ // Do traversal only when the node exists
this.inOrderTraverseNode(node.left,cb)
cb(node.key)
this.inOrderTraverseNode(node.right,cb)
}
}
// order traversal first
preOrderTraverse(cb){ // Receives a callback that iterates through the structure of the data
this.preOrderTraverseNode(this.root,cb) // Start with the root node
}
preOrderTraverseNode(node,cb){ // First traversal the recursive method
if(node){ // Do traversal only when the node exists
cb(node.key)
this.preOrderTraverseNode(node.left,cb)
this.preOrderTraverseNode(node.right,cb)
}
}
// after the sequence traversal
postOrderTraverse(cb){ // Receives a callback function, traversed sequentially
this.postOrderTraverseNode(this.root,cb) // Sort from the root node
}
postOrderTraverseNode(node,cb){ // the post-order traversal recursive method
if(node){ // Do traversal only when the node exists
this.postOrderTraverseNode(node.left,cb)
this.postOrderTraverseNode(node.right,cb)
cb(node.key)
}
}
// Search function
searchKey(key){
return this.searchNode(this.root,key)
}
searchNode(node,key){ // Recursive method
// Check if there is anything inside the tree
if(node){ // There must be nodes in the tree to search
// Determine the size of the value and determine which side to search
if(key < node.key){ // If the value passed is smaller than the value of the current node, continue the search for the left child node
return this.searchNode(node.left,key)
}else if(key > node.key){ // If the value passed is greater than the value of the current node, continue the search for the right child node
return this.searchNode(node.right,key)
}else{ // It is neither greater than nor less than
return true}}else{ // If the node does not exist, do not search
return false}}// Delete function
removeKey(key){
this.root = this.removeNode(this.root,key)
}
removeNode(node,key){
if(node){ // The tree can be deleted only if there are nodes in it
if(key < node.key){ // Search from the left
node.left = this.removeNode(node.left,key)
return node // Return the spliced node
}else if(key > node.key){ // Search from the right
node.right = this.removeNode(node.right,key)
return node // Return the spliced node
}else{ // The object to delete is found
// In the first case, the node to be deleted has children on both the left and right sides
if(node.left && node.right){
let target = this.minNode(node.right) // Find the smallest child node of the child node on the right of the node to be deleted, that is, the smallest grandson node
node.key = target.key // The smallest grandchild node is replaced by the deleted node
node.right = this.removeNode(node.right,key) // Delete the smallest grandchild node from the original grandchild node
return node
}
// In the second case, there are children to the left or right of the node to be deleted
if(node.left || node.right){
if(node.left){ // If there are children on the left of the node to be deleted, the child on the left replaces the deleted node
node = node.left
}
if(node.right){ / / in the same way
node = node.right
}
return node // Return the replaced node
}
// Third case: the node to be deleted is a leaf node
node = null
return node
}
}else{
return null}}// Modify the function
updateKey(key,key1){
return this.updateNode(this.root,key,kye1)
}
updateNode(node,key,key1){ // Recursive method
// Check if there is anything inside the tree
if(node){ // There must be nodes in the tree to search
// Determine the size of the value and determine which side to search
if(key < node.key){ // If the value passed is smaller than the value of the current node, continue the search for the left child node
return this.updateNode(node.left,key,key1)
}else if(key > node.key){ // If the value passed is greater than the value of the current node, continue the search for the right child node
return this.updateNode(node.right,key,key1)
}else{ // It is neither greater than nor less than
node.key = key1
return true}}else{ // If the node does not exist, do not search
return false}}}// The next part is the real start of self-balancing binary trees
// Define a standard mapping table of balance factors for later reading
const BalanceFactor = {
UNBALANCED_RIGHT: -2.// The right side is extremely unbalanced
SLIGHTLY_UNBALANCED_RIGHT: -1.// The right side is a bit unbalanced
BALANCED:0.// Both sides are flat
UNBALANCED_LEFT:1.// The left side is a bit unbalanced
SLIGHTLY_UNBALANCED_LEFT:2.// The left side is extremely unbalanced
}
// The self-balancing binary tree class inherits the binary search tree class
class AVLTree extends BinarySearchTree{
constructor(){
super()}getNodeHeight(node){ // Get the height of the incoming node
if(node){ // Check whether the node exists
return Math.max(this.getNodeHeight(node.left),this.getNodeHeight(node.right)) + 1 // Implicit type conversion occurred, recursive entry
Math. Max (-1,-1) returns -1,-1 +1 equals 0
}else{
return -1 // Recursive exit}}getBalanceFactor(node){ // Calculate the balance factor
const heightDifference = this.getNodeHeight(node.left) - this.getNodeHeight(node.right) // Subtract the right subtree height from the left subtree height
switch(heightDifference){
case -2:
return BalanceFactor.UNBALANCED_RIGHT
case -1:
return BalanceFactor.SLIGHTLY_UNBALANCED_RIGHT
case 0:
return BalanceFactor.BALANCED
case 1:
return BalanceFactor.SLIGHTLY_UNBALANCED_LEFT
case 2:
return BalanceFactor.UNBALANCED_LEFT
}
}
// The entire left subtree is heavier, and the left subtree is right-rotated
rotationLL(node){ // Left left (LL) : single rotation to the right
let temp = node.left
node.left = temp.right
temp.right = node
return temp
}
// The entire right subtree is heavy, so rotate the right subtree left
rotationRR(node){ // Right (RR) : single rotation to the left
let temp = node.right
node.right = temp.left
temp.left = node
return temp
}
// The right side of the left subtree is heavier, so the whole left subtree is heavier, and the whole left subtree is right-rotated
rotationLR(node){ // left/right (LR) : double rotation to the right (RR = left, LL = right)
node.left = this.rotationRR(node.left) // If the left subtree is rotated to the left, the left subtree will balance the heavier part of the left subtree to the heavier part of the whole left subtree
return this.rotationLL(node) // Perform a single rotation to the right when the entire left subtree is heavy
}
// The left side of the right subtree is heavier, then the whole right subtree is heavier, then the whole right subtree is left-handed
rotationRL(node){ // RL: double rotation to left (LL to right, RR to left)
node.right = this.rotationLL(node.right) // Rotate the right subtree to the right. If you pass LL to the right subtree, the left part of the right subtree will be balanced first, and the whole right subtree will be heavy
return this.rotationRR(node) // When the entire right-hand subtree is heavy, a single rotation to the left is performed
}
// Insert a new node
insert(key) {
this.root = this.insertNode(this.root,key)
}
insertNode(node, key) { // A recursive method to insert a new node
if(! node){// If the node does not exist, build and return the node
return new Node(key)
}else if(key < node.key){ // If the value to be inserted is smaller than the value of the current node, insert the left child node of the node
node.left = this.insertNode(node.left,key)
}else if(key > node.key){ // If the value to be inserted is greater than the value of the current node, insert the right child node of the node
node.right = this.insertNode(node.right,key)
}else{ // If the value is repeated, return the node
return node
}
// The above code is the same as that of BST
// After insertion, check whether the current node is balanced. If not, perform balancing operation
switch(this.getBalanceFactor(node)){ // Balance a little bit at a time, balancing the new nodes immediately instead of waiting until they are all inserted
If the height difference is greater than 1, the left side is extremely unbalanced and the right side is extremely unbalanced
case BalanceFactor.UNBALANCED_LEFT:
if(key < node.left.key){ // The new value inserted is less than the value of the left child node, and LL balancing is required
node = this.rotationLL(node)
}else{ // Insert a new value greater than the parent value
node = this.rotationLR(node)
}
break
case BalanceFactor.UNBALANCED_RIGHT:
if(key < node.right.key){ // The new value inserted is less than the value of the right child node
node = this.rotationRL(node)
}else{
node = this.rotationRR(node)
}
break
}
return node // Return the balanced node
}
removeNode(node, key) { // A recursive method to delete a node
if(! node){// If the node to be deleted does not exist
return null
}
node = super.removeNode(node,key)
switch(this.getBalanceFactor(node)){ // Balance it a little bit at a time, balancing the remaining nodes immediately after the new deletion, rather than balancing it once after all deletion
If the height difference is greater than 1, the left side is extremely unbalanced and the right side is extremely unbalanced
case BalanceFactor.UNBALANCED_LEFT:
if(
this.getBalanceFactor(node.left) === BalanceFactor.BALANCED ||
this.getBalanceFactor(node.left) === BalanceFactor.SLIGHTLY_UNBALANCED_LEFT
){
node = this.rotationLL(node)
}else{ // Insert a new value greater than the parent value
node = this.rotationLR(node)
}
break
case BalanceFactor.UNBALANCED_RIGHT:
if(
this.getBalanceFactor(node.right) === BalanceFactor.BALANCED ||
this.getBalanceFactor(node.right) === BalanceFactor.SLIGHTLY_UNBALANCED_LEFT
){
node = this.rotationRR(node)
}else{
node = this.rotationRL(node)
}
break
}
return node // Return the balanced node}}let treeData = new AVLTree()
treeData.insert(10)
treeData.insert(5)
treeData.insert(3)
treeData.insert(15)
treeData.insert(13)
treeData
Copy the code