AVL-Balanced Binary Tree Processes MetalBase 5.0 ------------------------------------------------------------------------------- MetalBase 3.2 used straight, unbalanced binary-trees to keep track of data. 4.0 and up have migrated to AVL-balancing; the routines for keeping a tree in balance, and rebalancing it when needed, are below. I developed these by hand, just from common sense; if there's a flaw, it hasn't shown up after hundreds of thousands of uses. AVL balancing means that, at any node in a tree, the number of records to the left of a node is almost exactly equal to the number on the right; to make it, work, they can be off by 1. So the following are balanced: ___5___ ___4___ _2_ _8_ _2_ _6_ 1 4 7 1 3 5 7 And the following aren't (the first is too heavy to the left at 5, the second is too heavy to the right at 4): ___5___ ___4___ _2_ 8 6_ 1 4 7 This kind of balancing ensures, in effect, that only the last two levels of the tree can ever have any empty nodes... so a tree will always stay as shallow as possible, providing the following speeds for algorithms: Worst-Case Best-Case ------------ --------- SEARCH...........O(ln(n))........O(1) ADD..............O(n * ln (n))...O(ln (n)) UPDATE...........O(n * ln (n))...O(ln (n)) DELETE...........O(n * ln (n))...O(ln (n)) I'm particularly interested in getting a better rebalancing routine; mine is the elegant solution, but I can't believe it's the only, or the fastest. If you have any ideas, lemme know. ------------------------------------------------------------------------------- Note that some names have changed [to protect the innocent?] :) (*) indicates a procedure must be called once for each index ------------------------------------------------------------------------------- update (rcd) : * del_preserve (rcd, ) change records instance on disk * link (rcd, ) delete (rcd) : * del_preserve (rcd, ) remove (rcd) add (data) : rcd = append (data) * link (rcd, ) link (rcd) : *| drop (rcd, ) (these are called, one after the other, *| check (rcd, top, ) for each index in the relation) drop (pos, index) : for (loc = top; ; ) { dir = compare (rec (loc), rec(pos), index) -- (-1,0,1) loc->balance += dir; if ( loc->child[dir] == 0 ) { loc->child[dir] = rec rec->parent = loc break } } check (st, ed, index) : for (loc = st; ; loc=loc->parent) { if ( rec (loc) ->unbalanced(index) ) balance (loc, index) if (loc == ed) break; }; unlink (loc, index) : ch=loc->left || loc->right if (loc->pardir) loc->parent->right = ch; else loc->parent->left = ch; if (ch) ch->parent = loc->parent, ch->pardir = loc->pardir; /* DO NOT re-read loc */ for (dir=loc->pardir,tmp=loc->parent;tmp!=0;dir=tmp->pardir,tmp=tmp->parent) tmp->balance -= (dir == 1) ? 1 : -1; balance (loc, index) : if (! rep = find_seq (loc, rec(loc)->balance) ) ERROR!!! -- bal>0?Next:Prev rp=rep->parent unlink (rep, index) replace (loc, rep, index) -- Replace LOC with REP drop (loc, index) if (rp != loc) check (rp, rep) /* re-read loc */ check (loc->parent, rep) delete_preserve (bad) : bp = bad->parent if (bad->balance != 0) rep = find_seq (bad, bad->balance) --bal>0?Next:Prev else if (! rep = find_seq (bad, toggle (lastmove))) rep = find_seq (bad, toggle (lastmove)) if (! rep) unlink (bad) else { rp= rep->parent; unlink (rep) replace (bad, rep) if (rp != bad) check (rp, bp) } check (bp, top) replace (old, new) : new->left_c = old->left_c; new->right_ = old->right_; new->parent = old->parent; par=new->parent; new->pardir = old->pardir; par->[pardir]_c = new; new->left_c->parent = new; new->right_c->parent = new;