Through left or right rotation of nodes are balanced the AVL tree.
1 | #ifndef avltreecontrol_h
|
2 | #define avltreecontrol_h
|
3 | #include <string>
|
4 | #include <queue>
|
5 | #include "avltreeroot.h"
|
6 | using namespace std;
|
7 |
|
8 | template<typename T> class AVLTreeControl : protected virtual AVLTreeRoot<T> {
|
9 | protected:
|
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 */
|
1 | #ifndef avltreeprint_h
|
2 | #define avltreeprint_h
|
3 | #include <iostream>
|
4 | #include <sstream>
|
5 | #include <iomanip>
|
6 | #include <string>
|
7 | #include "avltreecontrol.h"
|
8 | using namespace std;
|
9 |
|
10 | template<typename T> class AVLTreePrint : protected virtual AVLTreeControl<T> {
|
11 | private:
|
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 |     
|
76 | protected:
|
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 */
|