定義：每個節點的左右子樹的高度最多差1的二叉查找樹。（空樹的高度為-1）。
AVL樹保證樹的高度隻比log(N)多一點，是以除了插入删除外，可以保證所有的樹操作都以O(logN)執行。
當插入一個節點的時候，隻有那些從插入點到根節點路徑上的點的平衡性可能被破壞，在最深的不滿足平衡性的節點進行平衡操作，可以重新使整個樹滿足AVL特性。
主要操作：對不滿足AVL特性的子樹執行單旋轉和雙旋轉操作，使得插入後的子樹保持和插入前的子樹相同的高度。
節點的基本定義：
1 struct AvlNode;
2 typedef struct AvlNode *Position;
3 typedef struct AvlNode *AvlTree;
4
5 struct AvlNode{
6 ElementType Element;
7 AvlTree Left;
8 AvlTree Right;
9 int Height;
10 }; 單旋轉（左-左 右-右）代碼如下：
1 Position SingleRotateWithLeft(AvlTree K2){
2 Position K1;
3 K1 = K2->Left;
4 K2->Left = K1->Right;
5 K1->Right = K2;
6
7 K2->Height = max(Height(K2->Left), Height(K2->Right)) + 1;
8 K1->Height = max(Height(K1->Left), K2->Height) + 1;
9 return K1;
10 }
11
12 Position SingleRotateWithRight(AvlTree K2){
13 Position K1;
14 K1 = K2->Right;
15 K2->Right = K1->Left;
16 K1->Left = K2;
17
18 K2->Height = max(Height(K2->Left), Height(K2->Right)) + 1;
19 K1->Height = max(K2->Height, Height(K1->Right)) + 1;
20 return K1;
21 } 雙旋轉（左-右 右-左）代碼如下：
1 Position DoubleRotateWithLeft(AvlTree K3){
2 K3->Left = SingleRotateWithRight(K3->Left);
3 return SingleRotateWithLeft(K3);
4 }
5
6 Position DoubleRotateWithRight(AvlTree K3){
7 K3->Right = SingleRotateWithLeft(K3->Right);
8 return SingleRotateWithRight(K3);
9 } 插入算法如下：
1 AvlTree Insert(ElementType X, AvlTree T){
2 if(T == NULL){
3 T = (AvlTree)malloc(sizeof(struct AvlNode));
4 T->Height = 0;
5 T->Left = T->Right = NULL;
6 T->Element = X;
7 }
8 else if(X < T->Element){
9 T->Left = Insert(X, T->Left);
10 if(Height(T->Left)-Height(T->Right) == 2){
11 if(X < T->Left->Element){
12 T = SingleRotateWithLeft(T);
13 }
14 else{
15 T = DoubleRotateWithLeft(T);
16 }
17 }
18 }
19 else if(X > T->Element){
20 T->Right = Insert(X, T->Right);
21 if(Height(T->Right)-Height(T->Left) == 2){
22 if(X > T->Right->Element){
23 T = SingleRotateWithRight(T);
24 }
25 else{
26 T = DoubleRotateWithRight(T);
27 }
28 }
29 }
30
31 T->Height = max(Height(T->Left), Height(T->Right)) + 1;
32 return T;
33 }