avl_tree.zip_avl tree

#include <stdio.h> #include <stdlib.h> #include <string.h> #ifndef NULL #define NULL ((void*) 0) #endif int arrData[10000]; int n; FILE *fd; typedef struct {int count;int max;void **mem;} vector_t; void vector_init(vector_t *vec) {vec->count = 0;vec->max = 0;vec->mem = NULL;return ;} void vector_free(vector_t *vec) {if(vec->mem != NULL){free(vec->mem);}vector_init(vec);return ;} void vector_get(vector_t *vec, int index, void **item) {if (index >= 0 && index < vec->count) {*item = vec->mem[index];}return ;} void vector_apply(vector_t *vec, void (*func)(void *)) { void *item;int i;for (i = 0; i < vec->count; ++i) {vector_get(vec, i, &item);func(item);} return ; } void vector_delete(vector_t *vec, int index, void **item) { int i; if (index >= 0 && index < vec->count) { if (item != NULL) {*item = vec->mem[index];} if (index < vec->count - 1) {for (i = index; i < vec->count - 1; ++i){vec->mem[i] = vec->mem[i + 1];}} vec->mem[vec->count - 1] = NULL;vec->count--; } return ; } int vector_reserve(vector_t *vec, int size) { int max;void *temp;max = 0; if (size <= vec->max) {return 1;} else if (vec->max == 0 && size > 0) {max = 4;if(size > 4){do {max *= 2;} while (size > max);}} else if (vec->max > 0 && size > vec->max) {max = vec->max;do {max *= 2;} while (size > max);} if (max > 0) { temp = NULL;temp = realloc(vec->mem, max * sizeof(void *)); if (temp != NULL) {vec->mem = temp;vec->max = max;return 1;}else{return 0;} } else {return 1;} } int vector_add(vector_t *vec, void *item) { if (vector_reserve(vec, vec->count + 1) == 1) {vec->mem[vec->count] = item;vec->count++;return 1;} else {return 0;} } typedef struct avl_tree_node { int balance;int count;void *data;vector_t dataVec; struct avl_tree_node *left;struct avl_tree_node *right;struct avl_tree_node *parent; } avl_tree_node_t; typedef struct {avl_tree_node_t *root;} avl_tree_t; int compareData(void *pLeft,void *pRight) { int *left;int *right;left = (int *)pLeft;right = (int *)pRight; if(*left < *right){return -1;}else if(*left > *right){return 1;}else{return 0;} } void printData(void *data) { fprintf(fd, "%d ",*((int *)data)); } avl_tree_node_t * avl_tree_node_alloc(void *data) { avl_tree_node_t *node;node = NULL; node = (avl_tree_node_t *)malloc(sizeof(avl_tree_node_t)); if (node != NULL) { node->left = NULL;node->right = NULL;node->parent = NULL; node->balance = 0;node->count = 1;node->data = data;vector_init(&(node->dataVec)); if(vector_add(&(node->dataVec), data) == 0){free(node);node = NULL;return node;} } return node; } void avl_tree_node_free(avl_tree_node_t *node){if(node != NULL){vector_free(&(node->dataVec));free(node);}} avl_tree_t * avl_tree_alloc() { avl_tree_t *tree;tree = NULL; tree = (avl_tree_t *)malloc(sizeof(avl_tree_t)); if (tree != NULL){tree->root = NULL;} return tree; } void avl_tree_free(avl_tree_t *tree) { avl_tree_node_t *last;avl_tree_node_t *node;avl_tree_node_t *oneNodePtr; if(tree->root == NULL){free(tree);return ;} last = NULL;node = tree->root; while(node != NULL) { if(last == node->parent) { last = node; if(node->left != NULL){node = node->left;} else { if(node->right != NULL){node = node->right;} else{oneNodePtr = node;node = node->parent;avl_tree_node_free(oneNodePtr);} } } else if(last == node->left) { last = node; if(node->right != NULL){node = node->right;} else{oneNodePtr = node;node = node->parent;avl_tree_node_free(oneNodePtr);} } else if(last == node->right) { last = node;oneNodePtr = node;node = node->parent;avl_tree_node_free(oneNodePtr); } } free(tree);return ; } void avl_tree_one_rotateRight(avl_tree_t *tree, avl_tree_node_t *node) { avl_tree_node_t *left;left = node->left; if(node->parent == NULL){tree->root = left;} else {if(node->parent->left == node){node->parent->left = left;}else {node->parent->right = left;}} left->parent = node->parent;node->left = left->right;if(left->right != NULL){left->right->parent = node;} left->right = node;node->parent = left; if(left->balance >= 0){node->balance += 1;}else {node->balance += ( 1 - left->balance);} if(node->balance >= 0){left->balance += ( 1 + node->balance);}else{left->balance += 1;} node->count = node->dataVec.count; if(node->left != NULL){node->count += node->left->count;} if(node->right != NULL){node->count += node->right->count;} left->count = left->dataVec.count; if(left->left != NULL){left->count += left->left->count;} if(left->right != NULL){left->count += left->right->count;} } void avl_tree_one_rotateLeft(avl_tree_t *tree, avl_tree_node_t *node) { avl_tree_node_t *right;right = node->right; if(node->parent == NULL){tree->root = right;} else {if(node->parent->left == node){node->parent->left = right;}else {node->parent->right = right;}} right->parent = node->parent;node->right = right->left;if(right->left != NULL){right->left->parent = node;} right->left = node;node->parent = right; if(right->balance >= 0){node->balance -= ( 1 + right->balance);}else {node->balance -= 1;} if(node->balance >= 0){right->balance -= 1;}else{right->balance -= ( 1 - node->balance);} node->count = node->dataVec.count; if(node->left != NULL){node->count += node->left->count;} if(node->right != NULL){node->count += node->right->count;} right->count = right->dataVec.count; if(right->left != NULL){right->count += right->left->count;} if(right->right != NULL){right->count += right->right->count;} } void avl_tree_two_rotateLeftRight(avl_tree_t *tree, avl_tree_node_t *node) {avl_tree_one_rotateLeft(tree, node->left);avl_tree_one_rotateRight(tree, node);} void avl_tree_two_rotateRightLeft(avl_tree_t *tree, avl_tree_node_t *node) {avl_tree_one_rotateRight(tree, node->right);avl_tree_one_rotateLeft(tree, node);} void avl_tree_balance(avl_tree_t *tree, avl_tree_node_t *node) { if(node->balance == -1 || node->balance == 0 || node->balance == 1){return ;} if(node->balance < -1) { if(node->left->balance == 1){avl_tree_two_rotateLeftRight(tree, node);}else{avl_tree_one_rotateRight(tree, node);} return ; } if(node->balance > 1) { if(node->right->balance == -1){avl_tree_two_rotateRightLeft(tree, node);}else{avl_tree_one_rotateLeft(tree, node);} return ; } } avl_tree_node_t * avl_tree_search(avl_tree_t *tree, void *data, avl_tree_node_t **parentPtr, int *rank) { int result;avl_tree_node_t *node; if(data == NULL){return NULL;} if(tree->root == NULL){return NULL;} node = tree->root; while(node != NULL) { result = compareData(node->data,data); if(result == 0) { if(rank != NULL) { if(node->left == NULL){*rank = (*rank + node->dataVec.count);} else{*rank = (*rank + (node->left->count+node->dataVec.count));} } return node; } else if(result > 0){if(parentPtr != NULL){*parentPtr = node;}node = node->left;} else { if(rank != NULL) { if(node->left == NULL){*rank = (*rank + node->dataVec.count);} else{*rank = (*rank + (node->left->count+node->dataVec.count));} } if(parentPtr != NULL){*parentPtr = node;}node = node->right; } } return NULL; } avl_tree_node_t * avl_tree_first_upper_equal_search(avl_tree_t *tree, void *data) { int result;avl_tree_node_t *node;avl_tree_node_t *last; if(data == NULL){return NULL;} if(tree->root == NULL){return NULL;} node = tree->root;last = NULL; while(node != NULL) { result = compareData(node->data,data); if(result == 0){return node;}else if(result > 0){last = node;node = node->left;}else{node = node->right;} } return last; } avl_tree_node_t * avl_tree_last_lower_equal_search(avl_tree_t *tree, void *data) { int result;avl_tree_node_t *node;avl_tree_node_t *last; if(data == NULL){return NULL;} if(tree->root == NULL){return NULL;} node = tree->root;last = NULL; while(node != NULL) { result = compareData(node->data,data); if(result == 0){return node;}else if(result > 0){node = node->left;}else{last = node;node = node->right;} } return last; } avl_tree_node_t * avl_tree_insert(