Algorithm Alley
by Steven Pigeon and Yoshua Bengio


Example 1:  

Procedure Update_M(a : symbol)
 {
  q,p :pointers to leaves ;
  p = find(a) ;  // Leaf/set containing a
  q = find(p's frequency + 1) ; // where to migrate ?

  if (q != NIL) { // somewhere to migrate?
    remove a from p's set ; adjust p's weight ;
    Add a to q's set ; adjust q's weight ;
    Rebalance(q);
    If (p is empty) remove p from the tree ;
    else Rebalance(p's sibling) ;
  } else { // Need a new set
    create a new node t ;
    t's left child = p ;
    t's right child = a new node n ;
    n's set = {a} ;
    n's weight = p's frequency + 1 ;
    n's frequency = p's frequency + 1 ;
    replace the old p in the tree by t ;

    remove a from p's set ;
    p's weight = p's weight - p's frequency ;

    If (p is empty) remove p from the tree ;
    else Rebalance(p's sibling) ;
    
    Rebalance(t) ;
   }
 }


Example 2: 

Procedure Rebalance(t : pointer to leaf) {
  while (t is not the root)
   {
    t's weight = t's right child's weight + 
                 t's left  child's weight ;
    if ( (t's weight > t's sibling's weigth+1) &&
         (t's weight > t's uncle's weight)) 
     then {
           q = parent of parent of t ;
           exchange t with t's uncle ;
           exchange q's right and left child ;
           Update t's ancient parent's weight ;
          }
    t = t's parent ;
   }
 }


2