Category

Development Platform
Home > SourceCode/Document > Mathimatics-Numerical algorithms > View Code
ab_tree.h
Package: leda.tar.gz　[view]
Upload User: gzelex
Upload Date: 2007-01-07
Package Size: 707k
Code Size: 6k
Category:

Mathimatics-Numerical algorithms

Development Platform:

MultiPlatform

ab_tree.h：Code Content
  1. /*******************************************************************************
  2. +
  3. +  LEDA-R  3.2.3
  4. +
  5. +  ab_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. *******************************************************************************/
  13. #ifndef LEDA_AB_TREE_H
  14. #define LEDA_AB_TREE_H
  16. //------------------------------------------------------------------------------
  17. //
  18. // (a,b)-trees 
  19. //
  20. // Evelyn Haak, Juergen Dedorath, and Dirk Basenach   (1989)
  21. //
  22. // Implementation follows
  23. // Kurt Mehlhorn : "Data Structures and Algorithms 1", section III, 5.2 - 5.3
  24. //
  25. // Modifications:
  26. // -------------
  27. //
  28. // - member-function insert_at_item added  ( Michael Wenzel , Nov. 89)
  29. //
  30. // - virtual compare function ( Michael Wenzel , Nov. 89)
  31. //
  32. // - delete : overwrite copies of inner nodes by
  33. //            following links between different
  34. //            instances of the same key    ( Michael Wenzel , Jan. 90)
  35. //
  36. // - virtual clear functions  ( S. Naeher, Mai 90)
  37. //
  38. //------------------------------------------------------------------------------
  40. #include    <LEDA/basic.h>
  42. //------------------------------------------------------------------------------
  43. //  some declarations
  44. //------------------------------------------------------------------------------
  47. class ab_tree;
  48. class ab_tree_node;
  50. typedef ab_tree_node* abnode;
  52. typedef ab_tree_node* ab_tree_item;
  55. /*------------------------------------------------------------*/
  56. /*  class ab_tree_node                                        */
  57. /*------------------------------------------------------------*/
  59. class ab_tree_node {
  60.   friend class ab_tree;
  62.   friend void concat(ab_tree& s1,ab_tree& s2,ab_tree_node* current,GenPtr cur_key);
  63.   friend void pr_ab_tree(ab_tree_node* localroot,int blancs);
  64.   friend void del_ab_tree(ab_tree_node* localroot);
  66.  
  67.   int p;           /* number of sons,a<=p<=b,0 iff leave*/
  68.   int height;      /* height of node*/
  69.   int index;       /* v is index'th son of his father*/
  70.   ab_tree_node* father;   
  71.   GenPtr* k;    /* array[1..b] --------------------------  */
  72.                          //-----------------------------------
  73.                          /*to every node v of T we assign p(v)-1 */
  74.                          /*elements k[1](v),...,k[p(v)-1](v) of U*/
  75.                          /* such that for all i (1<i<p(v)-1):*/
  76.                          /* k[i](v) < k[i+1](v) and for all leaves*/
  77.                          /* w in the i-th subtree of v we have*/
  78.                          /* k[i-1] < key[w] <= k[i](v) */
  79.                          /*------------------------------------*/
  80.                          /* if v is a leave ==> k[1]=key[v]*/
  82.                          
  83.   ab_tree_node** son;    /* array [1..b+1] of pointer to sons*/
  84.   ab_tree_node** same;   /* m.w. : links between same keys */
  85.                          /* array [1..b]                   */
  86.   GenPtr inf;
  88. /* size = 8 words  */
  90. public:
  92.   ab_tree_node(int p,int height,int index,ab_tree_node* father,int b);
  94.  ~ab_tree_node();
  96.   LEDA_MEMORY(ab_tree_node)
  98.  }; 
  99.   
  100. /*-----------------------------------------------------------------*/
  101. class ab_tree   
  102.    {
  104.     friend class ab_tree_node;
  106.     friend void concat(ab_tree&,ab_tree&,ab_tree_node*,GenPtr); 
  109.     friend void pr_ab_tree(ab_tree_node* localroot,int blancs);
  110.     friend void del_ab_tree(ab_tree_node* localroot);
  112.     int a;
  113.     int b;
  115.     int height;             /* height of tree   */
  116.     int count;              /* number of leaves */
  118.     ab_tree_node* root;
  119.     ab_tree_node* minimum;  
  120.     ab_tree_node* maximum;
  122.     ab_tree_node* expand(ab_tree_node* v,int i);
  124.     void split_node(ab_tree_node* v);
  125.     void share(ab_tree_node* v,ab_tree_node* y,int direct);
  126.     void fuse (ab_tree_node* v,ab_tree_node* w);
  127.     void del_tree(ab_tree_node* localroot);
  128.     void exchange_leaves(ab_tree_node*, ab_tree_node*);
  129.     void pr_ab_tree(ab_tree_node*,int) const;
  133.     ab_tree_node* copy_ab_tree(ab_tree_node*,abnode&,int) const;
  135.     virtual int cmp(GenPtr, GenPtr) const { return 0; }
  136.     virtual int int_type() const { return 0; }
  137.     virtual void clear_key(GenPtr&) const {}
  138.     virtual void clear_inf(GenPtr&) const {}
  139.     virtual void copy_key(GenPtr&)  const {}
  140.     virtual void copy_inf(GenPtr&)  const {}
  141.     virtual void print_key(GenPtr)  const {}
  142.     virtual void print_inf(GenPtr)  const {}
  144. protected:
  145.  ab_tree_item item(void* p) const { return ab_tree_item(p); }
  148. public:
  152.     void clear();
  154.     GenPtr  inf(ab_tree_node* p)  const { return p->inf; }
  155.     GenPtr  key(ab_tree_node* p)  const { return p->k[1]; }
  157.     ab_tree_node* insert(GenPtr, GenPtr);
  158.     ab_tree_node* insert_at_item(ab_tree_node*, GenPtr, GenPtr);
  159.     ab_tree_node* locate(GenPtr) const;
  160.     ab_tree_node* locate_succ(GenPtr) const;
  161.     ab_tree_node* locate_pred(GenPtr) const;
  162.     ab_tree_node* lookup(GenPtr) const;
  164.     void del(GenPtr);
  165.     void del_item(ab_tree_node*);
  166.     void change_inf(ab_tree_node*, GenPtr);
  167.     void reverse_items(ab_tree_node*, ab_tree_node*);
  169.     ab_tree& conc(ab_tree&);
  170.     void split_at_item(ab_tree_node* w,ab_tree& L,ab_tree& R);
  172.     void del_min()                 { if (minimum) del_item(minimum); }
  173.     void decrease_key(ab_tree_node* p, GenPtr k) { GenPtr i = p->inf;
  174.                                                 copy_key(i);
  175.                                                 del_item(p);
  176.                                                 insert(k,i);
  177.                                                 clear_key(i);
  178.                                                }
  181.     bool member(GenPtr k)  const { return (lookup(k))? true: false ; }
  183.     ab_tree_node* min()                      const { return minimum; }
  184.     ab_tree_node* find_min()                 const { return minimum; }
  185.     ab_tree_node* max()                      const { return maximum; }
  186.     ab_tree_node* first_item()               const { return minimum; }
  187.     ab_tree_node* next_item(ab_tree_node* p) const { return p->son[2]; }
  188.     ab_tree_node* succ(ab_tree_node* p)      const { return p->son[2]; }
  189.     ab_tree_node* pred(ab_tree_node* p)      const { return p->son[1]; }
  191.     int  size()  const { return count;       }
  192.     bool empty() const { return (count==0) ? true : false;   }
  193.     void print() const { pr_ab_tree(root,1); }
  195.     //ab_tree(int a_=2,int b_=4); 
  196.     ab_tree(int=2,int=16); 
  197.     ab_tree(const ab_tree& T);
  199.     ab_tree& operator=(const ab_tree&);
  200.  
  201.     virtual ~ab_tree(){ clear(); }
  202.  };
  204. #endif