AVL tree implementation. I have the codes for insertion and find, but I don't know how to implement the delete function or modify(change) function.

Codes:

avlnode.cpp:

/* Filename: avlnode.cpp Programmer: Br. David Carlson Reference: Data Structures with C++, by Ford and Topp Date: October 12, 1997 This file defines the constructor for the class AVLNodeClass, which is set up in avlnode.h. */ #include "avlnode.h" /* Given: Item Data item to place in Info field. LeftPtr Pointer to place in Left field. RightPtr Pointer to place in Right field. BalanceValue Value to place in Balance field. Task: This is the constructor. It's job is to create a new object containing the above 4 values. Return: Nothing directly, but the implicit object is created. */ AVLNodeClass::AVLNodeClass(const ItemType & Item, AVLNodeClass * LeftPtr, AVLNodeClass * RightPtr, int BalanceValue): // call BSTNodeClass constructor, initialize field: BSTNodeClass(Item, LeftPtr, RightPtr), Balance(BalanceValue) { #ifdef DEBUG cout  
avlnode.h:
 
/* Filename: avlnode.h Programmer: Br. David Carlson Reference: Data Structures with C++, by Ford and Topp Date: October 12, 1997 Modified: June 9, 1999 to create AVLNodePtr type. This is the header file to accompany avlnode.cpp. It sets up the class AVLNodeClass as shown below. */ #ifndef AVLNODE_H #define AVLNODE_H #include "bstnode.h" class AVLNodeClass: public BSTNodeClass { private: int Balance; public: // constructor: AVLNodeClass(const ItemType & Item, AVLNodeClass * LeftPtr = NULL, AVLNodeClass * RightPtr = NULL, int BalanceValue = 0); friend class AVLClass; friend class AVLTableClass; // may not get to implementing this }; typedef AVLNodeClass * AVLNodePtr; #endif 
 
avltree.cpp:
 
