LibRCG  3.1.1
treemap.c
Go to the documentation of this file.
1 
9 #include <stdlib.h>
10 #include "treemap.h"
11 
21 {
22  TreeNode aux=tree;
23  if(tree&&tree->right)
24  {
25  aux=tree->right;
26  tree->right=aux->left;
27  aux->left=tree;
28  aux->super=tree->super;
29  tree->super=aux;
30  if(tree->right) tree->right->super=tree;
31  }
32  return aux;
33 }
34 
35 //==============================================================================
36 
46 {
47  TreeNode aux=tree;
48  if(tree&&tree->left)
49  {
50  aux=tree->left;
51  tree->left=aux->right;
52  aux->right=tree;
53 
54  aux->super=tree->super;
55  tree->super=aux;
56  if(tree->left) tree->left->super=tree;
57  }
58  return aux;
59 }
60 
61 //==============================================================================
62 
73 {
74  if(tree&&tree->left)
75  {
76  if(tree->left->bf==L)
77  {
78  tree=rightRotate(tree);
79  tree->bf=E;
80  tree->right->bf=E;
81  }
82  else
83  {
84  tree->left=leftRotate(tree->left);
85  tree=rightRotate(tree);
86  switch(tree->bf)
87  {
88  case L : tree->left->bf=E;
89  tree->right->bf=R;
90  break;
91  case E : tree->left->bf=E;
92  tree->right->bf=E;
93  break;
94  case R : tree->left->bf=L;
95  tree->right->bf=E;
96  break;
97  }
98  tree->bf=E;
99  }
100  }
101  else
102  {
103  tree=rightRotate(tree);
104  tree->right->bf=E;
105  tree->left->bf=E;
106  }
107  return tree;
108 }
109 
110 //==============================================================================
111 
122 {
123  if(tree&&tree->right)
124  {
125  if(tree->right->bf==R)
126  {
127  tree=leftRotate(tree);
128  tree->bf=E;
129  tree->left->bf=E;
130  }
131  else
132  {
133  tree->right=rightRotate(tree->right);
134  tree=leftRotate(tree);
135  switch(tree->bf)
136  {
137  case L : tree->left->bf=E;
138  tree->right->bf=R;
139  break;
140  case E : tree->left->bf=E;
141  tree->right->bf=E;
142  break;
143  case R : tree->left->bf=L;
144  tree->right->bf=E;
145  break;
146  }
147  tree->bf=E;
148  }
149  }
150  else
151  {
152  tree=rightRotate(tree);
153  tree->left->bf=E;
154  tree->right->bf=E;
155  }
156  return tree;
157 }
158 
159 //=============================================================================
160 
171 static TreeNode rLeftBalance(TreeNode tree,int* h)
172 {
173  if(tree&&tree->left)
174  {
175  switch(tree->left->bf)
176  {
177  case L : tree=rightRotate(tree);
178  tree->bf=E;
179  tree->right->bf=E;
180  break;
181  case E : tree=rightRotate(tree);
182  tree->bf=R;
183  tree->bf=L;
184  *h=2;
185  break;
186  case R : tree->left=leftRotate(tree->left);
187  tree=rightRotate(tree);
188  switch(tree->bf)
189  {
190  case L : tree->left->bf=E;
191  tree->right->bf=E;
192  break;
193  case E : tree->left->bf=E;
194  tree->right->bf=E;
195  break;
196  case R : tree->left->bf=L;
197  tree->right->bf=E;
198  break;
199  }
200  tree->bf=E;
201  break;
202  }
203  }
204  return tree;
205 }
206 
207 //==============================================================================
208 
219 static TreeNode rRightBalance(TreeNode tree,int* h)
220 {
221  if(tree&&tree->right)
222  {
223  switch(tree->right->bf)
224  {
225  case L : tree->right=rightRotate(tree->right);
226  tree=leftRotate(tree);
227  switch(tree->bf)
228  {
229  case L : tree->left->bf=E;
230  tree->right->bf=R;
231  break;
232  case E : tree->left->bf=E;
233  tree->right->bf=E;
234  break;
235  case R : tree->left->bf=L;
236  tree->right->bf=E;
237  break;
238  }
239  tree->bf=E;
240  break;
241  case E : tree=leftRotate(tree);
242  tree->bf=L;
243  tree->left->bf=R;
244  *h=2;
245  break;
246  case R : tree=leftRotate(tree);
247  tree->bf=E;
248  tree->left->bf=E;
249  break;
250  }
251  }
252  return tree;
253 }
254 
255 //==============================================================================
256 
266 {
267  while(tree->right) tree=tree->right;
268  return tree;
269 }
270 
271 //==============================================================================
272 
273 TreeMap newTree(int(*keyComp)(void*,void*))
274 {
275  TreeMap tree=NULL;
276  if(keyComp)
277  {
278  tree=malloc(sizeof(STreeMap));
279  if(tree)
280  {
281  tree->keyComp=*keyComp;
282  tree->size=0;
283  tree->root=NULL;
284  }
285  }
286  return tree;
287 }
288 
289 //==============================================================================
290 
291 int treeSetKComp(TreeMap tree,int(*keyComp)(void*,void*))
292 {
293  int result=0;
294  if(!keyComp) result=1;
295  else tree->keyComp=*keyComp;
296  return result;
297 }
298 
299 //==============================================================================
300 
306 static void treeDelAux(TreeNode tree)
307 {
308  if(tree)
309  {
310  treeDelAux(tree->left);
311  treeDelAux(tree->right);
312  free(tree);
313  }
314 }
315 
316 //==============================================================================
317 
318 void treeDelete(TreeMap tree)
319 {
320  treeDelAux(tree->root);
321  free(tree);
322 }
323 
324 //==============================================================================
325 
340 static TreeNode treeInsAux(TreeNode tree,void* key,void* val,int replace,int* h,
341  int(*comp)(void*,void*))
342 {
343  int sig;
344  if(!tree)
345  {
346  tree=malloc(sizeof(STreeNode));
347  if(tree)
348  {
349  tree->key=key;
350  tree->value=val;
351  tree->bf=E;
352  tree->super=NULL;
353  tree->left=NULL;
354  tree->right=NULL;
355  *h=0;
356  }
357  else *h=2;
358  }
359  else
360  {
361  sig=comp(key,tree->key);
362  if(sig<0)
363  {
364  tree->left=treeInsAux(tree->left,key,val,replace,h,comp);
365  if(!(*h))
366  {
367  tree->left->super=tree;
368  switch(tree->bf)
369  {
370  case L : tree=leftBalance(tree);
371  tree->bf=E;
372  *h=-1;
373  break;
374  case E : tree->bf=L;
375  break;
376  case R : tree->bf=E;
377  *h=-1;
378  break;
379  }
380  }
381  }
382  else if(sig>0)
383  {
384  tree->right=treeInsAux(tree->right,key,val,replace,h,comp);
385  if(!(*h))
386  {
387  tree->right->super=tree;
388  switch(tree->bf)
389  {
390  case L : tree->bf=E;
391  *h=-1;
392  break;
393  case E : tree->bf=R;
394  break;
395  case R : tree=rightBalance(tree);
396  tree->bf=E;
397  *h=-1;
398  break;
399  }
400  }
401  }
402  else
403  {
404  if(replace) tree->value=val;
405  *h=1;
406  }
407  }
408  return tree;
409 }
410 
411 //==============================================================================
412 
413 int treeInsert(TreeMap tree,void* key,void* val,int replace)
414 {
415  int h,result=0;
416  tree->root=treeInsAux(tree->root,key,val,replace,&h,tree->keyComp);
417  if(h<1) tree->size++;
418  else result=h;
419  return result;
420 }
421 
422 //==============================================================================
423 
438 static TreeNode treeRemAux(TreeNode tree,void* key,void** value,
439  void(*del)(void*),int* h,int(*comp)(void*,void*))
440 {
441  int sig;
442  TreeNode aux;
443  if(!tree)
444  {
445  if(value) *value=NULL;
446  *h=1;
447  aux=NULL;
448  }
449  else
450  {
451  sig=comp(key,tree->key);
452  if(sig<0)
453  {
454  tree->left=treeRemAux(tree->left,key,value,del,h,comp);
455  if(!(*h))
456  {
457  switch(tree->bf)
458  {
459  case L : tree->bf=E;
460  break;
461  case E : tree->bf=R;
462  *h=2;
463  break;
464  case R : tree=rRightBalance(tree,h);
465  break;
466  }
467  }
468  aux=tree;
469  }
470  else if(sig>0)
471  {
472  tree->right=treeRemAux(tree->right,key,value,del,h,comp);
473  if(!(*h))
474  {
475  switch(tree->bf)
476  {
477  case L : tree=rLeftBalance(tree,h);
478  break;
479  case E : tree->bf=L;
480  *h=2;
481  break;
482  case R : tree->bf=E;
483  break;
484  }
485  }
486  aux=tree;
487  }
488  else
489  {
490  if(!tree->right)
491  {
492  aux=tree->left;
493  if(aux) aux->super=tree->super;
494  if(del) del(tree->key);
495  if(value) *value=tree->value;
496  free(tree);
497  *h=0;
498  }
499  else if(!tree->left)
500  {
501  aux=tree->right;
502  if(aux) aux->super=tree->super;
503  if(del) del(tree->key);
504  if(value) *value=tree->value;
505  free(tree);
506  *h=0;
507  }
508  else
509  {
510  if(del) del(tree->key);
511  if(value) *value=tree->value;
512  aux=upperLeft(tree->left);
513  tree->key=aux->key;
514  tree->value=aux->value;
515  aux->value=NULL;
516  tree->left=treeRemAux(tree->left,aux->key,NULL,NULL,h,comp);
517  if(!(*h))
518  {
519  switch(tree->bf)
520  {
521  case L : tree->bf=E;
522  break;
523  case E : tree->bf=R;
524  *h=2;
525  break;
526  case R : tree=rRightBalance(tree,h);
527  break;
528  }
529  }
530  aux=tree;
531  }
532  }
533  }
534  return aux;
535 }
536 
537 //=============================================================================
538 
539 int treeRemove(TreeMap tree,void* key,void** value,void(*del)(void*))
540 {
541  int h,result=0;
542  tree->root=treeRemAux(tree->root,key,value,del,&h,tree->keyComp);
543  if(h==1) result=1;
544  else tree->size--;
545  return result;
546 }
547 
548 //==============================================================================
549 
550 int treeGet(TreeMap tree,void* key,void** value)
551 {
552  TreeNode aux;
553  int r,result=0;
554  for(r=-1,aux=tree->root;
555  aux&&(r=(*tree->keyComp)(key,aux->key));
556  aux=r<0?aux->left:aux->right);
557  if(r)
558  {
559  *value=NULL;
560  result=1;
561  }
562  else *value=aux->value;
563  return result;
564 }
565 
566 //==============================================================================
567 
578 {
579  int left,right,result=0;
580  if(tree)
581  {
582  left=treeIsBalancedAux(tree->left);
583  right=treeIsBalancedAux(tree->right);
584  if(left<0||right<0) result=-1;
585  else if(left>right) result=left-right>1?-1:++left;
586  else result=right-left>1?-1:++right;
587  }
588  return result;
589 }
590 
591 //=============================================================================
592 
594 {
595  return treeIsBalancedAux(tree->root)==-1?0:1;
596 }
597 
598 //==============================================================================
599 
608 static int treeHightAux(TreeNode tree)
609 {
610  int hLeft,hRight,result=0;
611  if(tree)
612  {
613  hLeft=treeHightAux(tree->left);
614  hRight=treeHightAux(tree->right);
615  result=hLeft>hRight?++hLeft:++hRight;
616  }
617  return result;
618 }
619 
620 //=============================================================================
621 
623 {
624  return treeHightAux(tree->root);
625 }
626 
627 //==============================================================================
628 
629 int treeSize(TreeMap tree)
630 {
631  return tree->size;
632 }
633 
634 //==============================================================================
635 
642 static void treeInOAux(TreeNode tree,void(*fun)(void*,void*))
643 {
644  if(tree)
645  {
646  treeInOAux(tree->left,fun);
647  fun(tree->key,tree->value);
648  treeInOAux(tree->right,fun);
649  }
650 }
651 
652 //=============================================================================
653 
654 int treeInOrder(TreeMap tree,void(*fun)(void*,void*))
655 {
656  int result=0;
657  if(!tree->size) result=1;
658  else treeInOAux(tree->root,fun);
659  return result;
660 }
661 
662 //==============================================================================
663 
671 static void treePreOrderAux(TreeNode tree,void(*fun)(void*,void*))
672 {
673  if(tree)
674  {
675  fun(tree->key,tree->value);
676  treePreOrderAux(tree->left,fun);
677  treePreOrderAux(tree->right,fun);
678  }
679 }
680 
681 //=============================================================================
682 
683 int treePreOrder(TreeMap tree,void(*fun)(void*,void*))
684 {
685  int result=0;
686  if(!tree->size) result=1;
687  else treePreOrderAux(tree->root,fun);
688  return result;
689 }
690 
691 //==============================================================================
692 
699 static void treePostOrderAux(TreeNode tree,void(*fun)(void*,void*))
700 {
701  if(tree)
702  {
703  treePostOrderAux(tree->left,fun);
704  treePostOrderAux(tree->right,fun);
705  fun(tree->key,tree->value);
706  }
707 }
708 
709 //=============================================================================
710 
711 int treePostOrder(TreeMap tree,void(*fun)(void*,void*))
712 {
713  int result=0;
714  if(!tree->size) result=1;
715  else treePostOrderAux(tree->root,fun);
716  return result;
717 }
718 
719 //=============================================================================
720 
731 static int treeKAux(TreeNode tree,Iterator it)
732 {
733  int result=0;
734  if(tree)
735  {
736  result=treeKAux(tree->left,it);
737  result=result||itAdd(it,tree->key);
738  result=result||treeKAux(tree->right,it);
739  }
740  return result;
741 }
742 
743 //=============================================================================
744 
746 {
747  Iterator it=newIt(tree->size);
748  if(it&&treeKAux(tree->root,it))
749  {
750  itDelete(it);
751  it=NULL;
752  }
753  return it;
754 }
755 
756 //=============================================================================
757 
769 static int treeVAux(TreeNode tree,Iterator it)
770 {
771  int result=0;
772  if(tree)
773  {
774  result=treeVAux(tree->left,it);
775  result=result||itAdd(it,tree->value);
776  result=result||treeVAux(tree->right,it);
777  }
778  return result;
779 }
780 
781 //=============================================================================
782 
784 {
785  Iterator it=newIt(tree->size);
786  if(it&&treeVAux(tree->root,it))
787  {
788  itDelete(it);
789  it=NULL;
790  }
791  return it;
792 }
int treePostOrder(TreeMap tree, void(*fun)(void *, void *))
Applies a function to the elements of an tree (postorder traversal).
Definition: treemap.c:711
int treePreOrder(TreeMap tree, void(*fun)(void *, void *))
Applies a function to the elements of an tree (preorder traversal).
Definition: treemap.c:683
static TreeNode rLeftBalance(TreeNode tree, int *h)
Rebalances a tree that is balanced to the left as result of a remotion operation. ...
Definition: treemap.c:171
int treeHeight(TreeMap tree)
Returns the height of a tree.
Definition: treemap.c:622
void * key
Node's key.
Definition: treemap.h:46
int treeRemove(TreeMap tree, void *key, void **value, void(*del)(void *))
Removes the mapping for a key from a tree.
Definition: treemap.c:539
static void treePostOrderAux(TreeNode tree, void(*fun)(void *, void *))
Postorder traversal auxiliary function.
Definition: treemap.c:699
int treeSize(TreeMap tree)
Returns the number of elements present in a tree.
Definition: treemap.c:629
static TreeNode leftBalance(TreeNode tree)
Rebalances a tree that is balanced to the left as result of an insertion operation.
Definition: treemap.c:72
int treeGet(TreeMap tree, void *key, void **value)
Provides the mapping for a key from a tree.
Definition: treemap.c:550
static TreeNode treeRemAux(TreeNode tree, void *key, void **value, void(*del)(void *), int *h, int(*comp)(void *, void *))
Remotion auxiliary function.
Definition: treemap.c:438
struct sTreeNode * super
Node's parent.
Definition: treemap.h:52
struct sTreeNode * left
Node's left subtree.
Definition: treemap.h:54
Iterator structure.
Definition: iterator.h:17
void * value
Node's value.
Definition: treemap.h:48
int(* keyComp)(void *, void *)
Key comparison function of this tree.
Definition: treemap.h:70
void itDelete(Iterator it)
Deletes an iterator.
Definition: iterator.c:36
int treeIsBalancedAux(TreeNode tree)
Checks if a tree is balanced.
Definition: treemap.c:577
static TreeNode treeInsAux(TreeNode tree, void *key, void *val, int replace, int *h, int(*comp)(void *, void *))
Insertion auxiliary function.
Definition: treemap.c:340
Iterator treeValues(TreeMap tree)
Creates an iterator from the values of a tree.
Definition: treemap.c:783
TreeMap newTree(int(*keyComp)(void *, void *))
Creates a tree.
Definition: treemap.c:273
static TreeNode rightRotate(TreeNode tree)
Rotates a tree to right.
Definition: treemap.c:45
static int treeKAux(TreeNode tree, Iterator it)
Traverses a tree and adds the keys to an iterator.
Definition: treemap.c:731
static void treePreOrderAux(TreeNode tree, void(*fun)(void *, void *))
Preorder traversal auxiliary function.
Definition: treemap.c:671
int itAdd(Iterator it, void *val)
Adds an element to an iterator.
Definition: iterator.c:44
BFactor bf
Node's balance factor.
Definition: treemap.h:50
int size
Number of elements of this tree.
Definition: treemap.h:72
static TreeNode upperLeft(TreeNode tree)
Returns the node with the greatest key on the left subtree of a tree.
Definition: treemap.c:265
int treeIsBalanced(TreeMap tree)
Checks if a tree is balanced.
Definition: treemap.c:593
int treeSetKComp(TreeMap tree, int(*keyComp)(void *, void *))
Sets the comparison function of this tree.
Definition: treemap.c:291
static void treeInOAux(TreeNode tree, void(*fun)(void *, void *))
Inorder traversal auxiliary function.
Definition: treemap.c:642
static void treeDelAux(TreeNode tree)
Deletes a node of a tree and all of its children nodes.
Definition: treemap.c:306
static int treeVAux(TreeNode tree, Iterator it)
Traverses a tree and adds the values to an iterator.
Definition: treemap.c:769
Tree structure.
Definition: treemap.h:67
Tree node structure.
Definition: treemap.h:43
Implementation of an AVL tree (self-balancing binary search tree).
static TreeNode rRightBalance(TreeNode tree, int *h)
Rebalances a tree that is balanced to the right as result of a remotion operation.
Definition: treemap.c:219
Iterator treeKeys(TreeMap tree)
Creates an iterator from the keys of a tree.
Definition: treemap.c:745
struct sTreeNode * right
Node's right subtree.
Definition: treemap.h:56
static TreeNode rightBalance(TreeNode tree)
Rebalances a tree that is balanced to the right as result of an insertion operation.
Definition: treemap.c:121
static TreeNode leftRotate(TreeNode tree)
Rotates a tree to left.
Definition: treemap.c:20
int treeInsert(TreeMap tree, void *key, void *val, int replace)
Associates a value to a key in a tree.
Definition: treemap.c:413
TreeNode root
Root node of this tree.
Definition: treemap.h:74
int treeInOrder(TreeMap tree, void(*fun)(void *, void *))
Applies a function to the elements of an tree (inorder traversal).
Definition: treemap.c:654
static int treeHightAux(TreeNode tree)
Returns the height of a tree.
Definition: treemap.c:608
Iterator newIt(int size)
Creates an iterator.
Definition: iterator.c:12
void treeDelete(TreeMap tree)
Deletes a tree.
Definition: treemap.c:318

LibRCG © 2004-2015   Rui Carlos Gonçalves