AVL树是最先发明的自平衡二叉查找树。在AVL树中任何节点的两个儿子子树的高度最大差别为一,所以它也被称为高度平衡树。
查找、插入和删除在平均和最坏情况下都是O(log n)。增加和删除可能需要通过一次或多次树旋转来重新平衡这个树。
对二叉树的平衡调整过程,主要包含四种旋转操作:LL,LR,RR,RL 。
LR由当前节点左儿子的一次RR旋转和当前节点的一次LL旋转构成。同理, RR由当前节点右儿子的一次LL旋转和当前节点的一次RR旋转构成。
如图:
AVL树的 插入 和删除均要调整重新构成平衡树。
具体实现代码即注释如下:Head.h fun.c AvlTree.c
Head.h
- #ifndef HEAD_H_
- #define HEAD_H_
-
- #include <stdio.h>
- #include <stdlib.h>
-
- typedef int ElementType;
- typedef struct AvlNode
- {
- ElementType data;
- struct AvlNode *left;
- struct AvlNode *right;
- int Height;
- }*Position,*AvlTree;
-
- AvlTree MakeEmpty(AvlTree T);
- Position Find(ElementType x,AvlTree T);
- Position FindMin(AvlTree T);
- Position FindMax(AvlTree T);
- AvlTree Insert(ElementType x,AvlTree T);
- AvlTree Delete(ElementType x,AvlTree T);
- ElementType Retrieve(Position P);
- void Display(AvlTree T);
-
- #endif /* HEAD_H_ */
fun.c
- #include"Head.h"
-
-
-
- AvlTree MakeEmpty(AvlTree T)
- {
- if( T != NULL)
- {
- MakeEmpty(T->left);
- MakeEmpty(T->right);
- free(T);
- }
- return NULL;
- }
-
-
-
-
-
- Position Find(ElementType x,AvlTree T)
- {
- if(T == NULL)
- return NULL;
- if(x < T->data)
- return Find(x,T->left);
- else if(x > T->data)
- return Find(x,T->right);
- else
- return T;
- }
-
-
-
- Position FindMin(AvlTree T)
- {
- if(T == NULL)
- return NULL;
- if( T->left == NULL)
- return T;
- else
- return FindMin(T->left);
- }
- Position FindMax(AvlTree T)
- {
- if(T != NULL)
- while(T->right != NULL)
- T=T->right;
- return T;
- }
-
-
-
- static int Height(Position P)
- {
- if(P == NULL)
- return -1;
- else
- return P->Height;
- }
- static int Max(int h1,int h2)
- {
- return h1 > h2 ?h1:h2;
- }
-
-
-
-
-
- static Position SingleRotateWithLeft(Position k2)
- {
- 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),Height(k2->right)) + 1;
- return k1;
- }
-
-
-
-
-
- static Position SingleRotateWithRight(Position k1)
- {
- Position k2;
- k2=k1->right;
- k1->right=k2->left;
- k2->left=k1;
-
- k1->Height=Max(Height(k1->left),Height(k1->right)) + 1;
- k2->Height=Max(Height(k2->left),Height(k2->right)) + 1;
- return k2;
- }
-
-
-
-
-
- static Position DoubleRotateLeft(Position k3)
- {
-
- k3->left=SingleRotateWithRight(k3->left);
-
- return SingleRotateWithLeft(k3);
- }
-
-
-
-
-
- static Position DoubleRotateRight(Position k4)
- {
-
- k4->right = SingleRotateWithLeft(k4->right);
-
- return SingleRotateWithRight(k4);
- }
-
-
-
-
-
-
- AvlTree Insert(ElementType x,AvlTree T)
- {
-
- if(T == NULL)
- {
- T = (AvlTree)malloc(sizeof(struct AvlNode));
- {
- T->data = x;
- T->Height = 0;
- T->left = T->right = NULL;
- }
- }
-
- else if(x < T->data)
- {
-
- T->left=Insert(x,T->left);
-
- if(Height(T->left) - Height(T->right) == 2)
- {
-
- if(x < T->left->data)
- T = SingleRotateWithLeft(T);
- else
-
- T = DoubleRotateLeft(T);
- }
- }
-
- else if(x > T->data)
- {
- T->right=Insert(x,T->right);
- if(Height(T->right) - Height(T->left) == 2)
- {
- if(x > T->right->data)
- T = SingleRotateWithRight(T);
- else
- T = DoubleRotateRight(T);
- }
- }
- T->Height=Max(Height(T->left),Height(T->right)) + 1;
- return T;
- }
-
-
-
- AvlTree Rotate(AvlTree T)
- {
-
- if(Height(T->left) - Height(T->right) == 2)
- {
- if(Height(T->left->left) >= Height(T->left->right))
- T = SingleRotateWithLeft(T);
- else
- T = DoubleRotateLeft(T);
- }
- if(Height(T->right) - Height(T->left) == 2)
- {
- if(Height(T->right->right) >= Height(T->right->left))
- T = SingleRotateWithRight(T);
- else
- T = DoubleRotateRight(T);
- }
- return T;
- }
-
-
-
-
-
- AvlTree Delete(ElementType x,AvlTree T)
- {
- if(T == NULL)
- return NULL;
- if(T->data == x)
- {
- if(T->right == NULL )
- {
- AvlTree tmp = T;
- T = T->left;
- free(tmp);
- }
- else
- {
- AvlTree tmp = T->right;
- while(tmp->left)
- tmp=tmp->left;
- T->data = tmp->data;
-
- T->right = Delete(T->data,T->right);
- T->Height = Max(Height(T->left),Height(T->right))+1;
- }
- return T;
- }
- else if(x > T->data)
- {
- T->right=Delete(x,T->right);
- }
- else
- {
- T->left=Delete(x,T->left);
- }
-
-
-
- T->Height=Max(Height(T->left),Height(T->right)) + 1;
- if(T->left != NULL)
- T->left = Rotate(T->left);
- if(T->right != NULL)
- T->right = Rotate(T->right);
- if(T)
- T=Rotate(T);
- return T;
- }
-
-
-
- ElementType Retrieve(Position P)
- {
- return P->data;
- }
-
-
-
- void Display(AvlTree T)
- {
- static int n=0;
- if(NULL != T)
- {
- Display(T->left);
- printf("[%d] ndata=%d \n",++n,T->data);
- Display(T->right);
- }
- }
AvlTree.c
- #include"Head.h"
- #define N 15
- int main(void) {
- AvlTree T=NULL;
- int i;
- int j = 0;
- T = MakeEmpty( NULL );
- for( i = 0; i < N; i++, j = ( j + 7 ) % 50 )
- {
- printf("j=%d \n",j);
- T = Insert( j, T );
- }
- puts("插入 4 \n");
- T = Insert( 4, T );
- Display(T);
- for( i = 0; i < N; i += 2 )
- {
- printf("delelte: %d \n",i);
- T = Delete( i, T );
- }
- printf("detele:\n");
- printf("height=%d \n",T->Height);
- Display(T);
-
- printf( "Min is %d, Max is %d\n", Retrieve( FindMin( T ) ),
- Retrieve( FindMax( T ) ) );
- return EXIT_SUCCESS;
- }