|
|
Avl library
|
|
|
===========
|
|
|
|
|
|
Representation of data
|
|
|
----------------------
|
|
|
|
|
|
In computer science, an AVL tree is a self-balancing binary search tree,
|
|
|
and it was the first such data structure to be invented. In an AVL tree,
|
|
|
the heights of the two child sub-trees of any node differ by at most
|
|
|
one.\
|
|
|
Lookup, insertion, and deletion all take **O**(*log* n) time in both the
|
|
|
average and worst cases, where *n* is the number of nodes in the tree
|
|
|
prior to the operation.\
|
|
|
Insertions and deletions may require the tree to be rebalanced by one or
|
|
|
more tree rotations.
|
|
|
|
|
|
The AVL tree is named after its two Soviet inventors, G.M.
|
|
|
Adelson-Velskii and E.M. Landis, who published it in their 1962 paper
|
|
|
"An algorithm for the organization of information."
|
|
|
|
|
|
The balance factor of a node is the height of its left sub-tree minus
|
|
|
the height of its right sub-tree (sometimes opposite) and a node with
|
|
|
balance factor 1, 0, or −1 is considered balanced. A node with any other
|
|
|
balance factor is considered unbalanced and requires rebalancing the
|
|
|
tree. The balance factor is either stored directly at each node or
|
|
|
computed from the heights of the sub-trees.
|
|
|
|
|
|
Use of library
|
|
|
--------------
|
|
|
|
|
|
To be fully functional, a new tree need four pointer functions depending
|
|
|
of data you want to store.
|
|
|
|
|
|
### Data compare
|
|
|
|
|
|
First of all, an AVL tree need tools to compare your data. Prototype of
|
|
|
this function must be
|
|
|
|
|
|
```c
|
|
|
int data_cmp(void *a, void *b);
|
|
|
```
|
|
|
|
|
|
`a` and `b` are pointer to your data and function must return a positive
|
|
|
if `a` is higher than `b`, negative if `a` is lesser than `b` or `0` if
|
|
|
`a` is equal to `b`.\
|
|
|
If your data is integer, then an example of `data_cmp` implementation
|
|
|
could be:
|
|
|
|
|
|
```c
|
|
|
int data_cmp(void *a, void *b)
|
|
|
{
|
|
|
return *((int *) a) - *((int *) b);
|
|
|
}
|
|
|
```
|
|
|
|
|
|
If your data is a structure that contains a string key and an integer
|
|
|
value and if you want to order it in case sensitive lexicographic order
|
|
|
on string member, you can use the following example:
|
|
|
|
|
|
```c
|
|
|
struct _data {
|
|
|
char *key;
|
|
|
int value;
|
|
|
};
|
|
|
|
|
|
int data_cmp(void *a, void *b)
|
|
|
{
|
|
|
return strcmp((struct _data *) a)->key, ((struct _data *) b)->key);
|
|
|
}
|
|
|
```
|
|
|
|
|
|
### Data print
|
|
|
|
|
|
This function is mainly used for debug purpose. Its main goal is to
|
|
|
print a data to `stdout` and will be called on each node in tree during
|
|
|
the `print_tree` process.\
|
|
|
Its prototype is the following:
|
|
|
|
|
|
```c
|
|
|
void data_print(void *d);
|
|
|
```
|
|
|
|
|
|
With the two previous type of data example, you can use the following
|
|
|
implementation:
|
|
|
|
|
|
```c
|
|
|
// With integer data
|
|
|
void data_print(void *d)
|
|
|
{
|
|
|
printf("%d\n", *((int *) d));
|
|
|
}
|
|
|
|
|
|
// With struct _data
|
|
|
void data_print(void *d)
|
|
|
{
|
|
|
printf("\"%s\" => %d\n", ((struct _data *) d)->key, ((struct _data *) d)->value);
|
|
|
}
|
|
|
```
|
|
|
|
|
|
### Data delete
|
|
|
|
|
|
This function is used to correctly clean your memory after use. When you
|
|
|
delete a node (or the complete tree), this function is applied to the
|
|
|
specified node (or on each node of tree). Its prototype is the
|
|
|
following:
|
|
|
|
|
|
```c
|
|
|
void data_delete(void *d)
|
|
|
```
|
|
|
|
|
|
With the previous type example, you can use the following
|
|
|
implementation:
|
|
|
|
|
|
```c
|
|
|
// With integer data
|
|
|
void data_delete(void *d)
|
|
|
{
|
|
|
free(d);
|
|
|
}
|
|
|
|
|
|
// With struct _data
|
|
|
void data_delete(void *d)
|
|
|
{
|
|
|
if (d != NULL)
|
|
|
free(((struct _data *) d)->key);
|
|
|
free(d);
|
|
|
}
|
|
|
```
|
|
|
|
|
|
#### Data copy
|
|
|
|
|
|
This function is used to copy data in `get` function to extract the
|
|
|
whole data from a tree. It takes three arguments:\
|
|
|
a source pointer to data in tree, a destination pointer to external
|
|
|
memory allocated for data and the size of the data.
|
|
|
|
|
|
```c
|
|
|
void data_copy(void *src, void *dst, size_t len);
|
|
|
```
|
|
|
|
|
|
Again, with the previous type definition, you can use the following
|
|
|
implementation:
|
|
|
|
|
|
```c
|
|
|
// With integer
|
|
|
void data_copy(void *src, void *dst, size_t len)
|
|
|
{
|
|
|
memcpy(dst, src, len);
|
|
|
}
|
|
|
|
|
|
// With _data structure
|
|
|
void data_copy(void *src, void *dst, size_t len)
|
|
|
{
|
|
|
(void) len;
|
|
|
struct _data *src_t = (struct _data *) src;
|
|
|
struct _data *dst_t = (struct _data *) dst;
|
|
|
if (src_t != NULL && dst_t != NULL) {
|
|
|
dst_t->key = malloc((strlen(src_t->key) + 1) * sizeof(char));
|
|
|
if (dst_t->key != NULL)
|
|
|
strcpy(dst_t->key, src_t->key);
|
|
|
dst_t->value = src_t->value;
|
|
|
}
|
|
|
}
|
|
|
``` |
|
|
\ No newline at end of file |