Balanced Binary Tree

The AVL tree named for Soviet mathematicians Georgi Maximowitsch Adelson-Velski and Jewgeni Michailowitsch Landis presented this balanced data structure in 1962.

Through left or right rotation of nodes are balanced the AVL tree.

tree.h
1#ifndef tree_h
2#define tree_h
3
4template<typename T> class Tree {
5private:
6    T node;
7    int balance;
8    Tree *left;
9    Tree *right;
10    Tree *parent;
11    
12    void delete_tree(Tree<T> *node) {
13        if(node != NULL) {
14            delete_tree(node->left);
15            delete_tree(node->right);
16            delete parent;
17        }
18    }
19public:
20    //constructor
21    Tree(Tree<T> *parent, T node) {
22        this->node = node;
23        this->balance = 0;
24        this->parent = parent;
25        this->left = NULL;
26        this->right = NULL;
27    }
28    //destructor
29    virtual ~Tree<T>() { delete_tree(this->parent); }
30    
31    void setNode(T node) { this->node = node; }
32    
33    void setParent(Tree<T> *parent) { this->parent = parent; }
34    
35    void setLeftParent(Tree<T> *leftParent) { this->left->parent = leftParent; }
36    
37    void setParentLeft(Tree<T> *parentLeft) { this->parent->left = parentLeft; }
38    
39    void setLeftChild(Tree<T> *left) { this->left = left; }
40    
41    void setRightParent(Tree<T> *rightParent) { this->right->parent = rightParent; }
42    
43    void setParentRight(Tree<T> *parentRight) { this->parent->right = parentRight; }
44    
45    void setRightChild(Tree<T> *right) { this->right = right; }
46    
47    void setBalance(int balance) { this->balance = balance; }
48    
49    T getNode() { return this->node; }
50    
51    Tree<T> *getParent() { return this->parent; }
52    
53    Tree<T> *getLeftParent() { return this->left->parent; }
54    
55    Tree<T> *getParentLeft() { return this->parent->left; }
56    
57    Tree<T> *getLeftChild() { return this->left; }
58    
59    Tree<T> *getRightParent() { return this->right->parent; }
60    
61    Tree<T> *getParentRight() { return this->parent->right; }
62    
63    Tree<T> *getRightChild() { return this->right; }
64    
65    int getBalance() { return this->balance; }
66};
67
68#endif /* tree_h */
avltreeroot.h
1#ifndef avltreeroot_h
2#define avltreeroot_h
3#include "tree.h"
4
5template<typename T> class AVLTreeRoot {
6protected:
7    Tree<T> *root;
8
9public:
10    AVLTreeRoot() { root = NULL; }
11    virtual ~AVLTreeRoot() { delete root; }
12};
13
14#endif /* avltreeroot_h */
avltreecontrol.h
1#ifndef avltreecontrol_h
2#define avltreecontrol_h
3#include <string>
4#include <queue>
5#include "avltreeroot.h"
6using namespace std;
7
8template<typename T> class AVLTreeControl : protected virtual AVLTreeRoot<T> {
9protected:
10    int height(Tree<T> *node) {
11        if(node == NULL) return -1;
12        return 1 + max(height(node->getLeftChild()), height(node->getRightChild()));
13    }
14    
15    int treeHeight(Tree<T> *root) {
16        int level = 0;
17        
18        // Use a queue for breadth-first traversal of the tree. The pair is
19        // to keep track of the depth of each node. (Depth of root node is 1.)
20        typedef pair<Tree<int>*,int> node_level;
21        queue<node_level> q;
22        q.push(node_level(root, 1));
23        
24        while (!q.empty()) {
25            node_level nl = q.front();
26            q.pop();
27            
28            if (nullptr != (root = nl.first)) {
29                if (level != nl.second) {
30                    level = nl.second;
31                }
32                
33                q.push(node_level(root->getLeftChild(), 1 + level));
34                q.push(node_level(root->getRightChild(), 1 + level));
35            }
36        }
37        
38        return level;
39    }
40
41    void setBalance(Tree<T> *node) {
42        node->setBalance((height(node->getRightChild()) - height(node->getLeftChild())));
43    }
44    
45    Tree<T> *rotateLeft(Tree<T> *a) {
46        Tree<T> *b = a->getRightChild();
47        b->setParent(a->getParent());
48        a->setRightChild(b->getLeftChild());
49        
50        if(a->getRightChild() != NULL) a->setRightParent(a);
51        
52        b->setLeftChild(a);
53        a->setParent(b);
54        
55        if(b->getParent() != NULL) {
56            if(b->getParentRight() == a) b->setParentRight(b);
57            else b->setParentLeft(b);
58        }
59        
60        setBalance(a);
61        setBalance(b);
62        
63        return b;
64    }
65    
66    Tree<T> *rotateRight(Tree<T> *a) {
67        Tree<T> *b = a->getLeftChild();
68        
69        b->setParent(a->getParent());
70        
71        a->setLeftChild(b->getRightChild());
72        
73        if(a->getLeftChild() != NULL) a->setLeftParent(a);
74        
75        b->setRightChild(a);
76        
77        a->setParent(b);
78        
79        if(b->getParent() != NULL) {
80            if(b->getParentRight() == a) b->setParentRight(b);
81            
82            else b->setParentLeft(b);
83        }
84        
85        setBalance(a);
86        
87        setBalance(b);
88        
89        return b;
90    }
91    
92    Tree<T> *rotateLeftThenRight(Tree<T> *node) {
93        node->setLeftChild(rotateLeft(node->getLeftChild()));
94        return rotateRight(node);
95    }
96    
97    Tree<T> *rotateRightThenLeft(Tree<T> *node) {
98        node->setRightChild(rotateRight(node->getRightChild()));
99        
100        return rotateLeft(node);
101    }
102    
103    void rebalance(Tree<T> *node) {
104        setBalance(node);
105        
106        if(node->getBalance() == -2) {
107            if(height(node->getLeftChild()->getLeftChild()) >= height(node->getLeftChild()->getRightChild())) node = rotateRight(node);
108            
109            else node = rotateLeftThenRight(node);
110        }
111        
112        else if(node->getBalance() == 2) {
113            if(height(node->getRightChild()->getRightChild()) >= height(node->getRightChild()->getLeftChild())) node = rotateLeft(node);
114            else node = rotateRightThenLeft(node);
115        }
116        
117        if(node->getParent() != NULL) rebalance(node->getParent());
118        
119        else this->root = node;
120    }
121    
122    void clearNode(Tree<T> *node);
123    
124    Tree<T> *navigateToMinimum() {
125        Tree<T> *parent = this->root;
126        Tree<T> *child = this->root;
127        Tree<T> *next = this->root;
128        
129        while (child != NULL) {
130            parent = next;
131            next = child;
132            child = next->getLeftChild();
133        }
134        
135        return next;
136    }
137    
138    Tree<T> *navigateToMaximum() {
139        Tree<T> *parent = this->root;
140        Tree<T> *child = this->root;
141        Tree<T> *next = this->root;
142        
143        while (child != NULL) {
144            parent = next;
145            next = child;
146            child = next->getRightChild();
147        }
148        
149        return next;
150    }
151    
152    void erase(const T &key) {
153        if(this->root == NULL) return;
154        
155        Tree<T> *n = this->root;
156        Tree<T> *parent = this->root;
157        Tree<T> *delNode = NULL;
158        Tree<T> *child = this->root;
159        
160        while(child != NULL) {
161            parent = n;
162            n = child;
163            
164            child = key >= n->getNode() ? n->getRightChild() : n->getLeftChild();
165            
166            if(key == n->getNode()) delNode = n;
167        }
168        
169        if(delNode != NULL) {
170            delNode->setNode(n->getNode());
171            
172            child = n->getLeftChild() != NULL ? n->getLeftChild() : n->getRightChild();
173            
174            if(this->root->getNode() == key) this->root = child;
175            
176            else {
177                if(parent->getLeftChild() == n) parent->setLeftChild(child);
178                else parent->setRightChild(child);
179                
180                rebalance(parent);
181            }
182        }
183    }
184    
185    int search(T node) {
186        if(this->root == NULL) return -1;
187        
188        Tree<T> *parent = this->root;
189        Tree<T> *child = this->root;
190        Tree<T> *n = this->root;
191        
192        while(child != NULL) {
193            parent = n;
194            n = child;
195            
196            child = node >= n->getNode() ? n->getRightChild() : n->getLeftChild();
197            
198            if(node == n->getNode()) return 1;
199        }
200        
201        return 0;
202    }
203    
204    string getInOrder(Tree<T> *root) {
205        string ret;
206        
207        Tree<T> *current,*pre;
208        
209        if(root == NULL) return 0;
210        
211        current = root;
212        
213        while(current != NULL) {
214            if(current->getLeftChild() == NULL) {
215                ret = current->getNode();
216                
217                current = current->getRightChild();
218            }
219            
220            else {
221                /* Find the inorder predecessor of current */
222                pre = current->getLeftChild();
223                
224                while(pre->getRightChild() != NULL && pre->getRightChild() != current) pre = pre->getRightChild();
225                
226                /* Make current as right child of its inorder predecessor */
227                if(pre->getRightChild() == NULL) {
228                    pre->setRightChild(current);
229                    current = current->getLeftChild();
230                }
231                
232                /* Revert the changes made in if part to restore the original tree i.e., fix the right child of predecssor */
233                else {
234                    pre->setRightChild(NULL);
235                    
236                    ret = current->getNode();
237                    
238                    current = current->getRightChild();
239                } /* End of if condition pre->right == NULL */
240            } /* End of if condition current->left == NULL*/
241        } /* End of while */
242        
243        return ret;
244    }
245    
246    int countNodes(Tree<T> *root) {
247        int ret = 0;
248        Tree<T> *current,*pre;
249        
250        if(root == NULL) return 0;
251        
252        current = root;
253        while(current != NULL) {
254            if(current->getLeftChild() == NULL) {
255                ret = ret + 1;
256                current = current->getRightChild();
257            }
258            else {
259                /* Find the inorder predecessor of current */
260                pre = current->getLeftChild();
261                while(pre->getRightChild() != NULL && pre->getRightChild() != current) pre = pre->getRightChild();
262                
263                /* Make current as right child of its inorder predecessor */
264                if(pre->getRightChild() == NULL) {
265                    pre->setRightChild(current);
266                    current = current->getLeftChild();
267                }
268                
269                /* Revert the changes made in if part to restore the original tree i.e., fix the right child of predecssor */
270                else {
271                    pre->setRightChild(NULL);
272                    ret = ret + 1;
273                    current = current->getRightChild();
274                } /* End of if condition pre->right == NULL */
275            } /* End of if condition current->left == NULL*/
276        } /* End of while */
277        
278        return ret;
279    }
280    
281    AVLTreeControl<T>() : AVLTreeRoot<T>() {}
282    
283    virtual ~AVLTreeControl<T>() {}
284};
285
286#endif /* avltreecontrol_h */
avltreeinsert.h
1#ifndef avltreeinsert_h
2#define avltreeinsert_h
3#include "avltreecontrol.h"
4
5template<typename T> class AVLTreeInsert : protected virtual AVLTreeControl<T> {
6protected:
7    bool insert(T &node) {
8        if(this->root == NULL) this->root = new Tree<T>(NULL, node);
9        
10        else {
11            Tree<T> *n = this->root;
12            Tree<T> *parent;
13            
14            while(true) {
15                if(n->getNode() == node) return false;
16                
17                parent = n;
18                
19                bool goLeft = n->getNode() > node;
20                
21                n = goLeft ? n->getLeftChild() : n->getRightChild();
22                
23                if(n == NULL) {
24                    if(goLeft) parent->setLeftChild(new Tree<T>(parent, node));
25                    
26                    else parent->setRightChild(new Tree<T>(parent, node));
27                    
28                    this->rebalance(parent);
29                    
30                    break;
31                }
32            }
33        }
34        
35        return true;
36    }
37    
38    AVLTreeInsert<T>() : AVLTreeControl<T>() {}
39    
40    virtual ~AVLTreeInsert<T>() {}
41};
42
43
44#endif /* avltreeinsert_h */
avltreeprint.h
1#ifndef avltreeprint_h
2#define avltreeprint_h
3#include <iostream>
4#include <sstream>
5#include <iomanip>
6#include <string>
7#include "avltreecontrol.h"
8using namespace std;
9
10template<typename T> class AVLTreePrint : protected virtual AVLTreeControl<T> {
11private:
12    unsigned height(Tree<T> *node) {
13        if(!node) return 0;
14        unsigned left_height = 0, right_height = 0;
15        
16        if(node->getLeftChild()) left_height = height(node->getLeftChild());
17        
18        if(node->getRightChild()) right_height = height(node->getRightChild());
19        
20        // Der höchste Unterbaum bestimmt die Gesamthöhe
21        return std::max(left_height, right_height) + 1;
22    }
23    
24    unsigned width(Tree<T> *node) {
25        if(!node) return 0;
26        unsigned left_width = 0, right_width = 0;
27        
28        if(node->getLeftChild()) left_width = width(node->getLeftChild());
29        if(node->getRightChild()) right_width = width(node->getRightChild());
30        
31        return left_width + format_label(node).length() + right_width;
32   }
33    
34    string format_label(Tree<T> *node) {
35        if(node) {
36            std::ostringstream out;
37            out << node->getNode();
38            return out.str();
39        }
40        
41        else return "";
42    }
43    
44    void dump_spaces(std::ostream &out, unsigned count) {
45        for(unsigned i = 0; i < count; ++i) {
46            out.put(' ');
47        }
48    }
49    
50    void dump_line(std::ostream &out, Tree<T> *node, unsigned line){
51        if(!node) return;
52        
53        if(line == 1) {
54            //output root
55            dump_spaces(out, width(node->getLeftChild()));
56            out << format_label(node);
57            dump_spaces(out, width(node->getRightChild()));
58        }
59        else {
60            //the roots are one level down and the line number is changed of both subtrees
61            dump_line(out, node->getLeftChild(), line-1);
62            dump_spaces(out, format_label(node).length());
63            dump_line(out, node->getRightChild(), line-1);
64        }
65    }
66
67    void dump_node(std::ostream &out, Tree<T> *node) {
68        for(unsigned line = 1, h = height(node); line <= h; ++line) {
69            dump_line(out, node, line);
70            out.put('\n');
71        }
72        
73        out.flush();
74    }
75    
76protected:
77    void showBalance(Tree<T> *node) {
78        if(node != NULL) {
79            showBalance(node->getLeftChild());
80            cout << node->getBalance() << " ";
81            showBalance(node->getRightChild());
82        }
83    }
84    
85    void showPreOrder(Tree<T> *preorder) {
86        if(preorder == NULL) return;
87        else {
88            cout << preorder->getNode() << " ";
89            showPreOrder(preorder->getLeftChild());
90            showPreOrder(preorder->getRightChild());
91        }
92    }
93    
94    void showInOrder(Tree<T> *inorder) {
95        if(inorder == NULL) return;
96        else {
97            showInOrder(inorder->getLeftChild());
98            cout << inorder->getNode() << " ";
99            showInOrder(inorder->getRightChild());
100        }
101    }
102    
103    void showPostOrder(Tree<T> *postorder) {
104        if(postorder == NULL) return;
105        else {
106            showPostOrder(postorder->getLeftChild());
107            showPostOrder(postorder->getRightChild());
108            cout << postorder->getNode() << " ";
109        }
110    }
111    
112    void print_tree(Tree<T> *node) { dump_node(std::cout, node); }
113    
114    AVLTreePrint<T>() : AVLTreeControl<T>() {}
115    
116    virtual ~AVLTreePrint<T>() {}
117};
118
119
120#endif /* avltreeprint_h */
avltree.h
1
2#ifndef avltree_h
3#define avltree_h
4#include "avltreeinsert.h"
5#include "avltreeprint.h"
6using namespace std;
7
8template<typename T> class AVLTree : protected virtual AVLTreeInsert<T>, protected virtual AVLTreePrint<T> {
9protected:
10    Tree<T> *getRoot() { return this->root; }
11    
12public:
13    AVLTree<T>() : AVLTreeInsert<T>() {}
14    
15    virtual ~AVLTree<T>() {}
16    
17    void insertNode(T node) { this->insert(node); }
18    
19    void eraseNode(T node) { this->erase(node); }
20    
21    void printBalance() {
22        this->showBalance(this->root);
23        cout << endl;
24    }
25    
26    void printPreOrder() { this->showPreOrder(this->root); }
27    
28    void printInOrder() { this->showInOrder(this->root); }
29    
30    void printPostOrder() { this->showPostOrder(this->root); }
31    
32    void searchNode(T node) {
33        if (this->search(node) == -1) cout << "No tree";
34        else if (this->search(node) == 0) cout << node << " not found";
35        else cout << node << " found";
36        
37        cout << endl;
38    }
39    
40    string getTreeAsString() { return this->getInOrder(this->root); }
41    
42    void printTree() { this->print_tree(this->root); }
43};
44
45#endif /* avltree_h */
main.cpp
1#include <iostream>
2#include "avltree.h"
3using namespace std;
4
5int main(int argc, char **argv) {
6    AVLTree<int> *avl = new AVLTree<int>();
7    
8    for(int i = 1; i < 16; i++)
9        avl->insertNode(i);
10    
11    cout << "Print in-order:" << endl;
12    avl->printInOrder();
13    
14    //print tree
15    cout << endl << endl;
16    avl->printTree();
17    
18    //delete nodes
19    cout << endl << "erase nodes 6 and 12" << endl;
20    avl->eraseNode(6);
21    avl->eraseNode(12);
22    
23    //print new tree
24    avl->printTree();
25    
26    delete avl;
27    
28    return 0;
29}