Shulou(Shulou.com)06/01 Report--

What is a balanced binary tree AVL, many novices are not very clear about this, in order to help you solve this problem, the following editor will explain for you in detail, people with this need can come to learn, I hope you can gain something.

Preface

Wiki: in computer science, AVL tree is the first self-balanced binary search tree invented. In an AVL tree, the maximum height difference between the two subtrees corresponding to any node is 1, so it is also called a height balanced tree. The average and worst-case time complexity of finding, inserting, and deleting is O (logn). Adding and deleting elements may require one or more tree rotations to rebalance the tree. The AVL tree gets its name from its inventors G. M. Adelson-Velsky and Evgenii Landis, who disclosed this data structure in their 1962 paper "An algorithm for the organization of information".

1 Why should there be a balanced binary tree

The binary search tree can improve the search efficiency to some extent, but when the original sequence is ordered, for example, the sequence A = {1 ~ 2 ~ 3 ~ 4 ~ 5 ~ 5 ~ 6}, the binary search tree is constructed as shown in figure 1.1. The binary search tree constructed according to this sequence is a right oblique tree, at the same time, the binary tree is degenerated into a single linked list, and the search efficiency is reduced to O (n).

Find element 6 in this binary search tree 6 times.

The search efficiency of the binary search tree depends on the height of the tree, so keeping the height of the tree to a minimum can ensure the search efficiency of the tree. The same sequence An is stored in the way of figure 1.2. When looking for element 6, it only needs to be compared three times, and the search efficiency is doubled.

It can be seen that when the number of nodes is fixed and the left and right ends of the tree are balanced, the search efficiency of the tree is the highest.

The tree whose height difference between the left and right subtrees is no more than 1 is a balanced binary tree.

two。 Define

Balanced binary search tree: referred to as balanced binary tree. The highly balanced binary tree proposed by the former Soviet mathematicians Adelse-Velskil and Landis in 1962 is also called AVL tree according to the English name of scientists. It has the following properties:

It could be an empty tree.

If it is not an empty tree, the left and right subtrees of any node are balanced binary trees, and the absolute value of the difference in height is not more than 1.

Balance means, like a balance, that is, the weight on both sides is about the same.

For example, figure 2.1 is not a balanced binary tree, because the left subtree of node 60 is not a balanced binary tree.

Figure 2.2 is not a balanced binary tree either, because although the left and right subtrees of any node are balanced binary trees, the difference in height is more than 1.

Figure 2.3 is a balanced binary tree.

3. Equilibrium factor

Definition: the height (depth) difference between the left subtree and the right subtree of a node is the balance factor (BF,Balance Factor) of the node. There is no node with a balance factor greater than 1 in the balanced binary tree. In a balanced binary tree, the balance factor of the node can only be 0, 1 or-1, corresponding to the equal height of the left and right subtrees, respectively, the left subtree is higher and the right subtree is higher.

4. Node structure

Define the node structure of the balanced binary tree:

Typedef struct AVLNode * Tree

Typedef int ElementType

Struct AVLNode {

Int depth; / / depth, where the depth of each node is calculated. Whether it is balanced or not can be determined by comparing the depth.

Tree parent; / / the parent of this node

ElementTypeval; / / Node value

Tree lchild

Tree rchild

AVLNode (int val=0) {

Parent = NULL

Depth = 0

Lchild = rchild = NULL

This- > val=val

}

}

5. The imbalance and adjustment of AVL tree insertion.

Figure 5.1 is a balanced binary tree

Insert node 99 in this balanced binary tree, and the tree structure becomes:

In dynamic figure 5.2, the height of the left subtree of node 66 is 1, the height of the right subtree is 3, the balance factor is-2, and the tree is out of balance.

In dynamic figure 5.2, the tree with node 66 as the parent is called the minimum unbalanced subtree.

Minimum unbalanced subtree: look up in the newly inserted node, and the subtree rooted at the node whose absolute value of the first balance factor is more than 1 is called the minimum unbalanced subtree. In other words, an unbalanced tree, it is possible to have multiple sub-trees out of balance at the same time. At this time, as long as we adjust the smallest unbalanced subtree, we can adjust the unbalanced tree to a balanced tree.

