AVLtree
AVLtree
// AVL binary tree // Jesse B. Dooley // (c) 26 May 1996 // template tree class // strict binary search tree // The following overloaded operators are // assumed for the T data type. // < LESS THAN // > greater than // == equals // << OUTPUT STREAM // >> input stream // = assignment // avl_tree.cc #ifndef AVL_TREE_CC #define AVL_TREE_CC #ifndef STACK_CC #include "stack.cc" #endif template<CLASS T> class treenode { friend class avl_tree<T>; friend istream& operator >> (istream& IS, treenode<T> &A) { if( IS ) { IS >> A.Tdata; } return IS; } friend ostream& operator << (OSTREAM& OS, TREENODE<T> &A) { OS << A.TDATA; RETURN OS; } PUBLIC: T TDATA; UNSIGNED LONG ULLEFTHEIGHT; UNSIGNED LONG ULRIGHTHEIGHT; TREENODE<T> *Left, *Right; treenode() { ulLeftHeight = 0; ulRightHeight = 0; Left = NULL; Right = NULL; } treenode(const treenode<T> &A) { Tdata = A.Tdata; ulLeftHeight = A.ulLeftHeight; ulRightHeight = A.ulRightHeight; Left = A.Left; Right = A.Right; } ~treenode(){} treenode operator = (const treenode<T> &A) { Tdata = A.Tdata; ulLeftHeight = A.ulLeftHeight; ulRightHeight = A.ulRightHeight; Left = A.Left; Right = A.Right; return *this; } T getdata() { return Tdata; } }; template<CLASS T> class avl_tree: public treenode<T> { enum TranverseType{INORDER, PREORDER, POSTORDER, REVERSE}; enum LeftRight{LEFT,RIGHT}; treenode<T> *Root, *Current; unsigned long m_ulPopulation; TranverseType m_TranverseType; stack<TREENODE<T>*> m_stackTreePath; stack<LEFTRIGHT> m_stackLeftRight; friend istream& operator >> (istream& IS, avl_tree<T> &A) { T temp; IS >> temp; A += temp; return IS; } friend ostream& operator << (OSTREAM& OS, CONST AVL_TREE<T> &Q) { if ( Q.Root ) { switch (Q.m_TranverseType) { case INORDER: printinorder(OS, Q.Root); break; case PREORDER: printpreorder(OS, Q.Root); break; case POSTORDER: printpostorder(OS, Q.Root); break; case REVERSE: printreverse(OS, Q.Root); break; default: ; } return OS; } return OS; } void avlbalancetree() { long l_avlbalance = calc_avlbalance( Current ); //Current->avl_balance; if ( !m_stackTreePath.isempty() ) { if(l_avlbalance > 1) // left rotation rotate_left(); if(l_avlbalance < -1) // RIGHT ROTATION ROTATE_RIGHT(); CURRENT = M_STACKTREEPATH.POP(); LEFTRIGHT LR_TEMP = M_STACKLEFTRIGHT.POP(); AVLBALANCETREE(); } ELSE { IF(L_AVLBALANCE > 1) // left rotation rotate_left(); if(l_avlbalance < -1) // RIGHT ROTATION ROTATE_RIGHT(); } } LONG CALC_AVLBALANCE(TREENODE<T>* ptr) { if(ptr) { ptr->ulLeftHeight = getreeheight( ptr->Left ); ptr->ulRightHeight = getreeheight( ptr->Right ); return (long)(ptr->ulRightHeight - ptr->ulLeftHeight); } return 0; } // calc_avlbalance unsigned long getreeheight( treenode<T>* P ) { if( P ) { return (P->ulLeftHeight > P->ulRightHeight) ? (P->ulLeftHeight + 1) : (P->ulRightHeight + 1); } return 0; }// getreeheight void copynode(treenode<T> *ptrn, treenode<T> *ptr ) { if(ptr) { ptrn = new treenode<T>; ptrn->Tdata = ptr->Tdata; ptrn->Left = ptr->Left; ptrn->Right = ptr->Right; copynode( ptrn->Left, ptr->Left ); copynode( ptrn->Right, ptr->Right ); } } // copynode void deletenode( treenode<T>* P ) { if ( P ) { deletenode( P->Left ); deletenode( P->Right ); delete P; } } // deletenode void getleft() { m_stackTreePath.push( Current ); m_stackLeftRight.push( LEFT ); Current = Current->Left; } // getleft void getparent() { Current = m_stackTreePath.pop(); } void getright() { m_stackTreePath.push( Current ); m_stackLeftRight.push( RIGHT ); Current = Current->Right; } // getright void getroot () { Current = Root; m_stackTreePath.erase(); m_stackLeftRight.erase(); } // getroot void rotate_left( ) { if (Current == Root) // rotate the root { Root = Current->Right; Current->Right = Root->Left; Current->ulRightHeight = getreeheight( Current->Right ); Root->Left = Current; Root->ulLeftHeight = getreeheight( Root->Left ); } else // rotate subroot { LeftRight lr_Temp = m_stackLeftRight.top(); treenode<T> *p_Parent = m_stackTreePath.top(); treenode<T> *p_CurrentR = Current->Right; if (lr_Temp == LEFT) { p_Parent->Left = Current->Right; Current->Right = p_CurrentR->Left; Current->ulRightHeight = getreeheight( Current->Right ); p_CurrentR->Left = Current; p_CurrentR->ulLeftHeight = getreeheight( p_CurrentR->Left ); Current = p_Parent->Left; p_Parent->ulLeftHeight = getreeheight( p_Parent->Left ); } else { p_Parent->Right = Current->Right; Current->Right = p_CurrentR->Left; Current->ulRightHeight = getreeheight( Current->Right ); p_CurrentR->Left = Current; p_CurrentR->ulLeftHeight = getreeheight( p_CurrentR->Left ); Current = p_Parent->Right; p_Parent->ulRightHeight = getreeheight( p_Parent->Right ); } } } void rotate_right() { if (Current == Root) // rotate the root { Root = Current->Left; Current->Left = Root->Right; Current->ulLeftHeight = getreeheight( Current->Left ); Root->Right = Current; Root->ulRightHeight = getreeheight( Root->Right ); } else // rotate subroot { LeftRight lr_Temp = m_stackLeftRight.top(); treenode<T> *p_Parent = m_stackTreePath.top(); treenode<T> *p_CurrentL = Current->Left; if (lr_Temp == LEFT) { p_Parent->Left = Current->Left; Current->Left = p_CurrentL->Right; Current->ulLeftHeight = getreeheight( Current->Left ); p_CurrentL->Right = Current; p_CurrentL->ulRightHeight = getreeheight( p_CurrentL->Right ); Current = p_Parent->Left; p_Parent->ulLeftHeight = getreeheight( p_Parent->Left ); } else { p_Parent->Right = Current->Left; Current->Left = p_CurrentL->Right; Current->ulLeftHeight = getreeheight( Current->Left ); p_CurrentL->Right = Current; p_CurrentL->ulRightHeight = getreeheight( p_CurrentL->Right ); Current = p_Parent->Right; p_Parent->ulRightHeight = getreeheight( p_Parent->Right ); } } } int searchtree( T Xname ) { if (Current == NULL) return 0; else { if ( Current->Tdata == Xname) return 1; else if (Current->Tdata < XNAME) { GETRIGHT(); RETURN SEARCHTREE (XNAME); } ELSE { GETLEFT(); RETURN SEARCHTREE (XNAME); } } } // SEARCHTREE VOID DEL( ) { IF ( CURRENT == ROOT ) { IF ( CURRENT->Right != NULL ) { Root = Current->Right; Root->Right = NULL; } else Root = NULL; } else { treenode<T>* Parent = m_stackTreePath.top(); LeftRight lr_Temp = m_stackLeftRight.top(); if ( lr_Temp == RIGHT ) { Parent->Right = Current->Right; delete Current; Current = Parent->Right; } else { Parent->Left = Current->Right; delete Current; Current = Parent->Left; } } m_ulPopulation--; avlbalancetree(); } // del friend ostream& printinorder(ostream& OS, treenode<T>* Q) { if ( Q ) { printinorder( OS, Q->Left ); OS << Q->Tdata << ENDL; PRINTINORDER(OS, Q->Right); return OS; } return OS; } friend ostream& printpostorder(ostream& OS, treenode<T>* Q) { if ( Q ) { printpostorder(OS, Q->Left); printpostorder(OS, Q->Right); OS << Q->Tdata; return OS; } return OS; } friend ostream& printpreorder(ostream& OS, treenode<T>* Q) { if ( Q ) { OS << Q->Tdata; printpreorder(OS, Q->Left); printpreorder(OS, Q->Right); return OS; } return OS; } friend ostream& printreverse(ostream& OS, treenode<T>* Q) { if ( Q ) { printreverse(OS, Q->Right); OS << Q->Tdata; printreverse(OS, Q->Left); return OS; } return OS; } public: avl_tree() { Root = NULL; Current = NULL; m_ulPopulation = 0; m_TranverseType = INORDER; } ~avl_tree () { if ( Root ) { deletenode( Root->Left ); deletenode( Root->Right ); delete Root; } } avl_tree(const avl_tree<T> &n) { if (n.Root) { Root = new treenode<T>; Root->Tdata = n.Root->Tdata; Root->ulLeftHeight = n.Root->ulLeftHeight; Root->ulRightHeight = n.Root->ulRightHeight; Current = n.Current; m_ulPopulation = n.m_ulPopulation; m_TranverseType = n.m_TranverseType; m_stackTreePath = n.m_stackTreePath; m_stackLeftRight = n.m_stackLeftRight; treenode<T> *currL = n.Root->Left; treenode<T> *currR = n.Root->Right; copynode( Root->Left, currL ); copynode( Root->Right, currR ); } else { Root = NULL; Current = NULL; m_ulPopulation = 0; m_TranverseType = INORDER; } } void erase() { if ( Root ) { deletenode( Root->Left ); deletenode( Root->Right ); delete Root; } Root = NULL; Current = NULL; m_ulPopulation = 0; m_stackTreePath.erase(); m_stackLeftRight.erase(); } T* returncurrent() { if (Current) return &Current->Tdata; return NULL; } int operator += ( T Temp ) { if(!locate( Temp )) { treenode<T> *tempnode = new treenode<T>; if ( tempnode == NULL ) return 0; tempnode->Tdata = Temp; tempnode->ulLeftHeight = 0; tempnode->ulRightHeight = 0; tempnode->Left = NULL; tempnode->Right = NULL; if ( Root == NULL ) { Root = tempnode; Current = tempnode; } else { treenode<T>* p_Parent = m_stackTreePath.top(); if ( p_Parent->Tdata > Temp ) { p_Parent->Left = tempnode; m_stackLeftRight.push( LEFT ); } else { m_stackLeftRight.push( RIGHT ); p_Parent->Right = tempnode; } } Current = tempnode; m_ulPopulation++; avlbalancetree(); return 1; } getroot(); return 0; } void operator -= ( T &U ) { if (locate( U )) { treenode<T> *current, *parent; if ( Current->Left != NULL ) { parent = Current; current = Current->Left; while ( current->Right != NULL ) { m_stackTreePath.push( parent ); m_stackLeftRight.push( RIGHT ); parent = current; current = current->Right; } Current->Tdata = current->Tdata; Current = current; parent->Right = current->Left; delete current; avlbalancetree(); m_ulPopulation--; } else del(); } } avl_tree<T> operator=( const avl_tree<T> &n ) { if (n.Root) { Root = new treenode<T>; Root->Tdata = n.Root->Tdata; Current = n.Current; m_ulPopulation = n.m_ulPopulation; m_TranverseType = n.m_TranverseType; m_stackTreePath = n.m_stackTreePath; m_stackLeftRight = n.m_stackLeftRight; treenode<T> *currL = n.Root->Left; treenode<T> *currR = n.Root->Right; copynode( Root->Left, currL ); copynode( Root->Right, currR ); } else { Root = NULL; Current = NULL; m_ulPopulation = 0; m_TranverseType = INORDER; } return *this; } unsigned long census() { return m_ulPopulation; } int isempty() { return (Root == NULL); } // isempty int locate ( T Yname ) { getroot(); return searchtree ( Yname ); } // locate int printkey(ostream& OS, T i_Nodes ) { if(locate( i_Nodes )) { OS << CURRENT->Tdata; return 1; } return 0; } int returncurrent ( T &B ) { if ( Current ) { B = Current->Tdata; return 1; } return 0; } // returncurrent void set_Tree_INORDER() { m_TranverseType = INORDER; } void set_Tree_PREORDER() { m_TranverseType = PREORDER; } void set_Tree_POSTORDER() { m_TranverseType = POSTORDER; } void set_Tree_REVERSE() { m_TranverseType = REVERSE; } }; #endif // AVL_TREE_CC
Internal Links
Parent Article: Main Page