Approved Vendor List

1.品質管理系統中，AVL是Approved Vendor List,及一般意義上的合格供應商目錄。

2.在計算機科學中，AVL樹是最先發明的自平衡二叉查找樹。在AVL樹中任何節點的兩個兒子子樹的高度最大差別為一，所以它也被稱為高度平衡樹。查找、插入和刪除在平均和最壞情況下都是O(log n)。增加和刪除可能需要通過一次或多次樹旋轉來重新平衡這個樹。AVL樹得名於它的發明者 G.M. Adelson-Velsky 和 E.M. Landis，他們在 1962 年的論文 "An algorithm for the organization of information" 中發表了它。

高度為 h 的 AVL 樹, 節點數 N 最多2 − 1； 最少 ( 其中 )。

最少節點數 n 如以費伯納西數列可以用數學歸納法證明：

Nh = Fh + 2 - 1 (Fh + 2是 Fibonacci polynomial)。

即:

N0 = 0 (表示 AVL Tree 高度為0的節點總數)

N1 = 1 (表示 AVL Tree 高度為1的節點總數)

N2 = 2 (表示 AVL Tree 高度為2的節點總數)

Nh = Nh − 1 + Nh − 2 + 1 (表示 AVL Tree 高度為h的節點總數)

換句話説，當節點數為 N 時，高度 h 最多為 。

節點的平衡因子是它的右子樹的高度減去它的左子樹的高度。帶有平衡因子 1、0 或 -1 的節點被認為是平衡的。帶有平衡因子 -2 或 2 的節點被認為是不平衡的，並需要重新平衡這個樹。平衡因子可以直接存儲在每個節點中，或從可能存儲在節點中的子樹高度計算出來。

AVL樹的基本操作一般涉及運做同在不平衡的二叉查找樹所運做的同樣的算法。但是要進行預先或隨後做一次或多次所謂的"AVL 旋轉"。

假設由於在二叉排序樹上插入結點而失去平衡的最小子樹根結點的指針為a(即a是離插入點最近，且平衡因子絕對值超過1的祖先結點)，則失去平衡後進行進行的規律可歸納為下列四種情況：

單向右旋平衡處理RR：由於在*a的左子樹根結點的左子樹上插入結點，*a的平衡因子由1增至2，致使以*a為根的子樹失去平衡，則需進行一次右旋轉操作；

單向左旋平衡處理LL：由於在*a的右子樹根結點的右子樹上插入結點，*a的平衡因子由-1變為-2，致使以*a為根的子樹失去平衡，則需進行一次左旋轉操作；

雙向旋轉（先左後右）平衡處理LR：由於在*a的左子樹根結點的右子樹上插入結點，*a的平衡因子由1增至2，致使以*a為根的子樹失去平衡，則需進行兩次旋轉（先左旋後右旋）操作。

雙向旋轉（先右後左）平衡處理RL：由於在*a的右子樹根結點的左子樹上插入結點，*a的平衡因子由-1變為-2，致使以*a為根的子樹失去平衡，則需進行兩次旋轉（先右旋後左旋）操作。

向AVL樹插入可以通過如同它是未平衡的二叉查找樹一樣把給定的值插入樹中，接着自底向上向根節點折回，於在插入期間成為不平衡的所有節點上進行旋轉來完成。因為折回到根節點的路途上最多有 1.5 乘 log n 個節點，而每次 AVL 旋轉都耗費恆定的時間，插入處理在整體上耗費 O(log n) 時間。

在平衡的的二叉排序樹Balanced BST上插入一個新的數據元素e的遞歸算法可描述如下：

若BBST為空樹，則插入一個數據元素為e的新結點作為BBST的根結點，樹的深度增1；

若e的關鍵字和BBST的根結點的關鍵字相等，則不進行；

若e的關鍵字小於BBST的根結點的關鍵字，而且在BBST的左子樹中不存在和e有相同關鍵字的結點，則將e插入在BBST的左子樹上，並且當插入之後的左子樹深度增加(+1)時，分別就下列不同情況處理之：

BBST的根結點的平衡因子為-1(右子樹的深度大於左子樹的深度，則將根結點的平衡因子更改為0，BBST的深度不變；

BBST的根結點的平衡因子為0（左、右子樹的深度相等）：則將根結點的平衡因子更改為1，BBST的深度增1；

BBST的根結點的平衡因子為1（左子樹的深度大於右子樹的深度）：則若BBST的左子樹根結點的平衡因子為1：則需進行單向右旋平衡處理，並且在右旋處理之後，將根結點和其右子樹根結點的平衡因子更改為0，樹的深度不變；

若e的關鍵字大於BBST的根結點的關鍵字，而且在BBST的右子樹中不存在和e有相同關鍵字的結點，則將e插入在BBST的右子樹上，並且當插入之後的右子樹深度增加(+1)時，分別就不同情況處理之。

從AVL樹中刪除可以通過把要刪除的節點向下旋轉成一個葉子節點，接着直接剪除這個葉子節點來完成。因為在旋轉成葉子節點期間最多有 log n個節點被旋轉，而每次 AVL 旋轉耗費恆定的時間，刪除處理在整體上耗費 O(log n) 時間。

在AVL樹中查找同在一般BST完全一樣的進行，所以耗費 O(log n) 時間，因為AVL樹總是保持平衡的。不需要特殊的準備，樹的結構不會由於查詢而改變。(這是與伸展樹查找相對立的，它會因為查找而變更樹結構。)

給出一個操作AVLTREE的完整程序 大部分由Peter Brass編寫

#include <iostream.h>

#include <math.h>

#include <stdlib.h>

//建立一個整數類型

typedef struct obj_n_t

{

int obj_key;

} obj_node_t;

//建立樹結點的基本機構

typedef struct tree_n_t

{

int key;

struct tree_n_t *left,*right;

int height;

} tree_node_t;

//建立堆棧

#define MAXSIZE 512

tree_node_t *stack[MAXSIZE]; //warning!the tree can contain 256 leaves at most!

int i=0; //堆棧計數器

//堆棧清空

void stack_clear()

{

while(i!=0)

{

stack[i-1]=NULL;

i--;

}

}

//堆棧為空

int stack_empty()

{

return(i==0);

}

//入棧函數

int push(tree_node_t *node)

{

if(i<MAXSIZE)

{

stack[i++]=node;

return(0);

}

else

return(-1);

}

//出棧函數

tree_node_t *pop()

{

if(i>0)

return(stack[--i]);

else

return(0);

}

//建立get_node函數，用於動態分配內存空間

tree_node_t *get_node()

{

tree_node_t *tmp;

tmp=(tree_node_t *)malloc(sizeof(tree_node_t));

return(tmp);

}

//建立return_node函數，用於釋放內存

void return_node(tree_node_t *free_node)