/*-------------------------------------------------------------------------
*
*
* 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 */
#define LEFT(WHO) WHO(Left,Right,LEFT_NODE,RIGHT_NODE,SET_LEFT_NODE,SET_RIGHT_NODE,\
NEGATIVE_FLAG,POSITIVE_FLAG,SET_NEGATIVE_FLAG,SET_POSITIVE_FLAG)
#define RIGHT(WHO) WHO(Right,Left,RIGHT_NODE,LEFT_NODE,SET_RIGHT_NODE,SET_LEFT_NODE,\
POSITIVE_FLAG,NEGATIVE_FLAG,SET_POSITIVE_FLAG,SET_NEGATIVE_FLAG)
#define CREATE_ROTATE(lname,rname,LN,RN,SLN,SRN,NF,PF,SNF,SPF)\
static NODE Rotate##lname##(NODE root, int* depthchanged)\
{\
NODE sec;\
assert(!ISNULLNODE(root) && depthchanged);\
sec=RN(root);\
assert(PF(root));\
if (!(NF(sec)))\
{\
/* printf("single " #lname " rotation ");\
PRINT_NODE(root);\
printf("\n"); */\
SRN(root,LN(sec));\
SLN(sec,root);\
if (PF(sec))\
{\
SET_ZERO_FLAG(root);\
SET_ZERO_FLAG(sec);\
*depthchanged=1;\
return sec;\
}\
SPF(root);\
SNF(sec);\
return sec;\
}\
{\
NODE third=LN(sec);\
/* printf("double " #lname " rotation ");\
PRINT_NODE(root);\
printf("\n");*/\
SLN(sec,RN(third));\
SRN(root,LN(third));\
SRN(third,sec);\
SLN(third,root);\
*depthchanged=1;\
if (NF(third))\
{\
SPF(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);\
SNF(root);\
SET_ZERO_FLAG(third);\
return third;\
}\
}
LEFT(CREATE_ROTATE);
RIGHT(CREATE_ROTATE);
#define CREATE_HANG(lname,rname,LN,RN,SLN,SRN,NF,PF,SNF,SPF)\
{\
SLN(root,AddAvlNode_aux(LN(root),who,&heightchanged));\
if (heightchanged)\
{\
if (ZERO_FLAG(root))\
{\
SNF(root);\
*depthchanged=1;\
return root;\
}\
if (PF(root))\
{\
SET_ZERO_FLAG(root);\
return root;\
}\
heightchanged=0;\
root=Rotate##rname##(root,&heightchanged);\
/* als heightchanged verandert is; is root kleiner\
* geworden */\
if (!heightchanged) *depthchanged=1;\
return root;\
}\
return root;\
}
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) LEFT(CREATE_HANG);
/* 3. hang rechts aan */
RIGHT(CREATE_HANG);
}
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;
}
#define CREATE_FREEDOM(lname,rname,LN,RN,SLN,SRN,NF,PF,SNF,SPF)\
static NODE lname##Freedom_aux(NODE cur,NODE *placetostorefreedom,int*heightchanged)\
{\
assert(!ISNULLNODE(cur));\
assert(placetostorefreedom);\
if (ISNULLNODE(RN(cur)))\
{\
if (ISNULLNODE(LN(cur)))\
{\
*placetostorefreedom=cur;\
*heightchanged=1;\
return NULLNODE;\
}\
*heightchanged=1;\
*placetostorefreedom=cur;\
return LN(cur);\
}\
{\
int takverkleind=0;\
SRN(cur,##lname##Freedom_aux(RN(cur),placetostorefreedom,&takverkleind));\
if (takverkleind) \
{\
if (NF(cur)) return Rotate##rname##(cur,heightchanged);\
if (PF(cur))\
{\
SET_ZERO_FLAG(cur);\
*heightchanged=1;\
return cur;\
}\
SNF(cur);\
return cur;\
}\
return cur;\
}\
}\
\
static NODE Get##lname##Freedom(NODE root, NODE*placetostorefreedom,int *heightchanged)\
{\
NODE lname;\
assert(!ISNULLNODE(root));\
assert(!ISNULLNODE(LN(root)));\
assert(heightchanged);\
assert(placetostorefreedom);\
##lname##=LN(root);\
if (!ISNULLNODE(RN(##lname##)))\
return lname##Freedom_aux(##lname##,placetostorefreedom,heightchanged);\
*heightchanged=1;\
*placetostorefreedom=##lname##;\
return LN(##lname##);\
}
LEFT(CREATE_FREEDOM)
RIGHT(CREATE_FREEDOM)
#define CREATE_ZAK(lname,rname,LN,RN,SLN,SRN,NF,PF,SNF,SPF)\
SLN(root,DeleteAvlNode_naardelete(LN(root),wie,&takkleiner));\
if (takkleiner)\
{\
if (NF(root))\
{\
SET_ZERO_FLAG(root);\
*heightchanged=1;\
return root;\
}\
if (ZERO_FLAG(root))\
{\
SPF(root);\
return root;\
}\
return Rotate##lname##(root,heightchanged);\
}\
return root;
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 */ RIGHT(CREATE_ZAK);
case 1: /* root>wie */ LEFT(CREATE_ZAK);
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