AVL(Adelson-Velskii 和 Landis)樹是帶有平衡條件的二叉查找樹。在計算機(jī)科學(xué)中揍魂，AVL樹是最先發(fā)明的自平衡二叉查找樹。在AVL樹中任何節(jié)點的兩個子樹的高度最大差別為1肃廓，所以它也被稱為高度平衡樹挎峦。查找、插入和刪除在平均和最壞情況下的時間復(fù)雜度都是O(lngn)搜吧。增加和刪除可能需要通過一次或多次樹旋轉(zhuǎn)來重新平衡這個樹市俊。
節(jié)點的平衡因子是它的左子樹的高度減去它的右子樹的高度（有時相反）。帶有平衡因子1滤奈、0或-1的結(jié)點被認(rèn)為是平衡的摆昧。帶有平衡因子-2或2的節(jié)點被認(rèn)為是不平衡的，并需要重新平衡這個樹僵刮。平衡因子可以直接存儲在每個節(jié)點中据忘，或從可能存儲在節(jié)點中的子樹高度計算出來鹦牛。
AVL樹的基本操作一般涉及運(yùn)作同在不平衡的二叉查找樹所運(yùn)作的同樣的算法。但是要進(jìn)行預(yù)先或隨后做一次或多次所謂的"AVL旋轉(zhuǎn)"勇吊。
以下圖標(biāo)表示的四種情況曼追，就是AVL旋轉(zhuǎn)中常見的四種。（圖片用了維基百科的汉规，不確定不開vpn圖是否會掛）礼殊。
下面來看AVL樹的操作有哪些:
#ifndef _AvlTree_H
struct AvlNode;
typedef struct AvlNode *Position;
typedef struct AvlNode *AvlTree;
typedef int ElementType;
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 );
#endif /* _AvlTree_H */
下面是對于上面操作定義的實現(xiàn):
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include "AvlTree.h"
#define OK 1
#define ERROR 0
#define TRUE 1
#define FALSE 0
typedef int Status;
struct AvlNode
{
ElementType Element;
AvlTree Left;
AvlTree Right;
int Height;
};
AvlTree MakeEmpty(AvlTree T)
{
if (T != NULL)
{
MakeEmpty(T->Left);
MakeEmpty(T->Right);
free(T);
}
return NULL;
}
/**
* 計算Avl節(jié)點高度
* @param P 節(jié)點P
* @return 樹高
*/
static int Height(Position P)
{
if (P == NULL)
return -1;
else
return P->Height;
}
static int Max(int a, int b)
{
return a > b ? a : b;
}
/* 向左單旋 */
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), K2->Height) + 1;
return K1; /* New Root */
}
/* 向右單旋 */
static Position SingleRotateWithRight(Position K2)
{
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(K2->Height, Height(K1->Right)) + 1;
return K1; /*New root */
}
/* 向左雙旋 */
static Position DoubleRotateWithLeft(Position K3)
{
/* Rotate between K1 and K2 */
K3->Left = SingleRotateWithRight(K3->Left);
/* Rotate between K3 and K2 */
return SingleRotateWithLeft(K3);
}
/* 向右雙旋 */
static Position DoubleRotateWithRight(Position K3)
{
K3->Right = SingleRotateWithLeft(K3->Right);
return SingleRotateWithRight(K3);
}
AvlTree Insert(ElementType X, AvlTree T)
{
if (T == NULL)
{
T = malloc( sizeof( struct AvlNode ) );
if (T == NULL)
printf("Out of space!!!\n");
else
{
T->Element = X;
T->Height = 0;
T->Left = T->Right = NULL;
}
}
else if (X < T->Element) /* 左子樹插入新節(jié)點 */
{
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) /* 右子樹插入新節(jié)點 */
{
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);
}
/* Else X is in the tree alredy; we'll do nothing */
T->Height = Max(Height(T->Left), Height(T->Right)) + 1;
return T;
}
AvlTree Delete(ElementType X, AvlTree T)
{
Position TmpCell;
if(T == NULL) {
printf("沒找到該元素，無法刪除针史！\n");
return NULL;
}
else if (X < T->Element)
T->Left = Delete(X, T->Left);
else if (X > T->Element)
T->Right = Delete(X, T->Right);
else if(T->Left && T->Right) { //要刪除的樹左右都有兒子
TmpCell = FindMin(T->Right); //用該結(jié)點右兒子上最小結(jié)點替換該結(jié)點晶伦，然后與只有一個兒子的操作方法相同
T->Element = TmpCell->Element;
T->Right = Delete(T->Element, T->Right);
}else{
TmpCell = T; //要刪除的結(jié)點只有一個兒子
if(T->Left == NULL)
T = T->Right;
else if(T->Right == NULL)
T = T->Left;
free(TmpCell);
}
return T;
}
/* 查找X元素所在的位置 */
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;
}
/* search the min element in AvlTree*/
Position FindMin(AvlTree T)
{
if (T == NULL)
return NULL;
else if (T->Left == NULL)
return T;
else
return FindMin(T->Left);
}
/* search the max element in AvlTree */
Position FindMax(AvlTree T)
{
if (T == NULL)
return NULL;
else if (T->Right == NULL)
return T;
else
return FindMax(T->Right);
}
ElementType Retrieve(Position P)
{
if(P != NULL)
return P->Element;
return -1;
}
/**
* 前序遍歷"二叉樹"
* @param T Tree
*/
void PreorderTravel(AvlTree T)
{
if (T != NULL)
{
printf("%d\n", T->Element);
PreorderTravel(T->Left);
PreorderTravel(T->Right);
}
}
/**
* 中序遍歷"二叉樹"
* @param T Tree
*/
void InorderTravel(AvlTree T)
{
if (T != NULL)
{
InorderTravel(T->Left);
printf("%d\n", T->Element);
InorderTravel(T->Right);
}
}
/**
* 后序遍歷二叉樹
* @param T Tree
*/
void PostorderTravel(AvlTree T)
{
if (T != NULL)
{
PostorderTravel(T->Left);
PostorderTravel(T->Right);
printf("%d\n", T->Element);
}
}
/* 打印二叉樹信息 */
void PrintTree(AvlTree T, ElementType Element, int direction)
{
if (T != NULL)
{
if (direction == 0)
printf("%2d is root\n", T->Element);
else
printf("%2d is %2d's %6s child\n", T->Element, Element, direction == 1 ? "right" : "left");
PrintTree(T->Left, T->Element, -1);
PrintTree(T->Right, T->Element, 1);
}
}
在實現(xiàn)完成這些函數(shù)后，我們在main函數(shù)中對AVL樹進(jìn)行測試:
int main(int argc, char const *argv[])
{
printf("Hello World\n");
AvlTree T;
Position P;
int i;
T = MakeEmpty(NULL);
T = Insert(21, T);
T = Insert(2150, T);
T = Insert(50, T);
T = Insert(12, T);
T = Insert(1201, T);
printf("Root: %d\n", T->Element);
printf("樹的詳細(xì)信息: \n");
PrintTree(T, T->Element, 0);
printf("前序遍歷二叉樹: \n");
PreorderTravel(T);
printf("中序遍歷二叉樹: \n");
InorderTravel(T);
printf("后序遍歷二叉樹: \n");
PostorderTravel(T);
printf("最大值: %d\n", FindMax(T)->Element);
printf("最小值: %d\n", FindMin(T)->Element);
Delete(50, T);
printf("樹的詳細(xì)信息: \n");
PrintTree(T, T->Element, 0);
return 0;
}
