最近几月一直在自学C语言和数据结构，先是写了排序二叉树，觉得平衡二叉树作为一个经典数据结构，有必要实现一下。
?
网上看了些资料，在AVL和红黑树之间考虑，最后个人还是倾向于AVL。
?
不同于标准AVL的是，笔者没有使用平衡因子，直接根据左右孩子的高度差值判断是否平衡。整个平衡二叉树是在普通二叉查找树的基础上修改得到的，对于学习数据结构的同学来说，这样逐步提高难度，写起来挑战性没那么大。
?
代码经测试是可以运行，并实现插入、删除、修改节点时都可以保持平衡。相对于普通二叉查找树，AVL在查找时效率高耗时短，但为了保持高度平衡，必须牺牲插入和删除操作的复杂度。本文将分步讲解如何编写平衡二叉树，全文最后附有完整代码。
?
当左右子树的高度差超过1时（即≥2，在实际处理时，等于2即为不平衡，进行调整操作，所以不会出现大于2的情况），整棵树失去平衡。写代码之前先了解AVL是如何使二叉树保持平衡，这里涉及到对节点的旋转操作，分四种情况，左左，右右，左右，右左。下面分别解释：
?
一、左左单旋转
?
在节点x的左孩子插入节点b
?
①x无右孩子，旋转节点a即可达到平衡
?
②x有右孩子c，旋转节点a后，根据a>c>x，需将节点c移动到a的左子树
?
?
?
函数代码如下：
?
复制代码
?1 static BTNode *singleRotateLL(BTree *BT, BTNode *phead)
?2 {//不平衡情况为左左的单旋转操作
?3 ? ? BTNode *temp;
?4?
?5 ? ? if(phead == NULL)
?6 ? ? ? ? return 0;
?7?
?8 ? ? temp = phead->lchild;
?9 ? ??
10 ? ? if(temp->rchild != NULL){
11 ? ? ? ? phead->lchild = temp->rchild;
12 ? ? ? ? phead->lchild->height = tree_node_height(BT, phead->lchild);
13 ? ? }
14 ? ? else
15 ? ? ? ? phead->lchild = NULL;
16?
17 ? ? temp->rchild = phead;
18 ? ? if(temp->rchild->data == BT->phead->data){
19 ? ? ? ? BT->phead = temp;
20 ? ? }
21 ? ? phead = temp;
22 ? ? temp->rchild->height = tree_node_height(BT, temp->rchild);
23 ? ? temp->height = tree_node_height(BT, temp);
24 ? ? phead->height = tree_node_height(BT, phead);
25 ? ??
26 ? ? return phead;
27 }
复制代码
二、右右单旋转
?
在节点x的右孩子插入节点b
?
①x无左孩子，旋转节点a即可达到平衡
?
②x有左孩子c，旋转节点a后，根据x>c>a，需将节点c移动到a的右子树
?
?
?
函数代码如下：
?
复制代码
?1 static BTNode *singleRotateRR(BTree *BT, BTNode *phead)
?2 {//不平衡情况为右右的单旋转操作
?3 ? ? BTNode *temp;
?4?
?5 ? ? if(phead == NULL)
?6 ? ? ? ? return 0;
?7?
?8 ? ? temp = phead->rchild;
?9?
10 ? ? if(temp->lchild != NULL){
11 ? ? ? ? phead->rchild = temp->lchild;
12 ? ? ? ? phead->rchild->height = tree_node_height(BT, phead->rchild);
13 ? ? }
14 ? ? else
15 ? ? ? ? phead->rchild = NULL;
16?
17 ? ? temp->lchild = phead;
18 ? ? if(temp->lchild->data == BT->phead->data){
19 ? ? ? ? BT->phead = temp;
20 ? ? }
21 ? ? phead = temp;
22 ? ? temp->lchild->height = tree_node_height(BT, temp->lchild);
23 ? ? temp->height = tree_node_height(BT, temp);
24 ? ? phead->height = tree_node_height(BT, phead);
25?
26 ? ? return phead;
27 }
复制代码
注：需要注意的是节点旋转后，节点赋值和高度的更新，初学者很容易忽略或是弄错赋值顺序
?
三、左右双旋转
?
在节点x的右孩子插入节点b
?
①x无左孩子，②x有左孩子c，这两种情况的处理相同，首先对x节点进行右右单旋转操作，然后对a节点进行左左单旋转操作
?
?
?
函数代码如下：
?
复制代码
?1 static BTNode *doubleRotateLR(BTree *BT, BTNode *phead)
?2 {//不平衡情况为左右的双旋转操作
?3 ? ? BTNode *temp;
?4?
?5 ? ? if(phead == NULL)
?6 ? ? ? ? return 0;
?7?
?8 ? ? temp = phead->lchild; ? ?
?9 ? ? phead->lchild = singleRotateRR(BT, temp);
10 ? ? temp = phead;
11 ? ? phead = singleRotateLL(BT, temp);
12?
13 ? ? return phead;
14 }
复制代码
四、右左双旋转
?
在节点x的右孩子插入节点b
?
①x无右孩子，②x有右孩子c，这两种情况的处理相同，首先对x节点进行左左单旋转操作，然后对a节点进行右右单旋转操作
?
?
?
函数代码如下：
?
复制代码
?1 static BTNode *doubleRotateRL(BTree *BT, BTNode *phead)
?2 {//不平衡情况为右左的双旋转操作
?3 ? ? BTNode *temp;
?4?
?5 ? ? if(phead == NULL)
?6 ? ? ? ? return 0;
?7?
?8 ? ? temp = phead->rchild;
?9 ? ? phead->rchild = singleRotateLL(BT, temp);
10 ? ? temp = phead;
11 ? ? phead = singleRotateRR(BT, temp);
12?
13 ? ? return phead;