/* Filename: avltree.cpp Programmer: Br. David Carlson Reference: Data Structures with C++, by Ford and Topp. Date: October 12, 1997 Revised: June 9, 1999 to use the type AVLNodePtr, to supply code for a copy constructor, and also to change each C-style cast to a reinterpret_cast. This file implements the functions of the AVLClass as set up in avltree.h. */ #include "avltree.h" /* Given: Item A data item to insert in a new node. LeftPtr A pointer to place in Left field of the new node. RightPtr A pointer to place in the Right field. BalanceValue A value to put in Balance field of the node. Task: To create a new node filled with the above 4 values. Return: A pointer to the new node in the function name. */ AVLNodePtr AVLClass::GetNode(const ItemType & Item, AVLNodeClass * LeftPtr, AVLNodePtr RightPtr, int BalanceValue) { AVLNodePtr NodePtr; #ifdef DEBUG cout  (Root)); Root = NULL; Count = 0; } /* Given: Current A pointer to a node in the implicit AVLClass object. Task: To wipe out all nodes of this subtree. Return: Nothing directly, but the implicit AVLClass object is modified. */ void AVLClass::ClearSubtree(AVLNodePtr Current) { // Use a postorder traversal: if (Current != NULL) { ClearSubtree(reinterpret_cast  (Current->Left)); ClearSubtree(reinterpret_cast  (Current->Right)); FreeNode(Current); } } /* Given: Tree An AVL tree. Task: To copy Tree into the current (implicit) AVL tree object. Return: Nothing directly, but the implicit AVL tree is modified. */ void AVLClass::CopyTree(const AVLClass & Tree) { #ifdef DEBUG cout  (Tree.Root)); Count = Tree.Count; } /* Given: Current Pointer to the current node of the implicit AVL tree. Task: To make a copy of the subtree starting at node Current. Return: A pointer to the root node of this copy. */ AVLNodePtr AVLClass::CopySubtree(const AVLNodePtr Current) { AVLNodePtr NewLeftPtr, NewRightPtr, NewParentPtr; // Once this section works, leave this out as it gives too much output: //#ifdef DEBUG // cout Left == NULL) NewLeftPtr = NULL; else NewLeftPtr = CopySubtree(reinterpret_cast  (Current->Left)); if (Current->Right == NULL) NewRightPtr = NULL; else NewRightPtr = CopySubtree(reinterpret_cast  (Current->Right)); NewParentPtr = GetNode(Current->Info, NewLeftPtr, NewRightPtr, Current->Balance); return NewParentPtr; } /* Given: ParentPtr A pointer to the node at which to rotate left. Task: To do a left rotation at the node specified above in the implicit AVL tree object. Return: ParentPtr Points to the new root node of the rotated subtree. Note that the implicit AVL tree is modified. */ void AVLClass::SingleRotateLeft(AVLNodePtr & ParentPtr) { AVLNodePtr RightChildPtr; #ifdef DEBUG cout Info  (ParentPtr->Right); ParentPtr->Balance = Balanced; RightChildPtr->Balance = Balanced; ParentPtr->Right = RightChildPtr->Left; RightChildPtr->Left = ParentPtr; ParentPtr = RightChildPtr; } /* Given: ParentPtr A pointer to the node at which to rotate right. Task: To do a right rotation at the node specified above in the implicit AVL tree object. Return: ParentPtr Points to the new root node of the rotated subtree. Note that the implicit AVL tree is modified. */ void AVLClass::SingleRotateRight(AVLNodePtr & ParentPtr) { AVLNodePtr LeftChildPtr; #ifdef DEBUG cout Info  (ParentPtr->Left); ParentPtr->Balance = Balanced; LeftChildPtr->Balance = Balanced; ParentPtr->Left = LeftChildPtr->Right; LeftChildPtr->Right = ParentPtr; ParentPtr = LeftChildPtr; } /* Given: ParentPtr A pointer to the node at which to double rotate left. Task: To do a double left rotation at the node specified above in the implicit AVL tree object. Return: ParentPtr Points to the new root node of the rotated subtree. Note that the implicit AVL tree is modified. */ void AVLClass::DoubleRotateLeft(AVLNodePtr & ParentPtr) { AVLNodePtr RightChildPtr, NewParentPtr; #ifdef DEBUG cout Info  (ParentPtr->Right); NewParentPtr = reinterpret_cast  (RightChildPtr->Left); if (NewParentPtr->Balance == LeftHeavy) { ParentPtr->Balance = Balanced; RightChildPtr->Balance = RightHeavy; // patched to fix bug in book } else if (NewParentPtr->Balance == Balanced) { ParentPtr->Balance = Balanced; RightChildPtr->Balance = Balanced; } else { ParentPtr->Balance = LeftHeavy; RightChildPtr->Balance = Balanced; } NewParentPtr->Balance = Balanced; RightChildPtr->Left = NewParentPtr->Right; NewParentPtr->Right = RightChildPtr; ParentPtr->Right = NewParentPtr->Left; NewParentPtr->Left = ParentPtr; ParentPtr = NewParentPtr; } /* Given: ParentPtr Pointer to the node at which to double rotate right. Task: To do a double right rotation at the node specified above in the implicit AVL tree object. Return: ParentPtr Points to the new root node of the rotated subtree. Note that the implicit AVL tree is modified. */ void AVLClass::DoubleRotateRight(AVLNodePtr & ParentPtr) { AVLNodePtr LeftChildPtr, NewParentPtr; #ifdef DEBUG cout Info  (ParentPtr->Left); NewParentPtr = reinterpret_cast  (LeftChildPtr->Right); if (NewParentPtr->Balance == RightHeavy) { ParentPtr->Balance = Balanced; LeftChildPtr->Balance = LeftHeavy; // patched to fix bug in book } else if (NewParentPtr->Balance == Balanced) { ParentPtr->Balance = Balanced; LeftChildPtr->Balance = Balanced; } else { ParentPtr->Balance = RightHeavy; LeftChildPtr->Balance = Balanced; } NewParentPtr->Balance = Balanced; LeftChildPtr->Right = NewParentPtr->Left; NewParentPtr->Left = LeftChildPtr; ParentPtr->Left = NewParentPtr->Right; NewParentPtr->Right = ParentPtr; ParentPtr = NewParentPtr; } /* Given: ParentPtr Pointer to parent node, whose subtree needs to be updated to an AVL tree (due to insertion). ReviseBalance Indicates if we need to revise balances. Assume: Subtree rooted at this parent node is left heavy. Task: To update this subtree so that it forms an AVL tree. Return: ParentPtr Points to the root node of the updated subtree. ReviseBalance Indicates if we need to revise balances. Note that the implicit AVL tree is modified. */ void AVLClass::UpdateLeftTree(AVLNodePtr & ParentPtr, bool & ReviseBalance) { AVLNodePtr LeftChildPtr; #ifdef DEBUG cout Info  (ParentPtr->Left); if (LeftChildPtr->Balance == LeftHeavy) { // left subtree is also left heavy SingleRotateRight(ParentPtr); ReviseBalance = false; } else if (LeftChildPtr->Balance == RightHeavy) { // right subtree is also right heavy DoubleRotateRight(ParentPtr); ReviseBalance = false; } } /* Given: ParentPtr Pointer to parent node, whose subtree needs to be updated to an AVL tree (due to insertion). ReviseBalance Indicates if we need to revise balances. Assume: Subtree rooted at this parent node is right heavy. Task: To update this subtree so that it forms an AVL tree. Return: ParentPtr Points to the root node of the updated subtree. ReviseBalance Indicates if we need to revise balances. Note that the implicit AVL tree is modified. */ void AVLClass::UpdateRightTree(AVLNodePtr & ParentPtr, bool & ReviseBalance) { AVLNodePtr RightChildPtr; #ifdef DEBUG cout Info  (ParentPtr->Right); if (RightChildPtr->Balance == RightHeavy) { // right subtree is also right heavy SingleRotateLeft(ParentPtr); ReviseBalance = false; } else if (RightChildPtr->Balance == LeftHeavy) { // right subtree is also left heavy DoubleRotateLeft(ParentPtr); ReviseBalance = false; } } /* Given: Tree Pointer to node of implicit AVL tree. This node is the root of the subtree in which to insert. NewNodePtr Pointer to the new node to be inserted. ReviseBalance Indicates if we need to revise balances. Task: To insert the new node in the subtree indicated above. Return: Tree Pointer to the root node of the subtree. ReviseBalance Indicates if we need to revise balances. Note that the implicit AVL tree object is modified. */ void AVLClass::AVLInsert(AVLNodePtr & Tree, AVLNodePtr NewNodePtr, bool & ReviseBalance) { bool RebalanceCurrentNode; #ifdef DEBUG if (Tree == NULL) cout Info Info Info Balance = Balanced; ReviseBalance = true; // tell others to check balances due to new node } else if (NewNodePtr->Info Info) { AVLInsert(reinterpret_cast  (Tree->Left), NewNodePtr, RebalanceCurrentNode); if (RebalanceCurrentNode) { if (Tree->Balance == LeftHeavy) // now 1 node worse than this UpdateLeftTree(Tree, ReviseBalance); else if (Tree->Balance == Balanced) // was balanced, now 1 extra { Tree->Balance = LeftHeavy; ReviseBalance = true; } else // was right heavy, due to extra node on left now balanced { Tree->Balance = Balanced; ReviseBalance = false; } } else ReviseBalance = false; } else { AVLInsert(reinterpret_cast  (Tree->Right), NewNodePtr, RebalanceCurrentNode); if (RebalanceCurrentNode) { if (Tree->Balance == LeftHeavy) // extra node on right balances it { Tree->Balance = Balanced; ReviseBalance = false; } else if (Tree->Balance == Balanced) // now 1 node heavy on right { Tree->Balance = RightHeavy; ReviseBalance = true; } else // was right heavy, now off by 2 on right, must fix: UpdateRightTree(Tree, ReviseBalance); } else ReviseBalance = false; } } /* Given: Nothing. Task: This is the default constructor for creating the implicit AVL tree object. Return: Nothing directly, but the implicit AVL tree object is created. */ AVLClass::AVLClass(void) { // just use the automatic BSTClass default constructor #ifdef DEBUG cout  (Root), NewNodePtr, ReviseBalance); Count++; } 
 
