Part 3

As I mentioned earlier we're going to only modify our tree at the root. That means if the element we want to modify isn't at the root we have to get it there. To do this we use two different kinds of tree rotations: basic "Rotate" and "Z"; both of which can be done "Left" or "Right".

A RotateLeft returns a tree with the current root's left child as the root. This can be done by either a plain Rotate Left or, if there is an existing right child, the reverse of a Z Right:

[If it looks all squished up against the left side it's because Google Sites eats the tabs in the code blocks sometimes.]

static private ImTree<TK, TV> RotateLeft(ImTree<TK, TV> root)
{

if (root == null)

return null;

if (root.l_ == null)

return root;

if (root.r_ != null){

// reverse ZRight

//

// O L

// / \ / \

// L R --> ll R

// / \ / \ / \

// ll lr rl rr O rr

// / \

// lr rl

return new ImTree<TK, TV>

(

root.l_.k_, root.l_.v_,

root.l_.l_,

new ImTree<TK, TV>

(

root.r_.k_, root.r_.v_,

new ImTree<TK, TV>(root.k_, root.v_, root.l_.r_, root.r_.l_),

root.r_.r_

)

);

} else{

// O L

// / x / \

// L --> ll O

// / \ / x

// ll lr lr

//

return new ImTree<TK, TV>

(

root.l_.k_, root.l_.v_,

root.l_.l_,

new ImTree<TK, TV>

(

root.k_, root.v_,

root.l_.r_,

root.r_ // is null

)

);

}

}

Typically we prefer to do a Z operation over a Rotate as it tends to keep the tree in better balance when the next operation is another RotateLeft (which is fairly typical if the tree is out of balance).

A ZLeft looks like this:

static private ImTree<TK, TV> ZLeft(ImTree<TK, TV> root)
{

if (root == null)

return null;

if (root.l_ == null)

return root;

if (root.l_.r_ == null)

return root;

// make l_.r_ the root

// O

// / \ LR

// L r / \

// / \ ---> L O

// ll LR / \ / \

// / \ ll lrl lrr r

// lrl lrr

return new ImTree<TK, TV>

(

root.l_.r_.k_, root.l_.r_.v_,

new ImTree<TK, TV>(root.l_.k_, root.l_.v_, root.l_.l_, root.l_.r_.l_),

new ImTree<TK, TV>(root.k_, root.v_, root.l_.r_.r_, root.r_)

);

}

Z operations are used when the node we're trying to raise to the root is in-between a child of the current root and the current root. RotateRight and ZRight are the reverse of RotateLeft and ZLeft.

You might have noticed the ASCII diagrams and the mixed case. Capital case means the node changes, and lower case means it stays the same. O is the root, and other nodes are referred to by their path (L is left, LL is left's left, etc.)

Using RotateLeft, RotateRight, ZLeft, and ZRight it's possible to move any node to the root. If we maintain left as lower than root as lower than right we can search for a node like so:

static private ImTree<TK, TV> Root(ImTree<TK, TV> root, TK k)
{

for (;;){

var cmp = k.CompareTo(root.k_);

if (cmp == 0)

return root;

if (cmp > 0) // k is to the right

{

if (root.r_ != null){

var cmpr = k.CompareTo(root.r_.k_);

if (cmpr == 0)

return RotateRight(root);

if (cmpr > 0) // k is to the right or temp.r_

{

if (root.r_.r_ != null){

root = SkipRight(root);

continue;

}

// temp.r_ is a lower bound, return it

return RotateRight(root);

}

// k is inbetween temp and temp.r_

if (root.r_.l_ != null){

root = ZRight(root);

continue;

}

return root; // nothing between temp_.k_ and k in the tree, return lower bound.

}

return root; // nothing greater than temp_.k_ in the tree, return lower bound.

} else // k is to the left

{

if (root.l_ != null){

var cmpl = k.CompareTo(root.l_.k_);

if (cmpl == 0)

return RotateLeft(root);

if (cmpl < 0) // k is to the left of temp.l_

{

if (root.l_.l_ != null){

root = SkipLeft(root);

continue;

}

// left is a lower bound, return it.

return RotateLeft(root);

}

// k is inbetween temp and temp.l_;

if (root.l_.r_ != null){

root = ZLeft(root);

continue;

}

 

return RotateLeft(root); // nothing between temp.l_.k_ and k in the tree, return lower bound.

}

return root; // nothing lower than temp.k_ in the tree, return lowest

}

}

}

SkipLeft and SkipRight move LL and RR to the root, and are the subject of the next installment.