www.delorie.com/gnu/docs/avl/libavl_154.html

search

	Buy GNU books!

GNU libavl 2.0.1

9.2 Rotations

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:

Exercises:

1. Write functions for right and left rotations in threaded BSTs, analogous to those for unthreaded BSTs developed in Exercise 4.3-2. [answer]