Dr. Dobb's Journal October 1998
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) ;
}
}