Mastering Algorithms With C - Kyle Loudon [92]
Complexity
O (lg n), where n is the number of nodes in the binary search tree.
Name
bistree_remove
Synopsis
int bistree_remove(BisTree *tree, const void *data);
Return Value
0if removing the node is successful, or -1 otherwise.
Description
Removes the node matching data from the binary search tree specified by tree. In actuality, this operation only performs a lazy removal, in which the node is simply marked as hidden. Thus, no pointer is returned to the data matching data. The data in the tree must remain valid even after it has been removed. Consequently, the size of the binary search tree, as returned by bistree_size, does not decrease after removing a node. This approach is explained further in the implementation and analysis section.
Complexity
O (lg n), where n is the number of nodes in the binary search tree.
Name
bistree_lookup
Synopsis
int bistree_lookup(const BisTree *tree, void **data);
Return Value
0if the data is found in the binary search tree, or -1 otherwise.
Description
Determines whether a node matches data in the binary search tree specified as tree. If a match is found, data points to the matching data in the binary search tree upon return.
Complexity
O (lg n), where n is the number of nodes in the binary search tree.
Name
bistree_size
Synopsis
int bistree_size(const BisTree *tree);
Return Value
Number of nodes in the tree.
Description
Macro that evaluates to the number of nodes in the binary search tree specified by tree.
Complexity
O (1)
Implementation and Analysis of Binary Search Trees
As described earlier, binary search trees perform well only if the tree remains balanced. Unfortunately, keeping a binary search tree balanced is a more difficult problem than it may at first appear. Nevertheless, there are a few clever approaches one can take. One of the best approaches is to implement the tree as an AVL tree.
An AVL (Adel'son-Vel'skii and Landis) tree is a special type of binary tree that stores an extra piece of information with each node: its balance factor . The balance factor of a node is the height of the subtree rooted at its left child minus the height of the subtree rooted at its right child (see Figure 9.9). As nodes are inserted, an AVL tree adjusts itself so that all balance factors stay +1, -1, or 0. A subtree whose root node has a balance factor of +1 is said to be left-heavy. A subtree whose root node has a balance factor of -1 is said to be right-heavy. A subtree whose root node has a balance factor of is considered balanced. By keeping its subtrees nearly balanced, an AVL tree stays approximately balanced overall.
Figure 9.9. An AVL tree, including balance factors
The basic means of searching and inserting nodes in an AVL tree is the same as described earlier. However, when we insert a node into an AVL tree, we have some additional work to do after the node descends to its appropriate position. First, we must account for the change in balance factors that occurs as a result of the insertion. Also, if any balance factor becomes ±2, we must rebalance the tree from that point down, which is done by performing an operation called a rotation.
Rotations in AVL Trees
A rotation rebalances part of an AVL tree by rearranging nodes while preserving the relationship wherein the left is smaller than the parent and the parent is smaller than the right, which must be maintained for the tree to remain a binary search tree. After the rotation, the balance factors of all nodes in the rotated subtree are +1, -1, or 0.
There are only four types of rotations that ever have to be performed. These are the LL (left-left), LR (left-right), RR (right-right), and RL (right-left) rotations. The functions rotate_left and rotate_right, presented later in Example 9.5, implement each of these rotations. To understand when we need to apply each