Buy GNU books!
|[ < ]||[ > ]||[ << ]||[ Up ]||[ >> ]||[Top]||[Contents]||[Index]||[ ? ]|
Rotations are just as useful in threaded BSTs as they are in unthreaded ones. We do need to re-examine the idea, though, to see how the presence of threads affect rotations.
A generic rotation looks like this diagram taken from 5.3 Rotations:
Any of the subtrees labeled a, b, and c may be in fact threads. In the most extreme case, all of them are threads, and the rotation looks like this:
As you can see, the thread from X to Y, represented by subtree b, reverses direction and becomes a thread from Y to X following a right rotation. This has to be handled as a special case in code for rotation. See Exercise 1 for details.
On the other hand, there is no need to do anything special with threads originating in subtrees of a rotated node. This is a direct consequence of the locality and order-preserving properties of a rotation (see section 5.3 Rotations). Here's an example diagram to demonstrate. Note in particular that the threads from A, B, and C point to the same nodes in both trees:
1. Write functions for right and left rotations in threaded BSTs, analogous to those for unthreaded BSTs developed in Exercise 4.3-2. [answer]
|webmaster||delorie software privacy|
|Copyright © 2003 by The Free Software Foundation||Updated Jun 2003|