本文内容是关于：平衡二叉搜索树，AVL Tree。

在《二叉搜索树(BST)的实现（C语言）》一文中，我们给出了一般二叉搜索树(BST)的实现。

BST在面对一些特殊数据的时候，性能会大幅下降，例如用一个有序序列构造BST的时候，BST将退
化为一个单链表，其查找时间将由O(logn)退化为O(N)。

平衡二叉树（AVL树）的基本借口和BST一致，
只是在实现中，对于每次的数据插入和数据删除，都在普通插入和删除算法的基础上加入了调整策略，
使得树一致保持平衡，从而比BST有更高的效率。 

下面是根据《数据结构教程（第2版）》（清华大学出版社）一书中的讲解实现的AVL树的源码，
其基本算法和BST的实现一致。但是AVL的树节点多了一个字段_bf，它表示每个节点的平衡因子，在
AVL树的插入和删除过程中，需要进行LL、LR、RL、RR调整，使得每个节点的平衡因子_bf总是-1, 0, 1
三个值中的一个，从而保持树的平衡。这些调整策略在代码中做了一些注释，这里不再一一说明。 

源码一共有三个文件，其中avltree.h是AVL数据结构和函数借口，avltree.c是AVL函数的实现,
main.c是测试文件。

/*
 * File : avltree.h
 * Purpose : impementation of AVL Tree
 * Language : C
 * Compiler : VC 6.0
 * Author : puresky
 * Date: 2011/05/07
 */

#ifndef _AVL_TREE_H
#define _AVL_TREE_H

// AVL Tree Node struct
typedef struct _AVLTreeNode AVLTreeNode;
struct _AVLTreeNode
{
    int _key;      //key
    void *_data;   //data
    int _bf;       // balance factor
    struct _AVLTreeNode *_left, *_right; //left child and right child
};

// AVL Tree Struct
typedef struct _AVLTree AVLTree;
struct _AVLTree
{
    AVLTreeNode *_root;
    int _count;
};

//To create AVLTree struct, return a pointer to the new AVLTree
AVLTree *avltree_new();

//To free AVLTree struct
void avltree_free(AVLTree *avlt);

//To find a AVLTreeNode with key in the AVLTree
//return the AVLTreeNode found or NULL
AVLTreeNode *avltree_find(AVLTree *avlt, int key);

//To insert a key-data pair into the AVLTree
//return 1 if inserting successfully, otherwize 0
int avltree_insert(AVLTree *avlt, int key, void *data);

//To remove a AVLTreeNode with key from the AVLTree
//return 1 if removing successfully, otherwize 0
int avltree_remove(AVLTree *avlt, int key);

//To get the number of elements in the AVLTree
//In fact, the AVLTree->_count
int avltree_size(AVLTree *avlt);

//To get the height of the AVLTree
int avltree_height(AVLTree *avlt);

//To check if the AVLTree is empty
//return 1 if the AVLTree is empty, otherwize 0
int avltree_empty(AVLTree *avlt);

//To print the information of the AVLTree
void avltree_print(AVLTree *avlt);

#endif

/*
 * File : avltree.c
 * Purpose : impementation of AVL Tree
 * Language : C
 * Compiler : VC 6.0
 * Author : puresky
 * Date: 2011/05/07
 */

#include <stdio.h>
#include <stdlib.h>
#include "avltree.h"

#define DO_INSERT_ADJUST 1
#define DO_REMOVE_ADJUST 1

#define MAX(a, b) (a > b ? a : b)

//To create a AVLTreeNode
//return a pointer to the AVLTreeNode
static AVLTreeNode *avltree_node_new(int key, void *data)
{
    AVLTreeNode *avltn = (AVLTreeNode *)malloc(sizeof(AVLTreeNode));
    avltn->_key = key;
    avltn->_data = data;
    avltn->_bf = 0;
    avltn->_left = NULL;
    avltn->_right = NULL;
    //fprintf(stdout, "To create AVLTreeNode: %d\n", avltn->_key);
    return avltn;
}
//To free the AVLTreeNode itself
static void avltree_node_free(AVLTreeNode *avltn)
{
    if(avltn)
    {
        //fprintf(stdout, "To free AVLTreeNode: %d\n", avltn->_key);
        free(avltn);
    }
}
//To free the AVLTreeNode and its children recursively
static void avltree_node_free_recursively(AVLTreeNode *avltn)
{
    if(avltn)
    {
        avltree_node_free_recursively(avltn->_left);
        avltree_node_free_recursively(avltn->_right);
        avltree_node_free(avltn);
    }
}