The imbalance adjustment of the balanced binary tree is mainly realized by rotating the minimum unbalanced subtree. There are two ways to deal with it according to the direction of rotation, left-handed and right-handed.

The purpose of rotation is to reduce the height and balance by reducing the height of the whole tree. Whichever tree is high, rotate the tree over there.

5.1 left-handed

Taking figure 5.1.1 as an example, after adding a new node 99, the height of the left subtree of node 66 is 1, the height of the right subtree is 3, and the balance factor is-2. In order to ensure the balance of the tree, node 66 needs to be rotated at this time, because the height of the right subtree is higher than that of the left subtree. The process is as follows:

(1) the right child of the node replaces the position of the node.

(2) the left subtree of the right child becomes the right subtree of the node.

(3) the node itself becomes the left subtree of the right child.

The whole operation flow is shown in figure 5.1.2.

The right child of the node replaces the location of this node-the right child of node 66 is node 77, replacing node 66 with node 77

The left subtree of the right child becomes the right subtree of the node-the left subtree of node 77 is node 75, and move node 75 to the right subtree of node 66

The node itself becomes the left subtree of the right child-node 66 becomes the left subtree of node 77.

5.2 right-handed rotation

The right-handed operation is similar to the left-handed operation, and the operation procedure is:

(1) the left child of the node represents this node.

(2) the right subtree of the left child of the node becomes the left subtree of the node.

(3) regard this node as the right subtree of the left child node.

6. Four ways of inserting nodes into AVL trees

If a node of an AVL tree is A, there are four operations that will make the height difference between the left and right subtrees of A greater than 1, thus destroying the balance of the original AVL tree. There are four situations in which a balanced binary tree inserts nodes:

The specific analysis is as follows:

6.1A left child's left subtree insert node (LL)

You only need to perform a right-handed rotation.

The implementation code is as follows:

/ / L-type adjustment function

/ / return: new parent node

Tree LL_rotate (Tree node) {

/ / node is the nearest unbalanced node to the operating node

Tree parent=NULL,son

/ / get the parent node of the unbalanced node

Parent=node- > parent

/ / get the left child of the unbalanced node

Son=node- > lchild

/ / set the parent pointer of the right child of the son node

If (son- > rchildbirth null) son- > rchild- > parent=node

/ / the left child of the unbalanced node is changed to the right child of son

Node- > lchild=son- > rchild

/ / Update the height information of unbalanced nodes

Update_depth (node)

/ / the unbalanced node becomes the right child of son.

Son- > rchild=node

/ / set the parent of the son to be the parent of the original unbalanced node

Son- > parent=parent

/ / if the unbalanced node is not the root node, start updating the parent node

If (parentless invalid null) {

/ / if the left child of the parent node is an unbalanced node, point to the updated new child son

If (parent- > lchild==node) {

Parent- > lchild=son

} else {

/ / the right child of the parent node is the unbalanced node

Parent- > rchild=son

}

}

/ / set the father of the unbalanced node

Node- > parent=son

/ / Update the height information of son nodes

Update_depth (son)

Return son

}

The right subtree of the right child of 6.2A inserts the node (RR)

You only need to perform a left-handed turn.

The implementation code is as follows:

/ / RR adjustment function

/ / return to the new parent node

Tree RR_rotate (Tree node) {

/ / node is the nearest unbalanced node to the operating node

Tree parent=NULL,son

/ / get the parent node of the unbalanced node

Parent=node- > parent

/ / get the right child of the unbalanced node

Son=node- > rchild

/ / set the parent pointer of the left child of the son node

If (son- > lchildchildbirth null) {

Son- > lchild- > parent=node

}

/ / the right child of the unbalanced node is changed to the left child of son

Node- > rchild=son- > lchild

/ / Update the height information of unbalanced nodes

Update_depth (node)

/ / the unbalanced node becomes the left child of son.

Son- > lchild=node

/ / set the parent of the son to be the parent of the original unbalanced node

Son- > parent=parent

/ / if the unbalanced node is not the root node, start updating the parent node

If (parentless invalid null) {

/ / if the left child of the parent node is an unbalanced node, point to the updated new child son

If (parent- > lchild==node) {

Parent- > lchild=son

} else {

/ / the right child of the parent node is the unbalanced node

Parent- > rchild=son

}

}

/ / set the father of the unbalanced node

Node- > parent=son

/ / Update the height information of son nodes

Update_depth (son)

Return son

}

