大二的时候数据结构课死活没看懂的一个东东，看了2小时，敲了2小时，调了2小时。。。

平衡树某一节点的左右子树高度相差大于1的时候即需要调整，调整可分为四中情况 ll,rr,lr,rl其中lr,rl是由不同顺序的ll,rr来实现的，代码比想象的简短。

一棵平衡的树只有在插入和删除节点的时候，才会变的不平衡，所以掌握好时机，判断平衡是否破坏及不平衡的种类，再纠正即可

 

代码如下。。

 

avl.h

struct AVLNode {    struct AVLNode *left;    struct AVLNode *right;    int data;    int height;};static const int AVL_STATUS_OK = 0;static const int AVL_STATUS_FOUNDED = 1;static const int AVL_STATUS_NOTFOUNDED = 2;static const int AVL_STATUS_FAILED = -1;int avl_insert(struct AVLNode **root, int data);int avl_find(struct AVLNode *root, int data);int avl_del(struct AVLNode **root, int data);int avl_del_tree(struct AVLNode *root);void print_avl_tree(struct AVLNode *root);int _get_height(struct AVLNode *node);int _max(int a, int b);void _single_rotate_left(struct AVLNode **node);void _single_rotate_right(struct AVLNode **node);void _double_rotate_left_right(struct AVLNode **node);void _double_rotate_right_left(struct AVLNode **node);

　

 

avl.c

#include 
     
      #include 
      
       #include 
       
        #include "avl.h"int avl_insert(struct AVLNode **ptr_root, int data) {    int ret;    if(NULL == *ptr_root) {        *ptr_root = malloc(sizeof(struct AVLNode));        if(NULL == *ptr_root) {            return AVL_STATUS_FAILED;        }        (*ptr_root)->data = data;        (*ptr_root)->left = NULL;        (*ptr_root)->right = NULL;        (*ptr_root)->height = 0;        return AVL_STATUS_OK;    }    if(data == (*ptr_root)->data) {        return AVL_STATUS_OK;    }    else if(data < (*ptr_root)->data) {        ret = avl_insert(&((*ptr_root)->left), data);        if(_get_height((*ptr_root)->left) - _get_height((*ptr_root)->right) > 1){            if(data < (*ptr_root)->left->data){                _single_rotate_left(ptr_root);            }            else {                _double_rotate_left_right(ptr_root);            }        }    }    else {        ret = avl_insert(&((*ptr_root)->right), data);        if(_get_height((*ptr_root)->right) - _get_height((*ptr_root)->left) > 1){            if(data > (*ptr_root)->right->data) {                _single_rotate_right(ptr_root);            }            else {                _double_rotate_right_left(ptr_root);            }        }    }    (*ptr_root)->height = _max(_get_height((*ptr_root)->left), _get_height((*ptr_root)->right)) + 1;    return ret;}int avl_find(struct AVLNode *root, int data) {    if(NULL == root) {        return AVL_STATUS_NOTFOUNDED;    }    if(data == root->data) {        return AVL_STATUS_FOUNDED;    }    if(data < root->data) {        return avl_find(root->left, data);    }    else {        return avl_find(root->right, data);    }}int avl_del(struct AVLNode **root, int data) {    struct AVLNode *t;    if(*root == NULL) {        return AVL_STATUS_OK;    }    if(data < (*root)->data) {        avl_del(&((*root)->left), data);        if(_get_height((*root)->right) - _get_height((*root)->left) > 1){            if((*root)->right->left != NULL && (_get_height((*root)->right->left) > _get_height((*root)->right->right))) {                _double_rotate_right_left(root);            }            else {                _single_rotate_right(root);            }        }    }    else if(data > (*root)->data) {        avl_del(&((*root)->right), data);        if(_get_height((*root)->left) - _get_height((*root)->right) > 1){            if((*root)->left->right != NULL && (_get_height((*root)->left->right) > _get_height((*root)->left->left))) {                _double_rotate_left_right(root);            }            else {                _single_rotate_left(root);            }        }    }    else {        if(NULL != (*root)->left && NULL != (*root)->right) {            t = (*root) -> right;            while(t->left != NULL) {                t = t->left;            }            (*root) -> data = t->data;            avl_del(&((*root)->right), t->data);            if(_get_height((*root)->left) - _get_height((*root)->right) > 1){            if((*root)->left->right != NULL && (_get_height((*root)->left->right) > _get_height((*root)->left->left))) {                _double_rotate_left_right(root);            }            else {                _single_rotate_left(root);            }        }        }        else {            t = *root;            if((*root)->left == NULL) {                *root = (*root) -> right;            }            else if((*root)->right == NULL) {                *root = (*root) -> left;            }            free(t);        }    }    return AVL_STATUS_OK;}int avl_del_tree(struct AVLNode *root) {    if(NULL == root) {        return AVL_STATUS_OK;    }    avl_del_tree(root->left);    avl_del_tree(root->right);    free(root);    return AVL_STATUS_OK;}int _get_height(struct AVLNode *node) {    if(NULL == node){        return -1;    }    else{        return node->height;    }}int _max(int a, int b) {    return a > b ? a:b;}void _single_rotate_left(struct AVLNode **node) {    struct AVLNode* root = *node;    *node = root->left;    root->left = (*node)->right;    (*node)->right = root;    root->height = _max(_get_height(root->left), _get_height(root->right)) + 1;    (*node)->height = _max(_get_height((*node)->left), _get_height((*node)->right)) + 1;}void _single_rotate_right(struct AVLNode **node) {    struct AVLNode* root = *node;    *node = root->right;    root->right = (*node)->left;    (*node)->left = root;    root->height = _max(_get_height(root->left), _get_height(root->right)) + 1;    (*node)->height = _max(_get_height((*node)->left), _get_height((*node)->right)) + 1;}void _double_rotate_left_right(struct AVLNode **node) {    struct AVLNode* root = *node;    _single_rotate_right(&(root->left));    _single_rotate_left(node);}void _double_rotate_right_left(struct AVLNode **node) {    struct AVLNode* root = *node;    _single_rotate_left(&(root->right));    _single_rotate_right(node);}void print_avl_tree(struct AVLNode *node) {    if(NULL == node) {        return;    }    print_avl_tree(node->left);    printf("%d\t%d\n", node->data, node->height);    print_avl_tree(node->right);}
       
      
     

　　

 

