56 if(tree->
left) tree->
left->super=tree;
88 case L : tree->
left->bf=E;
91 case E : tree->
left->bf=E;
94 case R : tree->
left->bf=L;
123 if(tree&&tree->
right)
125 if(tree->
right->bf==R)
137 case L : tree->
left->bf=E;
140 case E : tree->
left->bf=E;
143 case R : tree->
left->bf=L;
175 switch(tree->
left->bf)
190 case L : tree->
left->bf=E;
193 case E : tree->
left->bf=E;
196 case R : tree->
left->bf=L;
221 if(tree&&tree->
right)
223 switch(tree->
right->bf)
229 case L : tree->
left->bf=E;
232 case E : tree->
left->bf=E;
235 case R : tree->
left->bf=L;
294 if(!keyComp) result=1;
341 int(*comp)(
void*,
void*))
361 sig=comp(key,tree->
key);
367 tree->
left->super=tree;
387 tree->
right->super=tree;
404 if(replace) tree->
value=val;
417 if(h<1) tree->
size++;
439 void(*del)(
void*),
int* h,
int(*comp)(
void*,
void*))
445 if(value) *value=NULL;
451 sig=comp(key,tree->
key);
494 if(del) del(tree->
key);
495 if(value) *value=tree->
value;
503 if(del) del(tree->
key);
504 if(value) *value=tree->
value;
510 if(del) del(tree->
key);
511 if(value) *value=tree->
value;
554 for(r=-1,aux=tree->
root;
556 aux=r<0?aux->left:aux->
right);
562 else *value=aux->
value;
579 int left,right,result=0;
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;
610 int hLeft,hRight,result=0;
615 result=hLeft>hRight?++hLeft:++hRight;
657 if(!tree->
size) result=1;
686 if(!tree->
size) result=1;
714 if(!tree->
size) result=1;
int treePostOrder(TreeMap tree, void(*fun)(void *, void *))
Applies a function to the elements of an tree (postorder traversal).
int treePreOrder(TreeMap tree, void(*fun)(void *, void *))
Applies a function to the elements of an tree (preorder traversal).
static TreeNode rLeftBalance(TreeNode tree, int *h)
Rebalances a tree that is balanced to the left as result of a remotion operation. ...
int treeHeight(TreeMap tree)
Returns the height of a tree.
int treeRemove(TreeMap tree, void *key, void **value, void(*del)(void *))
Removes the mapping for a key from a tree.
static void treePostOrderAux(TreeNode tree, void(*fun)(void *, void *))
Postorder traversal auxiliary function.
int treeSize(TreeMap tree)
Returns the number of elements present in a tree.
static TreeNode leftBalance(TreeNode tree)
Rebalances a tree that is balanced to the left as result of an insertion operation.
int treeGet(TreeMap tree, void *key, void **value)
Provides the mapping for a key from a tree.
static TreeNode treeRemAux(TreeNode tree, void *key, void **value, void(*del)(void *), int *h, int(*comp)(void *, void *))
Remotion auxiliary function.
struct sTreeNode * super
Node's parent.
struct sTreeNode * left
Node's left subtree.
void * value
Node's value.
int(* keyComp)(void *, void *)
Key comparison function of this tree.
void itDelete(Iterator it)
Deletes an iterator.
int treeIsBalancedAux(TreeNode tree)
Checks if a tree is balanced.
static TreeNode treeInsAux(TreeNode tree, void *key, void *val, int replace, int *h, int(*comp)(void *, void *))
Insertion auxiliary function.
Iterator treeValues(TreeMap tree)
Creates an iterator from the values of a tree.
TreeMap newTree(int(*keyComp)(void *, void *))
Creates a tree.
static TreeNode rightRotate(TreeNode tree)
Rotates a tree to right.
static int treeKAux(TreeNode tree, Iterator it)
Traverses a tree and adds the keys to an iterator.
static void treePreOrderAux(TreeNode tree, void(*fun)(void *, void *))
Preorder traversal auxiliary function.
int itAdd(Iterator it, void *val)
Adds an element to an iterator.
BFactor bf
Node's balance factor.
int size
Number of elements of this tree.
static TreeNode upperLeft(TreeNode tree)
Returns the node with the greatest key on the left subtree of a tree.
int treeIsBalanced(TreeMap tree)
Checks if a tree is balanced.
int treeSetKComp(TreeMap tree, int(*keyComp)(void *, void *))
Sets the comparison function of this tree.
static void treeInOAux(TreeNode tree, void(*fun)(void *, void *))
Inorder traversal auxiliary function.
static void treeDelAux(TreeNode tree)
Deletes a node of a tree and all of its children nodes.
static int treeVAux(TreeNode tree, Iterator it)
Traverses a tree and adds the values to an iterator.
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.
Iterator treeKeys(TreeMap tree)
Creates an iterator from the keys of a tree.
struct sTreeNode * right
Node's right subtree.
static TreeNode rightBalance(TreeNode tree)
Rebalances a tree that is balanced to the right as result of an insertion operation.
static TreeNode leftRotate(TreeNode tree)
Rotates a tree to left.
int treeInsert(TreeMap tree, void *key, void *val, int replace)
Associates a value to a key in a tree.
TreeNode root
Root node of this tree.
int treeInOrder(TreeMap tree, void(*fun)(void *, void *))
Applies a function to the elements of an tree (inorder traversal).
static int treeHightAux(TreeNode tree)
Returns the height of a tree.
Iterator newIt(int size)
Creates an iterator.
void treeDelete(TreeMap tree)
Deletes a tree.