www.delorie.com/gnu/docs/avl/libavl_154.html   search  
Buy GNU books!

GNU libavl 2.0.1

[ < ] [ > ]   [ << ] [ Up ] [ >> ]         [Top] [Contents] [Index] [ ? ]

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:



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