The right subtree of the left child of 6.3A inserts the node (LR)

If the right subtree E of A's left child node B is inserted into node F, node An is out of balance, as shown in the figure:

The balance factor of An is 2. If the balance factor of An is still adjusted according to right-hand rotation, the changed figure is as follows:

After right-handed adjustment, it is found that the adjusted tree is still out of balance, indicating that the tree can not be rebalanced simply by right-handed operation. Then this insertion requires two steps to make the right child of the left child of the original root node after rotation as the new root node.

(1) the left-handed operation is performed on the left child B of the unbalanced node A, that is, the above-mentioned RR operation.

(2) perform a right-handed operation on the unbalanced node A, that is, the above-mentioned LL operation.

The adjustment process is as follows:

In other words, after these two steps, the right child E node of the left child of the original root node becomes the new root node.

Code implementation:

/ / LR type, rotate first left, then right

/ / return: new parent node

Tree LR_rotate (Tree node) {

RR_rotate (node- > lchild)

Return LL_rotate (node)

}

6.4A right child's left subtree insert node (RL)

The process of inserting a right child into the left node is similar to that of the left child inserting the right node, which requires two steps to make the rotation the left child of the right child of the original root node as the new root node.

(1) perform a right-handed operation on the right child C of the unbalanced node A, that is, the above-mentioned LL operation.

(2) perform a left-handed operation on the unbalanced node A, that is, the above-mentioned RR operation.

In other words, after these two steps, the left child D node of the right child of the original root node becomes the new root node.

Code implementation:

/ / RL type, rotate first right, then left

/ / return: new parent node

Tree RL_rotate (Tree node) {

LL_rotate (node- > rchild)

Return RR_rotate (node)

}

Add:

The auxiliary code for the code implementation of the above four insertion methods is as follows:

/ / Update current depth

Void update_depth (Tree node) {

If (node==NULL) {

Return

} else {

Int depth_Lchild=get_balance (node- > lchild); / / left child depth

Int depth_Rchild=get_balance (node- > rchild); / / depth of right child

Node- > depth=max (depth_Lchild,depth_Rchild) + 1

}

}

/ / get the depth of the current node

Int get_balance (Tree node) {

If (node==NULL) {

Return 0

}

Return node- > depth

}

/ / returns the current balance factor

Int is_balance (Tree node) {

If (node==NULL) {

Return 0

} else {

Return get_balance (node- > lchild)-get_balance (node- > rchild)

}

}

6.5 small summary

In all the unbalanced cases, the operation of the immobilization program is based on finding the minimum unbalanced tree first, then finding the unbalanced category to which it belongs, and then according to the four categories.

LL, LR, RR, and RL have actually provided us with the last node to point the way as the new root. For example, the last root node of LR type is the right child of the left child of the original root, and the last root node of RL type is the left child of the right child of the original root. As long as you keep these four cases in mind, you can quickly deduce all of them.

The most troublesome part of maintaining a balanced binary tree is the maintenance of the balance factor. Readers are advised to draw them themselves according to the pictures and motion pictures provided by Xiao Wu, so that they can have a more perceptual understanding of the operation.

7. Four ways to delete nodes in AVL tree

The deletion operations of the AVL tree and the binary lookup tree are the same, and can be divided into four situations:

(1) Delete leaf node

(2) only the left subtree is deleted.

(3) only the right subtree is deleted.

(4) the deleted node has both left and right subtrees.

