home *** CD-ROM | disk | FTP | other *** search
/ Power-Programmierung / CD2.mdf / c / library / dos / diverses / leda / src / basic / _rb_tree.c < prev    next >
Encoding:
C/C++ Source or Header  |  1991-11-15  |  20.3 KB  |  764 lines
  1. /*******************************************************************************
  2. +
  3. +  LEDA  2.1.1                                                 11-15-1991
  4. +
  5. +
  6. +  _rb_tree.c
  7. +
  8. +
  9. +  Copyright (c) 1991  by  Max-Planck-Institut fuer Informatik
  10. +  Im Stadtwald, 6600 Saarbruecken, FRG     
  11. +  All rights reserved.
  12. + 
  13. *******************************************************************************/
  14.  
  15.  
  16. //  red-black-tree ( rb-tree )
  17. //  implementation of memberfunctions
  18. //  mit verkettung der blaetter
  19.  
  20. //------------------------------------------------------------------
  21.  
  22. #include <LEDA/rb_tree.h>
  23.  
  24.  
  25. enum left_or_right { left = 0 ,right = 1, undefined = 2 };
  26.  
  27. enum colour  { node_red = 0 ,node_black = 1 ,leaf_red = 2 ,                                    leaf_black = 3 , unknown = 4 }; 
  28.  
  29. class rb_tree_node;
  30.  
  31.  
  32. rb_tree_node* rb_tree::next_item(rb_tree_node* p) const
  33. { rb_tree_node* x = p->son[right];
  34.   return (x == list_ptr) ? 0 : x;
  35.  }
  36.  
  37.  
  38. //------------------------------------------------------------------
  39. // next_smaller(x) : gibt zeiger auf den knoten mit key x zurueck
  40. // falls dieser nicht exist. sucht er den knoten mit key y , wobei
  41. // y < x und y maximal ; falls dieser auch nicht vorhanden => return 0
  42. //------------------------------------------------------------------
  43.  
  44. rb_tree_node* rb_tree::next_smaller(ent x) const
  45. {
  46.   TRACE(( "next_smaller : key : %d\n",int(x) ));
  47.  
  48.   rb_tree_node* p = get_node(x);
  49.  
  50.   if ( !p ) return 0;    // baum leer
  51.  
  52.   if ( cmp(p->k,x) <= 0 ) return p;
  53.   else if ( p != min() ) return p->son[left]; 
  54.   else return 0;
  55. }
  56.  
  57. //------------------------------------------------------------------
  58. // next_bigger(x) : gibt zeiger auf den knoten mit key x zurueck
  59. // falls dieser nicht exist. sucht er den knoten mit key y , wobei
  60. // y > x und y minimal ; falls dieser auch nicht vorhanden => return 0
  61. //------------------------------------------------------------------
  62.  
  63. rb_tree_node* rb_tree::next_bigger(ent x) const
  64. {
  65.   TRACE((" next_bigger : key : %d\n",int(x) ));
  66.  
  67.   rb_tree_node* p = get_node(x);
  68.  
  69.   if ( !p ) return 0;    // baum leer
  70.  
  71.   if ( cmp( p->k,x ) >= 0 ) return p;
  72.   else if ( p != max() ) return p->son[right];
  73.   else return 0;
  74. }
  75.  
  76. // by sn :
  77.  
  78. rb_tree_node* rb_tree::lookup(ent x) const
  79. { rb_tree_node* p = get_node(x);
  80.   if ( !p ) return 0;  
  81.   if ( cmp( p->k,x ) == 0 ) return p;
  82.   else return 0;
  83. }
  84.  
  85. void  rb_tree::change_inf(rb_tree_node* p,ent y) 
  86. { clear_inf(p->e);
  87.   copy_inf(y);
  88.   p->e = y; 
  89.  }
  90.  
  91.  
  92. //------------------------------------------------------------------
  93. // get_node1(x) : gibt pointer auf das blatt zurueck , das bei der suche
  94. //               nach dem element mit key x gefunden wird            
  95. //               falls treesize = 0 => pointer = 0
  96. // mit cmp-function
  97. //------------------------------------------------------------------
  98.  
  99.  rb_tree_node* rb_tree::get_node1(ent x) const
  100.  
  101. { 
  102.   TRACE(("get_node1 : key :%d\n",int(x) ));
  103.  
  104.   rb_tree_node* p;
  105.   if ( p = root)    // p:=root; if ( p != 0) continue
  106.      while ( p->is_node()  )
  107.        p =  (cmp(x,p->k) <= 0)  ? p->son[left] : p->son[right]  ; 
  108.   return p;
  109. }
  110.  
  111.  
  112. //----------------------------------------------------------------------
  113. // member(x) : true ,falls element with key x im baum , sonst 0
  114. //----------------------------------------------------------------------
  115.  
  116. int rb_tree::member(ent x) const
  117. {
  118.   TRACE(("member : key :%d\n",int(x) ));
  119.  
  120.   rb_tree_node* p = get_node(x);
  121.   return ( p  &&  ( cmp(p->k,x) == 0 ) ) ? true : false  ;
  122. }
  123.  
  124. //------------------------------------------------------------------
  125. // access(x) : gibt eintrag des elements mit key x zurueck
  126. //------------------------------------------------------------------
  127.  
  128. ent& rb_tree::access(ent x)
  129.  
  130. { 
  131.    TRACE(("access : key :%d\n",int(x) ));
  132.  
  133.    rb_tree_node* p = get_node(x);
  134.    if ( p  &&   ( cmp(x,p->k) == 0 ) )
  135.      return p->e;
  136.    else  error_handler(1," access(x) ,but no element with key x in tree ");
  137. }
  138.  
  139.  
  140. //----------------------------------------------------------------------
  141. // search :
  142. //----------------------------------------------------------------------
  143. // prog.34 in mehlhorn page 192
  144. // wird fuer insert und delete benoetigt . gibt Stack zurueck, worin 
  145. // pfad von wurzel zum blatt (inkl.) gespeichert ist
  146. //
  147. // search : version mit cmp-function
  148. //----------------------------------------------------------------------
  149.  
  150. rb_tree_node* rb_tree::search(ent x)
  151. {
  152.   TRACE(("search : key : %d \n",int(x) ));
  153.  
  154. // s.n.: result = inner node with key x (nil if not existing)
  155.  
  156.   rb_tree_node* result=nil;
  157.  
  158.   st.clear();
  159.  
  160.   rb_tree_node* p = root ;
  161.   if ( p )    // p:=root; if ( p != 0) continue
  162.    { while ( p->is_node() )     // else Stack remains empty
  163.         { int rel = cmp(x,p->k);
  164.           if (  rel <= 0 )
  165.                 { if (  rel == 0 ) result = p;
  166.                   push(p,left); 
  167.                   p = p->son[left];
  168.                } 
  169.            else { push(p,right); 
  170.                   p = p->son[right];
  171.                  }
  172.          }
  173.        push(p,undefined);  //leaf on the top of Stack
  174.      }
  175.   return result;
  176. }
  177.  
  178. //----------------------------------------------------------------------
  179. // pop() : private memberfunktion ( fuer insert,delete )
  180. //----------------------------------------------------------------------
  181.  
  182. void rb_tree::pop(rb_tree_node_ptr& q, int& dir1)
  183. {  
  184.    TRACE(("pop betreten : leerer keller : %s \n",                                              st.empty() ? "ja"  : "nein" ));
  185.  
  186.    stack_el z = st.pop();
  187.    q = z.nodeptr;
  188.    dir1 = z.dir;
  189.  
  190.    TRACE(("pop verlassen: key : %d :dir : %d  :leerer keller : %s \n"                   ,int(q->k),dir1, st.empty() ? "ja" : "nein"));
  191. }
  192.  
  193. //----------------------------------------------------------------------
  194. // rotation : private memberfunktion ( fuer insert,delete )
  195. //----------------------------------------------------------------------
  196.  
  197. void rb_tree::rotation(rb_tree_node* p,rb_tree_node* q, int left_right)
  198. {
  199.    TRACE(("rotation\n"));
  200.  
  201.    p->son[left_right] = q->son[1-left_right];
  202.    q->son[1-left_right] = p;
  203. }  
  204.  
  205.  
  206. //----------------------------------------------------------------------
  207. // double_rotation : private memberfunktion ( fuer insert, delete )
  208. //----------------------------------------------------------------------
  209.  
  210. void rb_tree::double_rotation(rb_tree_node* p, rb_tree_node* q, rb_tree_node* r,
  211.                               int dir1, int dir2)
  212. {
  213.    TRACE(("double_rotation\n"));
  214.  
  215.    p->son[dir1] = r->son[dir2];
  216.    q->son[dir2] = r->son[dir1]; 
  217.    r->son[dir1] =q;
  218.    r->son[dir2] =p;
  219. }
  220.  
  221. //----------------------------------------------------------------------
  222. // if_root : falls p == root => root = q
  223. //           sonst haenge q an frueheren vater von p ( den vater 
  224. //            erhaelt man durch pop )
  225. //----------------------------------------------------------------------
  226.  
  227. void rb_tree::if_root(rb_tree_node* p,rb_tree_node* q)
  228. { 
  229.   TRACE(( "if_root \n"));
  230.  
  231.   int dir;
  232.  
  233.   if ( p == root ) root = q;
  234.   else {
  235.          TRACE((" if_root :Stacksize ist %d\n", st.size() ));
  236.          pop(p,dir);
  237.          p->son[dir] = q;
  238.        }
  239. }
  240.  
  241. //----------------------------------------------------------------------
  242. // insert(x,y) : prog. 35/36/37 in mehlhorn seite 193     
  243. // fuegt element mit key x und entry y ein
  244. // gibt zeiger auf eingefuegten knoten zurueck
  245. //----------------------------------------------------------------------
  246.  
  247. rb_tree_node* rb_tree::insert( ent x, ent y)
  248. {  
  249.    TRACE(("insert : key = %d \n" , int (x) ));
  250.  
  251.    copy_key(x);
  252.    copy_inf(y);
  253.  
  254.    rb_tree_node* q = new rb_tree_node(x,y,leaf_black,0,0);
  255.    rb_tree_node* r = new rb_tree_node;
  256.    rb_tree_node* p; 
  257.    rb_tree_node* back = q;  // wird von insert zurueckgegeben
  258.    int dir1,dir2;
  259.  
  260.    ++ counter;
  261.  
  262.    if ( !root ) 
  263.    { 
  264.      delete r;
  265.      list_ptr = root = q;
  266.      root->son[right] = root->son[left] = root;  // verkettung
  267.      return back ;
  268.    }
  269.  
  270.    search(x);       // danach steht im Stack st der suchpfad
  271.  
  272.    pop(p,dir1);
  273.  
  274.    if ( cmp(p->k,x) == 0 )  
  275.                                       // falls element mit gleichem
  276.    {                                  // key exist. => ueberschreiben
  277.      delete r;
  278.      delete q;
  279.      --counter;
  280.      p->e = y;
  281.      return p;
  282.    }
  283.  
  284.    r->gets_red_node();
  285.    if ( cmp(x,p->k) < 0 )
  286.       { r->k = x;
  287.         r->son[left] = q;
  288.         r->son[right]= p;
  289.  
  290.        q->son[left] = p->son[left];   // verkettung
  291.        q->son[right] = p;
  292.        p->son[left]->son[right] = q;
  293.        p->son[left] = q;
  294.        if ( p == list_ptr ) list_ptr = q;     
  295.                 // p->key war minimum , x neues minimum
  296.            
  297.       }
  298.     else 
  299.       { r->k = p->k;
  300.         r->son[left] = p;
  301.         r->son[right]= q;
  302.  
  303.         q->son[left] = p;            // verkettung
  304.         q->son[right] = p->son[right];
  305.         p->son[right]->son[left] = q;
  306.         p->son[right] = q;
  307.       }
  308.  
  309.     if ( st.empty() )      //  baum vor einfuegen einelementig
  310.       { 
  311.         r->gets_black_node();
  312.         root = r;
  313.         p->son[right] = p->son[left] = q;  // verkettung
  314.         return back ;
  315.       }
  316.  
  317.     pop(q,dir2);
  318.     q->son[dir2] = r;
  319.     if ( q->is_black() ) return back; // end of prog.35 in mehlhorn
  320.     
  321.     while (1)
  322.     {
  323.       pop(p,dir1);
  324.  
  325.       if ( p->son[1-dir1]->is_red() ) //p hat 2 rote soehne=> farbtausch
  326.      { 
  327.        p->son[left]->gets_black_node();
  328.            p->son[right]->gets_black_node();
  329.        p->gets_red_node();
  330.        if ( p == root )  { p->gets_black_node(); return back; }
  331.        r = p;
  332.        pop(q,dir2);
  333.        if ( q->is_black() )  return back;
  334.          }
  335.       else if (dir1 == dir2)      // rebalancieren  durch eine rotation
  336.         {
  337.           rotation(p,q,dir1);
  338.       p->gets_red_node();
  339.       q->gets_black_node();
  340.           if_root(p,q);     
  341.       return back;
  342.         }       
  343.       else
  344.     {
  345.       double_rotation(p,q,r,dir1,dir2);
  346.       p->gets_red_node();
  347.       r->gets_black_node();
  348.           if_root(p,r);     
  349.       return back;
  350.     }
  351.     }
  352. }
  353. //----------------------------------------------------------------------
  354. // end of insert
  355. //----------------------------------------------------------------------
  356.  
  357.  
  358. //----------------------------------------------------------------------
  359. // del(x) :
  360. // loescht element mit key x und gibt entry dieses elements zurueck,
  361. // falls ein solches existiert , sonst 0 .
  362. //----------------------------------------------------------------------
  363.  
  364. void rb_tree::del(ent x)
  365. {
  366.   TRACE(("del : %d \n",int(x) ));
  367.  
  368.   rb_tree_node_ptr u,v,w,p,x1,y;
  369.   int dir1,dir2;
  370.  
  371.   if ( !root ) return; // error_handler(2, " del , but treesize = 0 ");
  372.  
  373.  
  374.   rb_tree_node* pp = search(x);  // danach im Stack st der suchpfad gespeichert 
  375.                                  // pp ist innerer Knoten mit Kopie von x
  376.                                  // (nil, falls keiner existiert)
  377.   
  378.   
  379.   pop(v,dir1);
  380.  
  381.   if ( cmp(v->k,x) != 0 ) return;   // x nicht gefunden: nichts zu tun
  382.  
  383.  
  384.   -- counter;
  385.  
  386.   rb_tree_node* back = v;  // back ist zu entfernendes Blatt
  387.  
  388.   if ( v == root )                                     // treesize = 1
  389.      {
  390.        root = list_ptr = 0;
  391.        clear_key(back->k);
  392.        clear_inf(back->e);
  393.        delete back;
  394.        return;
  395.      } 
  396.  
  397.   //s.n.: overwrite possible copy of x in inner node pp
  398.  
  399.   if (pp && v->son[left]) pp->k = v->son[left]->k;
  400.  
  401.  
  402.   if ( v == list_ptr ) list_ptr = v->son[right];
  403.   v->son[left]->son[right] = v->son[right];           // verkettung
  404.   v->son[right]->son[left] = v->son[left];
  405.   
  406.   pop(u,dir1);
  407.   if (st.empty() )                                      // u = root
  408.      {
  409.        root = u->son[1-dir1];
  410.        if ( root->is_node() )      // tree hat zwei blaetter
  411.          root->gets_black_node();
  412.        else                       // tree besteht nur noch aus root
  413.      root->gets_black_leaf();
  414.  
  415.        delete(u);
  416.        clear_key(back->k);
  417.        clear_inf(back->e);
  418.        delete back;
  419.        return;
  420.      }
  421.  
  422.   pop(p,dir2);
  423.   w = u->son[1-dir1];
  424.   p->son[dir2] = w;
  425.   if (u->is_red() || w->is_red() )    // situation 1 , 2
  426.     { 
  427.       TRACE(( " situation 1,2 \n " ));
  428.  
  429.       if ( w->is_red() ) w->gets_black_node(); 
  430.       delete(u);
  431.       clear_key(back->k);
  432.       clear_inf(back->e);
  433.       delete back;
  434.       return; 
  435.     } 
  436.   delete(u);
  437.  
  438.   // situation 3 : schwarztiefe des unterbaums mit wurzel v um 
  439.   //               zu niedrig
  440.   //  =>  tiefe im unterbaum mit wurzel v um 1 erhoehen 
  441.   //      bzw. v wandert weiter nach oben
  442.   // bem: u ist vater von v , w der bruder von v
  443.  
  444. v = w;
  445. u = p;
  446. dir1 = dir2;
  447.   while(1)
  448. {
  449.   w = u->son[1-dir1];
  450.   if ( w->is_black() )              // fall2 , v und bruder w sind black
  451.   {  if ( w->son[1-dir1]->is_red() )  // fall 2.b 
  452.         {
  453. TRACE((" 2b \n"));
  454.             rotation(u,w,1-dir1);
  455.         w->c = u->col();
  456.         u->gets_black_node();
  457.         (w->son[1-dir1])->gets_black_node();
  458.         if_root(u,w);
  459.             clear_key(back->k);
  460.             clear_inf(back->e);
  461.             delete back;
  462.         return;
  463.         }
  464.      else   if ( ( y = w->son[dir1] )->is_red() ) // 2.c 
  465.         { 
  466. TRACE((" 2c \n"));
  467.         double_rotation(u,w,y,1-dir1,dir1);
  468.         y->c = u ->col();
  469.         u->gets_black_node();
  470.         if_root(u,y);
  471.             clear_key(back->k);
  472.             clear_inf(back->e);
  473.             delete back;
  474.         return;
  475.         }
  476.      else if ( u->is_red() )     // fall 2.a2
  477.     {
  478. TRACE((" 2a2 \n"));
  479.         w->gets_red_node();
  480.         u->gets_black_node();
  481.             clear_key(back->k);
  482.             clear_inf(back->e);
  483.             delete back;
  484.             return; 
  485.     }
  486.      else {                      // fall 2.a1
  487. TRACE((" 2a1 \n"));
  488.         rotation(u,w,1-dir1);
  489.         u->gets_red_node();
  490.         if ( u == root )
  491.              { 
  492. TRACE((" 2a1 nicht ende\n"));
  493.            root = w ;
  494.                    clear_key(back->k);
  495.                    clear_inf(back->e);
  496.                    delete back;
  497.            return;
  498.                  }
  499.         else {
  500. TRACE((" 2a1  ende\n"));
  501.            pop(u,dir1);
  502.            u->son[dir1] = w;
  503.            v = w;
  504.                  }
  505.             // einziger fall , der nicht sofort (d.h.nach einfach- 
  506.         // oder doppelrotation) terminiert ; v wandert zur wurzel
  507.           }
  508.   }     
  509. else                      // fall 3 ; v ist black, w ist red
  510.   { x1 = w->son[dir1];
  511.     if ( x1->son[1-dir1]->is_red() )              // fall 3.b
  512.       { 
  513. TRACE((" 3b \n"));
  514.         double_rotation(u,w,x1,1-dir1,dir1);
  515.         w->son[dir1]->gets_black_node();
  516.     if_root(u,x1);
  517.         clear_key(back->k);
  518.         clear_inf(back->e);
  519.         delete back;
  520.         return;
  521.       }
  522.     else if ( ( y = x1->son[dir1] )->is_red() )   // fall 3.c
  523.       {
  524. TRACE((" 3c \n"));
  525.         rotation(x1,y,dir1);
  526.         w->son[dir1] = y; 
  527.     double_rotation(u,w,y,1-dir1,dir1);
  528.         y->gets_black_node();
  529.     if_root(u,y);
  530.         clear_key(back->k);
  531.         clear_inf(back->e);
  532.         delete back;
  533.     return;
  534.       }
  535.     else                                         // fall 3.a 
  536.       { 
  537. TRACE((" 3a \n"));
  538.         rotation(u,w,1-dir1);
  539.     w->gets_black_node();
  540.     x1->gets_red_node ();
  541.     if_root(u,w);
  542.         clear_key(back->k);
  543.         clear_inf(back->e);
  544.         delete back;
  545.     return;
  546.       }
  547.   }  // end of fall 1,2,3
  548. } // end of while(1)
  549. } // end of del
  550.  
  551.  
  552. //------------------------------------------------------------------
  553. // operator=
  554. //------------------------------------------------------------------
  555.  
  556. rb_tree& rb_tree::operator=(const rb_tree& t)
  557. {
  558.   TRACE(( " operator= \n"));
  559.  
  560.    if (this == &t) return *this;
  561.  
  562.    clear();
  563.  
  564.    if ( t.root )   
  565.    { rb_tree_node* pre = 0;
  566.      root = t.copy_tree(t.root,pre);
  567.      list_ptr = root;
  568.      while (list_ptr->son[left]) list_ptr = list_ptr->son[left];
  569.      list_ptr->son[left] = pre;
  570.      pre->son[right] = list_ptr;
  571.      counter = t.counter;
  572.    }
  573.  
  574.    return *this; 
  575. }
  576.  
  577. //------------------------------------------------------------------
  578. // rb_tree(rb_tree&) constructor :
  579. //------------------------------------------------------------------
  580.  
  581.   rb_tree::rb_tree(const rb_tree& t)  : st(32)
  582.   { root  = list_ptr = 0 ;
  583.     if ( t.root ) 
  584.     { rb_tree_node* pre = 0;
  585.       root = t.copy_tree(t.root,pre);
  586.       list_ptr = root;
  587.       while (list_ptr->son[left]) list_ptr = list_ptr->son[left];
  588.       list_ptr->son[left] = pre;
  589.       pre->son[right] = list_ptr;
  590.       counter = t.counter; 
  591.      }
  592.   }
  593.  
  594. //------------------------------------------------------------------
  595. // copy_tree(p) kopiert baum mit wurzel p und gibt pointer auf wurzel
  596. // der kopie zurueck. pre enthaelt letztes erzeugtes Blatt ( Blaetter 
  597. // werden von links nach rechts erzeugt!
  598. //------------------------------------------------------------------
  599.  
  600. rb_tree_node* rb_tree::copy_tree( rb_tree_node* p, rb_tree_node_ptr& pre) const
  601. {
  602.   rb_tree_node* q = new rb_tree_node(p);  // q = p
  603.  
  604.   if ( p->is_node() )  // internal node: copy subtrees 
  605.   {
  606.     q->son[left] = copy_tree(p->son[left],pre);
  607.     q->son[right] = copy_tree(p->son[right],pre);
  608.   }
  609.   else   //leaf: chaining with last created leaf "pre"
  610.   {
  611.     copy_key(q->k);
  612.     copy_inf(q->e);
  613.  
  614.     if (pre) pre->son[right] = q; 
  615.     q->son[left] = pre;
  616.     pre = q;
  617.  
  618.    }
  619.  
  620.   return q;
  621. }
  622.  
  623. //------------------------------------------------------------------
  624. // clear
  625. //------------------------------------------------------------------
  626.  
  627. void rb_tree::clear() 
  628. {
  629.    TRACE(( " clear \n"));
  630.  
  631.    st.clear();
  632.  
  633.    if ( root )
  634.    {
  635.      del_tree(root);
  636.      root = list_ptr = 0;
  637.      counter = 0;
  638.    }
  639. }
  640.  
  641. //------------------------------------------------------------------
  642. // del_tree(p) : loeschen des unterbaums mit wurzel p
  643. //------------------------------------------------------------------
  644.  
  645. void rb_tree::del_tree(rb_tree_node* p)
  646. {
  647.   TRACE(("del_tree : nodekey :%d \n",int(p->k) ));
  648.  
  649.   if ( p->is_node() )
  650.   { del_tree(p->son[left]);
  651.     del_tree(p->son[right]);
  652.    }
  653.   else
  654.   { clear_key(p->k);
  655.     clear_inf(p->e);
  656.    }
  657.  
  658.   delete(p);
  659. }
  660.  
  661. //-----------------------------------------------------------------
  662. // test auf schwarztiefe und bildhafte darstellung des baums nur
  663. // im Trace-modus moeglich
  664. //-----------------------------------------------------------------
  665.  
  666. #ifdef TEST1
  667.  
  668. int rb_tree::deep_test(rb_tree_node* p) const
  669. {
  670.   if ( p->is_node() )
  671.   {
  672.     int i = deep_test(p->son[left]);
  673.     if ( i && i == deep_test( p->son[right] ) )
  674.         // falls i=0  => fehler im  linken sohn
  675.         return ( p->is_black() ? i+1  : i ) ;
  676.     else return false ;    // fehler => return false = 0
  677.   }
  678.   else return 1;           // p ist blatt ( immer black )      
  679. }
  680.  
  681. int rb_tree::black_deep_test() const
  682. {
  683.   if ( root )    // falls treesize > 0
  684.     return ( deep_test(root) ? true : false ) ;
  685.   else return true;
  686. }
  687.  
  688. //------------------------------------------------------------------
  689. // print()    : ausgeben des rb_trees ( um 90 grad gedreht )
  690. //              nur fuer type = int  
  691. // print_tree(p) : ausgeben des unterbaums mit wurzel p
  692. //------------------------------------------------------------------
  693.  
  694. void rb_tree::print_tree(rb_tree_node* p,int h) const
  695. {  
  696.        if ( p->is_node() ) print_tree(p->son[right],h+1);
  697.  
  698.        for( int j=1; j <= h ; j++ ) cout << "     ";
  699.  
  700.        switch (p->col())   {
  701.           case node_black   : cout << " b "; break;
  702.           case leaf_black   : cout << " b "; break;
  703.           case node_red     : cout << " r "; break;
  704.           case leaf_red     : cout << " r "; break;
  705.           case unknown      : cout << " u "; break;
  706.           default           : cout << " ? "; break;
  707.        }
  708.        cout << int(key(p)) ;
  709.        if ( p->is_leaf() )
  710.        {
  711.          cout << string(" succ : %d",int(key(p->son[right]))) ;
  712.          cout << string(" pred : %d\n",int(key(p->son[left]))) ;
  713.        }
  714.        else cout << "\n";
  715.  
  716.        if ( p->is_node() ) print_tree(p->son[left],h+1);
  717. }
  718.  
  719. void rb_tree::print() const
  720. {
  721.   cout << "tree.size : " << size() << "\n";
  722.   if ( root ) print_tree(root,1);
  723. }
  724.         
  725. #endif TEST1
  726.  
  727.  
  728. void rb_tree::draw(DRAW_RB_NODE_FCT draw_red_node,
  729.                    DRAW_RB_NODE_FCT draw_black_node,
  730.                    DRAW_RB_EDGE_FCT draw_edge, 
  731.                    rb_tree_node* r, 
  732.                    double x1, double x2, double y, 
  733.                    double ydist, double last_x)
  734. { 
  735.  
  736.  double x = (x1+x2)/2;
  737.  
  738.  if (r==nil) return;
  739.  
  740.  if (last_x != 0) draw_edge(last_x,y+ydist,x,y);
  741.  
  742.  if (r->is_red()) 
  743.     draw_red_node(x,y,r->k);
  744.  else 
  745.     draw_black_node(x,y,r->k);
  746.  
  747.  if (r->is_node()) 
  748.  { draw(draw_red_node,draw_black_node,draw_edge,r->son[0],x1,x,y-ydist,ydist,x);
  749.    draw(draw_red_node,draw_black_node,draw_edge,r->son[1],x,x2,y-ydist,ydist,x);
  750.   }
  751. }
  752.  
  753.  
  754. void rb_tree::draw(DRAW_RB_NODE_FCT draw_red_node,
  755.                    DRAW_RB_NODE_FCT draw_black_node, 
  756.                    DRAW_RB_EDGE_FCT draw_edge, 
  757.                    double x1, double x2, double y, double ydist)
  758. { draw(draw_red_node,draw_black_node,draw_edge,root,x1,x2,y,ydist,0); }
  759.  
  760.  
  761. //------------------------------------------------------------------
  762. // end of rb_tree.c
  763. //------------------------------------------------------------------
  764.