How about another algorithm?

------------------------------------------------------

A NODE contains a VALUE entry, which holds a number, and the entries 
CHILD0 and CHILD1, which either point to a NODE or point to nothing.

ADD(X, ROOT):
   1. If ROOT points to nothing then
     1. Let OUT = a new NODE.
     2. Let OUT.VALUE = X.
     3. Return OUT.
   2. If ROOT.VALUE < X then
     1. Let Y = ROOT.VALUE
     2. Let T = ROOT.CHILD0.
     2. Let ROOT.VALUE = X.
     3. Let ROOT.CHILD0 = ADD(Y, ROOT.CHILD1).
     4. Let ROOT.CHILD1 = T.
     5. Return ROOT.
   else
     1. Let T = ROOT.CHILD0.
     2. Let ROOT.CHILD0 = ADD(X, ROOT.CHILD1).
     3. Let ROOT.CHILD1 = T.
     4. Return ROOT.

------------------------------------------------------

Data of type HASH is either 'NODE' with a NUMBER value called VALUE and 
a HASH value named CHILD0 and a HASH value named CHILD1, or 'NULL'.

ADD(X, NULL) = HASH (VALUE = X, CHILD0 = NULL, CHILD1 = NULL)
ADD(X, NODE A B) = HASH (VALUE = if X < Y then Y else X, CHILD0 = ADD(if 
X < Y then X else Y, B), CHILD1 = A)

------------------------------------------------------

Notice: First program is long and thin. Second program is short and fat. 
(My, my... line wrapping!)

-- 
http://blog.orphi.me.uk/
http://www.zazzle.com/MathematicalOrchid*

Post a reply to this message