//To find a AVLTreeNode by key
//return the AVLTreeNode found or NULL
static AVLTreeNode *avltree_node_find(AVLTreeNode *avltn, int key)
{
    if(avltn == NULL)
        return NULL;

    if(avltn->_key == key)
    {
        return avltn;
    }
    else if(avltn->_key > key && avltn->_left)
    {
        return avltree_node_find(avltn->_left, key);
    }
    else if(avltn->_key < key && avltn->_right)
    {
        return avltree_node_find(avltn->_right, key);
    }
    else
    {
        return NULL;
    }
}
// Insert==========================================
static void LL_Adjust(AVLTreeNode **pavltn)
{
    AVLTreeNode *avltn = *pavltn;
    AVLTreeNode *lchild = avltn->_left;
    fprintf(stdout, "LL\n");
    avltn->_left = lchild->_right;
    lchild->_right = avltn;

    *pavltn = lchild;
}

static void LR_Adjust(AVLTreeNode **pavltn)
{
    AVLTreeNode *avltn = *pavltn;
    AVLTreeNode *lchild = avltn->_left;
    AVLTreeNode *lrchild = lchild->_right;
    fprintf(stdout, "LR\n");
    avltn->_left = lrchild->_right;
    lrchild->_right = avltn;
    lchild->_right = lrchild->_left;
    lrchild->_left = lchild;

    *pavltn = lrchild;
}

static void RL_Adjust(AVLTreeNode **pavltn)
{
    AVLTreeNode *avltn = *pavltn;
    AVLTreeNode *rchild = avltn->_right;
    AVLTreeNode *rlchild = rchild->_left;
    fprintf(stdout, "RL\n");
    avltn->_right = rlchild->_left;
    rlchild->_left = avltn;
    rchild->_left = rlchild->_right;
    rlchild->_right = rchild;

    *pavltn = rlchild;

}

static void RR_Adjust(AVLTreeNode **pavltn)
{
    AVLTreeNode *avltn = *pavltn;
    AVLTreeNode *rchild = avltn->_right;
    fprintf(stdout, "RR\n");
    avltn->_right = rchild->_left;
    rchild->_left = avltn;

    *pavltn = rchild;
}

static void left_adjust(AVLTreeNode **pavltn, int *changed)
{
    //A node inserted into the left subtree of the node [avltn]
    AVLTreeNode *avltn = *pavltn;
    AVLTreeNode *lchild;
    AVLTreeNode *lrchild;
    if(DO_INSERT_ADJUST == 0) return;
    if(avltn->_bf == 0)
    {
        //Before insertion the current node's balance factor which is zero means that
        //the height of left and right child is equal.
        //After insertion the height of the left child increase by 1. So
        //the balance factor of the current node [avltn] should increase by 1.
        avltn->_bf = 1;
        *changed = 1; //To indicate that the heigth of [avltn] is changed!
    }
    else if(avltn->_bf == -1)
    {
        //Before insertion the balance factor is -1 means that the height of the left
        //child is less than the height of the right child by 1.
        //After insertion the heigth of the left child increase by 1.
        //Now the heigth of the left child and the right child is equal.
        //So the balance factor needs setting to zero.
        avltn->_bf = 0;
        *changed = 0; //To indicate the heigth of [avltn] is not changed
    }
    else //avltn->_bf == 1
    {
        //Here avltn->_bf is equal to 1. So after the heigth of the left child
        //increase by 1, the balance of avltn will be 2.There is a unbalanced
        //node.We have to adjust the tree at once!
        lchild = avltn->_left;
        lrchild = lchild->_right;

        if(lchild->_bf == 1)
        {
            //The height of the lchild 's left child is greater than the height
            //of its right child by 1. So a LL-Ajust should be done!
            LL_Adjust(pavltn);
           
            avltn->_bf = 0;
            lchild->_bf = 0;
        }
        else if(lchild->_bf == -1)
        {
            //the height of the lchild 's left child is less than the height of
            //its right child by 1, So a LR-Adjust should be done!
            LR_Adjust(pavltn);

            if(lrchild->_bf == 0)
            {
                avltn->_bf = 0;
                lchild->_bf = 0;
            }
            else if(lrchild->_bf == 1)
            {
                lchild->_bf = 0;
                avltn->_bf = -1;
            }
            else //lrchild->_bf == -1
            {
                lchild->_bf = 1;
                avltn->_bf = 0;
            }
        }
        else //lchild->_bf
        {
            //This is impossible case, if the balanced factor is zero.
            //Its parent doesn't need adjusting!
        }
        *changed = 0;//After adjusting, there is no need to do more adjustment!
    }
}

