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


GNU libavl 2.0.1

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

15.2 Rotations

Let's consider how rotations work in PBSTs. Here's the usual illustration of a rotation:

rotation

As we move from the left side to the right side, rotating right at Y, the parents of up to three nodes change. In any case, Y's former parent becomes X's new parent and X becomes Y's new parent. In addition, if b is not an empty subtree, then the parent of subtree b's root node becomes Y. Moving from right to left, the situation is reversed.

See also: [ Cormen 1990], section 14.2.

Exercises:

1. Write functions for right and left rotations in BSTs with parent pointers, analogous to those for plain BSTs developed in Exercise 4.3-2. [answer]


  webmaster   donations   bookstore     delorie software   privacy  
  Copyright 2003   by The Free Software Foundation     Updated Jun 2003