chrismillward.com © Chris Millward 2010-2011
Valid XHTML 1.0 Transitional Valid CSS!
 
 
AVLTree.hpp
 
 
#ifndef _AvlTree_H #define _AvlTree_H // Required for string operations #include #include #include #include #pragma warning(push) #pragma warning(disable:4996) // ------------------------------------------------------------------------------ // ---------------------- Heap & Char Set Configuration ------------------------ // ------------------------------------------------------------------------------ // This section is to define KEY and DATA types and // related informations. #include "wchar.h" // Type of Key typedef wchar_t* KeyType; // Macro to compare two keys #define KEY_COMPARE(a,b) wcscmp((a),(b)) // Macro to copy the keys #define KEY_COPY(a,b) \ (a) = new WCHAR[wcslen((b)) + 1]; \ wcscpy((a),(b)); #define KEY_FREE(a) \ delete[] (a); // Macros to clone the key, just assignement is enough in case of array or pointers #define KEY_CLONE(a,b) a = b // Data type section // Have void* as data type typedef void* DataType; // Macro to copy the data. This will be simple pointer copy, if data is an array and // want to store it in the tree change this and data type appropriately #define DATA_COPY(a,b) a = b // Macro to create/free node memory based on memory heap model #define NODE_ALLOCATE() new AVLNode #define NODE_FREE(node) delete node // Macro return in case of empty tree #define CHECK_EMPTY_TREE(tree) if( !(tree)) return NULL; // Map to keep sorted list of nodes typedef std::map<__int64, void*> sorted_map; // Tree Node // This is the basic block of AVL Tree struct AVLNode { // Declare the element KeyType Key; // Pointer to store data DataType Data; // Left Tree AVLNode *Left; // Right Tree AVLNode *Right; // Parent tree AVLNode *Parent; // Height Balance flag of the tree // -1 : Tree is left biased // 0 : Tree is balanced // 1 : Tree is right biased int Height; // Set Node ID __int64 NodeID; }; class AVLIterator; // Main AVL class class AVLTree { // Have relatives declation here friend AVLIterator; private: // Have root of AVL tree AVLNode* root; // Have loacation variable H to denote height change during insert/delete int H; // Have counter to count the nodes __int64 _node_count; // Private Tree clean up function // Delete key memory and node memory void DeleteTree(AVLNode* root) { // If NULL return if( ! root) return; // use post order delete // Delete Left and Right Sub Trees and then delete the root node if( root->Left) { // Clean up Left Tree DeleteTree(root->Left); root->Left = NULL; } if( root->Right) { // Clean up Right Tree DeleteTree(root->Right); root->Right = NULL; } // Free key memory and then node memory KEY_FREE(root->Key); NODE_FREE(root); } // Set of internal functions used by AVL Tree to manipulate AVL Nodes // Internal Insert Function // This will be called by wrapper insert function with root node // and also recursively to complete insert AVLNode* Insert(AVLNode* root, KeyType X, DataType D, int* H) { // If root node/subtree root is empty then // use this node to insert the data if(!root) { // Create new node and set // balance as height root = NODE_ALLOCATE(); root->Left = root->Right = root->Parent = NULL; root->NodeID = _node_count++; KEY_COPY(root->Key,X); DATA_COPY(root->Data,D); root->Height = 0; *H = 1; return (root); } // Root is not empty // Check the value and based on that traverse the tree int val = KEY_COMPARE(X, root->Key); // New key value is smaller, take left path if(val < 0) { // Insert in to left tree root->Left = Insert(root->Left, X, D, H); // Update the parent root->Left->Parent = root; // If the heigth got changed // we may need to balance the tree if(*H) { // Temp swap nodes AVLNode *Node1; AVLNode *Node2; // Left branch has grown higher switch(root->Height) { case 1: // Right heavy root->Height = 0; // Now balanced *H = 0; break; case 0: // Balanced tree root->Height = -1; // Now left left heady break; case -1: // Left heavy // Alreay biased on left side and new insert will // violate AVL height rule, re-balance now Node1 = root->Left; if(Node1->Height == -1) { // Left to Left Rotation root->Left = Node1->Right; if(Node1->Right) Node1->Right->Parent = root; Node1->Right = root; Node1->Parent = root->Parent; root->Height = 0; root->Parent = Node1; root = Node1; } else { // Left to right rotation Node2 = Node1->Right; Node1->Right = Node2->Left; if(Node2->Left) Node2->Left->Parent = Node1; Node2->Left = Node1; Node1->Parent = Node2; root->Left = Node2->Right; if(Node2->Right) Node2->Right->Parent = root; Node2->Right = root; Node2->Parent = root->Parent; root->Parent = Node2; if( Node2->Height == -1 ) root->Height = 1; else root->Height = 0; if( Node2->Height == 1 ) Node1->Height = -1; else Node1->Height = 0; root = Node2; } // Now the tree is balanced and set the height root->Height = 0; // Ret height change flag *H = 0; } } } // New key value is greater, take right path if(val > 0) { // Insert the node in right sub tree root->Right = Insert(root->Right, X, D, H); // Update the parent root->Right->Parent = root; // Right branch has grown higher if(*H) { AVLNode *Node1; AVLNode *Node2; switch(root->Height) { case -1: // Left heavy root->Height = 0; *H = 0; break; case 0: // Balanced tree root->Height = 1; break; case 1: // Right heavy Node1 = root->Right; if(Node1->Height == 1) { // Right to Right Rotation root->Right= Node1->Left; if(Node1->Left) Node1->Left->Parent = root; Node1->Left = root; Node1->Parent = root->Parent; root->Parent = Node1; root->Height = 0; root = Node1; } else { // Right to Left Rotation Node2 = Node1->Left; Node1->Left = Node2->Right; if( Node2->Right) Node2->Right->Parent = Node1; Node2->Right = Node1; Node1->Parent = Node2; root->Right = Node2->Left; if(Node2->Left) Node2->Left->Parent = root; Node2->Left = root; Node2->Parent = root->Parent; root->Parent = Node2; if( Node2->Height == 1 ) root->Height = -1; else root->Height = 0; if( Node2->Height == -1 ) Node1->Height = 1; else Node1->Height = 0; root = Node2; } // Reset height overflow root->Height = 0; *H = 0; } } } return(root); } int Validate(AVLNode* root, AVLNode *parent) { if( parent) { if(parent != root->Parent) { printf("Error root: %p Parent: %p root->Parent: %p\n",root,parent,root->Parent); return 0; } } if( root->Left && !Validate(root->Left, root)) return 0; if( root->Right && !Validate(root->Right, root)) return 0; return 1; } // Helper functions to balance the tree // RHS Balancer AVLNode* Balance_Right_Heavy(AVLNode* root, int *H) { AVLNode *Node1, *Node2; switch(root->Height) { case -1: // Left Heavy root->Height = 0; break; case 0: // Balancced tree root->Height = 1; *H= 0; break; case 1: // Already Right Heavy, rebalance Node1 = root->Right; if(Node1->Height >= 0) { //Right to Right Rotation root->Right= Node1->Left; if(Node1->Left) Node1->Left->Parent = root; Node1->Left = root; Node1->Parent = root->Parent; root->Parent = Node1; if(Node1->Height == 0) { root->Height = 1; Node1->Height = -1; *H = 0; } else { root->Height = Node1->Height = 0; } root = Node1; } else { // Right to Left Rotation Node2 = Node1->Left; Node1->Left = Node2->Right; if(Node2->Right) Node2->Right->Parent = Node1; Node2->Right = Node1; Node1->Parent = Node2; root->Right = Node2->Left; if(Node2->Left) Node2->Left->Parent = root; Node2->Left = root; Node2->Parent = root->Parent; root->Parent = Node2; if(Node2->Height == 1) root->Height = -1; else root->Height = 0; if(Node2->Height == -1) Node1->Height = 1; else Node1->Height = 0; root = Node2; Node2->Height = 0; } } return(root); } // LHS Balancer AVLNode* Balance_Left_Heavy(AVLNode* root, int *H) { AVLNode *Node1, *Node2; // check the height balance switch(root->Height) { case 1: // Right Heavy root->Height = 0; // Now balanced break; case 0: // Balanced root->Height = -1; // Now left heavy *H= 0; break; case -1: // Left heady, rebalance Node1 = root->Left; if(Node1->Height <= 0) { //Left to Left Rotation root->Left= Node1->Right; if(Node1->Right) Node1->Right->Parent = root; Node1->Right = root; Node1->Parent = root->Parent; root->Parent = Node1; if(Node1->Height == 0) { root->Height = -1; Node1->Height = 1; *H = 0; } else { root->Height = Node1->Height = 0; } root = Node1; } else { //Left to Right Rotation Node2 = Node1->Right; Node1->Right = Node2->Left; if(Node2->Left) Node2->Left->Parent = Node1; Node2->Left = Node1; Node1->Parent = Node2; root->Left = Node2->Right; if(Node2->Right) Node2->Right->Parent = root; Node2->Right = root; Node2->Parent = root->Parent; root->Parent = Node2; if(Node2->Height == -1) root->Height = 1; else root->Height = 0; if(Node2->Height == 1) Node1->Height = -1; else Node1->Height = 0; root = Node2; Node2->Height = 0; } } return(root); } // Function to delete a node from AVL tree AVLNode* Delete(AVLNode* root, KeyType X, int* h) { // If the tree/subtree is empty then return if (!root) return false; // Compare the values int val = KEY_COMPARE(X, root->Key); if( val < 0 ) { // Continue with left root->Left = Delete(root->Left, X, h); if(root->Left) root->Left->Parent = root; // If deleted and height alter happened // then balance the tree if(*h) { root = Balance_Right_Heavy(root, h); } } else { // Value is greater if( val > 0 ) { // continue with right root->Right = Delete(root->Right, X, h); if(root->Right) root->Right->Parent = root; // If deleted and height alter happened // then balance the tree if(*h) { root = Balance_Left_Heavy(root, h); } } else { // Value matches here AVLNode* Temp= root; // If any one the children is empty then just move // the other one as root node if(Temp->Right == NULL) { root = Temp->Left; if(root) root->Parent = Temp->Parent; *h = 1; // Free the key first KEY_FREE(Temp->Key); // Now free the node NODE_FREE(Temp); } else if(Temp->Left == NULL) { root = Temp->Right; if(root) root->Parent = Temp->Parent; *h = 1; // Free the key first KEY_FREE(Temp->Key); // Now free the node NODE_FREE(Temp); } else { // Both children are active // We need to pick left subtree's max value node and // replace that as new root node Temp->Left = delete_internal(Temp->Left, Temp, h); if( Temp->Left) Temp->Left->Parent = Temp; if(*h) { root = Balance_Right_Heavy(root, h); } } } } // Return altered tree/subtree return(root); } // This function will look for max valued node and will replace // that node as new root. Pointer swap is used for replacing // the key to avoid extra new-delete operations AVLNode* delete_internal(AVLNode* root, AVLNode* temp, int *H) { AVLNode* Dnode = root; // Traverse till extreme right node if( root->Right != NULL) { // Goes till the end and delete the last node. This needs to // be a recursive call to balance subtrees during // unwind of the stack root->Right = delete_internal(root->Right, temp, H); if(root->Right) root->Right->Parent = root; // If height altered then balance the tree again. if(*H) root = Balance_Left_Heavy(root, H); } else { // We are at extreme right node // We need to copy this node data in to root node and root node // data should be deleted. // Rather copying key string just move the pointers alone as // both are dynamically allocated memory // Swap the nodes Dnode = root; // Copy the data (just pointer copy DATA_COPY(temp->Data, root->Data); // Delete the old data, to be sure check for null if( temp->Key) KEY_FREE(temp->Key); // Now just assign the pointer value KEY_CLONE(temp->Key, root->Key); // Copy parent //temp->Parent = root->Parent; if(root->Left) root->Left->Parent = temp; if(root->Right) root->Right->Parent = temp; // Make this root root = root->Left; // Delete the old node NODE_FREE(Dnode); // Mark height change *H = 1; } // Return new Tree return(root); } // Function to dump tree content visually void Dump(AVLNode* root,int Level) { int i; // If not null continue if (root) { // While displaying the tree vertically // Right subtree comes first Dump( root->Right, Level + 1 ); // Show the root content printf("\n"); // use space to denote the depth for ( i = 0; i < Level; i++ ) printf(" "); // print the Key value printf("%s", root->Key); // Print Left subtree Dump(root->Left, Level + 1); } } // Function to fill the nodes in to map // map key is node id // map data is node pointer // Note: Map iterator will give sorted key order void Fill_Map(AVLNode * root, sorted_map& map) { if( ! root ) return; map[root->NodeID] = root; if( root->Left) Fill_Map(root->Left,map); if(root->Right) Fill_Map(root->Right,map); } public: // default Constructor AVLTree() { root = NULL; _node_count = 0; } // Destructor ~AVLTree() { // Delete the tree DeleteTree(root); _node_count = 0; } // ------------------------------------------------------------------------------ // ------------------------------ Helper Functions ------------------------------ // ------------------------------------------------------------------------------ __int64 GetNodeCount() const { return _node_count; } // Function to Find a AVL node in the tree AVLNode* Find( AVLNode* searchNode) { // Return if input is invalid if( ! searchNode ) return NULL; // Check with key return Find(searchNode->Key); } // Function to Find a AVL node in the tree AVLNode* Find( KeyType searchKey) { // Return if tree is empty CHECK_EMPTY_TREE(root); // Loop through the tree till we find the node or hitting the leaf AVLNode* current = root; while(current) { // Compare with key int val = KEY_COMPARE(searchKey,current->Key); // Matched if( val == 0 ) { break; } // Go based on value if( val < 0 ) current = current->Left; else current = current->Right; } // Return mached, could be a valid node or NULL pointer in case of a miss return current; } // Function to Get the node that has minimum of the KeyValues AVLNode* FindMin() { // Return if tree is empty CHECK_EMPTY_TREE(root); // Minimum is the extreeme left node AVLNode* current = root; while(current->Left) current = current->Left; // Return Min node Pointer return current; } // Minimum of a sub tree AVLNode* FindMin(AVLNode *node) { CHECK_EMPTY_TREE(node); // return min of this tree AVLNode * current = node; while(current->Left) current = current->Left; return current; } // Function to Get the node that has maximum of the KeyValues AVLNode* FindMax() { CHECK_EMPTY_TREE(root); // return min of this tree AVLNode * current = root; while(current->Right) current = current->Right; return current; } // Function to Get the node that has Max of the KeyValues AVLNode* FindMax(AVLNode* node) { CHECK_EMPTY_TREE(node); // return min of this tree AVLNode * current = node; while(current->Right) current = current->Right; return current; } // Function to get node list in insert order // This will return a map that has sorted node // based on Node ID. At any point of time // Node ID tells the node insert order sorted_map* GetInsertList(AVLNode *root) { // If empty then return NULL if( ! root) return NULL; // Get the sorted map sorted_map* map = new sorted_map; // fill the map with pointers Fill_Map(root, *map); //GetSorted return map; } // Get root node of the tree // Must be used carefully to avoid any tree corruption and crash due to that AVLNode* GetRoot() { // Return the root of the tree return root; } // ------------------------------------------------------------------------------ // -------------------------- Tree Manupulation Functions ----------------------- // ------------------------------------------------------------------------------ // Function to insert a new Node AVLNode* Insert( KeyType X, DataType D ) { root = Insert(root,X,D,&H); return root; } // Insert new node AVLNode* Insert( AVLNode* newNode ) { // Return if insert node is NULL CHECK_EMPTY_TREE(newNode); // Insert new node root = Insert(root,newNode->Key,newNode->Data,&H); // Return the root node return root; } // Delete given key node if found AVLNode* Delete(KeyType X) { int height = 0; root = Delete(root, X, &height); return root; } // Delete node from the tree. Note, this node can no longer referred // by the caller as this is deleted now. This function will also adjust // parent hierarchy AVLNode* Delete(AVLNode* root) { AVLNode* Temp = root; int change; int *h = &change; if(!root) return root; // If any one the children is empty then just move // the other one as root node if(Temp->Right == NULL) { root = Temp->Left; if(root) root->Parent = Temp->Parent; // Update parent if( Temp->Parent->Left == Temp) Temp->Parent->Left = root; else Temp->Parent->Right = root; *h = 1; // Free the key first KEY_FREE(Temp->Key); // Now free the node NODE_FREE(Temp); } else { if(Temp->Left == NULL) { root = Temp->Right; if(root) root->Parent = Temp->Parent; // Update parent if( Temp->Parent->Left == Temp) Temp->Parent->Left = root; else Temp->Parent->Right = root; *h = 1; // Free the key first KEY_FREE(Temp->Key); // Now free the node NODE_FREE(Temp); } else { // Both children are active // We need to pick left subtree's max value node and // replace that as new root node Temp->Left = delete_internal(Temp->Left, Temp, h); if( Temp->Left) Temp->Left->Parent = Temp; if(*h) { root = Balance_Right_Heavy(root, h); } } } // Now we may need to rebalance parent while(*h && root && root->Parent) { // Check whether we are left child or right child if(root == root->Parent->Left) { root->Parent = Balance_Right_Heavy(root->Parent, h); } else { root->Parent = Balance_Left_Heavy(root->Parent, h); } root = root->Parent; } } // Clear AVL tree in one shot rather multiple delete void Clean() { DeleteTree(root); root = NULL; } // Function to dump the tree content // Note: Tree is dumped in vertical display format void Dump(int level = 1) { Dump(root,level); printf("\n"); } int Validate() { if( root) return Validate(root,NULL); else return 1; } }; // AVL Iterator class class AVLIterator { private: // Private data to save the state std::stack S; // Root of the iterator AVLNode* root; // Search start AVLNode* toSrch; // Current node AVLNode* current; // Are we done with the looping bool done; public: AVLIterator(AVLTree* root) { // Save the root this->root = root->root; // reset the iterator to the beginning Reset(); } AVLIterator(AVLNode* root) { // Save the root this->root = root; // reset the iterator to the beginning Reset(); } ~AVLIterator() { } // Reset Iterator state to initial state // Current marker will be set to in-order first element void Reset() { // Reset the stack while(!S.empty()) S.pop(); // Reset search beging toSrch=root; // reset end of run done = false; // Move to fitst Advance(); } // Move current marker to in-order successor void Advance() { // Go to in-order successor current = toSrch; while (current != NULL) { S.push(current); current = current->Left; } if (!S.empty()) { current = (AVLNode*)S.top(); S.pop(); toSrch = current->Right; } else { //stack is empty, completed all traversal done = true; } } // Operator ++ to advance the iterator AVLNode* operator ++() { Advance(); return Retrieve(); } // Function to get current node AVLNode* Retrieve() { return current; } // Function get EOF status bool Done() { return done; } }; #pragma warning(pop) #endif /* _AvlTree_H */