Node = stucture/record/class

Bitstring Value

int Position

Node[2] Next

Search(Node Parent, Bitstring Key)

Child = Parent.Next[Key[Parent.Position]]

if Child.Position <= Parent.Position then

comment: The node Child is an anscestor of the node Parent

Return Key == Child.Value

else Search(Child, Key)

Insert(Node Parent, Bitstring Key)

Child = Parent.Next[Key[Parent.Position]]

if Child.Position <= Parent.Position then

i=0

while key[i] == Child.Value[i] do i++

if i > Parent.Position then

comment: Add a new node as a child of Parent

temp = Child

Parent.Next[Key[Parent.Position]] = new Node

temp2 = Parent.Next[Key[Parent.Position]]

temp2.String=Key

temp2.Position = i

temp2.Next[Key[i]]=temp2

temp2.Next[temp.Value[i]] = temp

else

comment: The new node will have to be an ancestor of Parent in the tree

Insert2(Root, Key, i)

Else Insert(Child, Key)

Insert2(Node Parent, Bitstring Key, int Place)

Child = Parent.Next[Key[Parent.Position]]

if Parent.Position <= Place <= Child.Position then

comment: This is the right place to insert the new node

temp = new Node

Parent.Next[Key[Parent.Position]] = temp

temp.Value=Key

temp.Position=Place

temp.Next[Key[Place]] = temp

temp.Next[1 - Key[Place]] = Child

else Insert2(Child, Key, Place)