// $Id: rb_tree.cc,v 1.2 1999/06/05 23:29:16 greear Exp $ // $Revision: 1.2 $ $Author: greear $ $Date: 1999/06/05 23:29:16 $ // //ScryMUD Server Code //Copyright (C) 1998 Ben Greear // //This program is free software; you can redistribute it and/or //modify it under the terms of the GNU General Public License //as published by the Free Software Foundation; either version 2 //of the License, or (at your option) any later version. // //This program is distributed in the hope that it will be useful, //but WITHOUT ANY WARRANTY; without even the implied warranty of //MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the //GNU General Public License for more details. // //You should have received a copy of the GNU General Public License //along with this program; if not, write to the Free Software //Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA. // // To contact the Author, Ben Greear: greear@cyberhighway.net, (preferred) // greearb@agcs.com // // rb_tree.cc -- Implementation of the search tree library #include <stdlib.h> #include <iostream.h> #define True 1 #define False 0 #define Red(K,V) TreeNode<K,V>::Red #define Black(K,V) TreeNode<K,V>::Black #define Palette(K,V) TreeNode<K,V>::Palette //void log(const char*); //Ben's Standard log function // ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ // Constructors and Destructor // Constructor with comparison function // template <class K, class V> Tree<K,V>::Tree (int (*F)(const K &, const K &)) { Root = 0; Compare = F; } // Copy constructor // template <class K, class V> Tree<K,V>::Tree (const Tree<K,V> &T) { Root = Copy(T.Root); Compare = T.Compare; } // Copy -- Recursively copy a tree // template <class K, class V> TreeNode<K,V> *Tree<K,V>::Copy (register TreeNode<K,V> *N) { if (N) { TreeNode<K,V> *M = new TreeNode<K,V> (N->Color, Copy(N->Left), Copy(N->Right), N->Key, N->Value); if (!M) { //log("ERROR: (TreeNode) Memory allocation failed."); } return M; } else return 0; } // Destructor // template <class K, class V> Tree<K,V>::~Tree () { Clear (); } // ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ // Operators template <class K, class V> Tree<K, V> &Tree<K,V>::operator = (const Tree<K,V> &T) { Root = Copy(T.Root); Compare = T.Compare; return *this; } // ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ // Access // Find -- Find the value associated with a key // // Find returns 1 if the key is in the tree, and 0 otherwise. // The value associated with the key is returned through the second argument. // template <class K, class V> short Tree<K,V>::Find (register const K &Key, V &Value) { register TreeNode<K,V> *N = Root; while (N) { register int C = Compare(Key, N->Key); if (C < 0) N = N->Left; else if (C > 0) N = N->Right; else break; } return N ? (Value = N->Value, True) : False; } // ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ // Insertion and deletion // Insert -- Insert a key-value pair into a tree // // If the key is already in the tree, the associated value is updated. // template <class K, class V> void Tree<K,V>::Insert (const K &Y, const V &X) { Root = Insert1(Y, X, Root); Root->Color = Black(K,V); } // Insert1 -- Recursive helper function of Insert. // template <class K, class V> TreeNode<K,V> *Tree<K,V>::Insert1 (K Y, V X, TreeNode<K,V> *N) { if (!N) { TreeNode<K,V> *M = new TreeNode<K,V> (Red(K,V), (TreeNode<K,V> *)0, (TreeNode<K,V> *)0, Y, X); if (!M) { //log("ERROR: (rb_tree) No memory left"); } return M; } else if ((*Compare)(Y, N->Key) < 0) { N->Left = Insert1 (Y, X, N->Left); return InsertRebalance(N,Y); } else if ((*Compare)(Y, N->Key) > 0) { N->Right = Insert1 (Y, X, N->Right); return InsertRebalance(N,Y); } else { N->Value = X; return N; } } // InsertRebalance -- Restore the color invariants at a node after insertion // template <class K, class V> TreeNode<K,V> *Tree<K,V>::InsertRebalance (TreeNode<K,V> *N, const K &Key) { if (N && N->Color == Black(K,V)) if ((*Compare)(Key, N->Key) < 0) // Cases 1-4 { register TreeNode<K,V> *M = N->Left; if (M && M->Color == Red(K,V)) if (N->Right && N->Right->Color == Red(K,V)) // Cases 1,3 { FlipBoth(N); return N; } else // Cases 2,4 { if ((*Compare)(Key, M->Key) > 0) // Case 4 N->Left = RotateLeft(M); FlipLeft(N); return RotateRight(N); } else return N; } else // Cases 5-8 { register TreeNode<K,V> *M = N->Right; if (M && M->Color == Red(K,V)) if (N->Left && N->Left->Color == Red(K,V)) // Cases 5,7 { FlipBoth(N); return N; } else // Cases 6,8 { if ((*Compare)(Key, M->Key) < 0) // Case 8 N->Right = RotateRight(M); FlipRight(N); return RotateLeft(N); } else return N; } else return N; } // Delete -- Delete a key-value pair from a tree, given the key // // If the key is not in the tree, nothing is changed. // template <class K, class V> void Tree<K,V>::Delete (register const K &Y) { short Defect; Root = Delete1(Y, Root, Defect); if (Root) Root->Color = Black(K,V); } // Delete1 -- Recursive helper function of Delete // template <class K, class V> TreeNode<K,V> *Tree<K,V>::Delete1 (K Y, TreeNode<K,V> *N, short &Defect) { if (!N) return ((TreeNode<K,V> *) 0); else if (N && (*Compare)(Y, N->Key) < 0) { N->Left = Delete1 (Y, N->Left, Defect); return DeleteRebalance (N, N->Left, Defect); } else if (N && (*Compare)(Y, N->Key) > 0) { N->Right = Delete1(Y, N->Right, Defect); return DeleteRebalance (N, N->Right, Defect); } else if (!N->Left) return DeleteBasis (N, N->Right, Defect); else if (!N->Right) return DeleteBasis (N, N->Right, Defect); else { N->Right = Delete2(N->Right, N, Defect); return DeleteRebalance(N, N->Right, Defect); } } // Delete2 -- 2nd recursive helper function of Delete, called in Delete1 // template <class K, class V> TreeNode<K,V> *Tree<K,V>::Delete2 (TreeNode<K,V> *N, TreeNode<K,V> *P, short &Defect) { if (N->Left) { N->Left = Delete2(N->Left, P, Defect); return DeleteRebalance (N, N->Left, Defect); } else // (N->Left) { P->Key = N->Key; P->Value = N->Value; return DeleteRebalance(N, N->Right, Defect); } } // DeleteBasis -- Base cases for deletion and rebalancing // // Splice out a node with one child, and return the child. // template <class K, class V> inline TreeNode<K,V> *Tree<K,V>::DeleteBasis (register TreeNode<K,V> *N, register TreeNode<K,V> *M, short &Defect) { if (N->Color == Red(K,V)) Defect = False; else if (!M || M->Color == Black(K,V)) Defect = True; else { Flip(M); Defect = False; } delete N; return M; } // DeleteRebalance -- Restore the color invariants at a node after deletion // template <class K, class V> TreeNode<K,V> *Tree<K,V>::DeleteRebalance (register TreeNode<K,V> *N, register TreeNode<K,V> *M, short &Defect) { if (Defect) { if (M && M->Color == Red(K,V)) // Case 0 { Flip(M); Defect = False; } else if (M == N->Left) // Cases 1-4 { register TreeNode<K,V> *S = N->Right; if (S->Color == Red(K,V)) // Case 1 { FlipRight(N); N = RotateLeft(N); N->Left = DeleteRebalance(N->Left, N->Left->Left, Defect); // // This call will encounter one of cases 2-4, and within // two steps, set Defect to False } else if ((!S->Left || S->Left->Color == Black(K,V)) && (!S->Right || S->Right->Color == Black(K,V))) // Case 2 { Flip(S); Defect = True; } else // Cases 3,4 { if (S->Left && S->Left->Color == Red(K,V)) // Case 3 { N->Right = RotateRight(N->Right); FlipRight(N->Right); } N = RotateLeft(N); FlipLeft(N); Flip(N->Right); Defect = False; } } else // Cases 5-8 { register TreeNode<K,V> *S = N->Left; if (S->Color == Red(K,V)) // Case 5 { FlipLeft(N); N = RotateRight(N); N->Right = DeleteRebalance(N->Right, N->Right->Right, Defect); // // This call will encounter one of cases 6-8, and within // two steps, set Defect to False } else if ((!S->Right || S->Right->Color == Black(K,V)) && (!S->Left || S->Left->Color == Black(K,V))) // Case 6 { Flip(S); Defect = True; } else // Cases 7,8 { if (S->Right && S->Right->Color == Red(K,V)) // Case 7 { N->Left = RotateLeft(N->Left); FlipLeft(N->Left); } N = RotateRight(N); FlipRight(N); Flip(N->Left); Defect = False; } } } return N; } // ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ // Scaffolding // TreeCompare -- Default key comparison function // template <class T> inline int TreeCompare (const T &X, const T &Y) { return (X < Y) ? -1 : ((X > Y) ? 1 : 0); } // Flip -- Flip the color at a node // // Assumes the node is not nil. // template <class K, class V> inline void Tree<K,V>::Flip (register TreeNode<K,V> *N) { N->Color = (N->Color == Red(K,V)) ? Black(K,V) : Red(K,V); } // FlipLeft -- Exchange the color of a node with its left child // // Assumes the node and its left child are not nil. // template <class K, class V> inline void Tree<K,V>::FlipLeft (register TreeNode<K,V> *N) { Palette(K,V) C = N->Color; N->Color = N->Left->Color; N->Left->Color = C; } // FlipRight -- Exchange the color of a node with its right child // // Assumes the node and its right child are not nil. // template <class K, class V> inline void Tree<K,V>::FlipRight (register TreeNode<K,V> *N) { Palette(K,V) C = N->Color; N->Color = N->Right->Color; N->Right->Color = C; } // FlipBoth -- Exchange the color of a node with its left and right children // // Assumes the node and its right and left children are not nil. // template <class K, class V> inline void Tree<K,V>::FlipBoth (register TreeNode<K,V> *N) { Palette(K,V) C = N->Color; N->Color = N->Left->Color; N->Left->Color = C; N->Right->Color = C; } // RotateRight -- Right rotation at a node // // Assumes that both the node and its left child are not nil. // template <class K, class V> inline TreeNode<K,V> *Tree<K,V>::RotateRight (register TreeNode<K,V> *N) { register TreeNode<K,V> *M = N->Left; N->Left = M->Right; M->Right = N; return M; } // RotateLeft -- Left rotation at a node // // Assumes that both the node and its right child are not nil. // template <class K, class V> inline TreeNode<K,V> *Tree<K,V>::RotateLeft (register TreeNode<K,V> *N) { register TreeNode<K,V> *M = N->Right; N->Right = M->Left; M->Left = N; return M; } // Dump -- Write the subtree rooted a given node in preorder on standard error // template <class K, class V> void Tree<K,V>::Dump (TreeNode<K,V> *N, int D) { if (N) { for (int i = 1; i <= D; i++) cerr << " "; cerr << "(" << N->Key << ", " << N->Value << ")\n"; Dump(N->Left, D + 1); Dump(N->Right, D + 1); } } // ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ // Iteration // Min -- Looks up minimum key // // Min returns a 1 if the tree is not empty, 0 otherwise. // If the tree is not empty, the key is returned in Min's // reference argument. template <class K, class V> short Tree<K,V>::Min (K &Y) { if (Root) { TreeNode<K,V> *N = Root; while (N->Left) N = N->Left; Y = N->Key; return 1; } else return 0; } // Max -- Looks up maximum key // // Max returns a 1 if the tree is not empty, 0 otherwise. // If the tree is not empty, the key is returned in Max's // reference argument. template <class K, class V> short Tree<K,V>::Max (K &Y) { if (Root) { TreeNode<K,V> *N = Root; while (N->Right) N = N->Right; Y = N->Key; return 1; } else return 0; } // Next -- Finds the next highest key // // Next returns a 1 if there is a next higher key, 0 otherwise. // If there is a next higher key, even if the given key isn't in // the tree, Next returns the next highest key in its reference // argument. template <class K, class V> short Tree<K,V>::Next (K &Y) { K I; short S = Max(I); if (S && ((*Compare)(Y, I) < 0)) //if there is a Next { TreeNode<K,V> *N, *A, *P; N = Root; A = Root; P = Root; while (N && ((*Compare)(Y, N->Key))) //find N in tree, if there is one switch ((*Compare)(Y, N->Key)) //read these rem's as N is Node { //that has Y as key case -1: P = N; A = N; N = N->Left; break; case 1: P = N; N = N->Right; break; } if (!N) // if N isn't in tree switch ((*Compare)(Y, P->Key)) { case -1: Y = P->Key; break; case 1: Y = A->Key; break; } // having reached here, N is in the tree else if (!N->Right) // N doesn't have a rt child Y = A->Key; else // (N->Right), N does have a rt. child { N = N->Right; while (N->Left) N = N->Left; Y = N->Key; } return 1; } else // there is not a Next return 0; } // Prev -- Finds the next lowest key // // Prev returns a 1 if there is a next lower key, 0 otherwise. // If there is a next lower key, even if the given key isn't in // the tree, Prev returns the next lowest key in its reference // argument. template <class K, class V> short Tree<K,V>::Prev (K &Y) // This algorithm is basically based on the idea that if the Node N // that contains key Y, has a left child, the previous Node is // the Maximum Node in the subtree of which N's left child is the // root. If Node N doesn't have a left child, the previous node // is the closest left grandparent of N. { K I; short S = Max(I); if (S && ((*Compare)(Y, I) > 0)) // if there is a previous Node { TreeNode<K,V> *N, *A, *P; N, A, P = Root; while (N && (*Compare)(Y, N->Key)) //try to find N, if there is one switch ((*Compare)(Y, N->Key)) { case -1: P = N; N = N->Left; break; case 1: A = N; P = N; N = N->Right; break; } if (!N) //if there isn't an N switch ((*Compare)(Y, P->Key)) { case -1: Y = A->Key; break; case 1: Y = P->Key; break; } // there is an N in the tree else if (!N->Left) //if N has no left child Y = A->Key; else // (N->Left), N has a left child { while (N->Right) N = N->Right; Y = N->Key; } return 1; } else //if there is not a previous node return 0; } // ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ // Iteration // Size -- Calculates the size of the tree and returns that value // template <class K, class V> int Tree<K,V>::Size () { int X = 0; if (Root) Size1 (Root, X); return X; } // Size1 -- Help function of Size // template <class K, class V> void Tree<K,V>::Size1 (TreeNode<K,V> *N, int &X) { if (N->Left) Size1 (N->Left); if (N->Right) Size1 (N->Right); X++; } // IsEmpty -- Boolean for "Is the tree empty?" // // Isempty returns a 1 if the tree is not empty, 0 otherwise. template <class K, class V> short Tree<K,V>::IsEmpty () { return Root ? 1 : 0; } // Clear -- Deallocates the memory taken up by a tree. // // Clear uses the recursive helper function Clear1. template <class K, class V> void Tree<K,V>::Clear () { if (Root) Clear1(Root); delete Root; Root = (TreeNode<K,V> *) 0; } // Clear1 -- Recursive helper function of Clear. // template <class K, class V> void Tree<K,V>::Clear1 (TreeNode<K,V> *N) { if (N->Left) { if (N->Left->Left || N->Left->Right) Clear1(N->Left); delete N->Left; } if (N->Right) { if (N->Right->Left || N->Right->Right) Clear1(N->Right); delete N->Right; } }