avltree.h:
 
/* Filename: avltree.h Programmer: Br. David Carlson Reference: Data Structures with C++, by Ford and Topp. Date: October 12, 1997 Revised: June 9, 1999 to use the type AVLNodePtr. This is the header file to accompany avltree.cpp. It sets up the class AVLClass as shown below. Note that the following functions are not overwritten, so that in any reference to them, these mean functions of the BSTClass: SubtreeFind, PrintSubtree, NumItems, Empty, Find, Print. */ #ifndef AVLTREE_H #define AVLTREE_H #include "avlnode.h" #include "bstree.h" const int LeftHeavy = -1; const int Balanced = 0; const int RightHeavy = 1; class AVLClass: public BSTClass { private: AVLNodePtr GetNode(const ItemType & Item, AVLNodePtr LeftPtr = NULL, AVLNodePtr RightPtr = NULL, int BalanceValue = 0); void CopyTree(const AVLClass & Tree); AVLNodePtr CopySubtree(const AVLNodePtr Current); void SingleRotateLeft(AVLNodePtr & ParentPtr); void SingleRotateRight(AVLNodePtr & ParentPtr); void DoubleRotateLeft(AVLNodePtr & ParentPtr); void DoubleRotateRight(AVLNodePtr & ParentPtr); void UpdateLeftTree(AVLNodePtr & ParentPtr, bool & ReviseBalance); void UpdateRightTree(AVLNodePtr & ParentPtr, bool & ReviseBalance); void AVLInsert(AVLNodePtr & Tree, AVLNodePtr NewNodePtr, bool & ReviseBalance); void FreeNode(AVLNodePtr NodePtr); void ClearTree(void); void ClearSubtree(AVLNodePtr Current); public: AVLClass(void); AVLClass(const AVLClass & Tree); ~AVLClass(void); AVLClass & operator= (const AVLClass & Tree); void Insert(const ItemType & Item); // Some sort of Remove method could also be added, but it would // take effort to remake the AVL tree after the deletion of a node. }; #endif 
 