static void right_adjust(AVLTreeNode **pavltn, int *changed)
{
    //A node inserted into the right subtree of the node [avltn]
    //The right_adjust and the left_adjust are completely symmetrical!
    AVLTreeNode *avltn = *pavltn;
    AVLTreeNode *rchild;
    AVLTreeNode *rlchild;
   
    if(DO_INSERT_ADJUST == 0) return;

    if(avltn->_bf == 0)
    {
        avltn->_bf = -1;
        *changed = 1;
    }
    else if(avltn->_bf == 1)
    {
        avltn->_bf = 0;
        *changed = 0;
    }
    else //avltn->_bf == -1
    {
        rchild = avltn->_right;
        rlchild = rchild->_left;
        if(rchild->_bf == -1)
        {
            RR_Adjust(pavltn);
           
            avltn->_bf = 0;
            rchild->_bf = 0;
        }
        else if(rchild->_bf = 1)
        {
            RL_Adjust(pavltn);
           
            if(rlchild->_bf == 0)
            {
                avltn->_bf = 0;
                rchild->_bf = 0;
            }
            else if(rlchild->_bf == -1)
            {
                rchild->_bf = 0;
                avltn->_bf = 1;
            }
            else //lrchild->_bf == 1
            {
                rchild->_bf = -1;
                avltn->_bf = 0;
            }
        }
        else
        {
            //impossible case
        }
        *changed = 0;
    }
}

//To insert the Key-Data pair into the AVLTreeNode
//return 1 if insert successfully, otherwize 0.[eg: the key is already in the
//Tree]
static int avltree_node_insert(AVLTreeNode **pavltn, int key, void *data,
                               int *changed)
{
    AVLTreeNode *ptr;
    if(*pavltn == NULL)
    {
        *pavltn = avltree_node_new(key, data);
        (*pavltn)->_bf = 0;
        *changed = 1;
        return 1;
    }
    else
    {
        ptr = *pavltn;
        if(ptr->_key == key)
        {
            *changed = 0;
            return 0;
        }
        else if(ptr->_key > key)
        {
            if(avltree_node_insert(&ptr->_left, key, data, changed) == 0)
                return 0;
            if(*changed == 1)
                left_adjust(pavltn, changed);
        }
        else
        {
            if(avltree_node_insert(&ptr->_right, key, data, changed) == 0)
                return 0;
            if(*changed == 1)
                right_adjust(pavltn , changed);

        }
        return 1;
    }
}


