Binary Search Tree Rearrangements
When discussing the binary search tree, I stated that adding items to a binary tree could make it woefully unbalanced, sometimes even degenerating into a long spindly tree like a linked list.
The problem with this degeneration is not that the binary search tree stops functioning properly (items are still being stored in sorted order), it's that the tree's good efficiency takes a fatal knock if it happens. For a perfectly balanced tree (on average, all parent nodes have two children, and all leaves appear at the same level, plus or minus one), search time, insertion time, and deletion time are all O(log(n)). In other words, if a basic operation takes time t for a tree with 1,000 nodes, it will only take time 2t for a tree with 1,000,000 nodes. On the other hand, for a degenerate tree, the basic operations all become O(n) operations, and the time taken for 1,000,000 nodes would instead be 1,000t.
So, how do we avoid this descent into degenerate trees? The answer is to devise an algorithm that balances the binary search tree during insertion and deletion of items. Before we actually look at balancing algorithms, let's investigate various methods of rearranging binary search trees and then we can use these methods to balance our trees.
Recall that in a binary search tree, for every node, all of the nodes in the left child tree are all less than it, and all those in the right child tree are greater than it. (By a node being less than another, I mean, of course, that the key for the item in the one node is less than the key for the item in the other. However, it is certainly easier to write "one node is less than another" than continually having to refer to the keys for the nodes.) Let's explore this axiom a little more.
Look at the left child of a node in a binary search tree. What do we know about it? Well, it has a left child tree and a right child tree of its own, of course. It is greater than all of the nodes in its left child tree; it is less than all of the nodes in its right child tree. Furthermore, since it is a left child, its parent is greater than all of the nodes in its right child tree. So if we rotate the left child into its parent's position, such that its right child tree becomes the parent's new left child tree, the resulting binary search tree is still valid. Figure 8.3 shows this rotation. In this figure, the little triangles represent child trees that contain zero or more nodes—the exact number is not germane to the rotation algorithm.
Using the original tree, we could write the following inequality: (a<L<b)<P<c. In the new tree, we have a<L<(b<P<c), which, of course, is the same thing when the brackets are removed, because < is commutative. (Read the first inequality as: all the nodes in a are less than L, which is less than all of the nodes in b, and that tree taken as a whole is less than P, which in turn is less than all the nodes in c. We can interpret the second inequality in a similar manner.)
The operation we have just seen is known as a right rotation. It is said to promote the left child L and demote the parent P; in other words L is moved up a level and P is moved down a level. The rotation is said to be about P.
Of course, having seen the right rotation operation, we can easily conceive of another rotation, a left rotation: the rotation that would produce the first tree from the second. A left rotation promotes the right child P and demotes the parent L. Listing 8.17 shows both rotations, but coded from the viewpoint of the node being promoted.
Listing 8.17: Promotion of a node function TtdSplayTree.stPromote(aNode : PtdBinTreeNode)
: PtdBinTreeNode;
Parent : PtdBinTreeNode; begin
- make a note of the parent of the node we're promoting} Parent := aNode^.btParent;
- in both cases there are 6 links to be broken and remade: the node's link to its child and vice versa, the node's link with its parent and vice versa and the parent's link with its parent and vice versa; note that the node's child could be nil} {promote a left child = right rotation of parent} if (Parent~.btChild[ctLeft] = aNode) then begin Parent~.btChild[ctLeft] := aNode~.btChild[ctRight]; if (Parent~.btChild[ctLeft]<>nil) then
Parent~.btChild[ctLeft]~.btParent := Parent; aNode^.btParent := Parent^.btParent; if (aNode~.btParent~.btChild[ctLeft] = Parent) then aNode~.btParent~.btChild[ctLeft] := anode else aNode~.btParent~.btChild[ctRight] := aNode; aNode~.btChild[ctRight] := Parent; Parent^.btParent := aNode; end
{promote a right child = left rotation of parent}
else begin
Parent~.btChild[ctRight] := aNode~.btChild[ctLeft]; if (Parent~.btChild[ctRight]<>nil) then
Parent~.btChild[ctRight]~.btParent := Parent; aNode^.btParent := Parent^.btParent; if (aNode~.btParent~.btChild[ctLeft] = Parent) then aNode~.btParent~.btChild[ctLeft] := anode else aNode~.btParent~.btChild[ctRight] := aNode; aNode~.btChild[ctLeft] := Parent; Parent^.btParent := aNode; end;
{return the node we promoted} Result := aNode; end;
This method is from the splay tree class, which we'll be discussing in a moment, but the essential point to see is the way the links are broken and reformed for both types of promotion. Since the node passed in could be a left child or a right child, with different links to break and reform, this method is essentially an If statement for the two possibilities.
These two rotations rearrange the tree at a local level, but the main node ordering property of a binary search tree remains invariant. For a right rotation, all of the nodes in a move one level closer to the root, those in b stay at the same level and those in c move down by one level. For a left rotation, all of the nodes in a move one level farther from the root, those in b stay at the same level and those in c move up by one level. As you may imagine, assuming the control of some overall balancing algorithm, a series of these two rotations could help rebalance a binary search tree.
Frequently, these two rotations are combined in pairs and used in what are known as zig-zag and zig-zig forms. There are two zig-zag operations and two zig-zig operations. A zig-zag operation consists either of a right rotation followed by a left rotation or a left rotation followed by a right rotation, and the net result of both is to promote a node two levels up. Zig-zig operations, on the other hand, consist of two right rotations or two left rotations performed in sequence. The intent of all these paired operations is to promote a node up two levels.
- Figure 8.4 shows a zig-zag operation starting with a left rotation about P This promotes R and demotes P. In the next step we have a right rotation about G, and this promotes R yet again and demotes G. The overall effect of the zig-zag operation is to balance the tree locally.
Figure 8.5 shows both zig-zig operations since it turns out they are complementary. Notice that in a zig-zig operation you always start out with the upper rotation first.
Figure 8.5: Both zig-zag operations
Figure 8.5 shows both zig-zig operations since it turns out they are complementary. Notice that in a zig-zig operation you always start out with the upper rotation first.
Post a comment