AVL树呢，是平衡树中一个非常经典的例子。因为普通的查找树在插入和删除的过程有可能会产生树的一端子树高度比另一边大很多的情况，也就是所谓的退化为链表（查找是一个一个节点去找），降低了查找的效率。
AVL平衡树通过一系列旋转的方式让左子树和右子树的高度相差不大（<=1），这样搜索的效率将会维持在较好的水平。
方法就是当插入一个节点之后，
更新父节点的高度，判断父节点的左右子树高度差是否为2,若是，进行相应旋转操作（4种）来降低左右子树高度差。若不是，判断父节点的父的左右子树高度差是否为2，以此类推，直到根节点（当然是递归中完成）。
单左旋，单右旋，左右旋，右左旋就是将3个节点间调整次序来，代码如下，具体样子就不画图了，在这些点调节次序的过程中，我们可以发现搜索树节点大小顺序还是正常排列的。
也就是中序遍历的结果还是1234567这样从小到大排列。
#include<stdio.h>
#include<stdlib.h>
#include"avl_tree.h"
static Position SingleRotateWithLeft(Position K2);
static Position DoubleRotateWithLeft(Position K3);
static Position SingleRotateWithRight(Position K2);
static Position DoubleRotateWithRight(Position K3);
static int Height (Position P);
static Position SingleRotateWithLeft(Position K2)
{
// puts("右旋");
Position K1;
K1=K2->Left;
K2->Left=K1->Right;
K1->Right=K2;
K2->Height=Max(Height(K2->Left),Height(K2->Right))+1;
K1->Height=Max(Height(K1->Left),K2->Height)+1;
return K1;
}
static Position DoubleRotateWithLeft(Position K3)
{
//puts("左右");
K3->Left=SingleRotateWithRight(K3->Left);
return SingleRotateWithLeft(K3);
}
static Position SingleRotateWithRight(Position K2)
{
/*
1
0 2 k2
4 k1
5
1
0 4 k1
2 5
*/
// puts("单左旋");
Position K1;
K1=K2->Right;
K2->Right=K1->Left;
K1->Left=K2;
K2->Height=Max(Height(K2->Left),Height(K2->Right))+1;
K1->Height=Max(Height(K1->Left),K2->Height)+1;
return K1;
}
static Position DoubleRotateWithRight(Position K3)
{
// puts("右左");
/*
//120534
1 1 1
0 2 k3 --》 0 2 --》 0 3
5 k3->right 3 2 5
3 5
*/
K3->Right=SingleRotateWithLeft(K3->Right);
return SingleRotateWithRight(K3);
}
void InOrder(AvlTree T)
{
if(T!=NULL){
InOrder(T->Left);
printf("%d\n",T->Element);
InOrder(T->Right);
}
}
void PostOrder(AvlTree T)
{
if(T!=NULL){
PostOrder(T->Left);
PostOrder(T->Right);
printf("%d\n",T->Element);
}
}
void PreOrder_2(AvlTree T,int depth)
{
if(T!=NULL){
for (int i = 0; i < depth; i++)
printf("\t");
printf("%d\n",T->Element);
PreOrder_2(T->Left,depth+1);
PreOrder_2(T->Right,depth+1);
}
}
void InOrder_2(AvlTree T,int depth)
{
if(T!=NULL){
InOrder_2(T->Left,depth+1);
for (int i = 0; i < depth; i++)
printf("\t");
printf("%d\n",T->Element);
InOrder_2(T->Right,depth+1);
}
}
int PostOrder_2(AvlTree T,int depth)
{
int retSize;
int retSize2;
if(T!=NULL){
retSize=PostOrder_2(T->Left,depth+1);
retSize2=PostOrder_2(T->Right,depth+1);
for (int i = 0; i < depth; i++)
printf("\t");
printf("%d(%d)\n",T->Element,T->Element+retSize+retSize2);
return retSize2+retSize+T->Element;
}else{
return 0;
}
}
void PreOrder(AvlTree T)
{
if(T!=NULL){
printf("%d\n",T->Element);
PreOrder(T->Left);
PreOrder(T->Right);
}
}
AvlTree MakeEmpty(AvlTree T)
{
//后序
if(T!=NULL){
MakeEmpty(T->Left);
MakeEmpty(T->Right);
free(T);
}
return NULL;
}
static int Height (Position P)
{
if(P==NULL)
return -1;
else
return P->Height;
}
Position Find(ElementType X,AvlTree T)
{
if(T==NULL)
return NULL;
if(X<T->Element)
return Find(X,T->Left);
else if(X>T->Element)
return Find(X,T->Right);
else
return T;
}
AvlTree Insert(ElementType X,AvlTree T)
{
if(T==NULL){
T=malloc(sizeof(struct AvlNode));
if(T==NULL){
fprintf(stderr,"Out of space");
return NULL;
}
else{
T->Element=X;
T->Height=0;
T->Left=T->Right=NULL;
}
//放在左（递归）
}
else if(X<T->Element){
// printf("%d<%d\n",X,T->Element);
T->Left=Insert(X,T->Left);
if(Height(T->Left)-Height(T->Right)==2)
//左左->单右旋
if(X<T->Left->Element)
T=SingleRotateWithLeft(T);
//左右->双右左旋
else
T=DoubleRotateWithLeft(T);
}
else if(X>T->Element){
T->Right=Insert(X,T->Right);
if(Height(T->Right)-Height(T->Left)==2)
if(X>T->Right->Element){
T=SingleRotateWithRight(T);
}
else {
T=DoubleRotateWithRight(T);
}
}
T->Height=Max(Height(T->Left),Height(T->Right))+1;
return T;
}
自己写的新遍历函数，可以打印出先序遍历( PreOrder_2)，中序遍历(INOrder_2)，后序遍历( PostOrder_2)的效果
- 先序遍历:中左右 （维护深度，子节点从父节点继承）
- 中序遍历:左中右 从小到大
- 后序遍历:左右中（维护高度，父节点从子节点获取） （可用于统计目录的大小，子文件的大小相加再加到目录中）这里我就直接用数字代表节点的权值来代替文件大小，并合并到父节点中。
(我觉得中序打印出来的最像树)
#include<stdio.h>
#include<stdlib.h>
#include"avl_tree.h"
int main()
{
AvlTree T=NULL;
// int X=1;
// T=Insert(X,T);
// X=0;
// T=Insert(X,T);
// X=2;
// T=Insert(X,T);
// X=5;
// T=Insert(X,T);
// X=3;
// T=Insert(X,T);
/*
1 1 1
0 2 0 2 0 3
5 3 2 5
3 5
*/
for (int i = 0; i < 10; i++)
{
T=Insert((i+1),T);
}
// if(Find(3,T)->Right){
// printf("r%d\n",Find(3,T)->Right->Element);
// }
// if(Find(3,T)->Left){
// printf("l%d\n",Find(3,T)->Left->Element);
// }
puts("先");
PreOrder(T);
puts("中");
InOrder(T);
puts("后");
PostOrder(T);
// puts("后2");
// PostOrder_2(T,0);
// PreOrder_2(T,0);
InOrder_2(T,0);
MakeEmpty(T);
}
先
4
2
1
3
8
6
5
7
9
10
--------------------------
中
1
2
3
4
5
6
7
8
9
10
--------------------------
后
1
3
2
5
7
6
10
9
8
4
--------------------------
先
4
2
1
3
8
6
5
7
9
10
--------------------------
中
1
2
3
4
5
6
7
8
9
10
--------------------------
后
1(1)
3(3)
2(6)
5(5)
7(7)
6(18)
10(10)
9(19)
8(45)
4(55)
--------------------------
本文并没有做过多的讲解，也就是带大家看一下AVL的效果。
本来如果插入123456789 10可以想象树会一路长到什么地步。
至于旋转的四种函数，还是自己慢慢悟，自己悟出来永远比看别人博客有用。
吐槽一句当年发明这些算法的人真比我们强了太多。
参考《数据结构与算法 C语言描述》