Re: Questions about WOOD

["Mark A. Tapia" <markt@dgp.toronto.edu>]

In response to your question on Wood and the preservation of the parent
pointer, here are my thoughts.

You can always use the finger technique outlined in Knuth's Art of
Computer Programming - the volume on sorting. If you want to search
in a standard binary tree, I'll outline the steps. 

First some assumptions.

1. Conceptually, each node in the tree has several fields, some
   containing links (pointers) to other nodes, others with actual
   data.
2. The "left" field is either nil (no left field) or points to the
   top node of the left branch of the tree. All nodes in this rooted
   subtree contain keys that are less than the "current node".
3. The "right" field similarly points to the ppossibly empty rooted
   subtree with keys greater than the current node.
4. The current node contains information on the balancing factor
   (left-taller, right-taller, balanced) for rebalancing when nodes
   are added or deleted from some part of the entire tree.
5. The current node also contains a key and the value associated with
   the key. The key could be a word, the value its definition.

6. Optionally, add two fields min and max pointing to the nodes in the
   rooted tree based at the node. The min pointer is a pointer to the
   node with the smallest key (or null if there is not left branch).
   Similarly, max points to the node with the highest key (or null
   if there is no right branch).

To search for a key, maintain a finger pointing into the tree. The finger
contains a list with several fields, the direction  of the turn (left, right
or none), the node itself, and maybe more information. You push nodes
onto the stack as you travel down deeper into the tree. You can retract the
finger by poping the stack until you get to the relevant portion of
the tree. You can use the min/max nodes cleverly, by checking the min
node only when you change from turning right to turning left and by
checking the max node only when you change from turnining left to turning
right. Obviously, you have to check both min/max when you start at the
top of the tree.

For an implementation that supports btrees in this form (red/black),
see pub/MCL2/contrib/btree.sit.hqx available by anonymous ftp
from cambridge.apple.com.

mark