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