#include <stdlib.h>
#include <string.h>
#include <stdio.h>
#include "bistree.h"
static void destroy_right(BisTree *tree, BiTreeNode *node);
static int insert(BisTree *tree, BiTreeNode **node,const void *data,int *balanced);
BiTree *tree_ptr;
BiTreeNode *node_ptr;
int *bal_ptr;
void *key_ptr;
void main()
{
tree_ptr=(BiTree *)malloc(sizeof(BiTree));
bistree_init(tree_ptr,key_ptr,0);
insert(tree_ptr,node_ptr,3,bal_ptr);
printf("this: %d",tree_ptr->root);
}
//--------------------------rotate_left--------------------------------
static void rotate_left(BiTreeNode **node){
BiTreeNode *left, *grandchild;
left = bitree_left(*node);
if(((AvlNode *)bitree_data(left))->factor == AVL_LFT_HEAVY){
//perform an LL rotation
bitree_left(*node) = bitree_right(left);
bitree_right(left) = *node;
((AvlNode *)bitree_data(*node))->factor = AVL_BALANCED;
((AvlNode *)bitree_data(left))->factor = AVL_BALANCED;
*node = left;
}
else{
//perform an LR rotation
grandchild = bitree_right(left);
bitree_right(left) = bitree_left(grandchild);
bitree_left(grandchild) = left;
bitree_left(*node) = bitree_right(grandchild);
bitree_right(grandchild) = *node;
switch(((AvlNode * )bitree_data(grandchild))->factor) {
case AVL_LFT_HEAVY:
((AvlNode *)bitree_data(*node))->factor = AVL_RGT_HEAVY;
((AvlNode *)bitree_data(left))->factor = AVL_BALANCED;
break;
case AVL_BALANCED:
((AvlNode *)bitree_data(*node))->factor = AVL_BALANCED;
((AvlNode *)bitree_data(left))->factor = AVL_BALANCED;
break;
case AVL_RGT_HEAVY:
((AvlNode *)bitree_data(*node))->factor = AVL_BALANCED;
((AvlNode *)bitree_data(left))->factor = AVL_LFT_HEAVY;
break;
}
((AvlNode *)bitree_data(grandchild))->factor = AVL_BALANCED;
*node = grandchild;
}
return;
}
//--------------------------- rotate_right -------------------------------------
static void rotate_right(BiTreeNode **node){
BiTreeNode *right, *grandchild;
right = bitree_right(*node);
if(((AvlNode *)bitree_data(right))->factor == AVL_RGT_HEAVY){
//perform an RR rotation
bitree_right(*node) = bitree_left(right);
bitree_left(right) = *node;
((AvlNode *)bitree_data(* node))->factor = AVL_BALANCED;
((AvlNode *)bitree_data(right))->factor = AVL_BALANCED;
*node = right;
}
else{
//perform an RL rotation
grandchild = bitree_left(right);
bitree_left(right) = bitree_right(grandchild);
bitree_right(grandchild) = right;
bitree_right(*node) = bitree_left(grandchild);
bitree_left(grandchild) = *node;
switch(((AvlNode * )bitree_data(grandchild))->factor) {
case AVL_LFT_HEAVY:
((AvlNode *)bitree_data(*node))->factor = AVL_BALANCED;
((AvlNode *)bitree_data(right))->factor = AVL_RGT_HEAVY;
break;
case AVL_BALANCED:
((AvlNode *)bitree_data(*node))->factor = AVL_BALANCED;
((AvlNode *)bitree_data(right))->factor = AVL_BALANCED;
break;
case AVL_RGT_HEAVY:
((AvlNode *)bitree_data(*node))->factor = AVL_LFT_HEAVY;
((AvlNode *)bitree_data(right))->factor = AVL_BALANCED;
break;
}
((AvlNode *)bitree_data(grandchild))->factor = AVL_BALANCED;
*node = grandchild;
}
return;
}
//------------------------destroy_left------------------------------
static void destroy_left(BisTree *tree, BiTreeNode *node){
BiTreeNode **position;
//do not allow destructoin of an empty tree
if(bitree_size(tree)==0)
return;
//determine where to destroy nodes
if(node==NULL)
position = &tree->root;
else
position = &node->left;
//destroy the nodes
if(*position != NULL){
destroy_left(tree, *position);
destroy_right(tree, *position);
if(tree->destroy !=NULL){
//call a user-defined function to tree dynamically allocated data
tree->destroy(((AvlNode *)(*position)->data)->data);
}
//Free the AVL data in the node, then free the node itself
free((*position)->data);
free(*position);
*position = NULL;
//adjust the size of the tree to account for the destroyed node
tree->size--;
}
return;
}
//------------------------destroy_right------------------------------
static void destroy_right(BisTree *tree, BiTreeNode *node){
BiTreeNode **position;
//do not allow destructoin of an empty tree
if(bitree_size(tree)==0)
return;
//determine where to destroy nodes
if(node==NULL)
position = &tree->root;
else
position = &node->right;
//destroy the nodes
if(*position != NULL){
destroy_left(tree, *position);
destroy_right(tree, *position);
if(tree->destroy !=NULL){
//call a user-defined function to tree dynamically allocated data
tree->destroy(((AvlNode *)(*position)->data)->data);
}
//Free the AVL data in the node, then free the node itself
free((*position)->data);
free(*position);
*position = NULL;
//adjust the size of the tree to account for the destroyed node
tree->size--;
}
return;
}
//------------------------insert---------------------
static int insert(BisTree *tree, BiTreeNode **node, const void *data, int *balanced){
AvlNode *avl_data;
int cmpval, retval;
//insert the data into the tree
if(bitree_is_eob(*node)){
//Handle insertion into an empty tree
if((avl_data = (AvlNode *)malloc(sizeof(AvlNode))) == NULL)
return -1;
avl_data->factor = AVL_BALANCED;
avl_data->hidden = 0;
avl_data->data = (void *)data;
return bitree_ins_left(tree, *node, avl_data);
}
else{
//Handle insertion into a tree that is not empty
cmpval = tree->compare(data, ((AvlNode *)bitree_data(*node))->data);
if(cmpval <0){
//Move to the left
if(bitree_is_eob(bitree_left(*node))){
if((avl_data = (AvlNode *)malloc(sizeof(AvlNode))) == NULL)
return -1;
avl_data->factor = AVL_BALANCED;
avl_data->hidden = 0;
avl_data->data = (void *)data;
if (bitree_ins_left(tree, *node, avl_data) != 0)
return -1;
*balanced = 0;
}
else{
if((retval = insert(tree, &bitree_left(*node), data, balanced))!=0){
return retval;
}
}
//ensure that the tree remains balanced
if(!(*balanced)){
switch (((AvlNode *)bitree_data(*node))->factor){
case AVL_LFT_HEAVY:
rotate_left(node);
*balanced = 1;
break;
case AVL_BALANCED:
((AvlNode *)bitree_data(* node))->factor = AVL_LFT_HEAVY;
break;
case AVL_RGT_HEAVY:
((AvlNode *)bitree_data(*node))->factor = AVL_BALANCED;
*balanced = 1;
}
}
}
else if (cmpval > 0) {
//move to the right
if(bitree_is_eob(bitree_right(*node))){
if((avl_data = (AvlNode *)malloc(sizeof(AvlNode))) == NULL)
return -1;
avl_data->factor = AVL_BALANCED;
avl_data->hidden = 0;
avl_data->data = (void *)data;
if (bitree_ins_right(tree, *node, avl_data) != 0)
return -1;
*balanced = 0;
}
else{
if((retval = insert(tree, &bitree_right(*node), data, balanced))!=0){
return retval;
}
}
//ensure that the tree remains balanced
if(!(*balanced)){
switch (((AvlNode *)bitree_data(*node))->factor){
case AVL_LFT_HEAVY:
((AvlNode *)bitree_data(* node))->factor = AVL_BALANCED;
*balanced = 1;
break;
case AVL_BALANCED:
((AvlNode *)bitree_data(* node))->factor = AVL_RGT_HEAVY;
break;
case AVL_RGT_HEAVY:
rotate_right(node);
*balanced = 1;
}
}
} //if (cmpval >0)
else {
//Handle finding a copy of the data
if(!((AvlNode *)bitree_data(*node))->hidden){
//Do nothing since the data is in the tree and not hidden
return 1;
}
else{
//Insert the new data and mark it is being replaced
if(tree->destroy != NULL){
//destroy the hidden data since it is being replaced
tree->destroy(((AvlNode *)bitree_data(*node))->data);
}
((AvlNode *)bitree_data(*node))->data = (void *)data;
((AvlNode *)bitree_data(*node))->hidden = 0;
//Do not rebalanced because the tree structure is unchange
*balanced = 1;
}
}
}
return 0;
}
// --------------------------- hide -------------------
static int hide(BisTree *tree, BiTreeNode *node, const void *data){
int cmpval, retval;
if(bitree_is_eob(node)){
//Return that the data was not found
return -1;
}
cmpval = tree->compare(data, ((AvlNode *)bitree_data(node))->data);
if (cmpval < 0){
// move to the left
retval = hide(tree, bitree_left(node), data);
}
else if (cmpval >0){
//move to the right
retval = hide(tree, bitree_right(node), data);
}
else{
// Mark the node as hidden
((AvlNode *)bitree_data(node))->hidden =1;
retval = 0;
}
return retval;
}
// ------------------------ look up ---------------------
static int lookup(BisTree *tree, BiTreeNode *node, void **data){
int cmpval,retval;
if(bitree_is_eob(node)){
// Return that the data was not found
return -1;
}
cmpval = tree->compare(*data, ((AvlNode *)bitree_data(node))->data);
if(cmpval < 0){
//Move to the left
retval = lookup(tree,bitree_left(node),data);
}
else if (cmpval >0){
//Move to the right
retval = lookup(tree,bitree_right(node),data);
}
else{
if(!((AvlNode *)bitree_data(node))->hidden){
// Pass back the data from the tree
*data = ((AvlNode *)bitree_data(node))->data;
retval = 0;
}
else{
//Return that the data was not found
return -1;
}
}
return retval;
}
// ---------------------- bistree_init ------------------
void bistree_init(BisTree *tree, int (*compare)(const void *key1,
const void *key2),void(*destroy)(void *data)){
// Initialize the tree
bitree_init(tree, destroy);
tree->compare = compare;
return;
}
// ------------------------bistree_sedtory-------------------------
void bistree_destroy(BisTree *tree){
//destroy all nodes in the tree
destroy_left(tree, NULL);
// no operation are allowed now, but clear the structure as a precaution
memset(tree, 0, sizeof(BisTree));
return;
}
//------------------------ bistree_insert-----------------------
int bistree_insert(BisTree *tree, const void *data) {
int balanced = 0;
return insert(tree, &bitree_root(tree), data, &balanced);
}
//-------------------------bistree_remove--------------------------
int bistree_remove(BisTree *tree, const void *data){
return hide(tree, bitree_root(tree), data);
}
//-------------------------bistree_lookup-------------------------
int bistree_lookup(BisTree *tree, void **data){
return lookup(tree, bitree_root(tree), data);
}
#include <string.h>
#include <stdio.h>
#include "bistree.h"
static void destroy_right(BisTree *tree, BiTreeNode *node);
static int insert(BisTree *tree, BiTreeNode **node,const void *data,int *balanced);
BiTree *tree_ptr;
BiTreeNode *node_ptr;
int *bal_ptr;
void *key_ptr;
void main()
{
tree_ptr=(BiTree *)malloc(sizeof(BiTree));
bistree_init(tree_ptr,key_ptr,0);
insert(tree_ptr,node_ptr,3,bal_ptr);
printf("this: %d",tree_ptr->root);
}
//--------------------------rotate_left--------------------------------
static void rotate_left(BiTreeNode **node){
BiTreeNode *left, *grandchild;
left = bitree_left(*node);
if(((AvlNode *)bitree_data(left))->factor == AVL_LFT_HEAVY){
//perform an LL rotation
bitree_left(*node) = bitree_right(left);
bitree_right(left) = *node;
((AvlNode *)bitree_data(*node))->factor = AVL_BALANCED;
((AvlNode *)bitree_data(left))->factor = AVL_BALANCED;
*node = left;
}
else{
//perform an LR rotation
grandchild = bitree_right(left);
bitree_right(left) = bitree_left(grandchild);
bitree_left(grandchild) = left;
bitree_left(*node) = bitree_right(grandchild);
bitree_right(grandchild) = *node;
switch(((AvlNode * )bitree_data(grandchild))->factor) {
case AVL_LFT_HEAVY:
((AvlNode *)bitree_data(*node))->factor = AVL_RGT_HEAVY;
((AvlNode *)bitree_data(left))->factor = AVL_BALANCED;
break;
case AVL_BALANCED:
((AvlNode *)bitree_data(*node))->factor = AVL_BALANCED;
((AvlNode *)bitree_data(left))->factor = AVL_BALANCED;
break;
case AVL_RGT_HEAVY:
((AvlNode *)bitree_data(*node))->factor = AVL_BALANCED;
((AvlNode *)bitree_data(left))->factor = AVL_LFT_HEAVY;
break;
}
((AvlNode *)bitree_data(grandchild))->factor = AVL_BALANCED;
*node = grandchild;
}
return;
}
//--------------------------- rotate_right -------------------------------------
static void rotate_right(BiTreeNode **node){
BiTreeNode *right, *grandchild;
right = bitree_right(*node);
if(((AvlNode *)bitree_data(right))->factor == AVL_RGT_HEAVY){
//perform an RR rotation
bitree_right(*node) = bitree_left(right);
bitree_left(right) = *node;
((AvlNode *)bitree_data(* node))->factor = AVL_BALANCED;
((AvlNode *)bitree_data(right))->factor = AVL_BALANCED;
*node = right;
}
else{
//perform an RL rotation
grandchild = bitree_left(right);
bitree_left(right) = bitree_right(grandchild);
bitree_right(grandchild) = right;
bitree_right(*node) = bitree_left(grandchild);
bitree_left(grandchild) = *node;
switch(((AvlNode * )bitree_data(grandchild))->factor) {
case AVL_LFT_HEAVY:
((AvlNode *)bitree_data(*node))->factor = AVL_BALANCED;
((AvlNode *)bitree_data(right))->factor = AVL_RGT_HEAVY;
break;
case AVL_BALANCED:
((AvlNode *)bitree_data(*node))->factor = AVL_BALANCED;
((AvlNode *)bitree_data(right))->factor = AVL_BALANCED;
break;
case AVL_RGT_HEAVY:
((AvlNode *)bitree_data(*node))->factor = AVL_LFT_HEAVY;
((AvlNode *)bitree_data(right))->factor = AVL_BALANCED;
break;
}
((AvlNode *)bitree_data(grandchild))->factor = AVL_BALANCED;
*node = grandchild;
}
return;
}
//------------------------destroy_left------------------------------
static void destroy_left(BisTree *tree, BiTreeNode *node){
BiTreeNode **position;
//do not allow destructoin of an empty tree
if(bitree_size(tree)==0)
return;
//determine where to destroy nodes
if(node==NULL)
position = &tree->root;
else
position = &node->left;
//destroy the nodes
if(*position != NULL){
destroy_left(tree, *position);
destroy_right(tree, *position);
if(tree->destroy !=NULL){
//call a user-defined function to tree dynamically allocated data
tree->destroy(((AvlNode *)(*position)->data)->data);
}
//Free the AVL data in the node, then free the node itself
free((*position)->data);
free(*position);
*position = NULL;
//adjust the size of the tree to account for the destroyed node
tree->size--;
}
return;
}
//------------------------destroy_right------------------------------
static void destroy_right(BisTree *tree, BiTreeNode *node){
BiTreeNode **position;
//do not allow destructoin of an empty tree
if(bitree_size(tree)==0)
return;
//determine where to destroy nodes
if(node==NULL)
position = &tree->root;
else
position = &node->right;
//destroy the nodes
if(*position != NULL){
destroy_left(tree, *position);
destroy_right(tree, *position);
if(tree->destroy !=NULL){
//call a user-defined function to tree dynamically allocated data
tree->destroy(((AvlNode *)(*position)->data)->data);
}
//Free the AVL data in the node, then free the node itself
free((*position)->data);
free(*position);
*position = NULL;
//adjust the size of the tree to account for the destroyed node
tree->size--;
}
return;
}
//------------------------insert---------------------
static int insert(BisTree *tree, BiTreeNode **node, const void *data, int *balanced){
AvlNode *avl_data;
int cmpval, retval;
//insert the data into the tree
if(bitree_is_eob(*node)){
//Handle insertion into an empty tree
if((avl_data = (AvlNode *)malloc(sizeof(AvlNode))) == NULL)
return -1;
avl_data->factor = AVL_BALANCED;
avl_data->hidden = 0;
avl_data->data = (void *)data;
return bitree_ins_left(tree, *node, avl_data);
}
else{
//Handle insertion into a tree that is not empty
cmpval = tree->compare(data, ((AvlNode *)bitree_data(*node))->data);
if(cmpval <0){
//Move to the left
if(bitree_is_eob(bitree_left(*node))){
if((avl_data = (AvlNode *)malloc(sizeof(AvlNode))) == NULL)
return -1;
avl_data->factor = AVL_BALANCED;
avl_data->hidden = 0;
avl_data->data = (void *)data;
if (bitree_ins_left(tree, *node, avl_data) != 0)
return -1;
*balanced = 0;
}
else{
if((retval = insert(tree, &bitree_left(*node), data, balanced))!=0){
return retval;
}
}
//ensure that the tree remains balanced
if(!(*balanced)){
switch (((AvlNode *)bitree_data(*node))->factor){
case AVL_LFT_HEAVY:
rotate_left(node);
*balanced = 1;
break;
case AVL_BALANCED:
((AvlNode *)bitree_data(* node))->factor = AVL_LFT_HEAVY;
break;
case AVL_RGT_HEAVY:
((AvlNode *)bitree_data(*node))->factor = AVL_BALANCED;
*balanced = 1;
}
}
}
else if (cmpval > 0) {
//move to the right
if(bitree_is_eob(bitree_right(*node))){
if((avl_data = (AvlNode *)malloc(sizeof(AvlNode))) == NULL)
return -1;
avl_data->factor = AVL_BALANCED;
avl_data->hidden = 0;
avl_data->data = (void *)data;
if (bitree_ins_right(tree, *node, avl_data) != 0)
return -1;
*balanced = 0;
}
else{
if((retval = insert(tree, &bitree_right(*node), data, balanced))!=0){
return retval;
}
}
//ensure that the tree remains balanced
if(!(*balanced)){
switch (((AvlNode *)bitree_data(*node))->factor){
case AVL_LFT_HEAVY:
((AvlNode *)bitree_data(* node))->factor = AVL_BALANCED;
*balanced = 1;
break;
case AVL_BALANCED:
((AvlNode *)bitree_data(* node))->factor = AVL_RGT_HEAVY;
break;
case AVL_RGT_HEAVY:
rotate_right(node);
*balanced = 1;
}
}
} //if (cmpval >0)
else {
//Handle finding a copy of the data
if(!((AvlNode *)bitree_data(*node))->hidden){
//Do nothing since the data is in the tree and not hidden
return 1;
}
else{
//Insert the new data and mark it is being replaced
if(tree->destroy != NULL){
//destroy the hidden data since it is being replaced
tree->destroy(((AvlNode *)bitree_data(*node))->data);
}
((AvlNode *)bitree_data(*node))->data = (void *)data;
((AvlNode *)bitree_data(*node))->hidden = 0;
//Do not rebalanced because the tree structure is unchange
*balanced = 1;
}
}
}
return 0;
}
// --------------------------- hide -------------------
static int hide(BisTree *tree, BiTreeNode *node, const void *data){
int cmpval, retval;
if(bitree_is_eob(node)){
//Return that the data was not found
return -1;
}
cmpval = tree->compare(data, ((AvlNode *)bitree_data(node))->data);
if (cmpval < 0){
// move to the left
retval = hide(tree, bitree_left(node), data);
}
else if (cmpval >0){
//move to the right
retval = hide(tree, bitree_right(node), data);
}
else{
// Mark the node as hidden
((AvlNode *)bitree_data(node))->hidden =1;
retval = 0;
}
return retval;
}
// ------------------------ look up ---------------------
static int lookup(BisTree *tree, BiTreeNode *node, void **data){
int cmpval,retval;
if(bitree_is_eob(node)){
// Return that the data was not found
return -1;
}
cmpval = tree->compare(*data, ((AvlNode *)bitree_data(node))->data);
if(cmpval < 0){
//Move to the left
retval = lookup(tree,bitree_left(node),data);
}
else if (cmpval >0){
//Move to the right
retval = lookup(tree,bitree_right(node),data);
}
else{
if(!((AvlNode *)bitree_data(node))->hidden){
// Pass back the data from the tree
*data = ((AvlNode *)bitree_data(node))->data;
retval = 0;
}
else{
//Return that the data was not found
return -1;
}
}
return retval;
}
// ---------------------- bistree_init ------------------
void bistree_init(BisTree *tree, int (*compare)(const void *key1,
const void *key2),void(*destroy)(void *data)){
// Initialize the tree
bitree_init(tree, destroy);
tree->compare = compare;
return;
}
// ------------------------bistree_sedtory-------------------------
void bistree_destroy(BisTree *tree){
//destroy all nodes in the tree
destroy_left(tree, NULL);
// no operation are allowed now, but clear the structure as a precaution
memset(tree, 0, sizeof(BisTree));
return;
}
//------------------------ bistree_insert-----------------------
int bistree_insert(BisTree *tree, const void *data) {
int balanced = 0;
return insert(tree, &bitree_root(tree), data, &balanced);
}
//-------------------------bistree_remove--------------------------
int bistree_remove(BisTree *tree, const void *data){
return hide(tree, bitree_root(tree), data);
}
//-------------------------bistree_lookup-------------------------
int bistree_lookup(BisTree *tree, void **data){
return lookup(tree, bitree_root(tree), data);
}
출처 - c로 구현한 알고리즘 한빛미디어
