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

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

数值算法/人工智能

开发平台：

MultiPlatform

bin_tree.h：源码内容
  1. /*******************************************************************************
  2. +
  3. +  LEDA-R  3.2.3
  4. +
  5. +  bin_tree.h
  6. +
  7. +  Copyright (c) 1995  by  Max-Planck-Institut fuer Informatik
  8. +  Im Stadtwald, 66123 Saarbruecken, Germany     
  9. +  All rights reserved.
  10. + 
  11. *******************************************************************************/
  14. #ifndef LEDA_BIN_TREE_H
  15. #define LEDA_BIN_TREE_H
  17. //------------------------------------------------------------------------------
  18. //
  19. // bin_tree  
  20. //
  21. //     base class for all leaf oriented binary trees in LEDA
  22. //
  23. // Stefan N"aher (1993)
  24. //
  25. //------------------------------------------------------------------------------
  28. #include <LEDA/basic.h>
  30.  
  31. class bin_tree;
  32. class bin_tree_node;
  34. typedef bin_tree_node* bin_tree_item;
  36. typedef void (*DRAW_BIN_NODE_FCT)(double,double,void*,int);
  37. typedef void (*DRAW_BIN_EDGE_FCT)(double,double,double,double);
  40. //------------------------------------------------------------------------------
  41. // class bin_tree_node 
  42. //------------------------------------------------------------------------------
  44. class bin_tree_node
  45. {  
  46.    friend class bin_tree;
  47.    friend class avl_tree;
  48.    friend class bb_tree;
  49.    friend class rb_tree;
  50.    friend class rs_tree;
  53.    GenPtr   k;              // key
  54.    GenPtr   i;              // info
  56.    bin_tree_node* child[2]; // node: left and right child
  57.                             // leaf: successor and predecessor
  59.    bin_tree_node* parent;   // pointer to parent
  61.    bin_tree_node* corr;     // leaf: pointer to corresponding inner node
  62.                             // node: nil
  64.    int   bal;               // rebalancing data
  65.  
  67. /*
  68.    public:
  69. */
  72.    bin_tree_node(GenPtr key, GenPtr inf, int b)
  73.    { k = key;
  74.      i = inf; 
  75.      bal = b;
  76.     }         
  78.    bin_tree_node() { }         
  80.    bin_tree_node(bin_tree_node* p)
  81.    { k = p->k;
  82.      i = p->i ;
  83.      bal = p->bal;
  84.     }         
  86.    bool is_node()   { return (corr == nil);  }
  87.    bool is_leaf()   { return (corr != nil); }
  89.    void set_bal(int x) { bal = x; }
  90.    int  get_bal()      { return bal; }
  93.    LEDA_MEMORY(bin_tree_node)
  95. };
  98.  
  99. //------------------------------------------------------------------------------
  100. // class bin_tree
  101. //------------------------------------------------------------------------------
  103. class bin_tree
  104. { 
  105.   protected:
  107.   enum { left=0, right=1 };
  109.   bin_tree_node ROOT;       // "super root" to avoid special cases in rotations
  110.                             // ROOT.child[left] points to real root node
  111.                             // ROOT.child[right] points to leftmost leaf
  112.   int count;            
  115.   // functions depending on used rebalancing method
  116.   // will be defined in derived classes (rb_tree, avl_tree, ...)
  118.   virtual int leaf_balance() { return 0; }  // default balance value for leaves
  119.   virtual int node_balance() { return 0; }  // inner nodes
  120.   virtual int root_balance() { return 0; }  // root node
  122.   virtual void insert_rebal(bin_tree_node*)   {}
  123.   virtual void del_rebal(bin_tree_node*, bin_tree_node*) {}
  128.   // other protected member functions
  130.   bin_tree_node*& min_ptr() const 
  131.                            { return (bin_tree_node*&)ROOT.child[right];}
  133.   void rotation(bin_tree_node*, bin_tree_node*, int);
  134.   void double_rotation(bin_tree_node*, bin_tree_node*, bin_tree_node*, int);
  136.   void del_tree(bin_tree_node*);
  138.   bin_tree_node* int_search(GenPtr) const;
  139.   bin_tree_node* search(GenPtr) const;
  140.   bin_tree_node* copy_tree(bin_tree_node*,bin_tree_item&) const;
  144.   // functions depending on actual key type
  145.   // will be defined in dictionary and sortseq templates
  147.   virtual int cmp(GenPtr x, GenPtr y) const { return compare(x,y); }
  148.   virtual void clear_key(GenPtr&) const { }
  149.   virtual void clear_inf(GenPtr&) const { }
  150.   virtual void clear_iinf(GenPtr&)const { }
  151.   virtual void copy_key(GenPtr&)  const { }
  152.   virtual void copy_inf(GenPtr&)  const { }
  153.   virtual void print_key(GenPtr)  const { }
  154.   virtual void print_inf(GenPtr)  const { }
  155.   virtual int  int_type() const { return 0; }
  157.   //bin_tree_node* item(void* p) const { return (bin_tree_node*)p; }
  160. public:
  162.   bin_tree_node* item(void* p) const { return (bin_tree_node*)p; }
  164.   bin_tree_node*& root() const 
  165.                            { return (bin_tree_node*&)ROOT.child[left]; }
  168.   bin_tree_node* cyclic_succ(bin_tree_node* p) const { return p->child[right]; }
  169.   bin_tree_node* cyclic_pred(bin_tree_node* p) const { return p->child[left]; }
  171.   bin_tree_node* succ(bin_tree_node* p) const
  172.   { return (p->child[right] == min_ptr()) ? 0 : p->child[right]; }
  174.   bin_tree_node* pred(bin_tree_node* p) const
  175.   { return (p == min_ptr())  ?  0 : p->child[left] ; }
  177.   bin_tree_node* first_item()  const               { return min_ptr(); }
  178.   bin_tree_node* next_item(bin_tree_node* p) const { return succ(p); }
  180.   bin_tree_node* min() const { return min_ptr(); }
  181.   bin_tree_node* max() const { return (count>0) ? min_ptr()->child[left] : 0; }
  184.   bin_tree& conc(bin_tree&);
  185.   void split_at_item(bin_tree_node*,bin_tree&,bin_tree&);
  186.   void reverse_items(bin_tree_node*,bin_tree_node*);
  189.   bin_tree_node* insert(GenPtr,GenPtr,GenPtr=0);
  190.   bin_tree_node* insert_at_item(bin_tree_node*,GenPtr,GenPtr,GenPtr=0);
  191.   bin_tree_node* lookup(GenPtr) const;
  192.   bin_tree_node* locate(GenPtr) const;
  193.   bin_tree_node* locate_succ(GenPtr) const; 
  194.   bin_tree_node* locate_pred(GenPtr) const; 
  196.   GenPtr   key(bin_tree_node* p)  const { return  p->k; }
  197.   GenPtr   inf(bin_tree_node* p)  const { return  p->i; }
  198.   GenPtr&  info(bin_tree_node* p) const { return  p->i; }
  200.   void del(GenPtr);
  201.   void del_item(bin_tree_node* p);
  202.   void change_inf(bin_tree_node*,GenPtr);
  204.   void clear();
  206.   int size()   const { return count; } 
  207.   int empty()  const { return root() ? false : true ; }
  211.   // construction, assignment, destruction
  213.   bin_tree() {  count = 0; root() = nil; min_ptr() = nil; }
  215.   bin_tree(const bin_tree&);
  216.   bin_tree& operator=(const bin_tree&);
  218.   virtual ~bin_tree() { clear(); }
  222.   // additional operations used by range and segment trees
  224.   virtual void propagate_modification(int, GenPtr, GenPtr) {}
  226.   bin_tree_node* l_child(bin_tree_node* p) const
  227.   { return p->is_leaf() ? 0 : p->child[left]; }
  229.   bin_tree_node* r_child(bin_tree_node* p) const
  230.   { return p->is_leaf() ? 0 : p->child[right]; }
  232.   int is_inner(bin_tree_node* p)  const
  233.   { return p->corr == 0; }
  235.   bin_tree_node* parent(bin_tree_node* p)  const
  236.   { return (p==root()) ? 0 : p->parent; }
  239.   // miscellaneous
  241.   void draw(DRAW_BIN_NODE_FCT, DRAW_BIN_NODE_FCT, DRAW_BIN_EDGE_FCT, 
  242.             bin_tree_node*, double, double, double, double, double);
  244.   void draw(DRAW_BIN_NODE_FCT, DRAW_BIN_NODE_FCT, DRAW_BIN_EDGE_FCT, 
  245.             double, double, double, double);
  247.   void print() const;
  248.   void print_tree(bin_tree_node*,int) const;
  250. };
  254. inline void bin_tree::rotation(bin_tree_node* p,bin_tree_node* q, int dir)
  255. { bin_tree_node* r = q->child[1-dir];
  256.   bin_tree_node* x = p->parent;
  257.   p->child[dir] = r;
  258.   q->child[1-dir] = p;
  259.   p->parent = q;
  260.   r->parent = p;
  261.   if (p == x->child[left])
  262.      x->child[left] = q;
  263.   else
  264.      x->child[right] = q;
  265.   q->parent = x;
  267.   propagate_modification(4,p,r);
  268.   propagate_modification(5,q,p);
  269.   if( x!=&ROOT )
  270.     propagate_modification(6,x,q);
  271.  }
  274. inline void bin_tree::double_rotation(bin_tree_node* p, bin_tree_node* q, 
  275.                                       bin_tree_node* r, int dir1)
  276. { int dir2 = 1-dir1;
  277.   bin_tree_node* s = r->child[dir1];
  278.   bin_tree_node* t = r->child[dir2];
  279.   bin_tree_node* x = p->parent;
  280.   p->child[dir1] = t;
  281.   q->child[dir2] = s;
  282.   r->child[dir1] = q;
  283.   r->child[dir2] = p;
  284.   p->parent = r;
  285.   q->parent = r;
  286.   s->parent = q;
  287.   t->parent = p;
  289.   if (p == x->child[left])
  290.      x->child[left] = r;
  291.   else
  292.      x->child[right] = r;
  294.   r->parent = x;
  296.   propagate_modification(7,p,t);
  297.   propagate_modification(8,q,s);
  298.   propagate_modification(9,r,p);
  299.   propagate_modification(10,r,q);
  300.   if( x!=&ROOT )
  301.     propagate_modification(11,x,r);
  302. }
  306. #if !defined(__TEMPLATE_FUNCTIONS)
  307. // dummy I/O and cmp functions
  309. inline void Print(const bin_tree&,ostream&) { }
  310. inline void Read(bin_tree&, istream&) { }
  311. inline int  compare(const bin_tree&,const bin_tree&) { return 0; }
  312. #endif
  314. #endif