平衡二叉树定义(AVL)：它或者是一颗空树，或者具有以下性质的二叉树：它的左子树和右子树的深度之差的绝对值不超过1，且它的左子树和右子树都是一颗平衡二叉树。
平衡因子(bf)：结点的左子树的深度减去右子树的深度，那么显然-1<=bf<=1;
很显然，平衡二叉树是在二叉排序树(BST)上引入的，就是为了解决二叉排序树的不平衡性导致时间复杂度大大下降，那么AVL就保持住了(BST)的最好时间复杂度O(logn)，所以每次的插入和删除都要确保二叉树的平衡
变换规则：
插入实例：
{4， 5 ，7， 2， 1， 3， 6}
实现代码：
#include <stdio.h>#include <stdlib.h>
typedef struct avl_tree{ int data; /*存储数据*/ int height; /*树的深度*/ struct avl_tree* ltree; /*指向左子树*/ struct avl_tree* rtree; /*指向右子树*/}avl_tree_s;
static inline int min(int a, int b){ return (a < b ? a : b);}
static inline int max(int a, int b){ return (a > b ? a : b);}
/*返回节点的平衡度*/static inline int height(avl_tree_s* pNode){ if (NULL == pNode) return -1;return pNode->height;
}/******************************************************************** pNode pNode->ltree / \ pNode->ltree => pNode \ / pNode->ltree->rtree pNode->ltree->rtree *********************************************************************/static avl_tree_s* _rotate_single_left(avl_tree_s* pNode){ avl_tree_s* pNode1;
pNode1 = pNode->ltree;
pNode->ltree = pNode1->rtree; pNode1->rtree = pNode;/*结点的位置变了, 要更新结点的高度值*/
pNode->height = max(height(pNode->ltree), height(pNode->rtree)) + 1; pNode1->height = max(height(pNode1->ltree), pNode->height) + 1;return pNode1;
}/********************************************************************
pNode pNode->rtree \ / pNode->rtree ==> pNode / \ pNode->rtree->ltree pNode->rtree->ltree *********************************************************************/static avl_tree_s* _rotate_single_right(avl_tree_s* pNode){ avl_tree_s* pNode1;pNode1 = pNode->rtree;
pNode->rtree = pNode1->ltree; pNode1->ltree = pNode;/*结点的位置变了, 要更新结点的高度值*/
pNode->height = max(height(pNode->ltree), height(pNode->rtree)) + 1; pNode1->height = max(height(pNode1->rtree), pNode->height) + 1;return pNode1;
}static avl_tree_s* _rotate_double_left(avl_tree_s* pNode)
{ pNode->ltree = _rotate_single_right(pNode->ltree);return _rotate_single_left(pNode);
}static avl_tree_s* _rotate_double_right(avl_tree_s* pNode)
{ pNode->rtree = _rotate_single_left(pNode->rtree);return _rotate_single_right(pNode);
}/* 递归找到最小值 */
avl_tree_s *avl_tree_min(avl_tree_s * p) { if(p == NULL) { return NULL; } else if(p->ltree == NULL) { return p; } else { return avl_tree_min(p->ltree); }}/* 递归找到最大值 */
avl_tree_s *avl_tree_max(avl_tree_s *p) { if(p == NULL) { return NULL; } else if(p->rtree == NULL) { return p; } else { return avl_tree_max(p->rtree); }}avl_tree_s *avl_tree_clear(avl_tree_s *p)
{ if(p != NULL) { avl_tree_clear(p->ltree); avl_tree_clear(p->rtree); free(p); } return NULL; }avl_tree_s* avl_tree_balance(int data, avl_tree_s* p)
{ if (height(p->ltree) - height(p->rtree) == 2) /*AVL树不平衡*/ { if (data < p->ltree->data) { /*插入到了左子树左边, 做单旋转*/ p = _rotate_single_left(p); } else { /*插入到了左子树右边, 做双旋转*/ p = _rotate_double_left(p); } } else if (height(p->rtree) - height(p->ltree) == 2) /*AVL树不平衡*/ { if (data > p->rtree->data) { /*插入到了右子树右边, 做单旋转*/ p = _rotate_single_right(p); } else { /*插入到了右子树左边, 做双旋转*/ p = _rotate_double_right(p); } } else {}
return p;
}avl_tree_s* avl_tree_insert(int data, avl_tree_s* pNode)
{ if (NULL == pNode) { pNode = (avl_tree_s*)malloc(sizeof(avl_tree_s)); pNode->data = data; pNode->height = 0; pNode->ltree = pNode->rtree = NULL; } else if (data < pNode->data) /*插入到左子树中*/ { pNode->ltree = avl_tree_insert(data, pNode->ltree); pNode = avl_tree_balance(data, pNode); } else if (data > pNode->data) /*插入到右子树中*/ { pNode->rtree = avl_tree_insert(data, pNode->rtree); pNode = avl_tree_balance(data, pNode); } else {}
/*取左右子树中最大的深度，然后再加上1就是自己的深度*/
pNode->height = max(height(pNode->ltree), height(pNode->rtree)) + 1;return pNode;
}avl_tree_s *avl_tree_delete(int data, avl_tree_s *pNode)
{ avl_tree_s * node; if(pNode == NULL) { printf("No found!\n"); } else if(data < pNode->data) /* Go left */ { pNode->ltree = avl_tree_delete(data, pNode->ltree); pNode->height = max(height(pNode->ltree), height(pNode->rtree)) + 1; pNode = avl_tree_balance(data, pNode); } else if(data > pNode->data) /* Go Right */ { pNode->rtree = avl_tree_delete(data, pNode->rtree); pNode->height = max(height(pNode->ltree), height(pNode->rtree)) + 1; pNode = avl_tree_balance(data, pNode); } else /* Find node to be deleted */ { if(pNode->ltree && pNode->rtree) /* 2 children */ { /* Replace with smallest in right subtree */ node = avl_tree_min(pNode->rtree); pNode->data = node->data; pNode->rtree = avl_tree_delete(pNode->data, pNode->rtree); pNode->height = max(height(pNode->ltree), height(pNode->rtree)) + 1; pNode = avl_tree_balance(data, pNode); } else /* One or zero children */ { node = pNode; if(pNode->ltree == NULL) /* Also handles 0 children */ { pNode = pNode->rtree; } else if(pNode->rtree == NULL) { pNode = pNode->ltree; } free(node); } } return pNode; } /*中序遍历打印树的所有结点*/void avl_tree_printf(avl_tree_s* pRoot){ if (NULL == pRoot) return;avl_tree_printf(pRoot->ltree);
printf("%d ", pRoot->data); avl_tree_printf(pRoot->rtree);}avl_tree_s * avl_tree_find(int data, avl_tree_s * pRoot)
{ if (NULL == pRoot) { return NULL; }if(data < pRoot->data)
{ return avl_tree_find(data, pRoot->ltree); } else if(data > pRoot->data) { return avl_tree_find(data, pRoot->rtree); } else { return pRoot; }}int main(int argc, char * argv[])
{ int data; avl_tree_s* pRoot = NULL;srand((unsigned int)time(NULL));
unsigned int i = 0;
for(i = 0; i < 10; ++i) { data = rand()%100; printf("%d ", data); pRoot = avl_tree_insert(data, pRoot); } printf("\n");avl_tree_printf(pRoot);
char buf[10]; while(1) { printf("\n****************************************"); printf("\n* +number to insert :"); printf("\n* -number to delete :"); printf("\n* q to quit :"); printf("\n****************************************\n"); fgets(buf, sizeof(buf), stdin);if(buf[0] == 'q')
{ break; } else if(buf[0] == '+') { pRoot = avl_tree_insert(atoi(&buf[1]), pRoot); } else if(buf[0] == '-') { pRoot = avl_tree_delete(atoi(&buf[1]), pRoot); } else { continue; }avl_tree_printf(pRoot);
}pRoot = avl_tree_clear(pRoot);
return 0;
}