An implementation of AVL tree. Three files Ð a test program; the header file for the AVL class; the AVL implementation. ++++++++++++ /* main.cp, a test program. */ #include #include #include #include #include #include "tree.h" const int kTESTMAX = 5000; const int ADD_OK = 0; const int ADD_DUP = 1; const int FIND_OK = 2; const int FIND_EMPTY = 3; const int REMOVE_OK = 4; const int REMOVE_FAIL = 5; class TextItem : public KeyedItem { public: TextItem(const char* info, long k); ~TextItem(); long Key(void) const; void PrintOn(ostream& out) const; private: char *fText; long fk; }; TextItem::TextItem(const char *info, long k) { fk = k; fText = new char[strlen(info) + 1]; strcpy(fText, info); } TextItem::~TextItem() { delete fText; } void TextItem::PrintOn(ostream& out) const { out << "[ " << fText << ", " << fk << "] "; }; long TextItem::Key(void) const { return fk; } long gCounters[6]; short gUsed[kTESTMAX]; AVLTree gTree; void ReportProblem(long k) { cout << "Key value involved " << k << endl; cout << "TreeSize " << gTree.NumItems() << endl; #ifdef DEBUGGING cout << "Print tree?"; char ch; cin >> ch; if(ch == 'y') gTree.PrintTree(); #endif } void Initialize(int testsize) { for(int i = 0; i < testsize; i++) gUsed[i] = 0; for(int j = 0; j < 6; j++) gCounters[j] = 0; } TextItem *MakeATextItem(int testsize) { int r = rand() % testsize; return new TextItem("XXXX", r); } void Add(int testsize) { TextItem *t = MakeATextItem(testsize); long k = t->Key(); if(gUsed[k] ==0) { /* Should get a successful insert */ if(gTree.Add(t) != 0) gCounters[ADD_OK]++; else { cout << "Got a 'duplicate' response when should have been able to add" << endl; ReportProblem(k); exit(1); } gUsed[k] = 1; } else { /* Should get a duplicate message */ if(gTree.Add(t) == 0) { gCounters[ADD_DUP]++; delete t; } else { cout << "Failed to notice a duplicate" << endl; ReportProblem(k); exit(1); } } } void Find(int testsize) { long k = rand() % testsize; KeyedItem *d = gTree.Find(k); if(gUsed[k] == 0) { /* Find operation should have failed failed */ if(d == NULL) gCounters[FIND_EMPTY]++; else { cout << "Found a thing that wasn't there" << endl; ReportProblem(k); exit(1); } } else { /* Find operation should succeed */ if(d != NULL) gCounters[FIND_OK]++; else { cout << "Failed to find a data item" << endl; ReportProblem(k); exit(1); } } } void Remove(int testsize) { long k = rand() % testsize; KeyedItem *d = gTree.Remove(k); if(gUsed[k] == 0) { /* Remove operation should have failed failed */ if(d == NULL) gCounters[REMOVE_FAIL]++; else { cout << "Removed a thing that wasn't there" << endl; ReportProblem(k); exit(1); } } else { /* Remove operation should succeed */ if(d != NULL) { gCounters[REMOVE_OK]++; delete d; gUsed[k] = 0; } else { cout << "Failed to find and remove a data item" << endl; ReportProblem(k); exit(1); } } } void AutoTest() { int testsize; int runsize; cout << "Enter control parameters for auto-test "; cin >> testsize >> runsize; assert(testsize > 1); assert(testsize < kTESTMAX); Initialize(testsize); for(int i=0; i < testsize / 2; i++) Add(testsize); for(int j=0; j < runsize; j++) { int r = rand() % 4; switch(r) { case 0: Add(testsize); break; case 1: Find(testsize); break; case 2: case 3: Remove(testsize); break; } } cout << "Test complete, counters of actions: " << endl; for(i = 0; i < 6; i++) cout << i << ": " << gCounters[i] << endl; } void HandTest(void) { KeyedItem* d; for(;;) { char ch; cout << "Action (a = Add, d = Delete, f = Find, p = Print Tree, q = Quit) : "; cin >> ch; switch (ch) { case 'a': case 'A': { long key; char buff[100]; cout << "Key : " ; cin >> key; cout << "Name : "; cin >> buff; d = new TextItem(buff, key); if(gTree.Add(d) != 0) cout << "Inserted OK" << endl; else { cout << "Duplicate " << endl; delete d; } } break; case 'd': case 'D': { long bad; cout << "Enter key of record to be removed"; cin >> bad; d = gTree.Remove(bad); if(d == NULL) cout << "No such record" << endl; else { cout << "Removing " << *d << endl; delete d; } } break; case 'f': case 'F': { long sought; cout << "Enter key of record required : "; cin >> sought; d = gTree.Find(sought); if(d == NULL) cout << "There is no record with that key" << endl; else cout << *d << endl; } break; case 'p': case 'P': gTree.PrintTree(); break; case 'q': case 'Q': return; default: cout << "?" << endl; } } } int main() { cout << "Hand test (h) or auto" << endl; char ch; cint >> ch; if(ch == h) HandTest(); else AutoTest(); return 0; } ++++++++++ /* the header file, tree.h */ #include #define DEBUGGING class KeyedItem { public: virtual ~KeyedItem() { } virtual long Key(void) const = 0; virtual void PrintOn(ostream& out) const { } }; inline ostream& operator<<(ostream& out, const KeyedItem& d) { d.PrintOn(out); return out; } class AVLTreeNode; class AVLTree { public: AVLTree(); ~AVLTree(); int NumItems(void) const; int Add(KeyedItem* d); KeyedItem *Find(long key); KeyedItem *Remove(long key); #ifdef DEBUGGING void PrintTree(void) const; #endif private: /* Auxiliary functions for insertion and consequent rebalancing */ void Insert1(KeyedItem* d, AVLTreeNode*& t); void Rebalance_Left_Long(AVLTreeNode*& t); void Rebalance_Right_Long(AVLTreeNode*& t); /* Auxiliary functions for deletion and consequent rebalancing */ void Delete1(long bad_key, AVLTreeNode*& t); void Check_balance_after_Left_Delete(AVLTreeNode*& t); void Check_balance_after_Right_Delete(AVLTreeNode*& t); void Rebalance_Left_Short(AVLTreeNode*& t); void Rebalance_Right_Short(AVLTreeNode*& t); void DeleteRec(AVLTreeNode*& t); void Del(AVLTreeNode*& t, AVLTreeNode*& r); #ifdef DEBUGGING void PrintTree1(AVLTreeNode* t, short depth) const; #endif AVLTreeNode *fRoot; int fNum; KeyedItem *fReturnItem; int fResizing; int fAddOK; }; inline int AVLTree::NumItems(void) const { return fNum; } ++++++++++ /* the implementation file tree.cp */ #include #include "tree.h" const short CHANGED_SIZE = 1; const short UNCHANGED = 0; enum eBALANCE { LEFT_LONG, EVEN, RIGHT_LONG }; class AVLTreeNode { public: AVLTreeNode(KeyedItem *d); AVLTreeNode*& LeftLink(void); AVLTreeNode*& RightLink(void); long Key(void) const; eBALANCE Balance(void) const; KeyedItem *Data(void) const; void Replace(KeyedItem *d); void ResetBalance(eBALANCE newsetting); private: eBALANCE fbalance; KeyedItem *fData; AVLTreeNode *fLeft; AVLTreeNode *fRight; }; AVLTreeNode::AVLTreeNode(KeyedItem *d) { fbalance = EVEN; fLeft = fRight = NULL; fData = d; } inline eBALANCE AVLTreeNode::Balance(void) const { return fbalance; } inline long AVLTreeNode::Key(void) const { return fData->Key(); } inline KeyedItem *AVLTreeNode::Data(void) const { return fData; } inline void AVLTreeNode::Replace(KeyedItem *d) { fData = d; } inline AVLTreeNode*& AVLTreeNode::LeftLink(void) { return fLeft; } inline AVLTreeNode*& AVLTreeNode::RightLink(void) { return fRight; } inline void AVLTreeNode::ResetBalance(eBALANCE newsetting) { fbalance = newsetting; } AVLTree::AVLTree() { fRoot = 0; fNum = 0; } AVLTree::~AVLTree() { } #ifdef DEBUGGING void AVLTree::PrintTree1(AVLTreeNode *t,short depth) const { int i; if(t == NULL) return; PrintTree1(t->RightLink(),depth+2); for(i = 0; i < depth; i++) cout << ' '; cout << "( " << t->Key() << ", "; switch(t->Balance()) { case LEFT_LONG: cout << "left long)"; break; case EVEN: cout << "even)"; break; case RIGHT_LONG: cout << "right long)"; break; } cout << endl; PrintTree1(t->LeftLink(),depth+2); } void AVLTree::PrintTree(void) const { PrintTree1(fRoot,0); } #endif /* Insert1: given pointer to data item to be inserted reference to a pointer to a node that will contain data item */ void AVLTree::Insert1(KeyedItem* d, AVLTreeNode*& t) { /* NEW NEW NEW NEW NEW NEW NEW */ /* Item is not present, make a node for it */ if(t == NULL) { t = new AVLTreeNode(d); fResizing = CHANGED_SIZE; fAddOK = 1; return; } /* - - - - - - - - - - - - - - - - - - - - - */ /* Item may be present: */ /* DUPLICATE DUPLICATE DUPLICATE DUPLICATE */ /* Not dealing with case where new item has */ /* a key equal to an existing key */ if(d->Key() == t->Key()) { // cout << "Duplicate entry ignored\n"; fResizing = UNCHANGED; return; } /* LEFT LEFT LEFT LEFT LEFT LEFT LEFT */ /* If new item's key smaller than that of current */ /* tree node, insert in left branch */ if(d->Key() < t->Key()) { Insert1(d,t->LeftLink()); if(fResizing == CHANGED_SIZE) { switch (t->Balance()) { case LEFT_LONG: /* Left branch from current node was already */ /* larger than right branch, and it has grown. */ /* Have to rebalance */ Rebalance_Left_Long(t); t->ResetBalance(EVEN); /* Handling of tree growth now completed. Clear */ /* the fResizing flag because calling proc. */ /* won't also need to do any balancing. */ fResizing = UNCHANGED; break; case EVEN: /* This node which was even is now left LONG */ t->ResetBalance(LEFT_LONG); /* Effect of adding the left node has to be */ /* propagated upward. Leave fResizing as CHANGED_SIZE. */ /* Caller has to sort out whether more work to do. */ break; case RIGHT_LONG: /* Node back in balance */ t->ResetBalance(EVEN); /* No need for caller to consider further rebalancing */ /* because work just done here. So clear the info */ /* about tree growing larger. */ fResizing = UNCHANGED; break; } } return; } /* RIGHT RIGHT RIGHT RIGHT RIGHT RIGHT */ /* otherwise must insert new item in right branch */ Insert1(d,t->RightLink()); if(fResizing == CHANGED_SIZE) { switch (t->Balance()) { case LEFT_LONG: t->ResetBalance(EVEN); fResizing = UNCHANGED; break; case EVEN: t->ResetBalance(RIGHT_LONG); break; case RIGHT_LONG: /* Right branch from current node was already */ /* larger than left branch, and it has grown. */ /* Have to rebalance */ Rebalance_Right_Long(t); t->ResetBalance(EVEN); fResizing = UNCHANGED; break; } } return; } void AVLTree::Rebalance_Left_Long(AVLTreeNode*& t) { /* Two cases: LL : node is "left - long" and its left-child is also "left - long" LR : node is "left - long" but its left-child is "right - long" they differ in how pointers are re-threaded to get the balance back. */ /* Check balance of left child */ if((t->LeftLink())->Balance() == LEFT_LONG) { /* addition of node 1 has made tree rooted at 10 unbalanced (t)10 goes to 4 / \ / \ / \ / \ 4 12 2 10 / \ / / \ 2 6 1 6 12 / 1 */ AVLTreeNode *tptr = t->LeftLink(); /* tptr points to node with 4 */ /* change 10's leftlink to point to node with 6 */ t->LeftLink() = tptr->RightLink(); /* put 10 right of 4 */ tptr->RightLink() = t; t->ResetBalance(EVEN); /* Node with 10 should be even */ /* move "root" to 4 */ t = tptr; } else { /* 80 just added to a tree to get this unbalanced thing: viewed from node 100 which is left-long and whose left branch has just grown more. 50 is in this case right-long. 100 / \ / \ / \ 50 150 / \ 25 75 / \ ? 80 convert to: 75 / \ / \ 50 100 / / \ 25 80 150 */ AVLTreeNode *tptr = t->LeftLink(); /* tptr points to node with 50 */ AVLTreeNode *tptr2 = tptr->RightLink(); /* points to node with 75 */ /* left of 75, here ? could be a NULL or a link, reattached on right of 50 */ tptr->RightLink() = tptr2->LeftLink(); /* 50 attached left of 75 */ tptr2->LeftLink() = tptr; /* left link of 100 reset to point to 80 */ t->LeftLink() = tptr2->RightLink(); /* right of 75 attached to 100 */ tptr2->RightLink() = t; t->ResetBalance( (tptr2->Balance() == LEFT_LONG) ? RIGHT_LONG : EVEN); tptr->ResetBalance( (tptr2->Balance() == RIGHT_LONG) ? LEFT_LONG : EVEN); /* move root to 75 */ t = tptr2; } } void AVLTree::Rebalance_Right_Long(AVLTreeNode*& t) { /* Processing parallels left-long cases. */ if((t->RightLink())->Balance() ==RIGHT_LONG) { AVLTreeNode *tptr = t->RightLink(); /* tptr points to node with 4 */ t->RightLink() = tptr->LeftLink(); tptr->LeftLink() = t; t->ResetBalance(EVEN); t = tptr; } else { AVLTreeNode *tptr = t->RightLink(); AVLTreeNode *tptr2 = tptr->LeftLink(); tptr->LeftLink() = tptr2->RightLink(); tptr2->RightLink() = tptr; t->RightLink() = tptr2->LeftLink(); tptr2->LeftLink() = t; t->ResetBalance((tptr2->Balance() == RIGHT_LONG) ? LEFT_LONG : EVEN); tptr->ResetBalance( (tptr2->Balance() == LEFT_LONG) ? RIGHT_LONG : EVEN); t = tptr2; } } int AVLTree::Add(KeyedItem* d) { fAddOK = 0; Insert1(d,fRoot); if(fAddOK) fNum++; return fAddOK; } void AVLTree::Delete1(long bad_key, AVLTreeNode*& t) { /* Possibilities: 1 a null treenode pointer => no record has key 2 data associated with current record has key equal to bad_key => this record to be removed by auxiliary routine DeleteRec 3 data associated with current record has key less than bad_key => if required record present, it must be in left branch so recursively invoke Delete1 4 otherwise, sought record might be found in right branch. When unwinding recursion after successful deletion in left or right branch, it may be necessary to check tree balance at current level. */ if(t == NULL) { fResizing = UNCHANGED; return; } if(bad_key == t->Key()) { DeleteRec(t); return; } if(bad_key < t->Key()) { /* recurse in searching left */ Delete1(bad_key,t->LeftLink()); /* and on unwind of recursion, do rebalancing */ if(fResizing == CHANGED_SIZE) Check_balance_after_Left_Delete(t); return; } Delete1(bad_key,t->RightLink()); if(fResizing == CHANGED_SIZE) Check_balance_after_Right_Delete(t); return; } void AVLTree::Check_balance_after_Left_Delete(AVLTreeNode*& t) { switch (t->Balance()) { case LEFT_LONG: t->ResetBalance(EVEN); break; case EVEN: t->ResetBalance(RIGHT_LONG); fResizing = UNCHANGED; break; case RIGHT_LONG: /* Right branch from current node was */ /* longer than left branch, and left has shrunk more. */ /* Have to rebalance */ Rebalance_Left_Short(t); break; } } void AVLTree::Check_balance_after_Right_Delete(AVLTreeNode*& t) { switch (t->Balance()) { case LEFT_LONG: /* Right branch from current node was already */ /* shorter than left branch, and it has shrunk. */ /* Have to rebalance */ Rebalance_Right_Short(t); break; case EVEN: t->ResetBalance(LEFT_LONG); fResizing = UNCHANGED; break; case RIGHT_LONG: t->ResetBalance(EVEN); break; } } void AVLTree::Del(AVLTreeNode*& t, AVLTreeNode*& r) { /* auxiliary routine for DeleteRec. It is called when record to be deleted has left and right branches. In such cases, it is not possible to simply unhook the bad record. It has to be replaced by the largest (i.e. rightmost) record in it left branch. example delete 25 from this tree: 25 | +------------+------------+ | | 12 37 | | +-----+-----+ +-----+-----+ 6 20 30 48 | | | | +---+---+ +---+---+ +---+---+ +---+---+ | | | | | | | 4 9 18 22 33 42 50 | | | | +--+--+ +--+--+ +-+--+ +-+--+ | | | | | 5 14 19 23 45 | +--+--+ | 13 new tree will have 23 at root. This routine is called with pointer to 12 (left of node 25) as argument r. Recursively move down and right from 12 until get to 23. There do second part of code of routine (copy data defining node 23 into original node 25), unhook the 23 node (if its got left children then substitute them at point where 23 used to hook in) delete the node that used to hold the data 23 that will result in the following (unbalanced) tree 23 | +------------+------------+ | | 12 37 | | +-----+-----+ +-----+-----+ 6 20 30 48 | | | | +---+---+ +---+---+ +---+---+ +---+---+ | | | | | | | 4 9 18 22 33 42 50 | | | +--+--+ +--+--+ +-+--+ | | | | 5 14 19 45 | +--+--+ | 13 as unwind the recursion, check balance its OK at 22 but at 20 discover that we were "left-long" and right branch has just got shorter, so do a rebalance that operation will result in the tree 23 | +------------+------------+ | | 12 37 | | +-----+-----+ +-----+-----+ 6 18 30 48 | | | | +---+---+ +---+---+ +---+---+ +---+---+ | | | | | | | 4 9 14 20 33 42 50 | | | | +--+--+ +--+-+ +--+--+ +-+--+ | | | | | 5 13 19 22 45 If you had a complex tree (!), similar effects might propagate back to earlier levels */ if(r->RightLink() != NULL) { /* on inward recursion, chase right pointers */ Del(t,r->RightLink()); /* and when unwinding recursion do rebalancing */ if(fResizing == CHANGED_SIZE) Check_balance_after_Right_Delete(r); } else { AVLTreeNode *x; /* this is code that "promotes" the node copying data from 23 of example into original 25 record */ t->Replace(r->Data()); x = r; /* keep pointer to tree-node that is being unlinked */ /* unlinking 23 (if 23 had had a left, e.g. a 22.5 entry, this would become 22's right) */ r = r->LeftLink(); fResizing = CHANGED_SIZE; /* and get rid of the node that had the 23 */ delete x; } } void AVLTree::DeleteRec(AVLTreeNode*& t) { /* It is easy to remove a record that has only a right branch or only a left branch (or neither). The record is unhooked. The pointer to it is reset to its left branch, or right branch as appropriate. */ fReturnItem = t->Data(); if(t->RightLink() == NULL) { AVLTreeNode *x = t; t = t->LeftLink(); fResizing = CHANGED_SIZE; delete x; } else if(t->LeftLink() == NULL) { AVLTreeNode *x = t; t = t->RightLink(); fResizing = CHANGED_SIZE; delete x; } else { /* The difficult case is when one has both branches. Then, the node being deleted has to be replaced by one promoted from its descendants, either its successor (the least node in its right branch) or its predecessor (the greatest node in its left branch). Have chosen to promote the predecessor. The promotion is necessary to keep the tree correctly ordered. But, of course it may get the tree unbalanced. Call auxiliary routine Del to do most of the work; Del finds the node to promote, removes it from the left branch and uses its data to replace that in current node, and then rebalances at each level in the left branch. Once Del has finished, it may still be necessary to rebalance tree at current level (because, in effect, the left branch has shrunk). */ Del(t,t->LeftLink()); if(fResizing == CHANGED_SIZE) Check_balance_after_Left_Delete(t); } } void AVLTree::Rebalance_Left_Short(AVLTreeNode*& t) { /* t's right branch used to be longer than t's left and left just got shorter. So, sort of re-root on suitable element of right branch. */ /* e.g.had tree 3 and removed 2 to get / \ unbalanced thing / \ 3 / \ / \ 2 10 1 10 / / \ / \ 1 7 11 7 11 \ \ 9 9 or 3 and removed 2 to get / \ unbalanced thing / \ 3 / \ / \ 2 10 1 10 / / \ / \ 1 7 11 7 11 \ \ \ \ 9 15 9 15 rearrange tree to rebalance "at 3"; rearrangements depend on shape of right branch */ AVLTreeNode* tptr = t->RightLink(); /* pointer to node 10 */ if(tptr->Balance() != LEFT_LONG) { /* second of two examples */ /* hang the 7 and 9 to the right of 3 */ t->RightLink() = tptr->LeftLink(); /* slot the 3 in below left of the 10 */ tptr->LeftLink() = t; /* sort out balance on nodes */ if(tptr->Balance() == EVEN) { /* illustrated case */ t->ResetBalance(RIGHT_LONG); tptr->ResetBalance(LEFT_LONG); fResizing = UNCHANGED; } else { /* imagine illustration without the 9 */ t->ResetBalance(EVEN); tptr->ResetBalance(EVEN); } t = tptr; } else { /* The first of the two examples */ AVLTreeNode *tptr2 = tptr->LeftLink(); /* pointer to node with 7 */ /* reset 10's left pointer to 9 */ tptr->LeftLink() = tptr2->RightLink(); /* reset 7's right pointer to 10, i.e. moving 7 above 10 in tree */ tptr2->RightLink() = tptr; /* hook anything left of 7 onto 3's right pointer (here its a NULL link) */ t->RightLink() = tptr2->LeftLink(); /* attach 3 below and left of 7, so 7 now moved to top */ tptr2->LeftLink() = t; t->ResetBalance( (tptr2->Balance() == RIGHT_LONG) ? LEFT_LONG : EVEN); tptr->ResetBalance( (tptr2->Balance() == LEFT_LONG) ? RIGHT_LONG : EVEN); /* reroot at 7 */ t = tptr2; /* So, now have | 7 / \ 3 10 / / \ 1 9 11 */ tptr2->ResetBalance(EVEN); } } void AVLTree::Rebalance_Right_Short(AVLTreeNode*& t) { AVLTreeNode* tptr = t->LeftLink(); if(tptr->Balance() != RIGHT_LONG) { t->LeftLink() = tptr->RightLink(); tptr->RightLink() = t; if(tptr->Balance() == EVEN) { t->ResetBalance(LEFT_LONG); tptr->ResetBalance(RIGHT_LONG); fResizing = UNCHANGED; } else { t->ResetBalance(EVEN); tptr->ResetBalance(EVEN); } t = tptr; } else { AVLTreeNode *tptr2 = tptr->RightLink(); tptr->RightLink() = tptr2->LeftLink(); tptr2->LeftLink() = tptr; t->LeftLink() = tptr2->RightLink(); tptr2->RightLink() = t; t->ResetBalance((tptr2->Balance() == LEFT_LONG) ? RIGHT_LONG : EVEN); tptr->ResetBalance((tptr2->Balance() == RIGHT_LONG) ? LEFT_LONG : EVEN); t = tptr2; tptr2->ResetBalance(EVEN); } } KeyedItem *AVLTree::Remove(long bad_key) { fReturnItem = NULL; Delete1(bad_key, fRoot); if(fReturnItem != NULL) fNum--; return fReturnItem; } KeyedItem* AVLTree::Find(long sought_key) { AVLTreeNode *t = fRoot; for(; t != NULL; ) { if(t->Key() == sought_key) return t->Data(); else if(t->Key() > sought_key) t = t->LeftLink(); else t = t->RightLink(); } return NULL; }