// Remove=========================================
static void left_adjust2(AVLTreeNode **pavltn, int *changed)
{
    //A node removed from the left subtree of the node [avltn]
    AVLTreeNode *avltn = *pavltn;
    AVLTreeNode *rchild;
    AVLTreeNode *rlchild;
    if(DO_REMOVE_ADJUST == 0) return;
   
    if(avltn->_bf == 1)
    {
        //The height of the left child is greater than the right child
        //by 1. After deletion, the balance factor will be zero.
        //But the height of [avltn] will decrease by 1.
        //So we set the [changed] to be 1 so as to adjust its parent!
        avltn->_bf = 0;
        *changed = 1;
    }
    else if(avltn->_bf == 0)
    {
        //The height of the left child is equal to the right child.
        //After deletion, the balance factor will be -1 and the height
        //of the [avltn] will have no change.So there is no need to
        //adjust its parent!Therefore, let the changed be zero!
        avltn->_bf = -1;
        *changed = 0;
    }
    else //avltn->_bf == -1
    {
        //the height of the left child is less than the right child by 1.
        //After deletion, the balance factor will be -2. So we should
        //do some adjust to the Tree!
        rchild = avltn->_right;
        rlchild = rchild->_left;
        if(rchild->_bf == 0)
        {
            RR_Adjust(pavltn);
            avltn->_bf = -1;
            rchild->_bf = 1;
            *changed = 0;
        }
        else if(rchild->_bf == -1)
        {
            RR_Adjust(pavltn);
            avltn->_bf = 0;
            rchild->_bf  = 0;
            *changed = 1;
        }
        else //rchild->_bf == 1
        {
            RL_Adjust(pavltn);
            if(rlchild->_bf == 0)
            {
                avltn->_bf = 0;
                rchild->_bf = 0;
                rlchild->_bf = 0;
            }
            else if(rlchild->_bf == -1)
            {
                avltn->_bf = 1;
                rchild->_bf = 0;
                rlchild->_bf = 0;
            }
            else //rlchild->_bf == 1
            {
                avltn->_bf = 0;
                rchild->_bf = -1;
                rlchild->_bf = 0;
            }
            *changed = 1;
        }
    }
}

static void right_adjust2(AVLTreeNode **pavltn, int *changed)
{
    //A node removed from the right subtree of the node [avltn]
    //The right_adjust2 and the left_adjust2 are completely symmetrical!
    AVLTreeNode *avltn = *pavltn;
    AVLTreeNode *lchild;
    AVLTreeNode *lrchild;
    if(DO_REMOVE_ADJUST == 0) return;

    if(avltn->_bf == -1)
    {
        avltn->_bf = 0;
        *changed = 1;
    }
    else if(avltn->_bf == 0)
    {
        avltn->_bf = 1;
        *changed = 0;
    }
    else //avltn->_bf == 1
    {
        lchild = avltn->_left;
        lrchild = lchild->_right;
        if(lchild->_bf == 0)
        {
            LL_Adjust(pavltn);
            avltn->_bf = 1;
            lchild->_bf = -1;
            *changed = 0;
        }
        else if(lchild->_bf == 1)
        {
            LL_Adjust(pavltn);
            avltn->_bf = 0;
            lchild->_bf = 0;
            *changed = 1;
        }
        else //rchild->_bf == -1
        {
            LR_Adjust(pavltn);
            if(lrchild->_bf == 0)
            {
                avltn->_bf = 0;
                lchild->_bf = 0;
                lrchild->_bf = 0;
            }
            else if(lrchild->_bf == 1)
            {
                avltn->_bf = -1;
                lchild->_bf = 0;
                lrchild->_bf = 0;
            }
            else //lrchild->_bf == -1
            {
                avltn->_bf = 0;
                lchild->_bf = 1;
                lrchild->_bf = 0;
            }
            *changed = 1;
        }
    }
}
static void avltree_node_remove_left_max(AVLTreeNode **pavltn, AVLTreeNode *toRemove, int *changed)
{
    int key;
    void *data;
    AVLTreeNode *avltn = *pavltn;
    if(avltn->_right == NULL)
    {
        key = toRemove->_key;
        data = toRemove->_data;
        toRemove->_key = avltn->_key;
        toRemove->_data = avltn->_data;

        avltn->_key = key;
        toRemove->_data = avltn->_data;
        *pavltn = avltn->_left;
        avltree_node_free(avltn);
        *changed = 1;
    }
    else
    {
        avltree_node_remove_left_max(&avltn->_right, toRemove, changed);
        if(*changed == 1)
            right_adjust2(pavltn, changed);
    }
}
static int avltree_node_remove(AVLTreeNode **pavltn, int key, int *changed)
{
    AVLTreeNode *ptr = *pavltn;
    if(ptr == NULL)
    {
        return 0;
    }

    if(ptr->_key > key)
    {
        if(avltree_node_remove(&ptr->_left, key, changed) == 0)
            return 0;
        if(*changed == 1)
            left_adjust2(pavltn, changed);
    }
    else if(ptr->_key < key)
    {
        if(avltree_node_remove(&ptr->_right, key, changed) == 0)
            return 0;
        if(*changed == 1)
            right_adjust2(pavltn, changed);
    }
    else //ptr->_key == key
    {
       
        if(ptr->_left == NULL)
        {
            *pavltn = ptr->_right;
            avltree_node_free(ptr);
        }
        else if(ptr->_right == NULL)
        {
            *pavltn = ptr->_left;
            avltree_node_free(ptr);
        }
        else //ptr->_left != NULL && ptr->_right != NULL
        {
            avltree_node_remove_left_max(&ptr->_left, ptr, changed);
            if(*changed == 1)
                left_adjust2(pavltn, changed);
        }
    }
    return 1;
}