bstnode.cpp:
 
/* Filename: bstnode.cpp Programmer: Br. David Carlson Date: October 10, 1997 Modified: August 8, 1998. This file implements the class functions for the BSTNodeClass, which is declared in bstnode.h. Since no code is needed for the constructor, only the GetInfo function is found here. */ #include "bstnode.h" /* Given: Nothing other than the implicit object. Task: To look up the Info field of the object. Return: A copy of this data in TheInfo. */ void BSTNodeClass::GetInfo(ItemType & TheInfo) const { TheInfo = Info; // assumes assignment works on this type } 
 
bstnode.h
 
/* Filename: bstnode.h Programmer: Br. David Carlson Date: October 10, 1997 Revised: August 8, 1998 Revised: June 9, 1999 to use protected, not private, data fields. This is so that a derived class can directly access them. An alternate solution would be to make any derived class (such as AVLNodeClass) a friend of this class. This file was also revised to make AVLClass a friend of this class, so that it would have easy access to the data fields. This is the header file to accompany bstnode.cpp. It provides the BSTNodeClass shown below as well as the BSTNodePtr type. */ #ifndef BSTNODE_H #define BSTNODE_H #include "itemtype.h" class BSTNodeClass { protected: ItemType Info; BSTNodeClass * Left, * Right; public: BSTNodeClass(const ItemType & Item, BSTNodeClass * LeftPtr = NULL, BSTNodeClass * RightPtr = NULL): Info(Item), Left(LeftPtr), Right(RightPtr) { }; void GetInfo(ItemType & TheInfo) const; friend class BSTClass; friend class AVLClass; }; typedef BSTNodeClass * BSTNodePtr; #endif 
 
