home *** CD-ROM | disk | FTP | other *** search
/ Visual Basic Source Code / Visual Basic Source Code.iso / vbsource / vbdatabs / rbtree.h < prev    next >
Encoding:
C/C++ Source or Header  |  1999-03-14  |  8.7 KB  |  299 lines
  1. // ------------------------------- //
  2. // -------- Start of File -------- //
  3. // ------------------------------- //
  4. // ----------------------------------------------------------- //
  5. // C++ Header File Name: bstree.h
  6. // Compiler Used: MSVC40, DJGPP 2.7.2.1, GCC 2.7.2.1, HP CPP 10.24
  7. // Produced By: Doug Gaer   
  8. // File Creation Date: 01/23/1997 
  9. // Date Last Modified: 03/15/1999
  10. // Copyright (c) 1997 Douglas M. Gaer
  11. // ----------------------------------------------------------- // 
  12. // ---------- Include File Description and Details  ---------- // 
  13. // ----------------------------------------------------------- // 
  14. /*
  15. The VBD C++ classes are copyright (c) 1997, by Douglas M. Gaer.
  16. All those who put this code or its derivatives in a commercial
  17. product MUST mention this copyright in their documentation for
  18. users of the products in which this code or its derivative
  19. classes are used. Otherwise, you have the freedom to redistribute
  20. verbatim copies of this source code, adapt it to your specific
  21. needs, or improve the code and release your improvements to the
  22. public provided that the modified files carry prominent notices
  23. stating that you changed the files and the date of any change.
  24.  
  25. THIS SOFTWARE IS PROVIDED "AS IS" WITHOUT WARRANTY OF ANY KIND.
  26. THE ENTIRE RISK OF THE QUALITY AND PERFORMANCE OF THIS SOFTWARE
  27. IS WITH YOU. SHOULD ANY ELEMENT OF THIS SOFTWARE PROVE DEFECTIVE,
  28. YOU WILL ASSUME THE COST OF ALL NECESSARY SERVICING, REPAIR, OR
  29. CORRECTION.
  30.  
  31. This is a generic (R)ed (B)lack binary search (T)ree. The
  32. RBTree class maintains binary search tree properties, by
  33. allowing nodes to have no more then two children, but it
  34. ensures the tree will be balanced by assigning links the
  35. colors RED and BLACK. A black parent link is referred to as
  36. a black node and a red parent link is referred to as a red
  37. node.
  38.  
  39. Changes: 
  40. ================================================================
  41. 03/20/1998 - Removed duplicate definition of the FreeNode()
  42. function.
  43. Changed by: Doug Gaer
  44. ================================================================
  45. */
  46. // ----------------------------------------------------------- //   
  47. #ifndef __RBTREE_HPP
  48. #define __RBTREE_HPP
  49.  
  50. #include "rbnode.h"
  51. #include "bstreeb.h"
  52. #include "rbtreeb.h"
  53. #include "twalk.h"
  54.  
  55. template<class TYPE>
  56. class RBTree
  57. {
  58. public:
  59.   RBTree() { Root = 0; }
  60.   virtual ~RBTree();
  61.   RBTree(const RBTree<TYPE> &t) { Root = 0; Copy(t); }
  62.   void operator=(const RBTree<TYPE> &t) { if (this != &t) Copy(t); }
  63.  
  64. public:
  65.   int Copy(const RBTree<TYPE> &t);
  66.   int Copy(const RBTree<TYPE> &t, WalkOrder w);
  67.   void Clear() { DelTree(Root); Root = 0; }
  68.   RBNode<TYPE> *GetMember(const TYPE &X);
  69.   const RBNode<TYPE> *GetMember(const TYPE &X) const {
  70.     return ((RBTree<TYPE> *)this)->GetMember(X); }
  71.   RBNode<TYPE> *Add(const TYPE &X, int &existed);
  72.   RBNode<TYPE> *Add(const TYPE &X) { int dmy; return Add(X, dmy); }
  73.   RBNode<TYPE> *Detach(const TYPE &X);
  74.   RBNode<TYPE> *DetachMin() {
  75.     return (RBNode<TYPE> *)DetachMinMax((RBNodeBase *&)Root, 0); }
  76.   RBNode<TYPE> *DetachMax() {
  77.     return (RBNode<TYPE> *)DetachMinMax((RBNodeBase *&)Root, 1); }
  78.   int Delete(const TYPE &X);
  79.   void DeleteMin() { FreeNode(DetachMin()); }
  80.   void DeleteMax() { FreeNode(DetachMax()); }
  81.   RBNode<TYPE> *GetRoot() { return Root; }
  82.   RBNode<TYPE> *GetMin() { return (RBNode<TYPE> *)Minimum(Root); }
  83.   RBNode<TYPE> *GetMax() { return (RBNode<TYPE> *)Maximum(Root); }
  84.   int IsEmpty() const { return Root == 0; }
  85.  
  86. protected:
  87.   // Allocates a new RBNode<TYPE> node.
  88.   virtual RBNode<TYPE> *AllocNode
  89.   (const TYPE &X, char c=1, RBNode<TYPE> *l=0, RBNode<TYPE> *r=0);
  90.     
  91.   RBNode<TYPE> *DupTree(RBNode<TYPE> *t);
  92.   void FreeNode(RBNode<TYPE> *n);
  93.   void DelTree(RBNode<TYPE> *t);
  94.  
  95. protected:
  96.   RBNode<TYPE> *Root;
  97. };
  98.  
  99. template<class TYPE>
  100. RBTree<TYPE>::~RBTree()
  101. {
  102.   Clear();
  103. }
  104.  
  105. template<class TYPE>
  106. RBNode<TYPE> *RBTree<TYPE>::
  107. AllocNode(const TYPE &X, char c, RBNode<TYPE> *l, RBNode<TYPE> *r)
  108. {
  109.   return new RBNode<TYPE>(X, c, l, r);
  110. }
  111.  
  112. template<class TYPE>
  113. void RBTree<TYPE>::FreeNode(RBNode<TYPE> *n)
  114. {
  115.   delete n;
  116. }
  117.  
  118. template<class TYPE>
  119. RBNode<TYPE> *RBTree<TYPE>::GetMember(const TYPE &X)
  120. // Returns pointer to node containing data X if there is
  121. // such a node in the tree t, otherwise, a 0 is returned.
  122. // Assumes TYPE has '<' and '==' defined.
  123. {
  124.   RBNode<TYPE> *t = Root;
  125.   while (t) {
  126.     if (X == t->Data) break;
  127.     t = (X < t->Data) ? t->GetLeft() : t->GetRight();
  128.   }
  129.   return t;
  130. }
  131.  
  132. template<class TYPE>
  133. RBNode<TYPE> *RBTree<TYPE>::Add(const TYPE &X, int &exists)
  134. {
  135.   PtrPack pp;
  136.   int side;
  137.  
  138.   exists = 1;
  139.   pp.t = Root; pp.p = 0; pp.g = 0; pp.gg = 0;
  140.  
  141.   while(pp.t && X != ((RBNode<TYPE> *)(pp.t))->Data) {
  142.     // If on a set of three binary nodes with a black
  143.     // parent node and red child nodes, split it into
  144.     // two single binary nodes with two black children.
  145.     if ((pp.t->Left && pp.t->GetLeft()->color == RedNode) &&
  146.         (pp.t->Right && pp.t->GetRight()->color == RedNode)) {
  147.        pp.t->color = RedNode;
  148.        pp.t->GetLeft()->color = BlackNode;
  149.        pp.t->GetRight()->color = BlackNode;
  150.        // Check for two reds in a row, and adjust if so
  151.        if (pp.p && pp.p->color == RedNode)
  152.           Root = (RBNode<TYPE> *)InsBalance(Root, pp);
  153.     }
  154.     pp.gg = pp.g; pp.g = pp.p; pp.p = pp.t;
  155.     if (X < ((RBNode<TYPE> *)(pp.t))->Data) {
  156.        pp.t = pp.t->GetLeft(); side = 0;
  157.     }
  158.     else {
  159.        pp.t = pp.t->GetRight(); side = 1;
  160.     }
  161.   }
  162.  
  163.   // Reached the bottom, with no matching node
  164.   if (pp.t == 0) {
  165.      exists = 0;
  166.      pp.t = AllocNode(X, RedNode);
  167.      if (pp.t == 0) return 0; // Couldn't add
  168.      if (pp.p) {
  169.         if (side) pp.p->Right = pp.t; else pp.p->Left = pp.t;
  170.      }
  171.      else Root = (RBNode<TYPE> *)(pp.t);
  172.      // Check for two reds in a row, and adjust if so
  173.      if (pp.p && pp.p->color == RedNode)
  174.         Root = (RBNode<TYPE> *)InsBalance(Root, pp);
  175.   }
  176.  
  177.   Root->color = BlackNode; // Root always made black
  178.  
  179.   return (RBNode<TYPE> *)(pp.t);
  180. }
  181.  
  182. template<class TYPE>
  183. RBNode<TYPE> *RBTree<TYPE>::Detach(const TYPE &X)
  184. {
  185.   struct PtrPack pp;
  186.  
  187.   if (Root == 0) return 0;
  188.  
  189.   pp.t = Root; pp.p = 0; pp.g = 0;
  190.   pp.m = 0; pp.pm = 0;
  191.  
  192.   while (pp.t) {
  193.     // Go down the tree one level, searching for node to delete
  194.     if ( ((RBNode<TYPE> *)(pp.t))->Data == X ) {
  195.        pp.m = pp.t;  // Record matching node
  196.        pp.pm = pp.p; // And it's parent
  197.     }
  198.  
  199.     // Update ancestor pointers
  200.     pp.g = pp.p; pp.p = pp.t;
  201.  
  202.     if (X < ((RBNode<TYPE> *)(pp.t))->Data) {
  203.        pp.t = pp.p->GetLeft(); pp.s = pp.p->GetRight();
  204.     }
  205.     else { // Walk down even if t matches, to look for successor
  206.        pp.t = pp.p->GetRight(); pp.s = pp.p->GetLeft();
  207.     }
  208.  
  209.     if (pp.s) {
  210.        pp.ls = pp.s->GetLeft(); pp.rs = pp.s->GetRight();
  211.     }
  212.     else {
  213.        pp.ls = 0; pp.rs = 0;
  214.     }
  215.  
  216.     Root = (RBNode<TYPE> *)DelBalance(Root, pp);
  217.  
  218.   } 
  219.  
  220.   Root = (RBNode<TYPE> *)DoReplacement(Root, pp);
  221.  
  222.   if (Root) Root->color = BlackNode;
  223.  
  224.   return (RBNode<TYPE> *)pp.m; // Node to delete
  225.  
  226. }
  227.  
  228. template<class TYPE>
  229. int RBTree<TYPE>::Delete(const TYPE &X)
  230. {
  231.   RBNode<TYPE> *n = Detach(X);
  232.  
  233.   if (n) {
  234.      FreeNode(n);
  235.      return 1;
  236.   }
  237.   else return 0;
  238. }
  239.  
  240. template<class TYPE>
  241. void RBTree<TYPE>::DelTree(RBNode<TYPE> *t)
  242. // Recursively deletes tree t, using post-order traversal
  243. {
  244.   if (t == 0) return;
  245.   DelTree(t->GetLeft());
  246.   DelTree(t->GetRight());
  247.   FreeNode(t);
  248. }
  249.  
  250. template<class TYPE>
  251. RBNode<TYPE> *RBTree<TYPE>::DupTree(RBNode<TYPE> *t)
  252. // Duplicates all of the nodes of tree t using a post-order
  253. // traversal. Returns root of copy, or 0 if couldn't
  254. // allocate root.
  255. {
  256.   if (t == 0) return 0;
  257.   RBNode<TYPE> *l = DupTree(t->GetLeft());
  258.   RBNode<TYPE> *r = DupTree(t->GetRight());
  259.   return AllocNode(t->Data, t->color, l, r);
  260. }
  261.  
  262.  
  263. template<class TYPE>
  264. int RBTree<TYPE>::Copy(const RBTree<TYPE> &t)
  265. // Copies the nodes in tree t by using a recursive node
  266. // duplication process. Clears this tree first.
  267. {
  268.   Clear();
  269.   RBNode<TYPE> *r = DupTree(t.Root);
  270.   if (r) {
  271.      Root = r;
  272.      return 1;
  273.   }
  274.   else return 0;
  275. }
  276.  
  277. template<class TYPE>
  278. int RBTree<TYPE>::Copy(const RBTree<TYPE> &t, WalkOrder w)
  279. // Copies the nodes of tree t by walking t during a w-type
  280. // traversal, and adding the nodes to this tree using the
  281. // normal binary insertion process.
  282. {
  283.   Clear();
  284.   TreeWalker< RBNode<TYPE> > tw(t.Root, w);
  285.   RBNode<TYPE> *nxt;
  286.   while(1) {
  287.     nxt = tw.Next();
  288.     if (nxt == 0) break;
  289.     Add(nxt->Data);
  290.   }
  291.   return 1;
  292. }
  293.  
  294. #endif // __RBTREE_HPP
  295. // ----------------------------------------------------------- // 
  296. // ------------------------------- //
  297. // --------- End of File --------- //
  298. // ------------------------------- //
  299.