/*-------------------------------------------------------------------------
*
*
* AVLTREE 1.0
* (c) Werner Van Belle aug 95
*
*
* NODE AddAvlNode(NODE root, NODE who)
* Voegt who toe aan root, geeft als resultaat de nieuwe root weer
* O(log2n)
*
* NODE SearchAvlNode(NODE root, SEARCH_DATA watte)
* Zoekt watte op in root, geeft als resultaat de bijhorende node weer
* O(<log2n)
*
* NODE DeleteAvlNode(NODE root, SEARCH_DATA wie)
* Verwijdert wie uit root, geeft als resultaat de nieuwe root weer
* O(log2n)
*
* int ValidAvlTree(NODE root)
* Controleert of de AVL-tree wel aan de AVL-voorwaarde voldoet. Hier
* wordt niet gecontroleerd of de linkerkinderen kleiner zijn dan root
* en de rechterkinderen groter zijn dan root
* O(n)
*
* int AvlTreeCount(NODE root)
* geeft weer hoeveel elementen in de tree steken.
* O(n)
*
* int AvlDepth(NODE root)
* geeft de maximum diepte van een pad doorheen de tree weer.
* O(n)
*
* void PrintAvlTree(NODE root, int diepte)
* Print de avltree. Deze functie is enkel aanwezig als PRINT_NODE
* gedefinieerd is. Het output formaat is
* .rechterkind
* rootzelf
* .linkerkind
*/
#include <assert.h>
/* #define DEBUG_NODES */
static NODE RotateLeft(NODE root, int* depthchanged)
{
NODE sec;
assert(!ISNULLNODE(root));
assert(depthchanged);
sec=RIGHT_NODE(root);
assert(POSITIVE_FLAG(root));
if (!(NEGATIVE_FLAG(sec)))
{
#ifdef DEBUG_NODES
printf("single left rotation ");
PRINT_NODE(root);
printf("\n");
#endif
SET_RIGHT_NODE(root,LEFT_NODE(sec));
SET_LEFT_NODE(sec,root);
if (POSITIVE_FLAG(sec))
{
SET_ZERO_FLAG(root);
SET_ZERO_FLAG(sec);
*depthchanged=1;
return sec;
}
SET_POSITIVE_FLAG(root);
SET_NEGATIVE_FLAG(sec);
return sec;
}
{
NODE third=LEFT_NODE(sec);
#ifdef DEBUG_NODES
printf("double left rotation ");
PRINT_NODE(root);
printf("\n");
#endif
SET_LEFT_NODE(sec,RIGHT_NODE(third));
SET_RIGHT_NODE(root,LEFT_NODE(third));
SET_RIGHT_NODE(third,sec);
SET_LEFT_NODE(third,root);
*depthchanged=1;
if (NEGATIVE_FLAG(third))
{
SET_POSITIVE_FLAG(sec);
SET_ZERO_FLAG(root);
SET_ZERO_FLAG(third);
return third;
}
if (ZERO_FLAG(third))
{
SET_ZERO_FLAG(sec);
SET_ZERO_FLAG(third);
SET_ZERO_FLAG(root);
return third;
}
SET_ZERO_FLAG(sec);
SET_NEGATIVE_FLAG(root);
SET_ZERO_FLAG(third);
return third;
}
}
static NODE RotateRight(NODE root, int* depthchanged)
{
NODE sec;
assert(!ISNULLNODE(root));
assert(depthchanged);
sec=LEFT_NODE(root);
assert(NEGATIVE_FLAG(root));
if (!(POSITIVE_FLAG(sec)))
{
#ifdef DEBUG_NODES
printf("single right rotation ");
PRINT_NODE(root);
printf("\n");
#endif
SET_LEFT_NODE(root,RIGHT_NODE(sec));
SET_RIGHT_NODE(sec,root);
if (NEGATIVE_FLAG(sec))
{
SET_ZERO_FLAG(root);
SET_ZERO_FLAG(sec);
*depthchanged=1;
return sec;
}
SET_NEGATIVE_FLAG(root);
SET_POSITIVE_FLAG(sec);
return sec;
}
#ifdef DEBUG_NODES
printf("double right rotation ");
PRINT_NODE(root);
printf("\n");
#endif
{
NODE third=RIGHT_NODE(sec);
SET_RIGHT_NODE(sec,LEFT_NODE(third));
SET_LEFT_NODE(root,RIGHT_NODE(third));
SET_LEFT_NODE(third,sec);
SET_RIGHT_NODE(third,root);
*depthchanged=1;
if (NEGATIVE_FLAG(third))
{
SET_ZERO_FLAG(sec);
SET_POSITIVE_FLAG(root);
SET_ZERO_FLAG(third);
return third;
}
if (ZERO_FLAG(third))
{
SET_ZERO_FLAG(sec);
SET_ZERO_FLAG(third);
SET_ZERO_FLAG(root);
return third;
}
SET_NEGATIVE_FLAG(sec);
SET_ZERO_FLAG(third);
SET_ZERO_FLAG(root);
return third;
}
}
static NODE AddAvlNode_aux(NODE root, NODE who, int* depthchanged)
/* geeft de nieuwe root weer */
{
int CompareResult, heightchanged=0;
assert(depthchanged);
#ifdef DEBUG_NODES
printf("add ");
PRINT_NODE(who);
printf(" to root ");
if (ISNULLNODE(root)) printf("(null)");
else PRINT_NODE(root);
printf("\n");
#endif
if (ISNULLNODE(who)) return root;
SET_LEFT_NODE(who,NULLNODE);
SET_RIGHT_NODE(who,NULLNODE);
SET_ZERO_FLAG(who);
if (ISNULLNODE(root))
{
*depthchanged=1;
return who;
}
CompareResult=COMPARE_ADD_DATA(root,who);
/* 1. geen dubbels */
assert(CompareResult);
/* 2. hang links aan */
if (CompareResult==1)
{
SET_LEFT_NODE(root,AddAvlNode_aux(LEFT_NODE(root),who,&heightchanged));
if (heightchanged)
{
if (ZERO_FLAG(root))
{
SET_NEGATIVE_FLAG(root);
*depthchanged=1;
return root;
}
if (POSITIVE_FLAG(root))
{
SET_ZERO_FLAG(root);
return root;
}
heightchanged=0;
root=RotateRight(root,&heightchanged);
/* als heightchanged verandert is; is root kleiner
* geworden */
if (!heightchanged) *depthchanged=1;
return root;
}
return root;
}
/* 3. hang rechts aan */
SET_RIGHT_NODE(root,AddAvlNode_aux(RIGHT_NODE(root),who,&heightchanged));
if (heightchanged)
{
if (ZERO_FLAG(root))
{
SET_POSITIVE_FLAG(root);
*depthchanged=1;
return root;
}
if (NEGATIVE_FLAG(root))
{
SET_ZERO_FLAG(root);
return root;
}
heightchanged=0;
root=RotateLeft(root,&heightchanged);
if (!heightchanged) *depthchanged=1;
}
return root;
}
NODE AddAvlNode(NODE root, NODE who)
/* geeft de nieuwe root weer */
{
int depthchanged=0;
return AddAvlNode_aux(root,who,&depthchanged);
}
NODE SearchAvlNode(NODE root, SEARCH_DATA watte)
/* geeft het resultaat van het zoeken weer, NULLNODE indien niet gevonden */
{
int CompareResult;
while(root)
{
CompareResult=COMPARE_SEARCH_DATA(root,watte);
if (CompareResult==0) return root;
if (CompareResult==1) root=LEFT_NODE(root);
else root=RIGHT_NODE(root);
}
return NULLNODE;
}
static NODE LeftFreedom_aux(NODE cur,NODE *placetostorefreedom,int*heightchanged)
{
assert(!ISNULLNODE(cur));
assert(placetostorefreedom);
if (ISNULLNODE(RIGHT_NODE(cur)))
{
if (ISNULLNODE(LEFT_NODE(cur)))
{
*placetostorefreedom=cur;
*heightchanged=1;
return NULLNODE;
}
*heightchanged=1;
*placetostorefreedom=cur;
return LEFT_NODE(cur);
}
{
int takverkleind=0;
SET_RIGHT_NODE(cur,LeftFreedom_aux(RIGHT_NODE(cur),placetostorefreedom,&takverkleind));
if (takverkleind)
{
if (NEGATIVE_FLAG(cur)) return RotateRight(cur,heightchanged);
if (POSITIVE_FLAG(cur))
{
SET_ZERO_FLAG(cur);
*heightchanged=1;
return cur;
}
SET_NEGATIVE_FLAG(cur);
return cur;
}
return cur;
}
}
static NODE GetLeftFreedom(NODE root, NODE*placetostorefreedom,int *heightchanged)
{
NODE left;
assert(!ISNULLNODE(root));
assert(!ISNULLNODE(LEFT_NODE(root)));
assert(heightchanged);
assert(placetostorefreedom);
left=LEFT_NODE(root);
if (!ISNULLNODE(RIGHT_NODE(left)))
return LeftFreedom_aux(left,placetostorefreedom,heightchanged);
*heightchanged=1;
*placetostorefreedom=left;
return LEFT_NODE(left);
}
static NODE RightFreedom_aux(NODE cur,NODE *placetostorefreedom,int*heightchanged)
{
assert(!ISNULLNODE(cur));
assert(placetostorefreedom);
if (ISNULLNODE(LEFT_NODE(cur)))
{
if (ISNULLNODE(RIGHT_NODE(cur)))
{
*placetostorefreedom=cur;
*heightchanged=1;
return NULLNODE;
}
*heightchanged=1;
*placetostorefreedom=cur;
return RIGHT_NODE(cur);
}
{
int takverkleind=0;
SET_LEFT_NODE(cur,RightFreedom_aux(LEFT_NODE(cur),placetostorefreedom,&takverkleind));
if (takverkleind)
{
if (POSITIVE_FLAG(cur)) return RotateLeft(cur,heightchanged);
if (NEGATIVE_FLAG(cur))
{
SET_ZERO_FLAG(cur);
*heightchanged=1;
return cur;
}
SET_POSITIVE_FLAG(cur);
return cur;
}
return cur;
}
}
static NODE GetRightFreedom(NODE root, NODE*placetostorefreedom,int *heightchanged)
{
NODE right;
assert(!ISNULLNODE(root));
assert(!ISNULLNODE(RIGHT_NODE(root)));
assert(heightchanged);
assert(placetostorefreedom);
right=RIGHT_NODE(root);
if (!ISNULLNODE(LEFT_NODE(right)))
return RightFreedom_aux(right,placetostorefreedom,heightchanged);
*heightchanged=1;
*placetostorefreedom=right;
return RIGHT_NODE(right);
}
static NODE DeleteAvlNode_naardelete(NODE root, SEARCH_DATA wie, int* heightchanged)
{
int CompareResult,takkleiner=0;
assert(heightchanged);
if (ISNULLNODE(root)) return root;
CompareResult=COMPARE_SEARCH_DATA(root,wie);
switch (CompareResult)
{
case -1: /* root<wie */
SET_RIGHT_NODE(root,DeleteAvlNode_naardelete(RIGHT_NODE(root),wie,&takkleiner));
if (takkleiner)
{
if (POSITIVE_FLAG(root))
{
SET_ZERO_FLAG(root);
*heightchanged=1;
return root;
}
if (ZERO_FLAG(root))
{
SET_NEGATIVE_FLAG(root);
return root;
}
return RotateRight(root,heightchanged);
}
return root;
case 1: /* root>wie */
SET_LEFT_NODE(root,DeleteAvlNode_naardelete(LEFT_NODE(root),wie,&takkleiner));
if (takkleiner)
{
if (NEGATIVE_FLAG(root))
{
SET_ZERO_FLAG(root);
*heightchanged=1;
return root;
}
if (ZERO_FLAG(root))
{
SET_POSITIVE_FLAG(root);
return root;
}
return RotateLeft(root,heightchanged);
}
return root;
case 0: /* root==wie */
/* nu een opnderscheid maken voor welke kinderen de
* root heeft */
if (ISNULLNODE(LEFT_NODE(root)) && ISNULLNODE(RIGHT_NODE(root)))
{
DELETE_NODE(root);
*heightchanged=1;
return NULLNODE;
}
if (ISNULLNODE(LEFT_NODE(root)))
{
NODE rechter;
rechter=RIGHT_NODE(root);
assert(POSITIVE_FLAG(root));
assert(!ISNULLNODE(rechter));
assert(ISNULLNODE(LEFT_NODE(rechter)));
assert(ISNULLNODE(RIGHT_NODE(rechter)));
*heightchanged=1;
DELETE_NODE(root);
return rechter;
}
if (ISNULLNODE(RIGHT_NODE(root)))
{
NODE linker;
linker=LEFT_NODE(root);
assert(NEGATIVE_FLAG(root));
assert(!ISNULLNODE(linker));
assert(ISNULLNODE(LEFT_NODE(linker)));
assert(ISNULLNODE(RIGHT_NODE(linker)));
DELETE_NODE(root);
*heightchanged=1;
return linker;
}
if (POSITIVE_FLAG(root))
{
NODE freedom;
SET_RIGHT_NODE(root,GetRightFreedom(root,&freedom,heightchanged));
SET_LEFT_NODE(freedom,LEFT_NODE(root));
SET_RIGHT_NODE(freedom,RIGHT_NODE(root));
if (*heightchanged) SET_ZERO_FLAG(freedom);
else SET_POSITIVE_FLAG(freedom);
DELETE_NODE(root);
return freedom;
}
if (NEGATIVE_FLAG(root))
{
NODE freedom;
SET_LEFT_NODE(root,GetLeftFreedom(root,&freedom,heightchanged));
SET_LEFT_NODE(freedom,LEFT_NODE(root));
SET_RIGHT_NODE(freedom,RIGHT_NODE(root));
if (*heightchanged) SET_ZERO_FLAG(freedom);
else SET_NEGATIVE_FLAG(freedom);
DELETE_NODE(root);
return freedom;
}
if (ZERO_FLAG(root))
{
NODE freedom;
int takverkleind=0;
SET_LEFT_NODE(root,GetLeftFreedom(root,&freedom,&takverkleind));
SET_LEFT_NODE(freedom,LEFT_NODE(root));
SET_RIGHT_NODE(freedom,RIGHT_NODE(root));
if (takverkleind) SET_POSITIVE_FLAG(freedom);
else SET_ZERO_FLAG(freedom);
DELETE_NODE(root);
return freedom;
}
default: exit(57);
}
}
NODE DeleteAvlNode(NODE root, SEARCH_DATA wie)
{
int heightchanged=0;
return DeleteAvlNode_naardelete(root,wie,&heightchanged);
}
int AvlDepth(NODE root)
{
int l,r;
if (ISNULLNODE(root)) return 0;
l=AvlDepth(LEFT_NODE(root));
r=AvlDepth(RIGHT_NODE(root));
if (l>r) return l+1;
return r+1;
}
int ValidAvlTree(NODE root)
{
if (ISNULLNODE(root)) return 1;
if (!ValidAvlTree(LEFT_NODE(root))) return 0;
if (!ValidAvlTree(RIGHT_NODE(root))) return 0;
if (POSITIVE_FLAG(root))
return (AvlDepth(LEFT_NODE(root))==(AvlDepth(RIGHT_NODE(root))-1));
if (NEGATIVE_FLAG(root))
return (AvlDepth(LEFT_NODE(root))==(AvlDepth(RIGHT_NODE(root))+1));
return (AvlDepth(LEFT_NODE(root))==AvlDepth(RIGHT_NODE(root)));
}
int AvlTreeCount(NODE root)
{
if (ISNULLNODE(root)) return 0;
return 1+AvlTreeCount(LEFT_NODE(root))+AvlTreeCount(RIGHT_NODE(root));
}
#ifdef PRINT_NODE
void PrintAvlTree(NODE root, int diepte)
{
int t,l,r;
if (ISNULLNODE(root)) return;
PrintAvlTree(RIGHT_NODE(root),diepte+1);
for(t=diepte;t>0;t--) printf(".");
PRINT_NODE(root);
l=AvlDepth(LEFT_NODE(root));
r=AvlDepth(RIGHT_NODE(root));
printf(" left=%d, right=%d, count=%d ",l,r,AvlTreeCount(root));
if ((abs(l-r)>1) ||
(l<r && !POSITIVE_FLAG(root)) ||
(l>r && !NEGATIVE_FLAG(root)) ||
(l==r && !ZERO_FLAG(root)))
printf("*********");
printf("\n");
PrintAvlTree(LEFT_NODE(root),diepte+1);
}
#endif