bstree.cpp
 
/* Filename: BSTree.cpp Programmer: Br. David Carlson Date: October 10, 1997 Modified: August 8, 1998. Modified: June 9, 1999 so that ClearTree only tries to do any work if the root pointer is non-null. This file implements the functions for the BSTClass as set up in the header file bstree.h. */ #include "bstree.h" /* Given: Nothing, Task: This is the constructor to initialize a binary search tree as empty. Return: Nothing directly, but it creates the implicit BSTClass object. */ BSTClass::BSTClass(void) { Root = NULL; Count = 0; } /* Given: Nothing (other than the implicit BSTClass object). Task: This is the destructor. It's job is to wipe out all data storage used by this binary search tree. Return: Nothing directly, but the implicit BSTClass object is destroyed. */ BSTClass::~BSTClass(void) { ClearTree(); } /* Given: Nothing (other than the implicit BSTClass object). Task: To clear out all nodes of the implicit binary search tree. Return: Nothing directly, but the implicit BSTClass object is modified to be an empty binary search tree. */ void BSTClass::ClearTree(void) { if (Root != NULL) { ClearSubtree(Root); Root = NULL; Count = 0; } } /* Given: Current A pointer to a node in the implicit BSTClass object. Task: To wipe out all nodes of this subtree. Return: Nothing directly, but the implicit BSTClass object is modified. */ void BSTClass::ClearSubtree(BSTNodePtr Current) { // Use a postorder traversal: if (Current != NULL) { ClearSubtree(Current->Left); ClearSubtree(Current->Right); FreeNode(Current); } } /* Given: Item A data item to place into a new node. LeftPtr The pointer to place in the left field of the node. RightPtr The pointer to place in the right field of the node. Task: To create a new node containing the above 3 items. Return: A pointer to the new node. */ BSTNodePtr BSTClass::GetNode(const ItemType & Item, BSTNodePtr LeftPtr, BSTNodePtr RightPtr) { BSTNodePtr NodePtr; NodePtr = new BSTNodeClass(Item, LeftPtr, RightPtr); if (NodePtr == NULL) { cerr  0) return false; else return true; } /* Given: Item A data item to be inserted. Task: To insert a new node containing Item into the implicit binary search tree so that it remains a binary search tree. Return: Nothing directly, but the implicit binary search tree is modified. */ void BSTClass::Insert(const ItemType & Item) { BSTNodePtr Current, Parent, NewNodePtr; Current = Root; Parent = NULL; while (Current != NULL) { Parent = Current; if (Item Info) Current = Current->Left; else Current = Current->Right; } NewNodePtr = GetNode(Item, NULL, NULL); if (Parent == NULL) Root = NewNodePtr; else if (Item Info) Parent->Left = NewNodePtr; else Parent->Right = NewNodePtr; Count++; } /* Given: Item A data item to look for. Task: To search for Item in the implicit binary search tree. Return: A pointer to the node where Item was found or a NULL pointer if it was not found. */ BSTNodePtr BSTClass::Find(const ItemType & Item) const { return SubtreeFind(Root, Item); } /* Given: Current A pointer to a node in the implicit binary search tree. Item A data item to look for. Task: To search for Item in the subtree rooted at the node Current points to. Return: A pointer to the node where Item was found or a NULL pointer if it was not found. */ BSTNodePtr BSTClass::SubtreeFind(BSTNodePtr Current, const ItemType & Item) const { if (Current == NULL) return NULL; else if (Item == Current->Info) return Current; else if (Item Info) return SubtreeFind(Current->Left, Item); else return SubtreeFind(Current->Right, Item); } /* Given: NodePtr A pointer to the root of the subtree to be printed. Level Integer indentation level to be used. Task: To print (sideways) the subtree to which NodePtr points, using an indentation proportional to Level. Return: Nothing. */ void BSTClass::PrintSubtree(BSTNodePtr NodePtr, int Level) const { int k; if (NodePtr != NULL) { PrintSubtree(NodePtr->Right, Level + 1); for (k = 0; k Info Left, Level + 1); } } /* Given: Nothing (other than the implicit object). Task: To print (sideways) the implicit binary search tree. Return: Nothing. */ void BSTClass::Print(void) const { PrintSubtree(Root, 0); } 
 
