home *** CD-ROM | disk | FTP | other *** search
/ Power-Programmierung / CD2.mdf / c / library / dos / diverses / leda / src / basic / _bb_tree.c < prev    next >
Encoding:
C/C++ Source or Header  |  1991-11-15  |  18.3 KB  |  691 lines
  1. /*******************************************************************************
  2. +
  3. +  LEDA  2.1.1                                                 11-15-1991
  4. +
  5. +
  6. +  _bb_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.  
  17. //--------------------------------------------------------------------
  18. //  
  19. //  BB[alpha] Trees
  20. //
  21. //  Michael Wenzel   (1989)
  22. //
  23. // Implementation as described in
  24. // Kurt Mehlhorn: Data Structures and Algorithms 1, section III.5.1
  25. //
  26. // -------------------------------------------------------------------
  27. // Aenderungen:
  28. //   - keine virtuellen Funktionen  (M. Wenzel, Nov. 1989)
  29. //   - nicht rekursiv               (M. Wenzel, Nov. 1989)
  30. //   - virtuelle compare-Funktion   (M. Wenzel, Nov. 1989)
  31. //--------------------------------------------------------------------
  32.  
  33.  
  34.  
  35. #undef TEST
  36. #undef DUMP
  37.  
  38. #include <LEDA/bb_tree.h>
  39.  
  40. #ifdef TEST
  41. #define DPRINT(x) cout << string x
  42. #else
  43. #define DPRINT(x)   
  44. #endif
  45.  
  46. #ifdef DUMP
  47. #define DDUMP(x) cout << string x
  48. #else
  49. #define DDUMP(x)   
  50. #endif
  51.  
  52.  
  53.  
  54. enum children { left = 0 , right = 1 };
  55.  
  56. enum leaf_or_node { Leaf = 0 , Node = 1 } ;
  57.  
  58.  
  59. // -------------------------------------------------------------
  60. // member functions
  61. // -------------------------------------------------------------
  62.  
  63.  
  64.   bb_tree::bb_tree(float a)   : st(BSTACKSIZE)
  65.   { 
  66.     root = first = iterator = 0;
  67.     anzahl=0;
  68.     if ((a<=0.25) || (a>1-SQRT1_2))
  69.       error_handler(3,"alpha not in range");
  70.     alpha=a;
  71.     d = 1/(2-alpha) ;
  72.   }
  73.  
  74.   bb_tree::bb_tree(bb_tree& w)  : st(BSTACKSIZE)
  75.   { 
  76.     bb_item p;
  77.     bb_item l=0;
  78.     anzahl=w.anzahl;
  79.     alpha=w.alpha;
  80.     d=w.d;
  81.     iterator=0;
  82.     if (w.root)
  83.     { if (!w.root->blatt())
  84.       { p=new bb_node(w.root);
  85.         first=copytree(p,w.root,l); 
  86.         first->sohn[left]=l;
  87.         l->sohn[right]=first; }
  88.       else
  89.       { p=new bb_node(w.root);
  90.         first=p; }
  91.       root= p;                      }
  92.     else root = 0;
  93.   }
  94.  
  95. // -------------------------------------------------------------
  96. // locate()
  97. // liefert item mit key(item) >= y und
  98. //              und key(it)   <= key(it) fuer alle it
  99. //                                          mit key(it) >= y
  100. //         0, falls nicht existiert
  101.  
  102. bb_item bb_tree::locate(ent y)
  103.  
  104. { DPRINT(("locate %d in Baum %d\n",int(y),int(this)));
  105.   bb_item current;
  106.   if (root==0) return 0;  // by s.n
  107.   current=root;
  108.   while (!current->blatt())
  109.    { DDUMP(("current %d\n",int(current->key())));
  110.      if (cmp(y,current->key())<=0) current=current->sohn[left];
  111.      else current=current->sohn[right];   }
  112.   return (cmp(y,current->key())<=0) ? current : 0 ;
  113. }  
  114.  
  115. // -------------------------------------------------------------
  116. // located()
  117. // liefert item mit key(item) <= y und
  118. //              und key(it)   >= key(it) fuer alle it
  119. //                                       mit key(it) <= y
  120.  
  121. bb_item bb_tree::located(ent y)
  122.  
  123. { bb_item current;
  124.   if (root==0) return 0;  // by s.n
  125.   current=root;
  126.   while (!current->blatt())
  127.    if (cmp(y,current->key())<=0) current=current->sohn[left];
  128.    else current=current->sohn[right];
  129.   if (cmp(y,current->key())==0) return current;
  130.   current = current->sohn[left];
  131.   return (cmp(y,current->key())>=0) ? current : 0 ;
  132. }  
  133.  
  134. // -------------------------------------------------------------
  135. // lookup()
  136. // liefert item mit key(item)=y , falls existiert
  137. //                            0 , sonst
  138.  
  139. bb_item bb_tree::lookup(ent y)
  140.  
  141. { bb_item current = locate(y);
  142.   if (current==0) return 0;
  143.   return (cmp(y,current->key())==0) ? current : 0;
  144. }  
  145.  
  146. // -------------------------------------------------------------  
  147. // member()
  148. // liefert 1 , falls item existiert mit key(item)=y
  149. //         0 , sonst
  150.  
  151. int bb_tree::member(ent y)
  152.  
  153. { bb_item current = locate(y);
  154.   if (current==0) return 0;
  155.   return (cmp(y,current->key())==0);
  156. }  
  157.  
  158. // ------------------------------------------------------------
  159. // translate()
  160. // liefert info(item) , falls item existiert mit item = locate(y) 
  161. //                  0 , sonst
  162.  
  163. ent bb_tree::translate(ent y)
  164.  
  165. { bb_item current = locate(y);
  166.   if (current==0) return 0;
  167.   return (cmp(y,current->key())==0) ? current->inf : 0;
  168. }  
  169.  
  170. // ------------------------------------------------------------
  171. // change_obj()
  172. // liefert item mit key(item) = y und setzt info(item) auf x
  173. //                                    , falls existiert
  174. //         0                          , sonst
  175.  
  176. bb_item bb_tree::change_obj(ent y,ent x)
  177.  
  178. { bb_item current = lookup(y);
  179.   if ( current != 0 )
  180.   { current->inf = x ;  
  181.     return current; }
  182.   else return 0;
  183. }  
  184.  
  185. // ------------------------------------------------------------
  186. // search()
  187. // nachher: st = ( pk ,..., p1 ) mit 
  188. //          pk = locate(y) , p1 = root 
  189. //          p1 , ... , pk ist Suchpfad nach y
  190. // liefert inneren Knoten k mit key(k) = y , falls existiert
  191. //         0                               , sonst
  192.  
  193. bb_item bb_tree::search(ent y)
  194.  
  195. { DPRINT(("search %d in Baum %d\n",int(y),int(this)));
  196.   st.clear();
  197.   bb_item current = root;
  198.   bb_item k = 0;
  199.  
  200.   if (!root) return 0;         // Baum leer
  201.   while (!current->blatt())
  202.   { DDUMP(("current %d\n",int(current->key())));
  203.     if (cmp(y,current->key())<=0)
  204.     { if (cmp(y,current->key())==0) k=current;
  205.       st.push(current);
  206.       current = current->sohn[left];          }
  207.     else
  208.     { st.push(current);
  209.       current = current->sohn[right];         }
  210.                            }
  211.   st.push(current);
  212.   DDUMP(("Blatt %d\n",int(current->key())));
  213.   return k;
  214. }
  215.  
  216. // -----------------------------------------------------------
  217. // ord()
  218. // liefert item it mit
  219. //              |{key(it') < key(it) | it' item im Baum}| = k-1
  220. //         0 , falls kein solches item existiert
  221.     
  222. bb_item bb_tree::ord(int k)
  223.  
  224. { DPRINT(("ord %d\n",k));
  225.   if (k>anzahl || k<=0) return 0;
  226.   bb_item cur=root;
  227.   while (!cur->blatt())
  228.   { DDUMP(("ord loop k=%d key=%d\n",k,int(cur->key())));
  229.     int l=cur->sohn[left]->groesse();
  230.     if (k>l)
  231.     { k -= l;
  232.       cur=cur->sohn[right];           }
  233.     else cur=cur->sohn[left]; 
  234.   }
  235.   return cur;
  236. }
  237.     
  238. // ------------------------------------------------------------
  239. // move_iterator()
  240. // bewegt Iterator eine Stelle weiter
  241. // falls am Ende , Iterator = 0
  242.  
  243. bb_item bb_tree::move_iterator()
  244.  
  245.   { 
  246.     if (!root) 
  247.     { iterator = 0;
  248.       return 0;      }
  249.     
  250.     if (!iterator) iterator = first;
  251.     else if (iterator->sohn[right]==first) iterator = 0;
  252.      else iterator = iterator->sohn[right];
  253.     return iterator;
  254.   }
  255.     
  256. // ------------------------------------------------------------
  257. // lrot() , rrot() , ldrot() , rdrot()
  258. // Rotationen am Knoten p
  259.  
  260. void bb_tree::lrot(bb_item p, bb_item q)
  261. { DDUMP(("lrot p=%d \n",int(p->key())));
  262.   bb_item h = p->sohn[right];
  263.   p->sohn[right] = h->sohn[left];
  264.   h->sohn[left] = p;
  265.   if (!q) root=h;
  266.   else
  267.     if (cmp(p->key(),q->key())>0) q->sohn[right]=h;
  268.     else q->sohn[left]=h;
  269.   p->gr=p->sohn[left]->groesse()+p->sohn[right]->groesse();
  270.   h->gr=p->groesse()+h->sohn[right]->groesse();
  271. }
  272.  
  273. void bb_tree::rrot(bb_item p, bb_item q)
  274. { DDUMP(("rrot p=%d\n",int(p->key())));
  275.   bb_item h = p->sohn[left];
  276.   p->sohn[left] = h->sohn[right];
  277.   h->sohn[right] = p;
  278.   if (!q) root=h;
  279.   else
  280.   { if (cmp(p->key(),q->key())>0) q->sohn[right] = h;
  281.     else q->sohn[left] = h; }
  282.   p->gr=p->sohn[left]->groesse()+p->sohn[right]->groesse();
  283.   h->gr=p->groesse()+h->sohn[left]->groesse();
  284. }
  285.  
  286. void bb_tree::ldrot(bb_item p, bb_item q)
  287. { DDUMP(("ldrot p=%d\n",int(p->key())));
  288.   bb_item h = p->sohn[right];
  289.   bb_item g = h->sohn[left];
  290.   p->sohn[right] = g->sohn[left];
  291.   h->sohn[left] =  g->sohn[right];
  292.   g->sohn[left] = p;
  293.   g->sohn[right] = h;
  294.   if (!q) root=g;
  295.   else
  296.   { if (cmp(p->key(),q->key())>0) q->sohn[right] =g ;
  297.     else q->sohn[left] = g ; }
  298.   p->gr=p->sohn[left]->groesse()+p->sohn[right]->groesse();
  299.   h->gr=h->sohn[left]->groesse()+h->sohn[right]->groesse();
  300.   g->gr=p->groesse()+h->groesse();
  301. }
  302.  
  303. void bb_tree::rdrot(bb_item p, bb_item q)
  304. { DDUMP(("rdrot p=%d\n",int(p->key())));
  305.   bb_item h = p->sohn[left];
  306.   bb_item g = h->sohn[right];
  307.   p->sohn[left] = g->sohn[right];
  308.   h->sohn[right] =  g->sohn[left];
  309.   g->sohn[right] = p;
  310.   g->sohn[left] = h;
  311.   if (!q) root=g;
  312.   else
  313.   { if (cmp(p->key(),q->key())>0) q->sohn[right] =g ;
  314.     else q->sohn[left] = g ; }
  315.   p->gr=p->sohn[left]->groesse()+p->sohn[right]->groesse();
  316.   h->gr=h->sohn[left]->groesse()+h->sohn[right]->groesse();
  317.   g->gr=p->groesse()+h->groesse();
  318. }
  319.  
  320. // ------------------------------------------------------------------
  321. // sinsert()
  322. // fuegt ein neues Item (y,x) in den Baum ein
  323. //                 , falls noch kein Item it vorhanden mit key(it)=y
  324. // change_obj(y,x) ,sonst
  325. // fuellt Keller mit zu rebalancierenden Knoten 
  326. // gibt eingefuegtes Blatt zurueck
  327.  
  328.       bb_item bb_tree::sinsert(ent y,ent x=0)
  329.       { DPRINT(("sinsert %d [%d] in Baum %d\n",int(y),int(x),int(this)));
  330.     bb_item inserted;
  331.     bb_item help;
  332.  
  333.     if (!alpha) error_handler(5,"alpha nicht gesetzt");
  334.     if (iterator)  error_handler(6,"insert while tree listed");
  335.  
  336.     st.clear();                           // loesche Suchpfad
  337.  
  338.     if (!root) { DDUMP(("Baum war leer\n"));
  339.              bb_item p=new  bb_node(y,x);
  340.              p->sohn[left]=p;
  341.              p->sohn[right]=p;
  342.              root=p; 
  343.              first=p;
  344.              first->sohn[left]=first;
  345.              first->sohn[right]=first;
  346.              anzahl=1; 
  347.              inserted = p;
  348.            }
  349.     else
  350.       if (root->blatt())
  351.         if (cmp(y,root->key())<0)
  352.         { DDUMP(("links von Wurzel\n"));
  353.           bb_item p=new bb_node(y,x,Leaf,root,root);
  354.           DDUMP(("Blatt[%d] %d %d %d %d\n",(int)p,(int)p->key(),(int)p->info(),(int)p->sohn[left],(int)p->sohn[right]));
  355.           root->sohn[left]=p;
  356.           root->sohn[right]=p;
  357.           bb_item s=new bb_node(y,x,Node,p,root);
  358.           DDUMP(("Knoten[%d] %d %d %d %d\n",(int)s,(int)s->key(),(int)s->info(),(int)s->sohn[left],(int)s->sohn[right]));
  359.           first=p;
  360.           root=s;
  361.           st.push(s);
  362.           anzahl++; 
  363.           inserted = p;
  364.          }
  365.         else if (cmp(y,root->key())>0)         // hier rechts einfuegen
  366.          { DDUMP(("rechts von Wurzel\n"));
  367.            bb_item p=new bb_node(y,x,Leaf,root,root);
  368.            root->sohn[left]=p;
  369.            root->sohn[right]=p;
  370.            bb_item s=new bb_node(root->key(),root->inf,Node,root,p);
  371.            root=s;
  372.            st.push(s);
  373.            anzahl++;
  374.            inserted = p;
  375.           }
  376.          else { DPRINT(("gleicher Schluessel vorhanden\n"));
  377.             root->inf = x;
  378.             inserted = root;
  379.                }
  380.       else                           // root ist innerer Knoten
  381.       { bb_item father;
  382.         search(y);                   // fuelle Suchstack 
  383.         bb_item t=st.pop();
  384.         father = st.top();
  385.                      // einfuegen
  386.         if (cmp(y,t->key())<0)
  387.         { DDUMP(("insert links von Blatt\n"));
  388.           help = t->sohn[left];
  389.           bb_item  p = new bb_node(y,x,Leaf,help,t);
  390.           t->sohn[left]=p;
  391.           if (first==t) first=p;
  392.           help->sohn[right]=p;
  393.           bb_item s=new bb_node(y,x,Node,p,t);
  394.           if (cmp(s->key(),father->key())<=0) father->sohn[left]=s;
  395.           else father->sohn[right]=s;
  396.           anzahl++; 
  397.           inserted = p;
  398.           st.push(s);
  399.         }
  400.         else if (cmp(y,t->key())>0)     
  401.          { DDUMP(("insert rechts von Blatt -> neues Maximum\n"));
  402.            help=t->sohn[right];
  403.            bb_item p=new bb_node(y,x,Leaf,t,help);
  404.            t->sohn[right]=p;
  405.            help->sohn[left]=p;
  406.            bb_item s=new bb_node(t->key(),t->inf,Node,t,p);
  407.  
  408.            father->sohn[right] = s;
  409.            anzahl++;
  410.            inserted = p;
  411.            st.push(s);
  412.          }
  413.          else { DPRINT(("gleicher Schluessel vorhanden\n"));
  414.             t->inf = x;
  415.             st.clear();     // keine Rebalancierung notwendig
  416.             inserted = t;
  417.               }
  418.       }
  419.       return inserted;
  420.       }
  421.  
  422.  
  423. // ------------------------------------------------------------------
  424. // insert()
  425. // fuegt ein neues Item (y,x) in den Baum ein
  426. //       mittels sinsert
  427. // balanciert Baum mit ueblichen Rotationen
  428. // gibt eingefuegtes Blatt zurueck
  429.  
  430. bb_item bb_tree::insert(ent y, ent x)
  431. { 
  432.   bb_item inserted;
  433.   bb_item t,father;
  434.  
  435. /*
  436.   copy_key(y);
  437.   copy_inf(x);
  438. */
  439.  
  440.   inserted = sinsert(y,x);
  441.   if (!st.empty())
  442.     st.pop();                       // pop father of leaf
  443.   
  444.                     // rebalancieren
  445.   while (!st.empty())
  446.   { t=st.pop();
  447.     father = st.empty() ? 0 : st.top();
  448.     t->gr++;  
  449.     float i = t->bal();
  450.     DDUMP(("rebal cur=%d groesse=%d bal=%f\n",int(t->key()),t->groesse(),i));
  451.     if (i < alpha)
  452.       if (t->sohn[right]->bal()<=d) lrot(t,father);
  453.       else ldrot(t,father);
  454.     else if (i>1-alpha) 
  455.            if (t->sohn[left]->bal() > d ) rrot(t,father);
  456.        else rdrot(t,father);
  457.   }
  458.   DDUMP(("eingefuegtes Blatt hat key %d und info %d\n",int(inserted->key()),int(inserted->info())));
  459.   return inserted;
  460. }
  461.  
  462. // ------------------------------------------------------------------
  463. // sdel()
  464. // loescht Item it im Baum mit key(it)=y , falls existiert
  465. //         und gibt Zeiger auf it zurueck
  466. // 0 , sonst
  467. // fuellt Keller mit zu rebalancierenden Knoten
  468.  
  469. bb_item bb_tree::sdel(ent y)
  470. { DPRINT(("delete %d aus Baum %d\n",int(y),int(this)));
  471.  
  472.   if (!alpha) error_handler(5,"alpha nicht gesetzt");
  473.   if (iterator)  error_handler(6,"Baum gelistet beim Loeschen");
  474.  
  475.   st.clear();
  476.   if (root==0) return 0;                         // s.n.
  477.  
  478.   if (root->blatt())                             // Wurzel loeschen
  479.     if (cmp(y,root->key())==0)
  480.     { DDUMP(("Wurzel loeschen\n"));
  481.       bb_item p = root;
  482.       first=iterator=0;
  483.       anzahl=0; 
  484.       root=0; 
  485.       return p; 
  486.     }
  487.     else { DPRINT(("Element nicht im Baum\n"));  
  488.            return 0; }
  489.   else 
  490.   { bb_item p,father;
  491.     bb_item pp=search(y);
  492.     if (st.size()==2)                            // Sohn der Wurzel
  493.     { DDUMP(("Sohn der Wurzel loeschen\n"));
  494.       p=st.pop();
  495.       father=st.pop();
  496.  
  497.       int v1 = cmp(y,father->key());
  498.       if (cmp(y,p->key())!=0) { DPRINT(("Element nicht im Baum\n"));
  499.                               return 0; }
  500.       anzahl--;
  501.       if (v1<=0)
  502.         root=root->sohn[right];
  503.       else
  504.         root=root->sohn[left];
  505.       if (!root->blatt())
  506.       { if (first==p) first=p->sohn[right];
  507.         first->sohn[left]=p->sohn[left];
  508.         (first->sohn[left])->sohn[right]=first;
  509.       }
  510.       else
  511.       { first=root;
  512.         root->sohn[left]=root;
  513.         root->sohn[right]=root ;
  514.       }
  515.       st.push(father);
  516.       return p; 
  517.     }
  518.     else                                // Blatt mit Tiefe >= 2     
  519.     { bb_item q=st.pop();
  520.  
  521.       if (cmp(y,q->key())!=0)
  522.       { DDUMP(("Schluessel nicht vorhanden\n"));
  523.     return 0;   }
  524.  
  525.       bb_item p = st.pop();
  526.       father=st.top();
  527.       DDUMP(("Blatt %d mit Vater %d , Grossvater %d\n",int(q->key()),int(p->key()),int(father->key())));
  528.       int v2 = cmp(y,p->key());
  529.       int v1 = cmp(y,father->key());
  530.       anzahl--;
  531.       if (v1<=0)
  532.         if (v2<=0)
  533.         { father->sohn[left]=p->sohn[right];
  534.           if (first==q) { first=first->sohn[right];
  535.               q->sohn[right]->sohn[left]=first; }
  536.     }
  537.         else father->sohn[left]=p->sohn[left];
  538.       else if (v2<=0) father->sohn[right]=p->sohn[right];
  539.            else  father->sohn[right]=p->sohn[left];
  540.       q->sohn[right]->sohn[left]=q->sohn[left];
  541.       q->sohn[left]->sohn[right]=q->sohn[right];
  542.       if ( pp && (p!=pp) && p->sohn[left] )
  543.       { pp->ke = q->sohn[left]->key() ;
  544.         DPRINT(("inneren Knoten mit %d ueberschrieben und Info %d bleibt\n",int(pp->key()),int(pp->info())));
  545.       }
  546.       st.push(p);
  547.       return q;
  548.     }
  549.   }
  550. }
  551.  
  552. // ------------------------------------------------------------------
  553. // del()
  554. // loescht Item it im Baum mit key(it)=y , falls existiert
  555. //         und gibt Zeiger auf it zurueck
  556. // 0 , sonst
  557. // mittels sdel                                     
  558. // rebalanciert Baum danach
  559.  
  560. bb_item bb_tree::del(ent y)
  561. {
  562.   bb_item p,father;
  563.   bb_item deleted = sdel(y);
  564.   if (!deleted)
  565.     return 0;
  566.   if (!st.empty())
  567.     delete(st.pop());
  568.  
  569.                      // rebalancieren
  570.   while (!st.empty())
  571.   { p = st.pop();
  572.     father = st.empty() ? 0 : st.top() ;
  573.     p->gr--;              
  574.     float i=p->bal();
  575.     DDUMP(("rebal cur=%d groesse=%d bal=%f\n",int(p->key()),p->groesse(),i));
  576.     if (i<alpha)
  577.       if (p->sohn[right]->bal() <= d) lrot(p,father);
  578.       else ldrot(p,father);
  579.     else if (i>1-alpha)
  580.            if(p->sohn[left]->bal() > d) rrot(p,father);
  581.            else rdrot(p,father);
  582.   }
  583.   return deleted;
  584. } 
  585.  
  586. // -----------------------------------------------------------------
  587. // Gleichheitsoperator
  588. // weist this Kopie der Baumes w zu
  589.  
  590. bb_tree& bb_tree::operator=(bb_tree& w)
  591. { DDUMP(("operator = wurzel%d\n",(int)w.root->key()));
  592.   bb_item p;
  593.   bb_item l=0;
  594.   if (anzahl!=0) deltree(root); 
  595.   st.clear();
  596.   anzahl=w.anzahl;
  597.   alpha=w.alpha;
  598.   d=w.d;
  599.   iterator=0;
  600.   if (w.root)
  601.   { if (!w.root->blatt())
  602.     { p=new bb_node(w.root);
  603.       first=copytree(p,w.root,l);
  604.       first->sohn[left]=l ;
  605.       l->sohn[right]=first ; }
  606.     else
  607.     { p=new bb_node(w.root);
  608.       first=p; }
  609.     root= p;                       }
  610.   else root = 0;
  611.   DDUMP(("root=%d, first=%d\n",int(root->key()),int(first->key())));
  612.   return *this;
  613. }
  614.  
  615. bb_item bb_tree::copytree(bb_item p, bb_item q,bb_item& ll) 
  616. { DDUMP(("copytree %d\n",(int)p->key()));
  617.   bb_item a;
  618.   bb_item r;
  619.   bb_item s;
  620.   if (p->blatt())
  621.   { if (ll==0) p->sohn[left]=0;
  622.     else
  623.     { p->sohn[left]=ll;
  624.       ll->sohn[right]=p; }
  625.     p->sohn[right]=0;
  626.     a=p;
  627.     ll=p; 
  628.     DDUMP(("ll gesetzt %d\n",int(ll->key()))); }
  629.   else {
  630.     r=new bb_node(q->sohn[left]);
  631.     p->sohn[left]=r;
  632.     a=copytree(p->sohn[left],q->sohn[left],ll);
  633.     s=new bb_node(q->sohn[right]);
  634.     p->sohn[right]=s;
  635.     copytree(p->sohn[right],q->sohn[right],ll); }
  636.   return a; 
  637. }
  638.  
  639. // ------------------------------------------------------------------
  640. // Destruktoren
  641.  
  642. void bb_tree::clear()
  643. { if (root)
  644.   { DPRINT(("clear %d\n",int(root->key())));
  645.     deltree(root);
  646.    }
  647.   else DPRINT(("clear\n"));
  648.   root=0;
  649.   anzahl=0;
  650.   first=0;
  651. }
  652.  
  653. void bb_tree::deltree(bb_item p)
  654. { if (p)
  655.   { DDUMP(("deltree : current=%d\n",int(p->key())));
  656.     if (!p->blatt())
  657.     {  deltree(p->sohn[left]);
  658.        deltree(p->sohn[right]); 
  659.      }
  660.     delete(p);
  661.   }
  662. }
  663.  
  664.  
  665. void bb_tree::draw(DRAW_BB_NODE_FCT draw_node,
  666.                    DRAW_BB_EDGE_FCT draw_edge, 
  667.                    bb_node* r, 
  668.                    double x1, double x2, double y, 
  669.                    double ydist, double last_x)
  670. { 
  671.  double x = (x1+x2)/2;
  672.  
  673.  if (r==nil) return;
  674.  
  675.  if (last_x != 0) draw_edge(last_x,y+ydist,x,y);
  676.  
  677.  draw_node(x,y,r->key());
  678.  
  679.  if (!r->blatt()) 
  680.  { draw(draw_node,draw_edge,r->sohn[0],x1,x,y-ydist,ydist,x);
  681.    draw(draw_node,draw_edge,r->sohn[1],x,x2,y-ydist,ydist,x);
  682.   }
  683. }
  684.  
  685.  
  686. void bb_tree::draw(DRAW_BB_NODE_FCT draw_node,
  687.                    DRAW_BB_EDGE_FCT draw_edge, 
  688.                    double x1, double x2, double y, double ydist)
  689. { draw(draw_node,draw_edge,root,x1,x2,y,ydist,0); }
  690.  
  691.