Mastering Algorithms With C - Kyle Loudon [93]
LL rotation
We perform an LL, or left-left, rotation when x lies in the left subtree of the left subtree of A (see Figure 9.10). Let left be the left child of A. To perform an LL rotation, we set the left pointer of A to the right child of left, the right pointer of left to A, and the pointer referencing A to left. After the rotation, we set the balance factors of both A and left to 0. All other balance factors do not change.
Figure 9.10. An LL rotation in an AVL tree
LR rotation
We perform an LR, or left-right, rotation when x lies in the right subtree of the left subtree of A (see Figure 9.11). Let left be the left child of A and grandchild be the right child of left. To perform an LR rotation, we set the right child of left to the left child of grandchild, the left child of grandchild to left, the left child of A to the right child of grandchild, the right child of grandchild to A, and finally the pointer referencing A to grandchild.
Figure 9.11. An LR rotation in an AVL tree
Adjusting the balance factors of nodes after an LR rotation depends on the original balance factor of grandchild. Figure 9.12 illustrates the three cases to consider. If the original balance factor of grandchild was +1, we set the balance factor of A to -1 and left to 0. If the original balance factor of grandchild was 0, we set the balance factors of both A and left to 0. If the original balance factor of grandchild was -1, we set the balance factor of A to and that of left to +1. In all cases, we set the new balance factor of grandchild to 0. All other balance factors do not change.
Figure 9.12. Updating balance factors after an LR rotation in an AVL tree
RR rotation
We perform an RR, or right-right, rotation when x lies in the right subtree of the right subtree of A. The RR rotation is symmetric to the LL rotation. Let right be the right child of A. To perform an RR rotation, we set the right pointer of A to the left child of right, the left pointer of right to A, and the pointer referencing A to right. After the rotation, we set the balance factors of both A and left to 0. All other balance factors do not change.
RL rotation
We perform an RL, or right-left, rotation when x lies in the left subtree of the right subtree of A. The RL rotation is symmetric to the LR rotation. Let right be the right child of A and grandchild be the left child of right. To perform an RL rotation, we set the left child of right to the right child of grandchild, the right child of grandchild to right, the right child of A to the left child of grandchild, the left child of grandchild to A, and finally the pointer referencing A to grandchild.
Adjusting the balance factors of nodes after an RL rotation depends on the original balance factor of grandchild. There are three cases to consider. If the original balance factor of grandchild was +1, we set the balance factor of A to and that of right to -1. If the original balance factor of grandchild was 0, we set the balance factors of both A and left to 0. If the original balance factor of grandchild was -1, we set the balance factor of A to +1 and that of left to 0. In all cases, we set the new balance factor of grandchild to 0. All other balance factors do not change. These adjustments are symmetric to those shown in Figure 9.12 for an LR rotation.
The structure BisTree is the binary search tree data structure. A good way to implement a binary search tree is to use the binary tree abstract datatype discussed earlier. Thus, BisTree is implemented as a typedef to BiTree (see Example 9.4). In addition to simplicity, using a typedef has the benefit of making the binary search tree somewhat polymorphic, just as described for stacks and queues (see Chapter 6). This means that we can use binary tree operations on a binary search tree in addition to those operations defined specifically for binary search trees.
Since