static void avltree_node_print_recursively(AVLTreeNode * avltn, int depth)
{
    int i;
    for(i = 0; i < depth; ++i)
        fprintf(stdout, "  ");
    if(avltn)
    {
        fprintf(stdout, "%d[%d]\n", avltn->_key, avltn->_bf);
        avltree_node_print_recursively(avltn->_left, depth + 1);
        avltree_node_print_recursively(avltn->_right, depth + 1);
    }
    else
    {
        fprintf(stdout, "NULL\n");
    }
}

int avltree_node_height(AVLTreeNode *avltn)
{
    int a, b;
    if(avltn == NULL)
    {
        return 0;
    }
    else
    {
        a = avltree_node_height(avltn->_left);
        b = avltree_node_height(avltn->_right);
        return MAX(a, b) + 1;
    }
}

AVLTree *avltree_new()
{
    AVLTree *avlt = (AVLTree *)malloc(sizeof(AVLTree));
    avlt->_count = 0;
    avlt->_root = NULL;
    return avlt;
}
void avltree_free(AVLTree *avlt)
{
    if(avlt)
    {
        avltree_node_free_recursively(avlt->_root);
        free(avlt);
    }
}

AVLTreeNode *avltree_find(AVLTree *avlt, int key)
{
    return avltree_node_find(avlt->_root, key);
}

int avltree_insert(AVLTree *avlt, int key, void *data)
{
    int changed = 0; //for adjusting
    int ret = avltree_node_insert(&avlt->_root, key, data, &changed);
    if(ret) avlt->_count++;
    return ret;
}

int avltree_remove(AVLTree *avlt, int key)
{
    int changed = 0;//for adjusting
    int ret = avltree_node_remove(&avlt->_root, key, &changed);
    if(ret) avlt->_count--;
    return ret;
}
int avltree_size(AVLTree *avlt)
{
    return avlt->_count;
}
int avltree_height(AVLTree *avlt)
{
    return avltree_node_height(avlt->_root);
}
int avltree_empty(AVLTree *avlt)
{
    if(avlt->_root == NULL)
        return 1;
    return 0;
}
void avltree_print(AVLTree *avlt)
{
    printf("-----------------------------------------------\n");
    printf("size:%d, height:%d\n", avlt->_count, avltree_height(avlt));
    avltree_node_print_recursively(avlt->_root, 0);
}
 

/*
 * File : main.c
 */

#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include "avltree.h"

void findx(AVLTree *avlt, int n)
{
    AVLTreeNode *avltn = avltree_find(avlt, n);
    if(avltn)
    {
        printf("%d is found\n", avltn->_key);
    }
    else
    {
        printf("%d not found\n", n);
    }

}

void test_insert(int nCase)
{
    int i, a, b, c, d;
    AVLTree *avlt = avltree_new();
    for(i = 0; i < nCase; ++i)
    {
        avltree_insert(avlt, rand() % nCase, NULL);
        avltree_print(avlt);
    }

    printf("=========================================\n");

    a = rand() % nCase;
    b = rand() % nCase;
    c = rand() % nCase;
    d = rand() % nCase;
    findx(avlt, a);
    findx(avlt, b);
    findx(avlt, c);
    findx(avlt, d);
    avltree_remove(avlt, a);
    avltree_remove(avlt, b);
    avltree_remove(avlt, c);
    avltree_remove(avlt, d);
    findx(avlt, a);
    findx(avlt, b);
    findx(avlt, c);
    findx(avlt, d);
    avltree_print(avlt);
    avltree_free(avlt);
}


int main(int argc, char **argv)
{
    srand(time(NULL));
    test_insert(32);
    system("pause");
    return 0;
}