• Choose a category
• All
• Classic-Fiction

By Root 1429 0

factor to AVL_BALANCED. Otherwise, we compare the data to be inserted with that of the current node to determine the direction in which to move. We proceed as we described earlier for inserting a node into a binary search tree. When the data we are inserting is less than that of the current node we are traversing, we make a recursive call that moves us to the left. When the data is greater, we make a recursive call that moves us to the right. Once we locate the point at which to make the insertion, we allocate an AvlNode structure and insert it into the tree as the appropriate child of the current node. If the data to be inserted matches that of a node hidden as a result of being removed, we destroy the data currently in the node, insert the new data in its place, and mark the node as no longer hidden. In this case, rebalancing is not required.

Except after replacing a previously hidden node, we next determine how the balance of the tree has been affected so that we can make repairs if necessary. Whether we have inserted the node to the left or right, we set balanced to to indicate that the insertion may have upset the balance of the tree. This causes a switch statement to be executed that adjusts the balance factor of the current node. Adjusting the balance factor of the current node may, in turn, upset the balance factors of nodes higher in the tree. Thus, as we reenter each activation of insert, we update the balance factor of the node traversed at that level, provided balanced is still 0. Once we determine that no more updates are required, we set balanced to to inform previous activations of this decision.

The switch statements that determine how to update balance factors also determine when rotations should be performed. The actual function we call to perform the rotation, either rotate_left or rotate_right, determines the type of rotation to apply: either LL or LR if we call rotate_left, or RR or RL if we call rotate_right. Since rotations change the balance factors of nodes, each rotation function also adjusts balance factors. The best way to understand the process of updating balance factors and performing rotations is to trace through the example in Figure 9.13.

Figure 9.13. Inserting nodes into an AVL tree

Earlier it was mentioned that the runtime complexity of inserting a node into a perfectly balanced binary search tree is O (lg n). However, since an AVL tree keeps itself only approximately balanced, one might wonder how this affects performance. It turns out that the worst-case running time of inserting a node into an AVL tree is T (n) = 1.5k lg n, where k is some constant, n is the number of nodes in the tree, and T (n) = k lg n is the time to insert a node into a perfectly balanced binary tree. Just as with insertion into a perfectly balanced tree, this results in a runtime complexity of O (lg n). However, the constant of 1.5 does influence performance somewhat in practice.

bistree_remove

The bistree_remove operation removes a node from a binary search tree (see Example 9.5). For this operation, we apply a rather simplistic heuristic termed lazy removal , in which we hide nodes instead of actually removing them. To hide a node, we set the hidden member of its AvlNode structure to 1. If we insert the same data again later, we simply make the node visible again by setting its hidden member back to (see bistree_insert). In practice, this approach is acceptable if we do not expect to remove many nodes relative to the number we insert. If we plan to remove a large number of nodes, we might consider actually removing the node and adjusting the tree. To locate the node to hide, we recursively call hide until we reach the node we are looking for. Once we hide the node, there is no need to rebalance the tree because we did not change its structure. Thus, we set balanced to 1.

The analysis of removing a node from an AVL tree is the same as for inserting a node. Thus, the runtime complexity of bistree_remove is O (lg n).

bistree_lookup

The bistree_lookup operation searches for a node within a binary