开通博客赚积分
发布资源赚积分
分类

源码开发语言/平台
当前位置：首页 > 源码/资料 > 数值算法/人工智能 > 查看源码
_bb1_tree.c
资源名称：leda.tar.gz　[点击查看]
上传用户：gzelex
上传日期：2007-01-07
资源大小：707k
文件大小：19k
源码类别：

数值算法/人工智能

开发平台：

MultiPlatform

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