main.c

#include 
     
      #include "avl.h"int main() {    struct AVLNode *root = NULL;    int ret = avl_insert(&root, 7);    printf("hello, world\n");    printf("root:address %ld\n", (long)root);    printf("after:%d\n", 7);    print_avl_tree(root);    avl_insert(&root, 6);    printf("after:%d\n", 6);    print_avl_tree(root);    avl_insert(&root, 5);    printf("after:%d\n", 5);    print_avl_tree(root);    avl_insert(&root, 7);    printf("after:%d\n", 7);    print_avl_tree(root);    avl_insert(&root, 1);    printf("after:%d\n", 1);    print_avl_tree(root);    avl_insert(&root, 0);    printf("after:%d\n", 0);    print_avl_tree(root);    avl_insert(&root, 9);    printf("after:%d\n", 9);    print_avl_tree(root);    ret = avl_find(root, 7);    printf("find 7 result is %d\n", ret);    ret = avl_find(root, 17);    printf("find 17 result is %d\n", ret);    ret = avl_del(&root, 7);    printf("del 7 result is %d\n", ret);    print_avl_tree(root);    ret = avl_del(&root, 17);    printf("del 17 result is %d\n", ret);    print_avl_tree(root);    avl_del_tree(root);    return 0;}
     

　　

#gcc -g main.c avl.c -o main

#./main

hello, world

root:address 27951120

after:7

7 0

after:6

6 0

7 1

after:5

5 0

6 1

7 0

after:7

5 0

6 1

7 0

after:1

1 0

5 1

6 2

7 0

after:0

0 0

1 1

5 0

6 2

7 0

after:9

0 0

1 1

5 0

6 2

7 1

9 0

find 7 result is 1

find 17 result is 2

del 7 result is 0

0 0

1 1

5 0

6 2

9 0

del 17 result is 0

0 0

1 1

5 0

6 2

9 0

 

应该是正确的。