AvlTree.borg
AvlTree.borg
`*----------------------------------------------------------------------------
`* Avl Trees
`*----------------------------------------------------------------------------
`* author: Borg: Werner Van Belle nov 01
`* C: Werner Van Belle aug 95
`*----------------------------------------------------------------------------
{
MakeAvlTree(COMPARE, PRINT)::
{
` --------------
` node type
` --------------
RIGHT::POSITIVE::1;
LEFT::NEGATIVE::-1;
ROOTNODE:NULLNODE::void;
ZERO::0;
NewNode(w)::[NULLNODE,NULLNODE,0,w];
IsNullNode(x)::is_void(x);
Flag(x,val)::x[3] = val;
SetFlag(x,val)::x[3] := val;
Node(x,w)::x[(w+3)//2];
SetNode(x,w,v)::x[(w+3)//2]:=v;
inv_Flag(x,val)::Flag(x,-val);
inv_SetFlag(x,val)::SetFlag(x,-val);
inv_Node(x,w)::Node(x,-w);
inv_SetNode(x,w,v)::SetNode(x,-w,v);
COMPARE_ADD_DATA(w1,w2)::COMPARE(w1[4],w2[4]);
COMPARE_SEARCH_DATA(w,key)::COMPARE(w[4],key);
` --------------
` internals
` --------------
SearchAvlNode(root, watte)::
` geeft het resultaat van het zoeken weer, NULLNODE indien niet gevonden */
if (IsNullNode(root), root,
if ((CompareResult:COMPARE_SEARCH_DATA(root,watte))=0, root,
if (CompareResult=1, SearchAvlNode(Node(root,LEFT),watte),
SearchAvlNode(Node(root,RIGHT),watte))));
Rotate(root, depthchanged, Node, SetNode, Flag, SetFlag)::
{
sec:Node(root,RIGHT);
if (!Flag(sec,NEGATIVE),
{
SetNode(root,RIGHT,Node(sec,LEFT));
SetNode(sec,LEFT,root);
if (Flag(sec,POSITIVE),
{
SetFlag(root,ZERO);
SetFlag(sec, ZERO);
depthchanged[1]:=true
},
{
SetFlag(root,POSITIVE);
SetFlag(sec,NEGATIVE)
});
sec
},
{
third:Node(sec,LEFT);
SetNode(sec,LEFT,Node(third,RIGHT));
SetNode(root,RIGHT,Node(third,LEFT));
SetNode(third,RIGHT,sec);
SetNode(third,LEFT,root);
depthchanged[1]:=true;
if (Flag(third,NEGATIVE),
{
SetFlag(sec,POSITIVE);
SetFlag(root,ZERO)
},
if (Flag(third,ZERO),
{
SetFlag(sec,ZERO);
SetFlag(root,ZERO)
},
{
SetFlag(sec,ZERO);
SetFlag(root,NEGATIVE)
}));
SetFlag(third,ZERO);
third})
};
RotateLeft(root, depthchanged)::Rotate(root, depthchanged, Node,SetNode,Flag,SetFlag);
RotateRight(root,depthchanged)::Rotate(root, depthchanged, inv_Node,inv_SetNode,inv_Flag,inv_SetFlag);
AddAvlNode_aux(root, who, depthchanged)::
{
` functie die iets links of rechts hangt, afhankelijk van de situatie
Hang(rotation, Node, SetNode, Flag, SetFlag)::
{
SetNode(root,LEFT,AddAvlNode_aux(Node(root,LEFT),who,heightchanged));
if (heightchanged[1],
if (Flag(root,ZERO),
{
SetFlag(root,NEGATIVE);
depthchanged[1]:=true
},
if (Flag(root,POSITIVE),
SetFlag(root,ZERO),
{
heightchanged[1]:=false;
root:=rotation(root,heightchanged);
` als heightchanged verandert is; is root kleiner geworden
if (!heightchanged[1], depthchanged[1]:=true)
})));
root
};
HangLeft()::Hang(RotateRight, Node, SetNode, Flag, SetFlag);
HangRight()::Hang(RotateLeft, inv_Node, inv_SetNode, inv_Flag, inv_SetFlag);
heightchanged:[false];
if (IsNullNode(who),root,
{
SetNode(who,LEFT,NULLNODE);
SetNode(who,RIGHT,NULLNODE);
SetFlag(who,ZERO);
if (IsNullNode(root),
{
depthchanged[1]:=true;
who
},
{
CompareResult:COMPARE_ADD_DATA(root,who);
if (CompareResult=0, error("No duplicates please"),
if (CompareResult=1, HangLeft(), HangRight()))
})})};
DeleteAvlNode_naardelete(root, wie, heightchanged)::
{
freedom:void;
Freedom_aux(cur, heightchanged, FreedomAux, Rotate,Node,SetNode,Flag,SetFlag)::
if (IsNullNode(Node(cur,RIGHT)),
{
freedom:=cur;
heightchanged[1]:=true;
if (IsNullNode(Node(cur,LEFT)),
NULLNODE,
Node(cur,LEFT))
},
{
takverkleind:[false];
SetNode(cur,RIGHT,FreedomAux(Node(cur,RIGHT),takverkleind));
if (takverkleind[1],
if (Flag(cur,NEGATIVE), Rotate(cur,heightchanged),
if (Flag(cur,POSITIVE),
{
SetFlag(cur,ZERO);
heightchanged[1]:=true;
cur
},
{
SetFlag(cur,NEGATIVE);
cur})),
cur)
});
LeftFreedom_aux(c,heightchanged)::Freedom_aux(c,heightchanged,LeftFreedom_aux,RotateRight,Node,SetNode,Flag,SetFlag);
RightFreedom_aux(c,heightchanged)::Freedom_aux(c,heightchanged,RightFreedom_aux,RotateLeft,inv_Node,inv_SetNode,inv_Flag,inv_SetFlag);
GetFreedom(heightchanged, FreedomAux, Node)::
{
nname:Node(root,LEFT);
if (!IsNullNode(Node(nname,RIGHT)),
FreedomAux(nname,heightchanged),
{
heightchanged[1]:=true;
freedom:=nname;
Node(nname,LEFT)
})
};
GetLeftFreedom(heightchanged)::GetFreedom(heightchanged,LeftFreedom_aux,Node);
GetRightFreedom(heightchanged)::GetFreedom(heightchanged,RightFreedom_aux,inv_Node);
takkleiner:[false];
Zak(Rotate, Node, SetNode,Flag,SetFlag)::
{
SetNode(root,LEFT,DeleteAvlNode_naardelete(Node(root,LEFT),wie,takkleiner));
if (takkleiner[1],
{
if (Flag(root,NEGATIVE),
{
SetFlag(root,ZERO);
heightchanged[1]:=true;
root
},
if (Flag(root,ZERO),
{
SetFlag(root,POSITIVE);
root
},
Rotate(root,heightchanged)))
}, root)
};
ZakLeft()::Zak(RotateLeft,Node,SetNode,Flag,SetFlag);
ZakRight()::Zak(RotateRight,inv_Node,inv_SetNode,inv_Flag,inv_SetFlag);
if (IsNullNode(root), root,
{
CompareResult:COMPARE_SEARCH_DATA(root,wie);
if (CompareResult = -1, ZakRight(), ` root
if (CompareResult = 1, ZakLeft(), ` root>wie
if (IsNullNode(Node(root,LEFT)) & IsNullNode(Node(root,RIGHT)),
{
heightchanged[1]:=true;
NULLNODE
},
if (IsNullNode(Node(root,LEFT)),
{
rechter:Node(root,RIGHT);
heightchanged[1]:=true;
rechter
},
if (IsNullNode(Node(root,RIGHT)),
{
linker:Node(root,LEFT);
heightchanged[1]:=true;
linker
},
if (Flag(root,POSITIVE),
{
SetNode(root,RIGHT,GetRightFreedom(heightchanged));
SetNode(freedom,LEFT,Node(root,LEFT));
SetNode(freedom,RIGHT,Node(root,RIGHT));
if (heightchanged[1],SetFlag(freedom,ZERO),SetFlag(freedom,POSITIVE));
freedom
},
if (Flag(root,NEGATIVE),
{
SetNode(root,LEFT,GetLeftFreedom(heightchanged));
SetNode(freedom,LEFT,Node(root,LEFT));
SetNode(freedom,RIGHT,Node(root,RIGHT));
if (heightchanged[1], SetFlag(freedom,ZERO), SetFlag(freedom,NEGATIVE));
freedom
},
if (Flag(root,ZERO),
{
takverkleind:[false];
SetNode(root,LEFT,GetLeftFreedom(takverkleind));
SetNode(freedom,LEFT,Node(root,LEFT));
SetNode(freedom,RIGHT,Node(root,RIGHT));
if (takverkleind[1], SetFlag(freedom,POSITIVE), SetFlag(freedom,ZERO));
freedom
},
error("exit(57)")))))))))})
};
AvlDepth(root)::
if (IsNullNode(root), 0,
{
l:AvlDepth(Node(root,LEFT));
r:AvlDepth(Node(root,RIGHT));
if (l>r, l+1, r+1)
});
ValidAvlTree(root)::
if (IsNullNode(root), true,
if (!ValidAvlTree(Node(root,LEFT)), false,
if (!ValidAvlTree(Node(root,RIGHT)), false,
if (Flag(root,POSITIVE), AvlDepth(Node(root,LEFT))=(AvlDepth(Node(root,RIGHT))-1),
if (Flag(root,NEGATIVE), AvlDepth(Node(root,LEFT))=(AvlDepth(Node(root,RIGHT))+1),
AvlDepth(Node(root,LEFT))=AvlDepth(Node(root,RIGHT)))))));
AvlTreeCount(cell)::
if (IsNullNode(cell),0,
1+AvlTreeCount(Node(cell,LEFT))
+AvlTreeCount(Node(cell,RIGHT)));
PrintAvlTree(root, diepte)::
if (!IsNullNode(root),
{
PrintAvlTree(Node(root,RIGHT),diepte+".");
display(diepte);
display(if(root[3]=1, "+ ", if (root[3]= -1, "- ", "0 ")) + PRINT(root[4]));
l:AvlDepth(Node(root,LEFT));
r:AvlDepth(Node(root,RIGHT));
display(" left="+text(l)+" right="+text(r)+" count="+text(AvlTreeCount(root)));
if ((abs(l-r)>1) |
((lr) & !Flag(root,NEGATIVE)) |
((l=r) & !Flag(root,ZERO)), display("**********"));
display(eoln);
PrintAvlTree(Node(root,LEFT),diepte+".")
});
ForeachAvlTree(root, lambda)::
if (!IsNullNode(root),
{
ForeachAvlTree(Node(root,LEFT),lambda);
lambda(root[4]);
ForeachAvlTree(Node(root,RIGHT),lambda)
});
` --------------
` user functions
` --------------
Add(data):: ` O(log2n)
ROOTNODE:=AddAvlNode_aux(ROOTNODE,NewNode(data),[false]);
Search(key):: ` O(
{
node:SearchAvlNode(ROOTNODE,key);
if (IsNullNode(node),void,node[4])
};
Delete(key):: ` O(log2n)
ROOTNODE:=DeleteAvlNode_naardelete(ROOTNODE,key,[false]);
Foreach(lambda)::
ForeachAvlTree(ROOTNODE,lambda);
Print()::
PrintAvlTree(ROOTNODE,"");
Count()::
AvlTreeCount(ROOTNODE);
SetRoot(n)::
ROOTNODE:=n;
GetRoot()::
ROOTNODE;
Exist(name)::
!IsNullNode(SearchAvlNode(ROOTNODE,name));
clone()
};
AddAndDel()::
{
compareword(w1,w2)::if (w1>w2, 1, if(w1=w2, 0, -1));
printword(w)::display(w);
a:MakeAvlTree(compareword,printword);
i:100;
while(i>0,
{
a.Add("text"+text(i)+" ");
i:=i-1
});
a.Print();
i:100;
display("========================"+eoln);
while(i>0,
{
a.Delete("text"+text(i)+" ");
i:=i-2
});
a.Print();
i:99;
display("========================"+eoln);
while(i>0,
{
a.Delete("text"+text(i)+" ");
i:=i-2
});
a.Print()
};
"AddAndDel()"
}