COVISE Core
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Properties Friends Macros
covise_avl_tree.h
Go to the documentation of this file.
1 /* This file is part of COVISE.
2 
3  You can use it under the terms of the GNU Lesser General Public License
4  version 2.1 or later, see lgpl-2.1.txt.
5 
6  * License: LGPL 2+ */
7 
8 #ifndef EC_NEW_AVL_TREE_H
9 #define EC_NEW_AVL_TREE_H
10 
11 //*****************************************************************//
12 // search for a special value in a binary tree. return value is
13 // if search==-2: the biggest node with value < data,
14 // if search==+2: the smallest node with value > data,
15 // if search==-1: the biggest node with value <= data,
16 // if search==+1: the smallest node with value >= data,
17 // if search== 0: the node with value == data,
18 // or NULL, if the condition cannot be satisfied.
19 //*****************************************************************//
20 
21 #include <covise/covise.h>
22 
23 #ifdef __GNUC__
24 #define COVISE_GREATER_THAN 2
25 #define COVISE_GT_EQUAL 1
26 #define COVISE_EQUAL 0
27 #define COVISE_LS_EQUAL -1
28 #define COVISE_LESS_THAN -2
29 #else
30 const int COVISE_GREATER_THAN = 2;
31 const int COVISE_GT_EQUAL = 1;
32 const int COVISE_EQUAL = 0;
33 const int COVISE_LS_EQUAL = -1;
34 const int COVISE_LESS_THAN = -2;
35 #endif
36 
37 namespace covise
38 {
39 
40 int covise_std_compare(char *, char *); // default comparison function
41 
42 template <class T>
43 class AVLTree;
44 
45 template <class T>
46 class CO_AVL_Node /* structure for AVL-trees */
47 {
48  friend class CO_AVL_Tree;
49 
50 public:
51  CO_AVL_Node<T> *left; /* pointer to left subtree */
52  CO_AVL_Node<T> *right; /* pointer to right subtree */
53  CO_AVL_Node<T> *up; /* pointer to father node */
54  int balance; /* balance of subtrees =h(R)-h(L), normally -1..1 */
55  T *data; /* data the tree is sorted by */
57  {
58  data = d;
59  left = 0L;
60  right = 0L;
61  up = 0L;
62  balance = 0;
63  };
65  {
66  data = 0L;
67  };
68 
69  void print()
70  {
71  if (left)
72  left->print();
73  if (data)
74  data->print();
75  if (right)
76  right->print();
77  };
78  void remove_nod(void)
79  {
80  if (left)
81  {
82  left->remove_nod();
83  delete left;
84  }
85  if (right)
86  {
87  right->remove_nod();
88  delete right;
89  }
90  if (data)
91  delete data;
92  }
93 #if defined(__hpux) || defined(_SX)
95 #else
97  {
98  CO_AVL_Node<T> *retval = 0L;
99 
100  if (d == data)
101  return this;
102  if (left)
103  {
104  retval = left->search_identical_node(d);
105  if (retval)
106  return retval;
107  }
108  if (right)
109  {
110  retval = right->search_identical_node(d);
111  }
112  return retval;
113  };
114 #endif
115 };
116 
117 template <class T>
118 class AVLTree
119 {
120 private:
121  int (*compare)(T *a, T *b); // compare function
123  CO_AVL_Node<T> *best_node; /* after a search the found node can be found here */
124  const char *name;
125  int count; /* (number of elements in tree) */
126 public:
128  {
129  root = 0L;
130  compare = (int (*)(T *, T *))covise_std_compare;
131  count = 0; // standard initialization
132  };
133  AVLTree(int (*comp)(T *a, T *b))
134  {
135  root = 0L;
136  compare = comp;
137  name = "dummy";
138  count = 0;
139  };
140  // initialization with special comp. function
141  AVLTree(int (*comp)(T *a, T *b), const char *n)
142  {
143  root = 0L;
144  compare = comp;
145  name = n;
146  count = 0;
147  };
148  // initialization with special comp. function
150  {
151  if (name)
152  delete name;
153  };
154 
156  {
157  return root;
158  };
159 
160  void empty_tree(void)
161  {
162  if (root)
163  {
164  root->remove_nod();
165  delete root;
166  root = NULL;
167  }
168  count = 0;
169  };
170  T *search_node(T *data, int search);
171  void rebalance_tree(CO_AVL_Node<T> *tree_node, int add_balance,
172  int grow_shrink);
173  int insert_node(T *data);
174  T *remove_node(T *data);
175  T *remove_node_compare(T *data);
177  void print(char *);
178  void show_tree(CO_AVL_Node<T> *curr_node);
179 };
180 
181 template <class T>
183 {
184  CO_AVL_Node<T> *retval = 0L;
185 
186  if (start == 0L)
187  return 0L;
188 
189  if (start->data == d)
190  return start;
191  if (start->left)
192  {
193  if (compare((T *)start->left->data, d) < 0)
194  {
195  retval = search_identical_node(d, start->left->right);
196  if (retval)
197  return retval;
198  }
199  else
200  {
201  retval = search_identical_node(d, start->left);
202  if (retval)
203  return retval;
204  }
205  }
206  if (start->right)
207  {
208  if (compare((T *)start->right->data, d) > 0)
209  {
210  retval = search_identical_node(d, start->right->left);
211  if (retval)
212  return retval;
213  }
214  else
215  {
216  retval = search_identical_node(d, start->right);
217  if (retval)
218  return retval;
219  }
220  }
221  return 0L;
222 };
223 
224 /*--------------------------------------------------------------------------*\
225  ** **
226  ** AVL Tree Handling Version: 1.3 **
227  ** **
228  ** Description : search for a node in an AVL tree, **
229  ** insertion of a node into an AVL tree, and **
230  ** removal of a node from an AVL tree; **
231  ** both do rebalancing of the tree **
232  ** **
233  ** Call : **
234  ** void insert_node(tree,new_node) **
235  ** struct NODE **tree, *new_node; **
236  ** **
237  ** void remove_node(tree,old_node) **
238  ** struct NODE **tree, *old_node; **
239  ** **
240  ** struct NODE *search_node(tree,data,search) **
241  ** struct NODE **tree; **
242  ** char *data; **
243  ** int search; **
244  ** **
245  ** Parameters : tree: pointer to tree root pointer **
246  ** new_node: node to insert into tree **
247  ** old_node: node to remove from tree **
248  ** search: indicate what node to search for: **
249  ** -1==LESS_EQUAL, 0==COVISE_EQUAL, 1==COVISE_GT_EQUAL **
250  ** data: data to search for **
251  ** **
252  ** Result : insert_node inserts a node into the tree, **
253  ** remove_node removes a node from the tree, **
254  ** search_node searches for a node in the tree, where **
255  ** NULL is returned if no node is found that meets the **
256  ** search criteria; otherwise a pointer to the node. **
257  ** for COVISE_EQUAL search, the data must match exactly, **
258  ** for LESS_EQUAL search, the node with largest data **
259  ** less or equal to search-data is returned, and **
260  ** for COVISE_GT_EQUAL, the node with smallest data greater **
261  ** or equal to the search-data. **
262  ** **
263 \*--------------------------------------------------------------------------*/
264 
265 /* ERR_NODE definieren, wenn bei einem speziellen Knoten im Baum Fehler */
266 #define ERR_NODE 0x100403AC
267 #undef ERR_NODE
268 
269 #undef DEBUG
270 #undef debug
271 #ifndef NULL
272 #define NULL 0L
273 #endif
274 
275 //static const int GROW = 1;
276 //static const int SHRINK = -1;
277 
278 //static int covise_n_node=0;
279 //static int covise_depth=0;
280 
281 #if defined(__hpux) || defined(_SX)
282 template <class T>
283 CO_AVL_Node<T> *CO_AVL_Node<T>::search_identical_node(T *d)
284 {
285  CO_AVL_Node<T> *retval = 0L;
286 
287  if (d == data)
288  return this;
289  if (left)
290  {
291  retval = left->search_identical_node(d);
292  if (retval)
293  return retval;
294  }
295  if (right)
296  {
297  retval = right->search_identical_node(d);
298  }
299  return retval;
300 }
301 #endif
302 template <class T>
303 T *AVLTree<T>::search_node(T *data, int search)
304 {
305 #ifdef DEBUG
306  char tmp_str[255];
307 
308  sprintf(tmp_str, "AVLTree<T>::search_node, mode %d", search);
309  print(tmp_str);
310  print_comment(__LINE__, __FILE__, "searching node:");
311  data->print();
312 #endif
313 
314  CO_AVL_Node<T> *node;
316  T *best_data;
317 
318  if (root == NULL)
319  return (NULL);
320 
321 #ifdef DEBUG
322  print_comment(__LINE__, __FILE__, "root != NULL");
323 #endif
324 
326  node = root; /* we start searching at the tree's root */
327 
328  best_data = 0L;
329  best_node = 0L;
330  /* search for "<=" or "<" */
331  if (search == COVISE_LS_EQUAL || search == COVISE_LESS_THAN)
332  {
333  while (node)
334  {
335  if (compare((T *)node->data, data) <= 0)
336  {
337  if (best_data == 0L)
338  {
339  best_data = node->data;
340  best_node = node;
341  }
342  if (compare((T *)node->data, best_data) >= 0)
343  {
344  best_data = node->data;
345  best_node = node;
346  if ((search == COVISE_LS_EQUAL) && (compare((T *)best_data, data) == 0))
347  break;
348  }
349  node = node->right;
350  }
351  else
352  {
353  node = node->left;
354  }
355  }
356  }
357  /* search for ">=" or ">" */
358  else if (search == COVISE_GT_EQUAL || search == COVISE_GREATER_THAN)
359  {
360  while (node)
361  {
362  if (compare((T *)node->data, data) >= 0)
363  {
364  if (best_data == 0L)
365  {
366  best_data = node->data;
367  best_node = node;
368  }
369  if (compare((T *)node->data, best_data) <= 0)
370  {
371  best_data = node->data;
372  best_node = node;
373  if ((search == COVISE_GT_EQUAL) && (compare((T *)best_data, data) == 0))
374  break;
375  }
376  node = node->left;
377  }
378  else
379  {
380  node = node->right;
381  }
382  }
383  }
384  else if (search == COVISE_EQUAL) /* search for "==" */
385  {
386  while (node)
387  {
388  int cmp = compare((T *)node->data, data);
389  if (cmp >= 0)
390  {
391  if (cmp == 0)
392  {
393  best_data = node->data;
394  best_node = node;
395  break;
396  }
397  node = node->left;
398  }
399  else
400  {
401  node = node->right;
402  }
403  }
404  }
405  else /* wrong parameter for search */
406  {
407  printf("Sorry, wrong parameter for search\n");
408  return 0L;
409  }
410 /* now, best_data contains the return value. */
411 /* and best_node the corresponding node */
412 #ifdef DEBUG
413  print_comment(__LINE__, __FILE__, "found node:");
414  if (best_data)
415  best_data->print();
416  else
417  print_comment(__LINE__, __FILE__, "found nothing");
418 #endif
419  return (best_data);
420 } /* end search_node */
421 
422 /**********************************************************************/
423 
424 /* rebalance an AVL-tree */
425 
426 #define GROW 1
427 #define SHRINK -1
428 
429 template <class T>
431  int add_balance,
432  int grow_shrink)
433 {
434  CO_AVL_Node<T> *node, *father, *Left, *Right, *Left_right, *Right_left;
435  int add_b, bal;
436 
437 #ifdef DEBUG
438  print_comment(__LINE__, __FILE__, "AVLTree<T>::rebalance_tree");
439 #endif
440 #ifdef debug
441  if (grow_shrink == GROW)
442  {
443  fprintf(stdout, "\n rebalance_growing_tree(%8x,%8x,%d):",
444  this, tree_node, add_balance);
445  }
446  else
447  {
448  fprintf(stdout, "\n rebalance_shrinking_tree(%8x,%8x,%d):",
449  this, tree_node, add_balance);
450  if ((int *)this == (int *)0x10032c88 && (int *)tree_node == (int *)0x100b4858)
451  int i = 0;
452  }
453 #endif
454 
455  if (tree_node == NULL)
456  return; /* nothing to do ???? */
457 
458  node = tree_node;
459  add_b = add_balance;
460  while (node)
461  {
462 #ifdef ERR_NODE
463  if (node == ERR_NODE)
464  {
465  printf("[node=%x, data=%x]", node, node->data);
466  }
467 #endif
468 #ifdef debug
469  fprintf(stdout, " (node=%x,add_b=%d)", node, add_b);
470 #endif
471  bal = (node->balance += add_b);
472  if (((bal == 0) && (grow_shrink == GROW))
473  /* balance o.k. */
474  || ((bal == add_b) && (grow_shrink == SHRINK)))
475  {
476  break;
477  }
478  if (((bal != add_b) && (grow_shrink == GROW))
479  || ((bal != 0) && (grow_shrink == SHRINK))) /* must rotate */
480  {
481  Left = node->left;
482  Right = node->right;
483  if (add_b == -1) /* left subtree has grown */
484  {
485 #ifdef debug
486  if (Left == NULL)
487  {
488  printf("Left==NULL \n");
489  print("Left==NULL");
490  exit(0);
491  }
492 #endif
493  if ((Left->balance == -1) || (Left->balance == 0))
494  {
495  /* R-ROTATE */
496  /*****************************************\
497  * F F *
498  * | | *
499  * node ==> L *
500  * / \ / \ *
501  * L R LL node *
502  * / \ / \ *
503  * LL LR LR R *
504  \*****************************************/
505  father = node->up;
506  if (father)
507  {
508  if (father->left == node)
509  {
510  father->left = Left;
511  }
512  else
513  {
514  father->right = Left;
515  }
516  }
517  else /* it's the root */
518  {
519  root = Left;
520  }
521  (Left->up) = (node->up);
522  (node->left) = (Left->right);
523  if (Left->right)
524  {
525  (Left->right)->up = node;
526  }
527  Left->right = node;
528  node->up = Left;
529 
530  if (Left->balance == 0)
531  {
532  node->balance = -1; /* new balances */
533  Left->balance = 1;
534  break; /* tree is balanced now! */
535  }
536  else /* Left->balance == -1 */
537  {
538  node->balance = 0; /* new balances */
539  Left->balance = 0;
540  }
541 
542  node = Left;
543  }
544  else /* Left->balance == +1 */
545  {
546  /* LR-ROTATE */
547  /*********************************************************\
548  * F F F *
549  * | | | *
550  * node node LR *
551  * / \ ==> / \ ==> / \ *
552  * L R LR R L node *
553  * / \ / \ / \ / \ *
554  * LL LR L LRR LL LRL LRR R *
555  * / \ / \ *
556  * LRL LRR LL LRL *
557  \*********************************************************/
558  Left_right = Left->right;
559 #ifdef debug
560  if (Left_right == NULL)
561  {
562  printf("Left_right==NULL \n");
563  print("Left_right==NULL");
564  exit(0);
565  }
566 #endif
567  father = node->up;
568  if (father)
569  {
570  if (father->left == node)
571  {
572  father->left = Left_right;
573  }
574  else
575  {
576  father->right = Left_right;
577  }
578  }
579  else /* root */
580  {
581  root = Left_right;
582  }
583 
584  Left_right->up = father;
585  (Left->right) = (Left_right->left);
586  if (Left_right->left)
587  {
588  (Left_right->left)->up = Left;
589  }
590  Left_right->left = Left;
591  Left->up = Left_right;
592  (node->left) = (Left_right->right);
593  if (Left_right->right)
594  {
595  (Left_right->right)->up = node;
596  }
597  Left_right->right = node;
598  node->up = Left_right;
599 
600  if (Left_right->balance == -1)
601  node->balance = 1;
602  else
603  node->balance = 0;
604  if (Left_right->balance == 1)
605  Left->balance = -1;
606  else
607  Left->balance = 0;
608  Left_right->balance = 0;
609 
610  node = Left_right;
611  }
612  }
613  else /* right subtree has grown */
614  {
615 #ifdef debug
616  if (Right == NULL)
617  {
618  printf("Right==NULL \n");
619  print("Right==NULL");
620  exit(0);
621  }
622 #endif
623  if ((Right->balance == 1) || (Right->balance == 0))
624  {
625  /* L-ROTATE */
626  /*****************************************\
627  * F F *
628  * | | *
629  * node ==> R *
630  * / \ / \ *
631  * L R node RR *
632  * / \ / \ *
633  * RL RR L RL *
634  \*****************************************/
635  father = node->up;
636  if (father)
637  {
638  if (father->left == node)
639  {
640  father->left = Right;
641  }
642  else
643  {
644  father->right = Right;
645  }
646  }
647  else /* root */
648  {
649  root = Right;
650  }
651  (Right->up) = (node->up);
652  (node->right) = (Right->left);
653  if (Right->left)
654  {
655  (Right->left)->up = node;
656  }
657  Right->left = node;
658  node->up = Right;
659 
660  if (Right->balance == 0)
661  {
662  node->balance = 1;
663  Right->balance = -1;
664  break; /* tree height didn't change. */
665  }
666  else
667  {
668  node->balance = 0;
669  Right->balance = 0;
670  }
671 
672  node = Right;
673  }
674  else
675  {
676  /* RL-ROTATE */
677  /*********************************************************\
678  * F F F *
679  * | | | *
680  * node node RL *
681  * / \ ==> / \ ==> / \ *
682  * L R L RL node R *
683  * / \ / \ / \ / \ *
684  * RL RR RLL R L RLL RLR RR *
685  * / \ / \ *
686  * RLL RLR RLR RR *
687  \*********************************************************/
688  Right_left = Right->left;
689 #ifdef debug
690  if (Right_left == NULL)
691  {
692  printf("Right_left==NULL \n");
693  print("Right_left==NULL");
694  exit(0);
695  }
696 #endif
697  father = node->up;
698  if (father)
699  {
700  if (father->left == node)
701  {
702  father->left = Right_left;
703  }
704  else
705  {
706  father->right = Right_left;
707  }
708  }
709  else /* root */
710  {
711  root = Right_left;
712  }
713  Right_left->up = father;
714  (Right->left) = (Right_left->right);
715  if (Right_left->right)
716  {
717  (Right_left->right)->up = Right;
718  }
719  Right_left->right = Right;
720  Right->up = Right_left;
721  (node->right) = (Right_left->left);
722  if (Right_left->left)
723  {
724  (Right_left->left)->up = node;
725  }
726  Right_left->left = node;
727  node->up = Right_left;
728 
729  if (Right_left->balance == -1)
730  Right->balance = 1;
731  else
732  Right->balance = 0;
733  if (Right_left->balance == 1)
734  node->balance = -1;
735  else
736  node->balance = 0;
737  Right_left->balance = 0;
738 
739  node = Right_left;
740  }
741  }
742 
743  if (grow_shrink == GROW) /* tree is balanced now */
744  {
745  break;
746  }
747  }
748  else
749  {
750  /* no rotation here, go up in tree */
751  }
752 
753  father = node->up;
754  if (father)
755  {
756  if ((father->left) == node)
757  {
758  add_b = -grow_shrink; /* left subtree of father is changing */
759  }
760  else
761  {
762  add_b = grow_shrink; /* right subtree of father changes */
763  }
764  }
765  node = father;
766  }
767 
768 } /* end rebalance_tree */
769 
770 /**********************************************************************/
771 
772 /* insert a node into an AVL-tree, including re-balancing of the tree */
773 
774 template <class T>
776 {
777  CO_AVL_Node<T> *new_node, *node, *father;
778  T *new_data;
779  int add_balance;
780 #ifdef DEBUG
781  char tmp_str[255];
782 #endif
783 
784  if (data == 0L)
785  return 0;
786 
787 // count++;
788 
789 #ifdef DEBUG
790  print("AVLTree<T>::insert_node, before");
791  print_comment(__LINE__, __FILE__, "inserting node:");
792  data->print();
793 #endif
794 
795  new_node = new CO_AVL_Node<T>(data);
796 
797  if (root == 0L) /* empty tree */
798  {
799  root = new_node;
800 #ifdef DEBUG
801  print("tree after:");
802 #endif
803 
804  return 1;
805  }
806 
807  new_data = new_node->data;
808  node = root; /* we start with the root */
809  while (node)
810  {
811  father = node;
812  if (compare(node->data, new_data) >= 0)
813  {
814  node = node->left;
815  }
816  else
817  {
818  node = node->right;
819  }
820  }
821 
822  /* now, the new node can be inserted as a son of father */
823 
824  new_node->up = father;
825  if (compare(father->data, new_data) >= 0)
826  {
827  father->left = new_node;
828  add_balance = -1;
829  }
830  else
831  {
832  father->right = new_node;
833  add_balance = 1;
834  }
835 
836  /* rebalance_growing_tree( tree, father, add_balance );*/
837  rebalance_tree(father, add_balance, GROW);
838 
839 #ifdef DEBUG
840  print("tree after:");
841 #endif
842 
843  return 1;
844 } /* end insert_node */
845 
846 /**********************************************************************/
847 
848 /* remove a node from an AVL-tree, including re-balancing of the tree */
849 /* compare objects */
850 
851 template <class T>
853 {
854  CO_AVL_Node<T> *node, *old_node, *father;
855  T *ret_data;
856  int add_balance = 0;
857 #ifdef DEBUG
858  char tmp_str[255];
859 #endif
860 
861  if (data == NULL)
862  return 0;
863 
864 // count--;
865 
866 #ifdef DEBUG
867  print("AVLTree<T>::remove_node_compare, before");
868  data->print();
869 #endif
870 
871  if (search_node(data, COVISE_EQUAL))
872  old_node = best_node; // side effect of search_node()!!
873  else
874  {
875  print_comment(__LINE__, __FILE__, "node not found for removal");
876  return 0L;
877  }
878 
879  node = old_node;
880  ret_data = node->data;
881 #ifdef ERR_NODE
882  if (node == ERR_NODE)
883  {
884  printf("[node=%x, data=%x]", node, node->data);
885  }
886 #endif
887  if (node->left == NULL) /* replace node by the right subtree */
888  {
889 #ifdef debug
890  fprintf(stdout, " case 1");
891 #endif
892  /* F *\
893  * | F *
894  * N ==> | *
895  * \ R *
896  \* R */
897  father = node->up;
898  if (father)
899  {
900  // !(father->left) || in the following line inserted A.W. 15.03.96
901  // if (!(father->left) || compare(father->left->data, node->data) == 0) {
902  if (father->left == node)
903  {
904 #ifdef debug
905  fprintf(stdout, ".1");
906 #endif
907  (father->left) = (node->right);
908  add_balance = 1;
909  }
910  else
911  {
912 #ifdef debug
913  fprintf(stdout, ".2");
914 #endif
915  (father->right) = (node->right);
916  add_balance = -1;
917  }
918  }
919  else /* root */
920  {
921 #ifdef debug
922  fprintf(stdout, ".3");
923 #endif
924  root = (node->right);
925  }
926  if (node->right)
927  (node->right)->up = father;
928  // untested!!!
929  delete node;
930  }
931  else if (node->right == 0L) /* replace node by left subtree */
932  {
933 #ifdef debug
934  fprintf(stdout, " case 2");
935 #endif
936  /* F *\
937  * | F *
938  * N ==> | *
939  * / L *
940  \* L */
941  father = node->up;
942  if (father)
943  {
944  // if (compare(father->left->data, node->data) == 0) {
945  if (father->left == node)
946  {
947  (father->left) = (node->left);
948  add_balance = 1;
949  }
950  else
951  {
952  (father->right) = (node->left);
953  add_balance = -1;
954  }
955  }
956  else /* root */
957  {
958  root = (node->left);
959  }
960  if (node->left)
961  (node->left)->up = father;
962  // untested!!!
963  delete node;
964  }
965  else /* must search downward for a node to remove */
966  {
967  /* F F *\
968  * | | *
969  * N Y *
970  * / \ ==> / \ *
971  * V W V W *
972  * / \ / \ *
973  * X Y X Z *
974  * / *
975  \* Z */
976  if (node->balance < 1) /* left subtree of node is higher than right */
977  {
978 #ifdef debug
979  fprintf(stdout, " case 3");
980 #endif
981  node = (node->left); /* search for largest node in left subtree */
982  while (node->right)
983  {
984  node = (node->right);
985 #ifdef ERR_NODE
986  if (node == ERR_NODE)
987  {
988  printf("[node=%x, data=%x]", node, node->data);
989  }
990 #endif
991  }
992 
993  father = (node->up); /* node durch linken subtree ersetzen */
994 
995 #ifdef debug
996  if (father == NULL)
997  {
998  printf("\n father==NULL; tree=%8x; node=%8x : \n", root, node);
999  print("father==NULL");
1000  exit(0);
1001  }
1002 #endif
1003 
1004  if (father->right == node)
1005  {
1006  (father->right) = (node->left);
1007  add_balance = -1;
1008  }
1009  else
1010  {
1011  (father->left) = (node->left);
1012  add_balance = 1;
1013  }
1014  if (node->left)
1015  (node->left)->up = father;
1016  }
1017  else /* right subtree of node is higher than left */
1018  {
1019 #ifdef debug
1020  fprintf(stdout, " case 4");
1021 #endif
1022  node = (node->right); /* search for smallest node in right subtree */
1023  while (node->left)
1024  {
1025  node = (node->left);
1026  }
1027 
1028  father = (node->up); /* node durch rechten subtree ersetzen */
1029  // if (compare(father->right->data, node->data) == 0) {
1030  if (father->right == node)
1031  {
1032  (father->right) = (node->right);
1033  add_balance = -1;
1034  }
1035  else
1036  {
1037  (father->left) = (node->right);
1038  add_balance = 1;
1039  }
1040  if (node->right)
1041  (node->right)->up = father;
1042  }
1043 
1044  /* old_node durch node ersetzen */
1045  if (old_node->up)
1046  {
1047  // if (compare((old_node->up)->left->data, old_node->data) == 0)
1048  if ((old_node->up)->left == old_node)
1049  (old_node->up)->left = node;
1050  else
1051  (old_node->up)->right = node;
1052  (node->up) = (old_node->up);
1053  }
1054  else /* root */
1055  {
1056  root = node;
1057  node->up = NULL;
1058  }
1059  node->left = old_node->left;
1060  if (node->left)
1061  (node->left)->up = node;
1062  node->right = old_node->right;
1063  if (node->right)
1064  (node->right)->up = node;
1065  (node->balance) = (old_node->balance);
1066  if (father == old_node)
1067  father = node;
1068  // untested!!!
1069  delete old_node;
1070  }
1071 
1072  /* rebalance_shrinking_tree( tree, father, add_balance );*/
1073  rebalance_tree(father, add_balance, SHRINK);
1074 
1075 #ifdef DEBUG
1076  print("tree after:");
1077 #endif
1078 
1079  return ret_data;
1080 
1081 } /* end remove_node */
1082 
1083 /**********************************************************************/
1084 
1085 /* remove a node from an AVL-tree, including re-balancing of the tree */
1086 /* compare addresses */
1087 
1088 template <class T>
1090 {
1091  CO_AVL_Node<T> *node, *old_node, *father, *tmp_node;
1092  T *ret_data;
1093  int add_balance = 0;
1094 #ifdef DEBUG
1095  char tmp_str[255];
1096 #endif
1097 
1098  if (data == NULL)
1099  return 0;
1100 
1101  search_node(data, COVISE_EQUAL);
1102  if (!best_node)
1103  {
1104  printf("Serious Error, did not find a node with correct data\n");
1105  }
1106 
1107  tmp_node = best_node;
1108 
1109  old_node = node = search_identical_node(data, tmp_node);
1110 
1111  if (node == 0L)
1112  {
1113  printf("remove_node failed\n");
1114  search_identical_node(data, tmp_node);
1115  return 0L;
1116  }
1117 
1118  ret_data = node->data;
1119 
1120  if (node->left == NULL) /* replace node by the right subtree */
1121  {
1122 
1123  /* F *\
1124  * | F *
1125  * N ==> | *
1126  * \ R *
1127  \* R */
1128  father = node->up;
1129  if (father)
1130  {
1131  if (father->left == node)
1132  {
1133 #ifdef debug
1134  fprintf(stdout, ".1");
1135 #endif
1136  (father->left) = (node->right);
1137  add_balance = 1;
1138  }
1139  else
1140  {
1141 #ifdef debug
1142  fprintf(stdout, ".2");
1143 #endif
1144  (father->right) = (node->right);
1145  add_balance = -1;
1146  }
1147  }
1148  else /* root */
1149  {
1150 #ifdef debug
1151  fprintf(stdout, ".3");
1152 #endif
1153  root = (node->right);
1154  }
1155  if (node->right)
1156  (node->right)->up = father;
1157  // untested!!!
1158  delete node;
1159  }
1160  else if (node->right == 0L) /* replace node by left subtree */
1161  {
1162 #ifdef debug
1163  fprintf(stdout, " case 2");
1164 #endif
1165  /* F *\
1166  * | F *
1167  * N ==> | *
1168  * / L *
1169  \* L */
1170  father = node->up;
1171  if (father)
1172  {
1173  if (father->left == node)
1174  {
1175  (father->left) = (node->left);
1176  add_balance = 1;
1177  }
1178  else
1179  {
1180  (father->right) = (node->left);
1181  add_balance = -1;
1182  }
1183  }
1184  else /* root */
1185  {
1186  root = (node->left);
1187  }
1188  if (node->left)
1189  (node->left)->up = father;
1190  // untested!!!
1191  delete node;
1192  }
1193  else /* must search downward for a node to remove */
1194  {
1195  /* F F *\
1196  * | | *
1197  * N Y *
1198  * / \ ==> / \ *
1199  * V W V W *
1200  * / \ / \ *
1201  * X Y X Z *
1202  * / *
1203  \* Z */
1204  if (node->balance < 1) /* left subtree of node is higher than right */
1205  {
1206 #ifdef debug
1207  fprintf(stdout, " case 3");
1208 #endif
1209  node = (node->left); /* search for largest node in left subtree */
1210  while (node->right)
1211  {
1212  node = (node->right);
1213 #ifdef ERR_NODE
1214  if (node == ERR_NODE)
1215  {
1216  printf("[node=%x, data=%x]", node, node->data);
1217  }
1218 #endif
1219  }
1220 
1221  father = (node->up); /* node durch linken subtree ersetzen */
1222 
1223 #ifdef debug
1224  if (father == NULL)
1225  {
1226  printf("\n father==NULL; tree=%8x; node=%8x : \n", root, node);
1227  print("father==NULL");
1228  exit(0);
1229  }
1230 #endif
1231 
1232  if (father->right == node)
1233  {
1234  (father->right) = (node->left);
1235  add_balance = -1;
1236  }
1237  else
1238  {
1239  (father->left) = (node->left);
1240  add_balance = 1;
1241  }
1242  if (node->left)
1243  (node->left)->up = father;
1244  }
1245  else /* right subtree of node is higher than left */
1246  {
1247 #ifdef debug
1248  fprintf(stdout, " case 4");
1249 #endif
1250  node = (node->right); /* search for smallest node in right subtree */
1251  while (node->left)
1252  {
1253  node = (node->left);
1254  }
1255 
1256  father = (node->up); /* node durch rechten subtree ersetzen */
1257  if (father->right == node)
1258  {
1259  (father->right) = (node->right);
1260  add_balance = -1;
1261  }
1262  else
1263  {
1264  (father->left) = (node->right);
1265  add_balance = 1;
1266  }
1267  if (node->right)
1268  (node->right)->up = father;
1269  }
1270 
1271  /* old_node durch node ersetzen */
1272  if (old_node->up)
1273  {
1274  if ((old_node->up)->left == old_node)
1275  (old_node->up)->left = node;
1276  else
1277  (old_node->up)->right = node;
1278  (node->up) = (old_node->up);
1279  }
1280  else /* root */
1281  {
1282  root = node;
1283  node->up = NULL;
1284  }
1285  node->left = old_node->left;
1286  if (node->left)
1287  (node->left)->up = node;
1288  node->right = old_node->right;
1289  if (node->right)
1290  (node->right)->up = node;
1291  (node->balance) = (old_node->balance);
1292  if (father == old_node)
1293  father = node;
1294  // untested!!
1295  delete old_node;
1296  }
1297 
1298  /* rebalance_shrinking_tree( tree, father, add_balance );*/
1299  rebalance_tree(father, add_balance, SHRINK);
1300 
1301 #ifdef DEBUG
1302  print("tree after:");
1303 #endif
1304 
1305  return ret_data;
1306 
1307 } /* end remove_node */
1308 
1309 /**********************************************************************/
1310 
1311 template <class T>
1312 void AVLTree<T>::print(char *str)
1313 {
1314  char tmp_str[1000];
1315 
1316  print_comment(__LINE__, __FILE__, "------- %s: %s -------", name, str);
1317  //covise_n_node = 0;
1318  //covise_depth = 0;
1319  if (root == NULL)
1320  {
1321  print_comment(__LINE__, __FILE__, "Tree empty");
1322  printf("Tree empty");
1323  return;
1324  }
1325 
1326  show_tree(root);
1327 };
1328 
1329 template <class T>
1331 {
1332  int i;
1333  char tmp_str[1000];
1334 
1335  if (curr_node == curr_node->up)
1336  {
1337  print_comment(__LINE__, __FILE__, " .... recursive; ERROR!");
1338  printf(" .... recursive; ERROR!");
1339  return;
1340  }
1341 
1342  //covise_depth++;
1343  if (curr_node->right)
1344  show_tree(curr_node->right);
1345 #if 0
1346  covise_n_node++;
1347  // printf("\n ");
1348  for (i=0; i<covise_depth; i++)
1349  // printf("-");
1350  sprintf(tmp_str, " Node %4d @@%p: bal=%2d data=%p",
1351  covise_n_node, curr_node, curr_node->balance,
1352  (void *)curr_node->data);
1353  // printf(tmp_str);
1354  print_comment(__LINE__, __FILE__, tmp_str);
1355 #else
1356  (void)tmp_str;
1357 #endif
1358 
1359  if (curr_node->left)
1360  show_tree(curr_node->left);
1361  //covise_depth--;
1362  return;
1363 }
1364 }
1365 #endif
T * search_node(T *data, int search)
Definition: covise_avl_tree.h:303
GLuint const GLchar * name
Definition: khronos-glext.h:6722
int(* compare)(T *a, T *b)
Definition: covise_avl_tree.h:121
AVLTree(int(*comp)(T *a, T *b))
Definition: covise_avl_tree.h:133
int balance
Definition: covise_avl_tree.h:54
CO_AVL_Node< T > * right
Definition: covise_avl_tree.h:52
GLdouble n
Definition: khronos-glext.h:8447
GLboolean GLboolean GLboolean b
Definition: khronos-glext.h:6895
const int COVISE_EQUAL
Definition: covise_avl_tree.h:32
Definition: covise_avl_tree.h:46
void rebalance_tree(CO_AVL_Node< T > *tree_node, int add_balance, int grow_shrink)
Definition: covise_avl_tree.h:430
void print()
Definition: covise_avl_tree.h:69
const int COVISE_GT_EQUAL
Definition: covise_avl_tree.h:31
GLint left
Definition: khronos-glext.h:8444
CO_AVL_Node(T *d)
Definition: covise_avl_tree.h:56
CO_AVL_Node< T > * get_root(void)
Definition: covise_avl_tree.h:155
T * data
Definition: covise_avl_tree.h:55
CO_AVL_Node< T > * search_identical_node(T *d, CO_AVL_Node< T > *start)
Definition: covise_avl_tree.h:182
CO_AVL_Node< T > * root
Definition: covise_avl_tree.h:122
GLuint GLuint GLsizei count
Definition: khronos-glext.h:6343
const int COVISE_LS_EQUAL
Definition: covise_avl_tree.h:33
~AVLTree()
Definition: covise_avl_tree.h:149
void show_tree(CO_AVL_Node< T > *curr_node)
Definition: covise_avl_tree.h:1330
T * remove_node(T *data)
Definition: covise_avl_tree.h:1089
const char * name
Definition: covise_avl_tree.h:124
AVLTree(int(*comp)(T *a, T *b), const char *n)
Definition: covise_avl_tree.h:141
friend class CO_AVL_Tree
Definition: covise_avl_tree.h:48
void empty_tree(void)
Definition: covise_avl_tree.h:160
CO_AVL_Node< T > * best_node
Definition: covise_avl_tree.h:123
const int COVISE_LESS_THAN
Definition: covise_avl_tree.h:34
GLboolean GLboolean GLboolean GLboolean a
Definition: khronos-glext.h:6895
int count
Definition: covise_avl_tree.h:125
typedef void(APIENTRY *GLDEBUGPROCARB)(GLenum source
#define NULL
Definition: covise_avl_tree.h:272
int insert_node(T *data)
Definition: covise_avl_tree.h:775
GLuint start
Definition: khronos-glext.h:6343
void remove_nod(void)
Definition: covise_avl_tree.h:78
AVLTree()
Definition: covise_avl_tree.h:127
UTILEXPORT int compare(const coObjID &a, const coObjID &b)
void print_comment(int line, const char *filename, const char *fmt,...)
Definition: coLog.cpp:25
CO_AVL_Node< T > * left
Definition: covise_avl_tree.h:51
#define ERR_NODE
Definition: covise_avl_tree.h:266
Definition: covise_avl_tree.h:43
T * remove_node_compare(T *data)
Definition: covise_avl_tree.h:852
CO_AVL_Node< T > * search_identical_node(T *d)
Definition: covise_avl_tree.h:96
void print(char *)
Definition: covise_avl_tree.h:1312
GLdouble GLdouble right
Definition: khronos-glext.h:12128
#define GROW
Definition: covise_avl_tree.h:426
GLsizei GLsizei GLenum GLenum const GLvoid * data
Definition: khronos-glext.h:6354
#define SHRINK
Definition: covise_avl_tree.h:427
const int COVISE_GREATER_THAN
Definition: covise_avl_tree.h:30
CO_AVL_Node< T > * up
Definition: covise_avl_tree.h:53
~CO_AVL_Node()
Definition: covise_avl_tree.h:64
int covise_std_compare(char *, char *)
Definition: covise_statics.cpp:103