However, the AVL tree needs to re-check the balance and correct it after deleting the node. at the same time, the difference between the delete operation and the insert operation is that after the insert operation, only the first unbalanced node that pops up in the insert stack needs to be corrected, while the delete operation needs to correct all the unbalanced nodes in the stack.

The general steps for the delete operation are as follows:

Based on the previous three cases, try to delete the node and put the access node on the stack.

If the attempt is successful, the balance state of the top node of the stack is checked in turn, and the unbalanced node is encountered, that is, the rotation balance is carried out until the stack is empty.

If the attempt to delete fails, it proves to be the fourth case. At this time, first find the smallest node of the right subtree of the deleted node and delete it, and continue to stack the access node.

Then check the balance state and correction of the node at the top of the stack until the stack is empty.

For the correction of the non-equilibrium state caused by the deletion operation, it can be understood as follows: the deletion operation of the left or right subtree is equivalent to the insertion operation of the right or left subtree, and then choose the corresponding rotation corresponding to the four inserted cases.

7.1 Delete leaf node

Processing steps:

①, delete the node directly from the tree

The change of the height of the child tree of ② and its parent node will lead to the change of the balance factor of the parent node, and whether the parent node is out of balance is calculated by retrieving and calculating the parent node upward.

③, if its parent node is not out of balance, then continue to retrieve and calculate whether the parent node of its parent node is out of balance. The judgment of ② is repeated until the root node; if an imbalance is found in the process of upward calculation, the ④ is dealt with.

④, if its parent node is out of balance, judge which type of imbalance is [LL, LR, RR, RL], and balance it accordingly. If the height of the tree with the parent node as the root node changes after the balancing process, the retrieval calculation of ② will continue; if it is highly consistent with the original parent node as the root node, it can indicate that the balance factors of the parent node and ancestor node of the parent node will not change, so you can exit the processing.

Specific numerical demonstration:

7.2-7.3 only the left or right subtree is deleted

Processing steps:

①, replace the location of the original node C with the left subtree (right subtree)

After ② and node C are deleted, the parent node B of C is used as the starting point to retrieve and calculate whether each node (parent, ancestor) is out of balance.

③, if its parent node is not out of balance, then continue to retrieve and calculate whether the parent node of its parent node is out of balance. The judgment of ② is repeated until the root node; if an imbalance is found in the process of upward calculation, the ④ is dealt with.

④, if its parent node is out of balance, judge which type of imbalance is [LL, LR, RR, RL], and balance it accordingly. If the height of the tree with the parent node as the root node changes after the balancing process, the retrieval calculation of ② will continue; if it is highly consistent with the original parent node as the root node, it can indicate that the balance factors of the parent node and ancestor node of the parent node will not change, so you can exit the processing.

7.4 deleted nodes have both left and right subtrees

Processing steps:

①, find deleted Node B, and alternate Node BLR (predecessor or successor node of Node B-Select predecessor here)

②, assign the value of the replacement node BLR to node B, and then replace the position of the replacement node BLR with the left child BLRL of the replacement node BLR

③, starting with BL, the parent node of BLR, to retrieve and calculate whether the parent node or ancestor node is out of balance.

④, if its parent node is not out of balance, then continue to retrieve and calculate whether the parent node of its parent node is out of balance. The judgment of ③ is repeated until the root node; if an imbalance is found in the process of upward calculation, the ⑤ is dealt with.

⑤, if its parent node is out of balance, judge which type of imbalance is [LL, LR, RR, RL], and balance it accordingly. If the height of the tree with the parent node as the root node changes after the balancing process, the retrieval calculation of ② will continue; if it is highly consistent with the original parent node as the root node, it can indicate that the balance factors of the parent node and ancestor node of the parent node will not change, so you can exit the processing.

Is it helpful for you to read the above content? If you want to know more about the relevant knowledge or read more related articles, please follow the industry information channel, thank you for your support.

Welcome to subscribe "Shulou Technology Information " to get latest news, interesting things and hot topics in the IT industry, and controls the hottest and latest Internet news, technology news and IT industry trends.