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

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

数值算法/人工智能

开发平台：

MultiPlatform

_bin_tree.c：源码内容
  1. /*******************************************************************************
  2. +
  3. +  LEDA-R  3.2.3
  4. +
  5. +  _bin_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. //  bin_tree: base class for all binary tree types in LEDA
  17. //
  18. //  leaf oriented & doubly linked 
  19. //
  20. //  Stefan N"aher (1993)
  21. //
  22. //------------------------------------------------------------------------------
  24. #include <LEDA/impl/bin_tree.h>
  27. bin_tree_node* bin_tree::lookup(GenPtr x) const
  28. { bin_tree_node* p = locate(x);
  29.   if (p && cmp(p->k,x) == 0) return p;
  30.   return 0;
  31. }
  33. void  bin_tree::change_inf(bin_tree_node* p,GenPtr y) 
  34. { clear_inf(p->i);
  35.   copy_inf(y);
  36.   p->i = y; 
  37.  }
  40. //------------------------------------------------------------------------------
  41. // locate(x) : returns pointer to leaf with successor or predessor key of x
  42. //------------------------------------------------------------------------------
  44. bin_tree_node* bin_tree::locate(GenPtr x) const
  45. { 
  46.   if (count==0) return 0;
  47.   return  int_type() ? int_search(x) : search(x);
  48. }
  51. //------------------------------------------------------------------------------
  52. // locate_succ(x) : returns pointer to leaf with minimal key >= x
  53. //             nil if tree empty
  54. //------------------------------------------------------------------------------
  56. bin_tree_node* bin_tree::locate_succ(GenPtr x) const
  57. { if (count==0) return 0;
  58.   bin_tree_node* p =  int_type() ? int_search(x) : search(x);
  59.   return (cmp(x,p->k) > 0) ? succ(p) : p ;
  60.  }
  64. //------------------------------------------------------------------------------
  65. // locate_pred(x) : returns pointer to leaf with maximal key <= x
  66. //                  nil if tree empty
  67. //------------------------------------------------------------------------------
  69. bin_tree_node* bin_tree::locate_pred(GenPtr x) const 
  70. { if (count==0) return 0;
  71.   bin_tree_node* p =  int_type() ? int_search(x) : search(x);
  72.   return (cmp(x,p->k) < 0) ? pred(p) : p ;
  73.  }
  77. //------------------------------------------------------------------------------
  78. // search(x) : returns pointer to leaf with minimal key >= x
  79. //------------------------------------------------------------------------------
  81. bin_tree_node* bin_tree::search(GenPtr x) const
  82. {
  83.   bin_tree_node* p = root();
  85.   while (p->is_node())
  86.        p = (cmp(x,p->k) <= 0) ? p->child[left] : p->child[right];
  88.   return p;
  89.  }
  93. //------------------------------------------------------------------------------
  94. // int_search : search for integer key 
  95. //------------------------------------------------------------------------------
  97. bin_tree_node* bin_tree::int_search(GenPtr x) const
  98. {
  99.   bin_tree_node* p = root();
  101.   while (p->is_node())
  102.      if (LEDA_ACCESS(int,x) <= LEDA_ACCESS(int,p->k))
  103.        p =  p->child[left];
  104.      else
  105.        p =  p->child[right];
  107.   return p;
  108.  }
  112. //------------------------------------------------------------------------------
  113. // insert(x,y,ii):
  114. // inserts new leaf with key x and info y, sets info of new inner node to ii
  115. // returns pointer to the new leaf
  116. //------------------------------------------------------------------------------
  118. bin_tree_node* bin_tree::insert( GenPtr x, GenPtr y, GenPtr ii)
  119. {  
  120.   // key x, inf y, iinf ii
  122.   bin_tree_node* p;
  124.    if (count==0)  // tree is empty 
  125.      { copy_key(x);
  126.        copy_inf(y);
  127.        p = new bin_tree_node(x,y,leaf_balance());
  128.        p->corr = &ROOT;
  129.        ROOT.i = ii;
  130.        min_ptr() = p;
  131.        root() = p;
  132.        p->parent = &ROOT;
  133.        p->child[right] = p;
  134.        p->child[left] = p;
  135.        count = 1;
  136.      }
  137.    else
  138.      { p = (int_type()) ? int_search(x) : search(x);
  139.        p = insert_at_item(p,x,y,ii);
  140.       }
  142.    return p ;
  143.  }
  147. bin_tree_node* bin_tree::insert_at_item(bin_tree_node* p, GenPtr x, GenPtr y, 
  148.                                                                     GenPtr ii)
  149. {
  151.    bool insert_left;  //  true <==> insert new leaf q to the left of p
  153.    copy_inf(y);
  154.                    
  155.    if ( int_type() )
  156.      { if ( LEDA_ACCESS(int,x) == LEDA_ACCESS(int,p->k) ) 
  157.        { // x already stored in tree, overwrite info
  158.          clear_inf(p->i);
  159.          p->i = y;
  160.          return p;
  161.         }
  162.        insert_left = (LEDA_ACCESS(int,x) < LEDA_ACCESS(int,p->k));
  163.       }
  164.    else
  165.       { int c = cmp(x,p->k);
  166.         if ( c == 0 )
  167.         { clear_inf(p->i);
  168.           p->i = y;
  169.           return p;
  170.          }
  171.         insert_left = (c < 0);
  172.         copy_key(x);
  173.        }
  175.    int b = (count==1) ? root_balance() : node_balance();
  177.    count++;
  179.    bin_tree_node* q = new bin_tree_node(x,y,leaf_balance()); // new leaf
  180.    bin_tree_node* r = new bin_tree_node(0,0,b);              // new inner node
  181.    bin_tree_node* u = p->parent; 
  183.    q->parent = r;
  184.    p->parent = r;
  185.    r->parent = u;
  186.    r->corr = nil;
  189.    if (p == u->child[left])
  190.       u->child[left] = r;
  191.    else
  192.       u->child[right] = r;
  194.    // insertion of q, adjusting key & inf of corresponding inner nodes,
  195.    // double-chaining with neighbors, checking min pointer, ...
  197.    if (insert_left) // insert q left of p
  198.       { r->k = x;
  199.         q->corr = r;
  200.         r->i = ii;
  201.         r->child[left] = q;
  202.         r->child[right]= p;
  203.         u = p->child[left];
  204.         q->child[left]  = u;
  205.         q->child[right] = p;
  206.         u->child[right] = q;
  207.         p->child[left]  = q;
  208.         if ( p == min_ptr() ) min_ptr() = q;     
  209.        }
  210.     else         // insert q right of p
  211.       { bin_tree_node* pc = p->corr; 
  212.         r->k = p->k;
  213.         r->i = pc->i;
  214.         pc->i = ii;
  215.         q->corr = pc;
  216.         p->corr = r;
  217.         r->child[left] = p;
  218.         r->child[right]= q;
  219.         u = p->child[right];
  220.         q->child[left]  = p;
  221.         q->child[right] = u;
  222.         u->child[left] = q;
  223.         p->child[right] = q;
  224.        }
  226.     propagate_modification(1,r,p);
  227.     propagate_modification(2,r,q);
  229.     if (r != root()) insert_rebal(r);
  231.     return q;
  233. }
  237. //------------------------------------------------------------------------------
  238. // del(x) 
  239. // removes leaf with key x from the tree
  240. // overwrites possible copy of x in an inner node (if key type is not integer)
  241. //------------------------------------------------------------------------------
  243. void bin_tree::del(GenPtr x)
  244. {
  245.   bin_tree_item v;
  247.   if (count == 0) return;  // tree is empty
  249.   if ( int_type() )
  250.     { v = int_search(x);
  251.       if (LEDA_ACCESS(int,v->k) == LEDA_ACCESS(int,x)) del_item(v);
  252.      }
  253.   else
  254.     { v = search(x);
  255.       if ( cmp(v->k,x) == 0 ) del_item(v);
  256.      }
  259.  }
  262. void bin_tree::del_item(bin_tree_item v)
  263. {
  264.   bin_tree_item w;
  265.   bin_tree_item p = v->parent;
  266.   bin_tree_item u = v->corr;
  268.   clear_key(v->k);
  269.   clear_inf(v->i);
  271.   // overwrite copy of key in corresponding inner node u by its predecessor,
  272.   // but keep its information (not necessary in the case that v is a left child)
  274.   if (v != p->child[left]) 
  275.   { bin_tree_node* pred =  v->child[left];
  276.     u->k = pred->k;
  277.     clear_iinf(pred->corr->i);
  278.     pred->corr = u;
  279.   }
  280.   else
  281.     clear_iinf(u->i);
  283.   count--;
  284.  
  285.   if (count == 0)      // tree is now empty
  286.   { root() = min_ptr() = nil;
  287.     delete v;
  288.     return;
  289.    } 
  292.   bin_tree_node* pred = v->child[left];
  293.   bin_tree_node* succ = v->child[right];
  295.   // link neighbors
  296.   pred->child[right] = succ; 
  297.   succ->child[left] = pred;
  299.   // adjust min pointer
  300.   if ( v == min_ptr() ) min_ptr() = succ;
  303.   // replace p by sibling w of v
  305.   u = p->parent;
  306.   w = p->child[left];
  307.   if (v == w) w =  p->child[right];
  308.   w->parent = u;
  309.   if (p == u->child[left])
  310.      u->child[left] = w;
  311.   else
  312.      u->child[right] = w;
  314.                                 //     u             u            u
  315.                                 //     |             |            |
  316.                                 //     p     or      p    --->    w
  317.                                 //    /            / 
  318.                                 //   v   w         w   v
  320.   propagate_modification(3,u,w);
  322.   // rebalance tree, if necessary
  324.   if (w != root()) del_rebal(w,p);
  326.   delete v;
  327.   delete p;
  329. }
  332. //------------------------------------------------------------------
  333. // concatenate
  334. //------------------------------------------------------------------
  336. bin_tree& bin_tree::conc(bin_tree&) 
  337. { error_handler(1,"sorry, bin_tree::conc not implemented"); 
  338.   return *this;
  339.  }
  341. //------------------------------------------------------------------
  342. // split at item
  343. //------------------------------------------------------------------
  345. void bin_tree::split_at_item(bin_tree_node*,bin_tree&,bin_tree&) 
  346. { error_handler(1,"sorry, bin_tree::split_at_item not implemented"); }
  349. //------------------------------------------------------------------
  350. // reverse items
  351. //------------------------------------------------------------------
  353. void bin_tree::reverse_items(bin_tree_node* v, bin_tree_node* w)
  354. {
  355.   bin_tree_node* l = v;
  356.   bin_tree_node* r = w;
  358.   while (l != r && r->child[right] != l) 
  359.   {
  360.     bin_tree_node* pl = l->parent;
  361.     bin_tree_node* pr = r->parent;
  362.     bin_tree_node* cl = l->corr;
  363.     bin_tree_node* cr = r->corr;
  366.     // exchange l and r
  368.    if (pl == pr)
  369.      { pl->child[left] = r;
  370.        pl->child[right] = l;
  371.       }
  372.    else
  373.      { if (l == pl->child[left])
  374.           pl->child[left] = r;
  375.        else
  376.           pl->child[right] = r;
  377.     
  378.        r->parent = pl;
  379.     
  380.        if (r == pr->child[left])
  381.           pr->child[left] = l;
  382.        else
  383.           pr->child[right] = l;
  384.     
  385.        l->parent = pr;
  386.       }
  387.   
  389.    // update corresponding inner nodes
  391.    l->corr = cr;
  392.    cr->k = l->k;
  394.    r->corr = cl;
  395.    cl->k = r->k;
  397.    l = l->child[right]; 
  398.    r = r->child[left];
  400.   }
  402.   // reverse chaining of leaves v...w
  404.   if (count > 2)
  405.   { l = v->child[left];
  406.     r = w->child[right];
  407.   
  408.     r->child[left] = v;
  409.   
  410.     bin_tree_node* p = v; 
  411.   
  412.     while(p != w)
  413.     { bin_tree_node* q = p->child[right];
  414.       p->child[left] = q;
  415.       p = q;
  416.      }
  417.   
  418.     w->child[left] = l;
  419.   
  420.     p = r;
  421.   
  422.     while ( p != l )
  423.     { bin_tree_node* q = p->child[left];
  424.       q->child[right] = p;
  425.       p = q;
  426.      }
  427.    }
  428.   
  430.   // adjust min pointer
  431.   
  432.   if (v == min_ptr()) min_ptr() = w;
  434.  }
  437. //------------------------------------------------------------------
  438. // operator=
  439. //------------------------------------------------------------------
  441. bin_tree& bin_tree::operator=(const bin_tree& t)
  442. {
  443.    if (this == &t) return *this;
  445.    clear();
  447.    if ( t.root() )   
  448.    { bin_tree_node* pre = 0;
  449.      root() = t.copy_tree(t.root(),pre);
  450.      root()->parent = &ROOT;
  451.      pre->corr = &ROOT;
  452.      ROOT.i = t.ROOT.i;
  453.      min_ptr() = root();
  454.      while (min_ptr()->child[left]) min_ptr() = min_ptr()->child[left];
  455.      min_ptr()->child[left] = pre;
  456.      pre->child[right] = min_ptr();
  457.      count = t.count;
  458.    }
  460.    return *this; 
  461. }
  463. //------------------------------------------------------------------
  464. // copy constructor
  465. //------------------------------------------------------------------
  467.   bin_tree::bin_tree(const bin_tree& t)
  468.   { root()  = min_ptr() = 0 ;
  469.     count = t.count; 
  470.     if ( t.root() ) 
  471.     { bin_tree_node* pre = 0;
  472.       root() = t.copy_tree(t.root(),pre);
  473.       min_ptr() = root();
  474.       root()->parent = &ROOT;
  475.       pre->corr = &ROOT;
  476.       while (min_ptr()->child[left]) min_ptr() = min_ptr()->child[left];
  477.       min_ptr()->child[left] = pre;
  478.       pre->child[right] = min_ptr();
  479.      }
  480.   }
  483. //------------------------------------------------------------------
  484. // copy_tree(p) makes a copy of tree with root p and returns a pointer to the
  485. // root of the copy. pre is last created leaf ( leaves are created from left 
  486. // to right).
  487. //------------------------------------------------------------------
  489. bin_tree_node* bin_tree::copy_tree( bin_tree_node* p, bin_tree_item& pre) const
  490. {
  491.   bin_tree_node* q = new bin_tree_node(p);  // q = p
  493.   q->corr = nil;
  495.   if ( p->is_node() )  // internal node: copy subtrees 
  496.   {
  497.     q->child[left] = copy_tree(p->child[left],pre);
  498.     pre->corr = q;
  499.     q->child[right] = copy_tree(p->child[right],pre);
  500.     q->child[left]->parent = q;
  501.     q->child[right]->parent = q;
  502.   }
  503.   else   //leaf: chaining with last created leaf "pre"
  504.   {
  505.     copy_key(q->k);
  506.     copy_inf(q->i);
  508.     if (pre) pre->child[right] = q; 
  509.     q->child[left] = pre;
  510.     pre = q;
  512.    }
  514.   return q;
  515. }
  517. //------------------------------------------------------------------
  518. // clear
  519. //------------------------------------------------------------------
  521. void bin_tree::clear() 
  522. {
  523.    if ( root() )
  524.    { del_tree(root());
  525.      root() = min_ptr() = 0;
  526.      count = 0;
  527.    }
  528. }
  530. //------------------------------------------------------------------
  531. // del_tree(p) : deletes subtree rooted at node p
  532. //------------------------------------------------------------------
  534. void bin_tree::del_tree(bin_tree_node* p)
  535. {
  536.   if ( p->is_node() )
  537.   { del_tree(p->child[left]);
  538.     del_tree(p->child[right]);
  539.    }
  540.   else
  541.   { clear_key(p->k);
  542.     clear_inf(p->i);
  543.     clear_iinf(p->corr->i);
  544.    }
  546.   delete p;
  547. }
  552. //----------------------------------------------------------------------------
  553. // printing and drawing trees
  554. //----------------------------------------------------------------------------
  556. void bin_tree::print() const
  557. { cout << "size = " << size() << endl;
  558.   if ( root() ) print_tree(root(),1);
  559.   newline;
  560. }
  563. void bin_tree::print_tree(bin_tree_node* p,int h) const
  564. {  
  565.   if ( p->is_node() ) print_tree(p->child[right],h+1);
  567.  for( int j=1; j <= h ; j++ ) cout << "     ";
  569.  print_key(key(p));
  570.  cout << " bal=" << p->get_bal();
  572.  if ( p->is_leaf() )
  573.  { cout << " [" << p << "] ";  
  574.    cout << " succ[" << p->child[right] << "] ";  
  575.    cout << " pred[" << p->child[left] << "] "; 
  576.    newline;
  577.  }
  578.  else cout << "n";
  580.  if ( p->is_node() ) print_tree(p->child[left],h+1);
  581. }
  583.         
  585. void bin_tree::draw(DRAW_BIN_NODE_FCT draw_node,
  586.                     DRAW_BIN_NODE_FCT draw_leaf,
  587.                     DRAW_BIN_EDGE_FCT draw_edge, 
  588.                     double x1, double x2, double y, double ydist)
  589. { 
  590.   // draw a picture of the tree using the functions
  591.   // draw_node(x,y,k,b)   draws node with key k and balance b at (x,y)
  592.   // draw_leaf(x,y,k,b)   draws leaf with key k and balance b at (x,y)
  593.   // draw_edge(x,y,x',y') draws an edge from (x,y) to (x',y')
  595.   draw(draw_node,draw_leaf,draw_edge,root(),x1,x2,y,ydist,0); 
  596.  }
  600. void bin_tree::draw(DRAW_BIN_NODE_FCT draw_node,
  601.                     DRAW_BIN_NODE_FCT draw_leaf,
  602.                     DRAW_BIN_EDGE_FCT draw_edge, 
  603.                     bin_tree_node* r, 
  604.                     double x1, double x2, double y, 
  605.                     double ydist, double last_x)
  606. { 
  607.   // draw subtree rooted at r
  609.   double x = (x1+x2)/2;
  611.   if (r==nil) return;
  613.   if (last_x != 0) draw_edge(last_x,y+ydist,x,y);
  615.   if (r->is_node()) 
  616.      { draw_node(x,y,r->k,r->get_bal());
  617.        draw(draw_node,draw_leaf,draw_edge, r->child[0],x1,x,y-ydist,ydist,x);
  618.        draw(draw_node,draw_leaf,draw_edge, r->child[1],x,x2,y-ydist,ydist,x);
  619.       }
  620.   else
  621.      draw_leaf(x,y,r->k,r->get_bal());
  622. }