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

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

数值算法/人工智能

开发平台：

MultiPlatform

_ps_tree.c：源码内容
  1. /*******************************************************************************
  2. +
  3. +  LEDA-R  3.2.3
  4. +
  5. +  _ps_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. *******************************************************************************/
  13. //--------------------------------------------------------------------
  14. //  
  15. //  Priority Search Trees
  16. //
  17. //  Renate Lassen   (1990)
  18. //
  19. // Implementation follows
  20. // Kurt Mehlhorn: Data Structures and Algorithms 3, section III.5.1.2
  21. //
  22. // -------------------------------------------------------------------
  24. #include <LEDA/impl/ps_tree.h>
  27. // -------------------------------------------------------------
  28. // member functions
  29. // -------------------------------------------------------------
  31. // -------------------------------------------------------------
  32. // lrot() , rrot() , ldrot() , rdrot()
  33. // Rotationen am Knoten p
  35. void ps_tree::lrot(ps_item p, ps_item q)
  36. { 
  37.   x_typ xh ,yh;
  39. //  cout << "lrotn";
  40. //  cout << "p :" << p->split_value_x() << "n";
  41. //  cout << "q :" << q->split_value_x() << "n";
  42.   ps_item h = p->sohn[right];
  43. //  cout << "h :" << h->split_value_x() << "n";
  44.   xh = h->x_value();
  45.   yh = h->y_value();
  46.   
  47.   p->sohn[right] = h->sohn[left];
  48.   h->sohn[left] = p;
  49.    
  50.   if (!q) root=h;
  51.   else
  52.   {
  53.    if ( p == q->sohn[left] )   q->sohn[left]=h;
  54.    else q->sohn[right]=h;
  55.   }; 
  56.   
  57.   h->x_val = p->x_value();
  58.   h->y_val = p->y_value();
  59.   p->x_val = p->y_val = 0;
  61.   if (cmp(xh,yh,h->split_value_x(),h->split_value_y())>0)  
  62.       sink(h->sohn[right],xh,yh);
  63.   else  sink(p->sohn[right],xh,yh); 
  64.     
  65.   fill(p);
  66.   
  67.   p->gr=p->sohn[left]->groesse()+p->sohn[right]->groesse();
  68.   h->gr=p->groesse()+h->sohn[right]->groesse();
  69. }
  71. void ps_tree::rrot(ps_item p, ps_item q)
  72. { 
  73.   x_typ xh, yh;
  74.   
  75.   //cout << "rrotn"; 
  76.  // cout << "p :" << p->split_value_x() << "n";
  77.  // cout << "q :" << q->split_value_x() << "n";
  78.   ps_item h = p->sohn[left];
  79.  // cout << "h :" << h->split_value_x() << "n";
  80.   xh=h->x_value();
  81.   yh=h->y_value();
  82.   
  83.   p->sohn[left] = h->sohn[right];
  84.   h->sohn[right] = p;
  86.   if (!q) root=h;
  87.   else
  88.   {
  89.    if ( p == q->sohn[left] ) q->sohn[left] = h;
  90.    else q->sohn[right] = h; 
  91.   };
  93.   h->x_val = p->x_value();
  94.   h->y_val = p->y_value();
  95.   p->x_val = p->y_val = 0;
  96.   
  97.   if (cmp(xh,yh,h->split_value_x(),h->split_value_y())<=0)  
  98.       sink(h->sohn[left],xh,yh);
  99.   else sink(p->sohn[left],xh,yh);
  100.   
  101.   fill(p);
  103.   p->gr=p->sohn[left]->groesse()+p->sohn[right]->groesse();
  104.   h->gr=p->groesse()+h->sohn[left]->groesse();
  105. }
  107. void ps_tree::ldrot(ps_item p, ps_item q)
  108. { 
  109.     
  110.   //cout << "ldrotn";
  111.   ps_item h = p->sohn[right];
  112.   ps_item t = h->sohn[left];
  113.   rrot(h,p);
  114.   lrot(p,q);
  115.  // cout << "p:" << p->split_value_x() << "n";
  116.  // cout << "h:" << h->split_value_x() << "n";
  117. }
  119. void ps_tree::rdrot(ps_item p, ps_item q)
  120. {
  122.   //cout << "rdrotn";
  123.   ps_item h = p->sohn[left];
  124.   ps_item t = h->sohn[right];
  125.   lrot(h,p);
  126.   rrot(p,q);
  127.  // cout << "p:" << p->split_value_x() << "n";
  128.   //cout << "h:" << h->split_value_x() << "n";
  129.   //cout << "t:" << t->split_value() << "n";
  130. }
  131.  
  132. // ------------------------------------------------------------------
  133. // fill(ps_item)
  134. // fuellt Knoten bei Rotation wieder auf 
  135.   
  136. void ps_tree::fill(ps_item p)
  137. {
  139.  int leer=0;
  140.  int diff=0;
  141.  //cout << "filln";
  142.  while (!p->blatt() && leer!=1)
  143.  {
  144.   diff=cmp(p->sohn[left]->y_value(),p->sohn[right]->y_value()); 
  145.   //cout << "diff = " << diff << "n";
  146.   if (diff==0) leer=1;                                           // Kinder von p gefuellt ?
  147.   else if ( (diff<0 && p->sohn[left]->y_value()!=0) 
  148.             || (diff>0 && p->sohn[right]->y_value()==0))
  149.        {
  150.         p->x_val = p->sohn[left]->x_value();
  151.         p->y_val = p->sohn[left]->y_value();
  152.         p->sohn[left]->x_val = p->sohn[left]->y_val = 0;   
  153.   //cout <<"gefuellt von links :"<<p->split_value()<<":"<<p->x_value()<<":"<<p->y_value()<<"n";
  154.         p = p->sohn[left];
  155.        }
  156.        else if ( (diff>0 && p->sohn[right]->y_value()!=0) 
  157.                  || (diff<0 && p->sohn[left]->y_value()==0)) 
  158.             {
  159.             p->x_val = p->sohn[right]->x_value();
  160.             p->y_val = p->sohn[right]->y_value();
  161.             p->sohn[right]->x_val = p->sohn[right]->y_val = 0;   
  162.             p->sohn[right]->x_val = p->sohn[right]->y_val =0;
  163.             p = p->sohn[right];
  164.             };
  165.  };
  166. }
  168. // ------------------------------------------------------------------
  169. // sink() 
  170. // laesst Paar (x,y) im Unterbaum mit Wurzel p herabsinken.
  171.    
  172. ps_item ps_tree::sink(ps_item q, x_typ x, x_typ y)
  173. {
  174.  x_typ xh, yh, xneu=x;
  175.  x_typ yneu=y;
  176.  ps_item p =q;
  177.  ps_item inserted; 
  178.  
  179.  while(!p->blatt() && cmp(p->x_value(),0)!=0)
  180.  {
  181.   //cout << "sinkn";
  182.   //cout << p->split_value_x() << ":" << p->split_value_y() <<":"<< p->x_value() << ":" << p->y_value() <<"n";
  183.   if (cmp(p->y_value(),0)!=0 && cmp(y,p->y_value())<0)
  184.   {                                                    // Tausch
  185.    xh=p->x_value();
  186.    yh=p->y_value();
  187.    p->x_val=x;
  188.    p->y_val=y;
  189.    x=xh;
  190.    y=yh;
  191.    if (cmp(p->x_value(),xneu)==0 && cmp(p->y_value(),yneu)==0) inserted=p;
  192.   //cout << "inserted in Tauschn";
  193.   //cout << inserted->split_value() <<":"<< inserted->x_value() << ":" << inserted->y_value() <<"n";
  194.   };
  195.   //cout << "hallon";
  196.   if (cmp(x,y,p->split_value_x(),p->split_value_y())<=0)   p=p->sohn[left];
  197.   else 
  198.   {
  199.    p=p->sohn[right]; 
  200.   //cout << p->split_value_x() << ":" << p->split_value_y() <<":"<< p->x_value() << ":" << p->y_value() <<"n";
  201.   };
  202.  };
  203.  p->x_val=x;
  204.  p->y_val=y;
  205.  if (cmp(p->x_value(),xneu)==0 && cmp(p->y_value(),yneu)==0) inserted=p;
  206.  // cout << "inserted" << inserted->split_value_y() <<":"<< inserted->x_value() << ":" << inserted->y_value() <<"n";
  207.  return inserted;
  208. }
  210. // ------------------------------------------------------------------
  211. // search(x_typ,x_typ)
  212. // sucht Knoten, der das Paar (x,y) enthaelt,
  213. // oder Blatt, an dem neues Blatt fuer x angehaengt werden soll.
  215.  
  216. ps_item ps_tree::search(x_typ x,x_typ y)
  217. {
  218.  ps_item p = root;
  219.  ps_item q = 0;
  221. // cout << "searchn";
  222.  if (root->blatt())
  223.  {
  224.   st.push(root);
  225.   return p;
  226.  }
  227.  else
  228.  {
  229.   st.push(p);
  230.   while ( !p->blatt() && p!=0 )
  231.   {
  232.    if ( cmp(x,p->x_value())==0 && cmp(y,p->y_value())==0) 
  233.    {
  234.     p=0;
  235.    }
  236.    else 
  237.    { 
  238.     if ( cmp(x,y,p->split_value_x(),p->split_value_y())<=0 ) p=p->sohn[left];
  239.     else p=p->sohn[right]; 
  240.     st.push(p);
  241.    }
  242.   }
  243.   return p;
  244.  }
  245. }  
  247.   
  248. // ------------------------------------------------------------------
  249. // locate(x_typ x,x_typ y)
  250. // gibt Knoten oder Blatt mit Inhalt (x,y), falls existiert,
  251. //                                      0 , sonst.
  252.  
  253. ps_item ps_tree::locate(x_typ x,x_typ y)
  254. {
  255.  ps_item p = root;
  256.  ps_item q = 0;
  258.  //cout << "locaten";
  259.  while ( q==0 && p!=0 && cmp(y,p->y_value())>=0 )
  260.  {
  261.   st.push(p);
  262.   if ( cmp(x,p->x_value())==0 && cmp(y,p->y_value())==0) 
  263.   {
  264.    q=p;
  265.   }
  266.   else 
  267.   { 
  268.    if ( cmp(x,y,p->split_value_x(),p->split_value_y())<=0 ) p=p->sohn[left];
  269.    else p=p->sohn[right]; 
  270.   }
  271.  }
  272.  return q;
  273. }
  275. // ------------------------------------------------------------------
  276. // delleaf(ps_item)
  277. // loescht Blatt von Paar (x,y) und Vater des Blattes.
  278. // ( Zwei Blaetter mit gemeinsamen Vater sind nie beide gefuellt. )
  279.   
  280. void ps_tree::delleaf(ps_item q)
  281. {
  282.  ps_item p;
  283.  ps_item t;
  284.  ps_item father;
  285.  x_typ xh,yh;
  287.  //cout << "delleafn";
  288.  q->x_val=0;
  289.  q->y_val=0;
  290.  p=st.pop();
  291.  father=st.pop();
  292.  if (q==father->sohn[left] ) father->sohn[left]=0;
  293.  else father->sohn[right]=0;
  294.  delete (q);                                           // loescht Blatt
  295.  t= st.empty() ? 0 : st.top();
  296.  xh=father->x_value();
  297.  yh=father->y_value();
  298.  //cout << "xh: " << xh << "n";
  299.  //cout << "yh: " << yh << "n";
  300.   
  301.  if ( father->sohn[left]!=0) q=father->sohn[left];
  302.  else q=father->sohn[right];
  303.  if (t!=0)
  304.  {
  305.   if (father==t->sohn[left])  t->sohn[left]=q;
  306.   else  t->sohn[right]=q;
  307.  }
  308.  else root=q;
  309.  delete(father);                                       // loescht Vater
  310.  
  311.  //cout << "q-x_value: " << q->x_value() << "n";
  312.  //cout << "q-y_value: " << q->y_value() << "n";
  313.  //cout << "q-split_value: " << q->split_value() << "n";
  314.  sink(q,xh,yh);
  315. }
  316.   
  317. // ------------------------------------------------------------------
  318. // insert(x_typ x,x_typ y)
  319. // fuegt ein neues Item (x,y) in den Baum ein
  320. //                 , falls noch nicht vorhanden, 
  321. // Fehlermeldung   ,sonst
  322. // gibt Zeiger auf eingefuegtes Blatt zurueck
  324. ps_item ps_tree::insert(x_typ x,x_typ y)
  325. { 
  326.  ps_item p;
  327.  ps_item t;
  328.  ps_item father;
  329.  
  330.  if (!root)                                     // neuer Baum
  331.  {  
  332.   ps_item p=new ps_node(x,y,x,y);
  333.   root=p; 
  334.   anzahl=1; 
  335.   return p;
  336.  }
  337.  else
  338.  {
  339.   p=search(x,y);
  340.   //cout << "p-x_value: " << p->x_value() << "n";
  341.   //cout << "p-y_value: " << p->y_value() << "n";
  342.   //cout << "p-split_value_x: " << p->split_value_x() << "n";
  343.   //cout << "p-split_value_y: " << p->split_value_y() << "n";
  344.   
  345.   if (p==0)
  346.   {
  347.    error_handler(0,"point already there !");   // Warnung
  348.    st.clear();
  349.    return p;
  350.   }
  351.   else
  352.   {
  353.    ps_item q = new ps_node(0,0,p->split_value_x(),p->split_value_y());   
  354.    ps_item w = new ps_node(0,0,x,y);           // zwei neue Blaetter
  355.   //cout << "q-x_value: " << q->x_value() << "n";
  356.   //cout << "q-y_value: " << q->y_value() << "n";
  357.   //cout << "q-split_value_x: " << q->split_value_x() << "n";
  358.   //cout << "q-split_value_y: " << q->split_value_y() << "n";
  359.   //cout << "w-x_value: " << w->x_value() << "n";
  360.   //cout << "w-y_value: " << w->y_value() << "n";
  361.   //cout << "w-split_value_x: " << w->split_value_x() << "n";
  362.   //cout << "w-split_value_y: " << w->split_value_y() << "n";
  363.    if(cmp(p->split_value_x(),p->split_value_y(),x,y)<=0)
  364.    {
  365.     p->sohn[left]=q; 
  366.     p->sohn[right]=w; 
  367.    }
  368.    else
  369.    {
  370.     p->split_val[0] = x;
  371.     p->split_val[1] = y;
  372.     p->sohn[left]=w;
  373.     p->sohn[right]=q;
  374.    } 
  375.    
  376.   //cout << "p-x_value: " << p->x_value() << "n";
  377.   //cout << "p-y_value: " << p->y_value() << "n";
  378.   //cout << "p-split_value_x: " << p->split_value_x() << "n";
  379.   //cout << "p-split_value_y: " << p->split_value_y() << "n";
  380.    while (!st.empty())                          // rebalancieren
  381.    { 
  382.     t=st.pop();
  383.    // cout << "stackn";
  384.     father = st.empty() ? 0 : st.top();
  385.     t->gr++;  
  386.     float i = t->bal();
  387.   
  388.     //cout << "i" << i << "n";
  389.     if (i < alpha)
  390.     {
  391.      if (t->sohn[right]->bal()<=d) lrot(t,father);
  392.      else ldrot(t,father);
  393.     }
  394.     else if (i>1-alpha) 
  395.     {
  396.       if (t->sohn[left]->bal() > d ) rrot(t,father);
  397.       else rdrot(t,father);
  398.     }
  399.    }
  400.    p = sink(root,x,y);
  401.    //cout<< p->split_value() <<":"<< p->x_value() << ":" << p->y_value() <<"n";
  402.    return p;
  403.   }
  404.  } 
  405. }
  406. // ------------------------------------------------------------------
  407. // del()
  408. // loescht Item it im Baum mit x_value(it) = x ,
  409. //                             y_value(it) = y , falls existiert
  410. //         und gibt Zeiger auf it zurueck
  411. // 0 , sonst
  413. ps_item ps_tree::del(x_typ x,x_typ y)
  414. { 
  415.  ps_item p;
  416.  ps_item t;
  417.  ps_item father;
  418.  ps_item deleted = new ps_node(x,y,0,0);
  419.  
  420.  if (root==0) 
  421.  {
  422.   error_handler(0,"Tree is empty");
  423.   return 0;                                          // leerer Baum
  424.  }
  425.  else
  426.  {
  427.   p=locate(x,y);
  428.   //cout << "located:"<<p->split_value()<<"n";
  429.   if (p==0) 
  430.   {
  431.    error_handler(0,"Pair is not in tree ");
  432.    st.clear();
  433.    return 0;                                         // Paar nicht im Baum
  434.   }
  435.   else
  436.   { 
  437.    if (p->blatt()) 
  438.    {
  439.     if (p==root)
  440.     {
  441.      error_handler(0,"Root is deleted.");
  442.      p=st.pop();
  443.      root=0;
  444.      anzahl=0;
  445.      return p;                                       // Wurzel geloescht
  446.     } 
  447.     else
  448.     {
  449.      delleaf(p);                                 // (x,y) steht in einem Blatt
  450.     }
  451.    }
  452.    else                                          // (x,y) steht in einem Knoten
  453.    {
  454.     p->x_val = p->y_val = 0;
  455.     fill(p);
  456.     while (!p->blatt())                               // Knoteninhalt loeschen
  457.     {                                                 // und neu auffuellen
  458.      if (cmp(x,y,p->split_value_x(),p->split_value_y())<=0) p=p->sohn[left];
  459.      else p=p->sohn[right];
  460.      st.push(p);
  461.     };
  462.     
  463.     delleaf(p);                                    // loescht zugehoeriges Blatt
  464.    }
  465.  
  466.    while (!st.empty())                                 // rebalancieren
  467.    { 
  468.     t = st.pop();
  469.     //cout << "stackn";
  470.     //cout << t->split_value()<<":"<<t->x_value()<<":"<<t->y_value()<<"n";
  471.     father = st.empty() ? 0 : st.top() ;
  472.     t->gr--;              
  473.     float i=t->bal();
  474.     //cout << "i :" << i << "n";
  475.     if (i<alpha)
  476.     { 
  477.      if (t->sohn[right]->bal() <= d) lrot(t,father);
  478.      else ldrot(t,father);
  479.     }
  480.     else if (i>1-alpha)
  481.     { 
  482.      if(t->sohn[left]->bal() > d) rrot(t,father);
  483.      else rdrot(t,father);
  484.     }
  485.    }
  486.    return(deleted);
  487.   }
  488.  }
  489. } 
  490.    
  491. //-----------------------------------------------------------------------
  492. //enumerate(x1,x2,y0,p)
  493. //gibt alle Punkte (x,y) aus Unterbaum mit Wurzel p
  494. //mit folgender Eigenschaft an :
  495. //  x1 <= x <= x2   &&   y <= y0 
  496. //Voraussetzung : x1 < x2
  498. void ps_tree::enumerate(x_typ x1,x_typ x2,x_typ y0,ps_item p)
  499. {
  500.  if (cmp(y0,p->y_value())>=0 && p!=0)
  501.  {
  502.   if (cmp(x1,p->split_value_x())<=0 && cmp(p->split_value_x(),x2)<=0)
  503.   {
  504.    if (cmp(x1,p->x_value())<=0 && cmp(p->x_value(),x2)<=0)
  505.       cout <<p->split_value_x()<<"("<<p->x_value()<<","<<p->y_value()<<")n";
  506.    enumerate(x1,x2,y0,p->sohn[left]); 
  507.    enumerate(x1,x2,y0,p->sohn[right]); 
  508.   }
  509.   else if (cmp(p->split_value_x(),x1)<=0) 
  510.        {
  511.         if(cmp(x1,p->x_value())<=0 && cmp(p->x_value(),x2)<=0)
  512.            cout <<p->split_value_x()<<"("<<p->x_value()<<","<<p->y_value()<<")n";
  513.         enumerate(x1,x2,y0,p->sohn[right]);
  514.        }
  515.        else if (cmp(x2,p->split_value_x())<=0) 
  516.        {
  517.         if(cmp(x1,p->x_value())<=0 && cmp(p->x_value(),x2)<=0)
  518.            cout <<p->split_value_x()<<"("<<p->x_value()<<","<<p->y_value()<<")n";
  519.         enumerate(x1,x2,y0,p->sohn[left]);
  520.        }
  521.  }
  522. }
  523.    
  524. //-----------------------------------------------------------------------
  525. //void pr_ps_tree(ps_item p;int blancs)
  526. //gibt den Baum mit Wurzel p aus
  528. void ps_tree::pr_ps_tree(ps_item p,int blancs)
  529. {
  530.  if (p==0)
  531.    { for (int j=1;j<=blancs;j++) cout << " ";
  532.      cout << "NILn";
  533.      return;
  534.    }
  535.  else
  536.    { pr_ps_tree(p->sohn[left],blancs+10); 
  537.      for (int j=1;j<=blancs;j++) cout << " ";
  538.      cout << "(" << p->split_value_x() << "," << p->split_value_y() << "):";
  539.      cout << "(" << p->x_value() << "," << p->y_value() << ")n";
  540.      pr_ps_tree(p->sohn[right],blancs+10); 
  541.    }
  542. }
  543.  
  544. //-----------------------------------------------------------------------
  545. //min_x_in_rect(x1,x2,y0,p)
  546. //sucht nach Paar (x,y) im Unterbaum von p 
  547. //mit folgender Eigenschaft :
  548. //  min { x ; es gibt y, so dass x1<=x<=x2 und y<=y0 } , falls existiert,
  549. //                                                   0 , sonst.
  551. pair_item ps_tree::min_x_in_rect(x_typ x1,x_typ x2,x_typ y0,ps_item p)
  552. {
  553.  pair_item  c;
  555.  if (p==0)
  556.  {
  557.   return 0;                                   // Baum ist leer.
  558.  }
  559.  else
  560.  {
  561.   c=new pair;
  562.   c->x_pkt=c->y_pkt=0;
  563.   c->valid=false;
  564.   if (cmp(y0,p->y_value())>=0)
  565.   {
  566.    if (!p->blatt())
  567.    {
  568.     if (cmp(x1,p->split_value_x())<=0) 
  569.         c=min_x_in_rect(x1,x2,y0,p->sohn[left]);
  570.     if (!c->valid && cmp(p->split_value_x(),x2)<0) 
  571.         c=min_x_in_rect(x1,x2,y0,p->sohn[right]);
  572.    }
  573.    if (cmp(x1,p->x_value())<=0 && cmp(p->x_value(),x2)<=0 
  574.        && cmp(p->y_value(),y0)<=0
  575.        && (!c->valid || cmp(p->x_value(),c->x_pkt)<0)     )
  576.    {
  577.     c->x_pkt=p->x_value();  
  578.     c->y_pkt=p->y_value();  
  579.     c->valid=true;
  580.    }
  581.   }
  582.   return c;
  583.  }
  584. }
  586. //-----------------------------------------------------------------------
  587. //max_x_in_rect(x1,x2,y0,p)
  588. //sucht nach Paar (x,y) im Unterbaum von p 
  589. //mit folgender Eigenschaft :
  590. //  max { x ; es gibt y, so dass x1<=x<=x2 und y<=y0 } , falls existiert,
  591. //                                                   0 , sonst.
  593. pair_item ps_tree::max_x_in_rect(x_typ x1,x_typ x2,x_typ y0,ps_item p)
  594. {
  595.  pair_item c;
  597.  if (p==0) 
  598.  {
  599.   return 0;                                      // Baum ist leer.
  600.  }
  601.  else
  602.  {
  603.   c=new pair;
  604.   c->x_pkt=c->y_pkt=0;
  605.   c->valid=false;
  606.   if (cmp(y0,p->y_value())>=0)
  607.   {
  608.    if (!p->blatt())
  609.    {
  610.     if (cmp(p->split_value_x(),x2)<=0) 
  611.         c=max_x_in_rect(x1,x2,y0,p->sohn[right]);
  612.     if (!c->valid && cmp(x1,p->split_value_x())<0) 
  613.         c=max_x_in_rect(x1,x2,y0,p->sohn[left]);
  614.    }
  615.    if (cmp(x1,p->x_value())<=0 && cmp(p->x_value(),x2)<=0 
  616.        && cmp(p->y_value(),y0)<=0
  617.        && (!c->valid || cmp(p->x_value(),c->x_pkt)>0)     )
  618.    {
  619.     c->x_pkt=p->x_value();  
  620.     c->y_pkt=p->y_value();  
  621.     c->valid=true;
  622.    }
  623.   }
  624.   return c;
  625.  }
  626. }
  627.  
  628. //-----------------------------------------------------------------------
  629. //min_y_in_xrange(x1,x2,p)
  630. //sucht Paar (x,y) im Unterbaum von p
  631. //mit folgender Eigenschaft :
  632. // y = min { y ; es gibt x, so dass x1<=x<=x2 } , falls existiert,
  633. //                                            0 , sonst.
  634.  
  635. pair_item ps_tree::min_y_in_xrange(x_typ x1,x_typ x2,ps_item p)
  636. {
  637.  pair_item c1,c2;
  639.  if (p==0)
  640.  {
  641.   return 0;                                      // Baum ist leer.
  642.  }
  643.  else
  644.  {
  645.   c1 = new pair;
  646.   c2 = new pair;
  647.   c1->x_pkt=c1->y_pkt=c2->x_pkt=c2->y_pkt=0; 
  648.   c1->valid=c2->valid=false;
  649.   if (cmp(x1,p->x_value())<=0 && cmp(p->x_value(),x2)<=0)
  650.   {
  651.    c1->x_pkt=p->x_value();
  652.    c1->y_pkt=p->y_value();
  653.    c1->valid=true;
  654.   }
  655.   else if (!p->blatt())
  656.   {
  657.    if (cmp(x1,p->split_value_x())<=0) c1=min_y_in_xrange(x1,x2,p->sohn[left]);
  658.    if (cmp(p->split_value_x(),x2)<0)  c2=min_y_in_xrange(x1,x2,p->sohn[right]);
  659.    if (!c1->valid || (c2->valid && cmp(c2->y_pkt,c1->y_pkt)<0)) c1=c2;
  660.   }
  661.   return c1;
  662.  } 
  663. }
  664.  
  665. //-----------------------------------------------------------------------
  666. // Funktion fuer Destruktor
  667. //-----------------------------------------------------------------------
  668.   
  669. void ps_tree::deltree(ps_item p)
  670. {
  671.  if (p)
  672.  {
  673.   if (!p->blatt())
  674.   {
  675.    deltree(p->sohn[left]);
  676.    deltree(p->sohn[right]);
  677.   }
  678.   delete(p);
  679.  }
  680. }