HCE project C++ developers source code library  1.1.1
HCE project developer library
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros
AVLTree.h
Go to the documentation of this file.
1 #ifndef AVLTREE_H
2 #define AVLTREE_H
3 #include <sys/types.h>
4 #include <List.h>
5 #include <new>
6 template <class Key, class Data> class AVLTree;
7 
8 template <class Key, class Data>
9 class AVLNode
10 {
11  public:
12  AVLNode(Key key, Data data, int8_t balance = 0, AVLNode *parent = NULL, AVLNode *left = NULL, AVLNode *right = NULL);
13  ~AVLNode();
14  void getTree(List<Data> &list);
19  bool isLeftChild();
20  bool isRightChild();
21  bool LR();
22  bool RR();
23  bool dLR();
24  bool dRR();
26  unsigned int depth();
27  void print();
31  Key key;
32  Data data;
33  int8_t balance;
34  private:
35  AVLNode<Key, Data>* getInsertPosition(Key key);
36  bool resturctureInsert();
37  bool resturctureDelete();
38  friend class AVLTree<Key, Data>;
39 };
40 
41 template <class Key, class Data>
43 {
44  AVLNode<Key, Data> *item = this;
45  while(item->right)item = item->right;
46  return item;
47 }
48 
49 template <class Key, class Data>
51 {
52  AVLNode<Key, Data> *item = this;
53  while(item->left)item = item->left;
54  return item;
55 
56 }
57 
58 template <class Key, class Data>
60 {
61  if(right)
62  {
63  return right->getFirstInOrder();
64  }
65  if(isLeftChild())return parent;
66  AVLNode<Key, Data> *item = this;
67  while(item->parent)
68  {
69  if(item->isRightChild())
70  {
71  item = item->parent;
72  }
73  else
74  {
75  return item->parent;
76  }
77  }
78  return NULL;
79 }
80 
81 template <class Key, class Data>
83 {
84  if(left)
85  {
86  return left->getLastInOrder();
87  }
88  if(isRightChild())return parent;
89  AVLNode<Key, Data> *item = this;
90  while(item->parent)
91  {
92  if(item->isLeftChild())
93  {
94  item = item->parent;
95  }
96  else
97  {
98  return item->parent;
99  }
100  }
101  return NULL;
102 }
103 
104 template <class Key, class Data>
105 void AVLNode<Key, Data>::getTree(List<Data> &list)
106 {
107  if(left)left->getTree(list);
108  list.pushDown(data);
109  if(right)right->getTree(list);
110 }
111 
112 template <class Key, class Data>
114 {
115  //cout<<"this="<<this<<" left="<<left<<" right="<<right<<" parent="<<parent<<" key="<<key<<" balance="<<(int)balance<<"\n";
116  if(left)left->print();
117  if(right)right->print();
118 }
119 template <class Key, class Data>
121 {
122  unsigned int l = 0, r = 0;
123  if(left)l = left->depth();
124  if(right)r = right->depth();
125  return (l>r?l:r) + 1;
126 }
127 
128 template <class Key, class Data>
129 AVLNode<Key, Data>::AVLNode(Key key, Data data, int8_t balance, AVLNode *parent, AVLNode *left, AVLNode *right)
130 {
131  this->key = key;
132  this->data = data;
133  this->balance = balance;
134  this->parent = parent;
135  this->left = left;
136  this->right = right;
137 }
138 
139 template <class Key, class Data>
141 {
142  if(left)delete left;
143  if(right)delete right;
144 }
145 
146 template <class Key, class Data>
148 {
149  AVLNode<Key, Data> *cur = this;
150  while(cur->parent)cur = cur->parent;
151  return cur;
152 }
153 
154 template <class Key, class Data>
156 {
157  if(parent)
158  {
159  return parent->left == this;
160  }
161  return false;
162 }
163 
164 template <class Key, class Data>
166 {
167  if(parent)
168  {
169  return parent->right == this;
170  }
171  return false;
172 }
173 
174 template <class Key, class Data>
176 {
177  AVLNode<Key, Data> *cur = this;
178  while(cur)
179  {
180  if(key < cur->key)
181  {
182  if(!cur->left)return cur;
183  cur = cur->left;
184  }
185  else
186  {
187  if(key > cur->key)
188  {
189  if(!cur->right)return cur;
190  cur = cur->right;
191  }
192  else
193  {
194  return NULL;
195  }
196  }
197  }
198  return NULL;
199 }
200 
201 template <class Key, class Data>
203 {
204  if(!right)return false;
205  AVLNode<Key, Data>* b = right;
206  if(parent)
207  {
208  if(isLeftChild())
209  parent->left = b;
210  else
211  parent->right = b;
212  b->parent = parent;
213  }
214  else
215  {
216  b->parent = NULL;
217  }
218  right = b->left;
219  b->left = this;
220  parent = b;
221  if(right != NULL)right->parent = this;
222  if(b->balance == 0)
223  {
224  balance = 1;
225  b->balance = -1;
226  }
227  else
228  {
229  balance = 0;
230  b->balance = 0;
231  }
232  return true;
233 }
234 
235 template <class Key, class Data>
237 {
238  if(left == NULL)return false;
239  AVLNode<Key, Data>* b = left;
240  if (parent)
241  {
242  if (isLeftChild())
243  parent->left = b;
244  else
245  parent->right = b;
246  b->parent = parent;
247  }
248  else
249  {
250  b->parent = NULL;
251  }
252  left = b->right;
253  b->right = this;
254  parent = b;
255  if(left != NULL)left->parent = this;
256  if(b->balance == 0)
257  {
258  balance = -1;
259  b->balance = 1;
260  }
261  else
262  {
263  balance = 0;
264  b->balance = 0;
265  }
266  return true;
267 }
268 
269 template <class Key, class Data>
271 {
272  if(left == NULL || left->right == NULL) return false;
273  AVLNode<Key, Data>* b = left;
274  AVLNode<Key, Data>* c = left->right;
275  if (parent)
276  {
277  if(isLeftChild())
278  parent->left = c;
279  else
280  parent->right = c;
281  }
282  b->right = c->left;
283  left = c->right;
284  c->left = b;
285  c->right = this;
286  c->parent = parent;
287  parent = c;
288  b->parent = c;
289  if (b->right != NULL) b->right->parent = b;
290  if (left != NULL) left->parent = this;
291  switch (c->balance)
292  {
293  case -1:
294  balance = 1;
295  b->balance = 0;
296  break;
297  case 0:
298  balance = 0;
299  b->balance = 0;
300  break;
301  case 1:
302  balance = 0;
303  b->balance = -1;
304  break;
305  }
306  c->balance = 0;
307  return true;
308 }
309 
310 template <class Key, class Data>
312 {
313  if(right == NULL || right->left == NULL)return false;
314  AVLNode<Key, Data>* b = right;
315  AVLNode<Key, Data>* c = right->left;
316  if(parent)
317  {
318  if(isLeftChild())
319  parent->left = c;
320  else
321  parent->right = c;
322  }
323  right = c->left;
324  b->left = c->right;
325  c->left = this;
326  c->right = b;
327  c->parent = parent;
328  parent = c;
329  b->parent = c;
330  if (right != NULL) right->parent = this;
331  if (b->left != NULL) b->left->parent = b;
332  switch (c->balance)
333  {
334  case -1:
335  balance = 0;
336  b->balance = 1;
337  break;
338  case 0:
339  balance = 0;
340  b->balance = 0;
341  break;
342  case 1:
343  balance = -1;
344  b->balance = 0;
345  break;
346  }
347  c->balance = 0;
348  return true;
349 }
350 
351 template <class Key, class Data>
353 {
354  AVLNode<Key, Data>* item = this;
355  while(item->parent)
356  {
357  if(item->isLeftChild() && item->parent->balance == 0)
358  {
359  item->parent->balance = -1;
360  item = item->parent;
361  continue;
362  }
363  if(item->isRightChild() && item->parent->balance == 0)
364  {
365  item->parent->balance = 1;
366  item = item->parent;
367  continue;
368  }
369  if(item->isLeftChild() && item->parent->balance == 1)
370  {
371  item->parent->balance = 0;
372  break;
373  }
374  if(item->isRightChild() && item->parent->balance == -1)
375  {
376  item->parent->balance = 0;
377  break;
378  }
379  if(item->isLeftChild() && item->parent->balance == -1)
380  {
381  if(item->balance == 1)
382  item->parent->dLR();
383  else
384  item->parent->RR();
385  break;
386  }
387  if(item->isRightChild() && item->parent->balance == 1)
388  {
389  if(item->balance == -1)
390  item->parent->dRR();
391  else
392  item->parent->LR();
393  break;
394  }
395  }
396  return true;
397 }
398 
399 template <class Key, class Data>
401 {
402  AVLNode<Key, Data>* item = this;
403  if(item->balance == 0 && item->left == NULL)
404  {
405  item->balance = 1;
406  return true;
407  }
408  if(item->balance == 0 && item->right == NULL)
409  {
410  item->balance = -1;
411  return true;
412  }
413  if(item->balance == -1 && item->left == NULL)
414  {
415  item->balance = 0;
416  }
417  if(item->balance == 1 && item->right == NULL)
418  {
419  item->balance = 0;
420  }
421  if(item->balance == -1 && item->right == NULL)
422  {
423  if(item->left->balance == 1)
424  {
425  item->dLR();
426  item = item->parent;
427  }
428  else
429  {
430  item->RR();
431  item = item->parent;
432  }
433  if(item->balance == 1)
434  return true;
435  }
436  if(item->balance == 1 && item->left == NULL)
437  {
438  if(item->right->balance == -1)
439  {
440  item->dRR();
441  item = item->parent;
442  }
443  else
444  {
445  item->LR();
446  item = item->parent;
447  }
448  if(item->balance == -1)
449  return true;
450  }
451  while(item->parent)
452  {
453  if(item->isLeftChild() && item->parent->balance == 0)
454  {
455  item->parent->balance = 1;
456  break;
457  }
458  if(item->isRightChild() && item->parent->balance == 0)
459  {
460  item->parent->balance = -1;
461  break;
462  }
463  if(item->isLeftChild() && item->parent->balance == -1)
464  {
465  item->parent->balance = 0;
466  item = item->parent;
467  continue;
468  }
469  if(item->isRightChild() && item->parent->balance == 1)
470  {
471  item->parent->balance = 0;
472  item = item->parent;
473  continue;
474  }
475  if(item->isRightChild() && item->parent->balance == -1)
476  {
477  if(item->parent->left->balance == 1)
478  {
479  item->parent->dLR();
480  item = item->parent->parent;
481  }
482  else
483  {
484  item->parent->RR();
485  item = item->parent->parent;
486  }
487  if(item->balance == 1)
488  return true;
489  continue;
490  }
491  if(item->isLeftChild() && item->parent->balance == 1)
492  {
493  if(item->parent->right->balance == -1)
494  {
495  item->parent->dRR();
496  item = item->parent->parent;
497  }
498  else
499  {
500  item->parent->LR();
501  item = item->parent->parent;
502  }
503  if(item->balance == -1)
504  return true;
505  continue;
506  }
507  break;
508  }
509  return true;
510 }
511 
512 template <class Key, class Data>
513 class AVLTree
514 {
515  public:
516  AVLTree();
517  ~AVLTree();
518  void add(Key key, Data);
519  AVLNode<Key, Data>* find(Key key);
520  bool del(Key key);
521  AVLNode<Key, Data>* getRoot(){return root;}
522  void zerroRoot(){root = NULL; nodeCount = 0;}
523  void clear();
524  unsigned long getNodesCount(){return nodeCount;}
525  void setTree(const AVLTree<Key, Data> &tree){nodeCount = tree.nodeCount; root = tree.root;}
526  private:
527  AVLNode<Key, Data> *root;
528  unsigned long nodeCount;
529 };
530 
531 template <class Key, class Data>
533 {
534  if(root)delete root;
535  root = NULL;
536  nodeCount = 0;
537 }
538 
539 template <class Key, class Data>
541 {
542  root = NULL;
543  nodeCount = 0;
544 }
545 
546 template <class Key, class Data>
548 {
549  if(root)delete root;
550 }
551 
552 template <class Key, class Data>
553 void AVLTree<Key, Data>::add(Key key, Data data)
554 {
555  if(__builtin_expect(root!=NULL, 1))
556  {
557  AVLNode<Key, Data> *item = root->getInsertPosition(key);
558  if(__builtin_expect(item != NULL, 1))
559  {
560  AVLNode<Key, Data> *newItem = new(std::nothrow) AVLNode<Key, Data>(key, data, 0, item);
561  if(__builtin_expect(newItem != NULL, 1))
562  {
563  if(key < item->key)
564  {
565  item->left = newItem;
566  }
567  else
568  {
569  item->right = newItem;
570  }
571  newItem->resturctureInsert();
572  root = root->getRoot();
573  nodeCount++;
574  }
575  }
576  }
577  else
578  {
579  root = new(std::nothrow) AVLNode<Key, Data>(key, data);
580  nodeCount++;
581  return;
582  }
583 }
584 
585 template <class Key, class Data>
587 {
588  AVLNode<Key, Data> *cur = root;
589  while(cur)
590  {
591  if(cur->key == key)return cur;
592  cur = key < cur->key ? cur->left : cur->right;
593  }
594  return NULL;
595 }
596 
597 template <class Key, class Data>
599 {
600  if(!root) return false;
601  AVLNode<Key, Data>* item = find(key);
602  if(item == NULL) return false;
603  if(item == root)
604  {
605  if(item->left == NULL && item->right == NULL)
606  {
607  delete root;
608  root = NULL;
609  nodeCount--;
610  return true;
611  }
612  }
613  AVLNode<Key, Data>* startitem = NULL;
614  if(item->left == NULL && item->right == NULL)
615  {
616  if(item->isLeftChild())
617  item->parent->left = NULL;
618  else
619  item->parent->right = NULL;
620  startitem = item->parent;
621  delete item;
622  item = NULL;
623  }
624  if(item != NULL && item->left == NULL && item->right != NULL)
625  {
626  item->data = item->right->data;
627  item->key = item->right->key;
628  delete item->right;
629  item->right = NULL;
630  startitem = item;
631  }
632  if(item != NULL && item->left != NULL && item->right == NULL)
633  {
634  item->data = item->left->data;
635  item->key = item->left->key;
636  delete item->left;
637  item->left = NULL;
638  startitem = item;
639  }
640  if(item != NULL && item->left != NULL && item->right != NULL)
641  {
642  AVLNode<Key, Data>* y = item->left;
643  while(y->right)y = y->right;
644  AVLNode<Key, Data>* z = y->left;
645  item->data = y->data;
646  item->key = y->key;
647  if(z != NULL)
648  {
649  y->data = z->data;
650  y->key = z->key;
651  y->left = NULL;
652  delete z;
653  startitem = y;
654  }
655  else
656  {
657  if(y->isLeftChild())
658  y->parent->left = NULL;
659  else
660  y->parent->right = NULL;
661  startitem = y->parent;
662  delete y;
663  }
664  }
665  startitem->resturctureDelete();
666  while(root->parent)root = root->parent;
667  nodeCount--;
668  return true;
669 }
670 #endif