AVL树--C语言实现

/************************************************************************
 *                        AVL树 demo程序                                
 * Version:1.0    实现insert函数                                        
 * nizqsut 2009.1019 00:04                            
 *                                                                     
 ************************************************************************/
#include
#include

#include "avl_tree.h"
#include "fatal.h"

static avl_tree make_empty(avl_tree t){

    if (t != NULL) {
        if (t->left != NULL) {
            t->left = make_empty(t->left);
        }
        if (t->right != NULL) {
            t->right = make_empty(t->right);
        }
        free(t);
    }

    return NULL;
}

static avl_pos find(avl_element_type element, avl_tree t){

    if (NULL == t) {
        return NULL;
    }

    if (element < t->element) {
        return find(element,t->left);
    }else if (element > t->element) {
        return find(element,t->right);
    }

    return t;
}

static avl_pos find_min(avl_tree t){
    if (NULL == t) {
        return NULL;
    }

    if (NULL == t->left) {
        return t;
    }else{
        return find_min(t->left);
    }
}

static avl_pos find_max(avl_tree t){

    if (NULL != t) {
        while (t->right != NULL) {
            t = t->right;
        }
    }

    return t;
}

static int high(avl_pos p){
    if (p == NULL) {
        return -1;
    }else{
        return p->high;
    }
}

/************************************************************************/
/* This function can be called only if k2 has a left child              */
/* Perform a rotate between a node(k2) and its left child               */
/* Update heights, then return new root                                 */
/************************************************************************/
static avl_pos single_rotate_with_left(avl_tree k2){

    avl_pos k1;

    k1 = k2->left;
    k2->left = k1->right;
    k1->right = k2;
    
    //k2->high = max(k2->left->high,k2->right->high) + 1;
    //k1->high = max(k1->left->high, k2->high) + 1;
    k2->high = max( high(k2->left), high(k2->right) ) + 1;
    k1->high = max( high(k1->left),k2->high ) + 1;
    return k1;
}

static avl_pos single_rotate_with_right(avl_tree k1){

    avl_pos k2;

    k2 = k1->right;

    k1->right = k2->left;
    k2->left = k1;

    //k1->high = max(k1->left->high, k1->right->high) + 1;
    //k2->high = max(k1->high, k2->right->high) + 1;
    k1->high = max( high(k1->left), high(k1->right) ) + 1;
    k2->high = max( k1->high, high(k2->right) ) + 1;

    return k2;
}

static avl_pos double_rotate_with_left(avl_tree k3){

    /* rotate between k1 and k2 */
    k3->left = single_rotate_with_right(k3->left);

    /* rotate between k3 and k2*/
    return single_rotate_with_left(k3);
}

static avl_pos double_rotate_with_right(avl_tree k1){

    /* rotate between k3 and k2 */
    k1->right = single_rotate_with_left(k1->right);

    /* rotate between k1 and k2 */
    return single_rotate_with_right(k1);

}

static avl_tree insert(avl_element_type element, avl_tree t){
   
    if (NULL == t) {
        if ( (t = malloc(sizeof(*t))) == NULL) {
            Error("Out of space!");
            return NULL;
        }
        t->element = element;
        t->right = t->left = NULL;
        t->high = 0;
    }else
    if (element < t->element) {
        t->left = insert(element,t->left);
        //if ( (t->left->high - t->right->high) == 2){
        if ( (high(t->left) - high(t->right)) == 2) {
            if (element < t->left->element) {
                t = single_rotate_with_left(t);
            }else{
                t = double_rotate_with_left(t);
            }
        }
    }else
    if (element > t->element) {
        t->right = insert(element,t->right);
        //if ( (t->right->high - t->left->high) == 2) {
        if ( (high(t->right) - high(t->left)) == 2) {
            if (element > t->right->element) {
                t = single_rotate_with_right(t);
            }else{
                t = double_rotate_with_right(t);
            }
        }
    }else{
        //The element ready is the tree.
        //Do nothing.
    }

    //t->high = max(t->left->high,t->right->high) + 1;
    t->high = max( high(t->left), high(t->right) ) + 1;
    return t;
}

static void visit_t(avl_pos t,int high){
    //if (t) {
    while (high--) {
        printf("\t");
    }
    printf("element = %d, high = %d.\n",t->element,t->high);
    //}else{
    //    Error("NULL Pointer used.");
    //}
}

static void pre_order(avl_tree t,
               void (*visit)(avl_pos t, int high),
               int high)
{

    if (t == NULL) {
        return;
    }
    visit(t,high);

    if (t->left != NULL) {
        pre_order(t->left, visit, high+1);
    }
   
    //visit(t->element,high);

    if (t->right != NULL) {
        pre_order(t->right, visit, high+1);
    }

    return;
}

static int s_tree[] = {3,2,1,4,5,6,7,16,15,14,13,12,11,10,8};

void avl_tree_test(void){

    avl_tree t = NULL;
    int i;

    for (i = 0; i < sizeof(s_tree)/sizeof(s_tree[0]); i++) {
        if ( (t = insert(s_tree[i],t)) == NULL ) {
            Error("Insert error!\n");
            return;
        }
        printf("\t-------------------------------------\n");
        pre_order(t,visit_t,0);
        printf("\t-------------------------------------\n");
    }
    pre_order(t,visit_t,0);
    printf("\n\n");

    //tree_delete(2,t);
    //pre_order(t,visit_t,0);

    return;
}