bstree.h
 
/* Filename: bstree.h Programmer: Br. David Carlson Date: October 10, 1997 Modified: August 8, 1998. Modified: June 9, 1999 to make AVLClass a friend of BSTClass. This is the header file to accompany bstree.cpp. It provides the BSTClass as shown below. */ #ifndef BSTREE_H #define BSTREE_H #include "bstnode.h" class BSTClass { private: BSTNodePtr GetNode(const ItemType & Item, BSTNodePtr LeftPtr = NULL, BSTNodePtr RightPtr = NULL); void FreeNode(BSTNodePtr NodePtr); void ClearTree(void); void ClearSubtree(BSTNodePtr Current); BSTNodePtr SubtreeFind(BSTNodePtr Current, const ItemType & Item) const; void PrintSubtree(BSTNodePtr NodePtr, int Level) const; // The following data fields could be made protected instead of // private. This would make them accessible to the derived AVLClass // without making AVLClass a friend of BSTClass. BSTNodePtr Root; int Count; public: BSTClass(void); ~BSTClass(void); int NumItems(void) const; bool Empty(void) const; void Insert(const ItemType & Item); // Some sort of Remove method could also be added, but // it would require effort to remake the binary search tree // after the deletion of a node. BSTNodePtr Find(const ItemType & Item) const; void Print(void) const; friend class AVLClass; }; #endif 
 
itemtype.h
 
/* Filename: itemtype.h Programmer: Br. David Carlson Date: October 10, 1997 Modified: June 26, 2000 to use modern headers. This header file defines ItemType for use in bstnode.h. It also should be set up to define DEBUG if you want debugging output statements to be compiled. */ #ifndef ITEMTYPE_H #define ITEMTYPE_H #include  using namespace std; // Comment off the following line to omit debugging output statements: #define DEBUG // Customize the following as needed: typedef char ItemType; #endif 
 
and then a driver file to show you how to use these files:
 
avltest.cpp
 
/* Filename: avltest.cpp Programmer: Br. David Carlson Reference: Data Structures with C++, by Ford and Topp Date: October 10, 1997 Modified: June 9, 1999 to use AVLNodePtr type and also to change each C-style cast to a reinterpret_cast. Modified: June 26, 2000 to use modern headers. (See itemtype.h in particular.) Modified: April 21, 2001 to add the Pause function. Last Modified: December 23, 2001 This program inserts some hard-coded data (chars) into an AVL tree. It then tests the following functions by calling them and reporting the results on the screen: Find, NumItems, the overloaded = operator, the copy constructor, and Print. To compile this program in Visual C++, make sure that the project contains: avltest.cpp, bstnode.cpp, bstree.cpp, avlnode.cpp, avltree.cpp, bstnode.h, bstree.h, avlnode.h, avltree.h, and itemtype.h. In itemtype.h leave DEBUG defined if you want extra debugging output, or comment it off to omit such output. Tested with: Microsoft Visual C++ 6.0 Microsoft Visual C++ .NET g++ under Linux */ #include "avltree.h" void Pause(void); int main(void) { AVLClass AVLTreeA, AVLTreeB; AVLNodePtr Result; AVLTreeA.Insert('F'); AVLTreeA.Insert('B'); AVLTreeA.Insert('W'); AVLTreeA.Insert('M'); AVLTreeA.Insert('E'); AVLTreeA.Insert('A'); AVLTreeA.Insert('C'); cout  (AVLTreeA.Find('E')); if (Result == NULL) cout  (AVLTreeA.Find('D')); if (Result == NULL) cout  (AVLTreeB.Find('E')); if (Result == NULL) cout  (AVLTreeC.Find('W')); if (Result == NULL) cout