AVL樹是一個“加上了額外平衡條件”的二叉搜索樹。其平衡條件的建立時為了確保樹的深度為O(longN)。AVL樹要求任何節點左右子樹的高度相差不超過1。 插入操作：左-左插入和右-右插入需要單旋轉； ?????????????????左-右插入和右-左插入需要雙旋轉。 其實，AVL樹的插入刪除操作和[二叉查找樹的操作](http://blog.csdn.net/u013074465/article/details/41699891)類似，只是需要注意調整樹的平衡。 # AVL樹 C語言實現 刪除操作的旋轉示意圖：     在下面的代碼中，插入刪除過程中，對樹平衡的調整完全可以封裝為函數，顯得簡潔，但懶人我沒寫成函數。 ~~~ //3avl_tree.c #include "3avl_tree.h" #include "test.h" AvlTree MakeEmptyAvlTree(AvlTree avltree) { if (avltree != NULL) { MakeEmptyAvlTree(avltree->left); MakeEmptyAvlTree(avltree->right); free(avltree); } return NULL; } Position FindAvlTree(ElementType x, AvlTree avltree) { if (avltree == NULL) return NULL; if (x < avltree->element) return FindAvlTree(x, avltree->left); else if (x > avltree->element) return FindAvlTree(x, avltree->right); else return avltree; } Position FindMinFromAvlTree(AvlTree avltree) { if (avltree == NULL) return NULL; else if (avltree->left == NULL) return avltree; else return FindMinFromAvlTree(avltree->left); } Position FindMaxFromAvlTree(AvlTree avltree) { if (avltree == NULL) return NULL; else if (avltree->right == NULL) return avltree; else return FindMaxFromAvlTree(avltree->right); } static int HeightAvlTree(AvlTree avltree) { if (avltree == NULL) return -1; else return avltree->height; } static int Max(int lhs, int rhs) { return lhs > rhs ? lhs : rhs; } //左-左插入，使得k2失去平衡，因此需要在k2處單旋轉 static Position SingleRotateWithLeft(Position k2) { Position k1; k1 = k2->left; k2->left = k1->right; k1->right = k2; k2->height = Max(HeightAvlTree(k2->left), HeightAvlTree(k2->right)) + 1; k1->height = Max(HeightAvlTree(k1->left), HeightAvlTree(k1->right)) + 1; return k1; } //右-右插入，使得k1失去平衡，因此需要在k1處單旋轉 static Position SigleRotateWithRight(Position k1) { Position k2; k2 = k1->right; k1->right = k2->left; k2->left = k1; k1->height = Max(HeightAvlTree(k1->left), HeightAvlTree(k1->right)) + 1; k2->height = Max(HeightAvlTree(k2->left), HeightAvlTree(k2->right)) + 1; return k2; } //左-右插入，使得k3失去平衡，因此在k3處雙旋轉 //雙旋轉其實是兩次單旋轉操作 //先對k3的左子樹進行一次右-右單旋轉操作 //然后對k3進行一次左-左單旋轉操作 static Position DoubleRotateWithLeft1(Position k3) { //雙旋轉，遞歸 k3->left = SigleRotateWithRight(k3->left); return SingleRotateWithLeft(k3); } static Position DoubleRotateWithLeft2(Position k3) { Position k1, k2; k1 = k3->left; k2 = k1->right; k1->right = k2->left; k2->left = k1; k3->left = k2->right; k2->right = k3; k1->height = Max(HeightAvlTree(k1->left), HeightAvlTree(k1->right)) + 1; k3->height = Max(HeightAvlTree(k3->left), HeightAvlTree(k3->right)) + 1; k2->height = Max(k1->height, k3->height) + 1; return k2; } //右-左插入，使得k1失去平衡，因此在k1處雙旋轉 //雙旋轉其實是兩次單旋轉操作 //先對k1的右子樹進行一次左-左單旋轉操作 //然后對k1進行一次右-右單旋轉操作 static Position DoubleRotateWithRight(Position k1) { k1->right = SingleRotateWithLeft(k1->right); return SigleRotateWithRight(k1); } AvlTree InsertToAvlTree(ElementType x, AvlTree avltree) { if (avltree == NULL) { //如果樹為空，分配空間，插入節點 avltree = (struct AvlNode*)malloc(sizeof(struct AvlNode)); if (avltree == NULL) { cout << "malloc failed." << endl; } else { avltree->element = x; avltree->left = avltree->right = NULL; } } //插入值小于根節點的值，在左子樹插入節點 else if (x < avltree->element) { avltree->left = InsertToAvlTree(x, avltree->left); //樹失去了平衡，對樹進行調整，這幾個調整平衡的語句可以封裝下 if (HeightAvlTree(avltree->left) - HeightAvlTree(avltree->right) == 2) { if (x < avltree->left->element) //左-左，進行左單旋轉 avltree = SingleRotateWithLeft(avltree); else //左-右，雙旋轉 avltree = DoubleRotateWithLeft1(avltree); } } //插入值大于根節點的值，在右子樹插入節點 else if (x > avltree->element) { avltree->right = InsertToAvlTree(x, avltree->right); //樹失去了平衡，對樹進行調整，這幾個調整平衡的語句可以封裝下 if (HeightAvlTree(avltree->right) - HeightAvlTree(avltree->left) == 2) { if (x > avltree->right->element) avltree = SigleRotateWithRight(avltree); //右-右，單旋轉 else //右-左，雙旋轉 avltree = DoubleRotateWithRight(avltree); } } avltree->height = Max(HeightAvlTree(avltree->left), HeightAvlTree(avltree->right)) + 1; return avltree; } //刪除操作類似于二叉樹的操作，只是需要將樹調整平衡 AvlTree DeleteFromAvlTree(ElementType x, AvlTree avltree) { Position temp; if (avltree == NULL) return NULL; //在左子樹尋找刪除位置，刪除后可能導致左子樹高度變小，可能要調整樹 if (x < avltree->element) { avltree->left = DeleteFromAvlTree(x, avltree->left); //如果右子樹高度比左子樹高度超過1，那么需要將樹調整平衡，這幾個調整平衡的語句可以封裝下 if (2 == (HeightAvlTree(avltree->right) - HeightAvlTree(avltree->left))) { //如果是右-左型，則要進行左單旋、右單旋；即進行如下雙旋操作 //否則為右-右型，需要進行左單旋操作 if (HeightAvlTree(avltree->right->left) > HeightAvlTree(avltree->right->right)) avltree = DoubleRotateWithRight(avltree); else avltree = SigleRotateWithRight(avltree); } } //在右子樹尋找刪除位置，刪除后可能導致右子樹高度變小，可能要調整樹 else if (x > avltree->element) { avltree->right = DeleteFromAvlTree(x, avltree->right); //這幾個調整平衡的語句可以封裝下 if (2 == (HeightAvlTree(avltree->left) - HeightAvlTree(avltree->right))) { if (HeightAvlTree(avltree->left->right) > HeightAvlTree(avltree->left->left)) avltree = DoubleRotateWithLeft1(avltree); else avltree = SingleRotateWithLeft(avltree); } } //找到要刪除的元素,該節點有兩個孩子 //那么將節點的值用右子樹中最小的值A替換，然后在右子樹中刪除A else if (avltree->left && avltree->right){ avltree->element = (FindMinFromAvlTree(avltree->right))->element; avltree->right = DeleteFromAvlTree(avltree->element, avltree->right); } //找到要刪除的節點，該節點為葉子節點或僅有一個孩子 else { temp = avltree; if (avltree->left == NULL) //當節點只有右孩子或為葉節點時 avltree = avltree->right; else if (avltree->right == NULL) //當節點只有左孩子時 avltree = avltree->left; free(temp); } if (avltree) avltree->height = Max(HeightAvlTree(avltree->right), HeightAvlTree(avltree->left)) + 1; return avltree; } void VisitElement(AvlTree tree) { cout << tree->element << " "; } //先序遍歷樹 void PreOrderTraversal(AvlTree tree) { if (tree == NULL) return; VisitElement(tree); PreOrderTraversal(tree->left); PreOrderTraversal(tree->right); } //中序遍歷樹 void InOrderTraversal(AvlTree tree) { if (tree == NULL) return; InOrderTraversal(tree->left); VisitElement(tree); InOrderTraversal(tree->right); } int main() { AvlTree tree = NULL; tree = MakeEmptyAvlTree(tree); tree = InsertToAvlTree(1, tree); tree = InsertToAvlTree(3, tree); tree = InsertToAvlTree(5, tree); tree = InsertToAvlTree(122, tree); tree = InsertToAvlTree(7, tree); tree = InsertToAvlTree(9, tree); tree = InsertToAvlTree(11, tree); tree = InsertToAvlTree(21, tree); Position min = FindMinFromAvlTree(tree);; cout << "刪除前，樹高：" << HeightAvlTree(tree) << endl; cout << endl << "刪除前，先序遍歷：" << endl; PreOrderTraversal(tree); cout << endl << "刪除前，中序遍歷：" << endl; InOrderTraversal(tree); DeleteFromAvlTree(7, tree); cout << endl; cout << "刪除后，樹高：" << HeightAvlTree(tree) << endl; cout << endl << "刪除后，先序遍歷：" << endl; PreOrderTraversal(tree); cout << endl << "刪除后，中序遍歷：" << endl; InOrderTraversal(tree); } ~~~ ~~~ //3avl_tree.h typedef int ElementType; #ifndef TEST_AVL_TREE_H #define TEST_AVL_TREE_H struct AvlNode; typedef struct AvlNode *Position; typedef struct AvlNode *AvlTree; struct AvlNode { ElementType element; AvlTree left; AvlTree right; int height; }; AvlTree MakeEmptyAvlTree(AvlTree avltree); Position FindAvlTree(ElementType x, AvlTree avltree); Position FindMinFromAvlTree(AvlTree avltree); Position FindMaxFromAvlTree(AvlTree avltree); AvlTree InsertToAvlTree(ElementType x, AvlTree avltree); AvlTree DeleteFromAvlTree(ElementType x, AvlTree avltree); ElementType RetrieveAvlTree(Position pos); #endif ~~~ 程序執行結果：  # [Avl的C++實現](http://blog.csdn.net/u013074465/article/details/44748497)