1 /*
2 * AVL.h
3 * nlivarot
4 *
5 * Created by fred on Mon Jun 16 2003.
6 *
7 */
9 #ifndef my_avl
10 #define my_avl
12 #include <cstdlib>
13 #include "LivarotDefs.h"
15 /*
16 * base class providing AVL tree functionnality, that is binary balanced tree
17 * there is no Find() function because the class only deal with topological info
18 * subclasses of this class have to implement a Find(), and most certainly to
19 * override the Insert() function
20 */
22 class AVLTree
23 {
24 public:
26 AVLTree *elem[2];
28 // left most node (ie, with smallest key) in the subtree of this node
29 AVLTree *Leftmost();
31 protected:
33 AVLTree *son[2];
35 AVLTree();
36 ~AVLTree();
38 // constructor/destructor meant to be called for an array of AVLTree created by malloc
39 void MakeNew();
40 void MakeDelete();
42 // insertion of the present node in the tree
43 // insertType is the insertion type (defined in LivarotDefs.h: not_found, found_exact, found_on_left, etc)
44 // insertL is the node in the tree that is immediatly before the current one, NULL is the present node goes to the
45 // leftmost position. if insertType == found_exact, insertL should be the node with ak key
46 // equal to that of the present node
47 int Insert(AVLTree * &racine, int insertType, AVLTree *insertL,
48 AVLTree * insertR, bool rebalance);
50 // called when this node is relocated to a new position in memory, to update pointers to him
51 void Relocate(AVLTree *to);
53 // removal of the present element racine is the tree's root; it's a reference because if the
54 // node is the root, removal of the node will change the root
55 // rebalance==true if rebalancing is needed
56 int Remove(AVLTree * &racine, bool rebalance = true);
58 private:
60 AVLTree *dad;
62 int balance;
64 // insertion gruntwork.
65 int Insert(AVLTree * &racine, int insertType, AVLTree *insertL, AVLTree *insertR);
67 // rebalancing functions. both are recursive, but the depth of the trees we'll use should not be a problem
68 // this one is for rebalancing after insertions
69 int RestoreBalances(AVLTree *from, AVLTree * &racine);
70 // this one is for removals
71 int RestoreBalances(int diff, AVLTree * &racine);
73 // startNode is the node where the rebalancing starts; rebalancing then moves up the tree to the root
74 // diff is the change in "subtree height", as needed for the rebalancing
75 // racine is the reference to the root, since rebalancing can change it too
76 int Remove(AVLTree * &racine, AVLTree * &startNode, int &diff);
78 void insertOn(Side s, AVLTree *of);
79 void insertBetween(AVLTree *l, AVLTree *r);
80 AVLTree *leaf(AVLTree *from, Side s);
81 AVLTree *leafFromDad(AVLTree *from, Side s);
82 };
84 #endif
86 /*
87 Local Variables:
88 mode:c++
89 c-file-style:"stroustrup"
90 c-file-offsets:((innamespace . 0)(inline-open . 0)(case-label . +))
91 indent-tabs-mode:nil
92 fill-column:99
93 End:
94 */
95 // vim: filetype=cpp:expandtab:shiftwidth=4:tabstop=8:softtabstop=4:encoding=utf-8:textwidth=99 :