Part 4

Software Development‎ > ‎Immutable Trees‎ > ‎

If you only use RotateLeft/RotateRight to move the nodes around you'll end up with a tree with linear hieght because all nodes to the left will hang off left childs, and all nodes to the right hang off right childs. Basically you degrade into a doubly linked list.

To avoid this whenever we detect that we'd do two RotateLeft (or Right) operations in a row we in fold the tree over such that the depth of the opposing child is only pushed down one rather than down two. If you consider the worst case tree (no internal nodes) as the input you can see that the result will contain internal nodes. This operation is what (over time) balances the tree to logarithmic height.

static private ImTree<TK, TV> SkipLeft(ImTree<TK, TV> root)

{

// O LL

// / \ / \

// L r lll O

// / \ ---> / \

// LL lr L r

// / \ / \

// lll llr llr lr

return new ImTree<TK, TV>

(

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

root.l_.l_.l_,

new ImTree<TK, TV>

(

root.k_, root.v_,

new ImTree<TK, TV>

(

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

root.l_.l_.r_,

root.l_.r_

),

root.r_

)

);

}

static private ImTree<TK, TV> SkipRight(ImTree<TK, TV> root)

{

// O RR

// / \ / \

// l R O rrr

// / \ ---> / \

// rl RR l R

// / \ / \

// rrl rrr rl rrl

return new ImTree<TK, TV>

(

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

new ImTree<TK, TV>

(

root.k_, root.v_,

root.l_,

new ImTree<TK, TV>

(

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

root.r_.l_,

root.r_.r_.l_

)

),

root.r_.r_.r_

);

}

/* This skip functions attempt to convert linear sections (e.g. a sequence of left pointers) into a tree
 * of half the height. Successive application results in the O-L or O-R pair hanging off-angle as the right
 * left rotation happens.  e.g. a sequence of all left like this:
 * 
 *    6
 *    |
 *    5
 *    |
 *    4
 *    |
 *    3
 *    |
 *    2
 *    |
 *    1
 *    
 * when rooting 0 will become:
 * 
 *    0-2-4-6
 *      | | |
 *      1 3 5
 *
 * This is where the log performance of the tree comes from. Since rooting uses Skips to keep trying to
 * half the height of the traversed areas the tree self-balances to a minimal height over time.
 * 
 */