I'm coding a generic AVL tree as both a challenge to myself and, if I can do it properly, a resource for other CS students out there.
As one usually would, I started by implementing a recursive insertion function, which works. However, due to efficiency, I tried to implement the same function, but iteratively. I searched online and found lots of implementations, but the rest of the code was always too different from mine, which led me to continue attempting to create an implementation from scratch.
These are the relevant defined types:
typedef struct info {
int id;
char name[200];
} data;
typedef struct avl_node {
void * data;
struct avl_node * left;
struct avl_node * right;
int height;
} * avl_node_t;
typedef struct avl_tree {
avl_node_t root;
int num_nodes;
int (*less)(const void * first, const void * second);
int (*key)(const void * data);
} * avl_t;
And as follows is the iterative insertion function (which doesn't work as intended):
avl_node_t
avl_insert(avl_node_t node, void * data)
{
long key1 = 0, key2 = 0;
avl_node_t aux = NULL;
while (1) {
if (node == NULL) {
node = avl_node_create(data);
break;
}
key1 = key((void*)&data);
key2 = key((void*)&(node->data));
aux = node;
if (less((void*)&key1, (void*)&key2))
node = node->left;
else
node = node->right;
}
if (aux != NULL) {
if (less((void*)&key1, (void*)&key2))
aux->right = node;
else if (less((void*)&key2, (void*)&key1))
aux->left = node;
}
node = avl_balance(node);
return node;
}
In which the avl_balance function is defined as such:
static short
balance(avl_node_t node)
{
if (node == NULL)
return 0;
return avl_node_height(node->left) - avl_node_height(node->right);
}
static avl_node_t
avl_balance(avl_node_t node)
{
short balance_factor;
if (node == NULL)
return node;
balance_factor = balance(node);
if (balance_factor > 1)
if (balance(node->left) >= 0)
node = avl_rotRight(node);
else
node = avl_rotLeftRight(node);
else if (balance_factor < -1)
if (balance(node->right) <= 0)
node = avl_rotLeft(node);
else
node = avl_rotRightLeft(node);
else
update_height(node);
return node;
}
This is the code I'm using to test the AVL tree:
int main()
{
data d1 = { 1, "we are number one" };
data d2 = { 2, "boneless pizza" };
data d3 = { 3, "hehe" };
data d4 = { 4, "achoo" };
data d5 = { 5, "I like C" };
data d6 = { 6, "Assembly is cool too" };
data d7 = { 7, "SIGSEGV" };
avl_t tree = avl_create();
avl_node_t root = tree->root;
root = avl_insert(root, (void*)&d1);
traverse(root);
root = avl_insert(root, (void*)&d2);
traverse(root);
root = avl_insert(root, (void*)&d3);
root = avl_insert(root, (void*)&d4);
root = avl_insert(root, (void*)&d5);
root = avl_insert(root, (void*)&d6);
root = avl_insert(root, (void*)&d7);
traverse(root);
free(tree);
exit(0);
}
In which traverse is defined as such:
void visit(void * d)
{
data * my_data = (data*)d;
printf("I am element number %d named %s\n", (*my_data).id, (*my_data).name);
fflush(stdout);
}
void traverse(avl_node_t node)
{
if (node == NULL)
return;
traverse(node->left);
traverse(node->right);
visit(node->data);
}
And finally, this is the output I'm getting from this test:
I am element number 1 named we are number one
I am element number 2 named boneless pizza
I am element number 7 named SIGSEGV
Thank you in advance.
