當前位置：首頁 > 编程语言 > c/c++ >内容正文

c/c++

AVL树(二)之 C++的实现

發布時間：2025/3/20 c/c++ 12 豆豆

生活随笔收集整理的這篇文章主要介紹了 AVL树(二)之 C++的实现小編覺得挺不錯的,現在分享給大家,幫大家做個參考.

AVL樹(二)之 C++的實現

概要

上一章通過C語言實現了AVL樹，本章將介紹AVL樹的C++版本，算法與C語言版本的一樣。

1.?AVL樹的介紹
2.?AVL樹的C++實現

轉載請注明出處：http://www.cnblogs.com/skywang12345/p/3577360.html

更多內容:?數據結構與算法系列目錄?

(01)?AVL樹(一)之圖文解析和 C語言的實現
(02)?AVL樹(二)之 C++的實現
(03)?AVL樹(三)之 Java的實現

AVL樹的介紹

AVL樹是高度平衡的而二叉樹。它的特點是：AVL樹中任何節點的兩個子樹的高度最大差別為1。?

上面的兩張圖片，左邊的是AVL樹，它的任何節點的兩個子樹的高度差別都<=1；而右邊的不是AVL樹，因為7的兩顆子樹的高度相差為2(以2為根節點的樹的高度是3，而以8為根節點的樹的高度是1)。

AVL樹的C++實現

1. 節點

1.1 AVL樹節點

template <class T> class AVLTreeNode{public:T key; // 關鍵字(鍵值)int height; // 高度AVLTreeNode *left; // 左孩子AVLTreeNode *right; // 右孩子 AVLTreeNode(T value, AVLTreeNode *l, AVLTreeNode *r):key(value), height(0),left(l),right(r) {} };

AVLTreeNode是AVL樹的節點類，它包括的幾個組成對象:
(01) key -- 是關鍵字，是用來對AVL樹的節點進行排序的。
(02) left -- 是左孩子。
(03) right -- 是右孩子。
(04) height -- 是高度。

1.2 AVL樹

template <class T> class AVLTree {private:AVLTreeNode<T> *mRoot; // 根結點public:AVLTree();~AVLTree();// 獲取樹的高度int height();// 獲取樹的高度int max(int a, int b);// 前序遍歷"AVL樹"void preOrder();// 中序遍歷"AVL樹"void inOrder();// 后序遍歷"AVL樹"void postOrder();// (遞歸實現)查找"AVL樹"中鍵值為key的節點AVLTreeNode<T>* search(T key);// (非遞歸實現)查找"AVL樹"中鍵值為key的節點AVLTreeNode<T>* iterativeSearch(T key);// 查找最小結點：返回最小結點的鍵值。 T minimum();// 查找最大結點：返回最大結點的鍵值。 T maximum();// 將結點(key為節點鍵值)插入到AVL樹中void insert(T key);// 刪除結點(key為節點鍵值)void remove(T key);// 銷毀AVL樹void destroy();// 打印AVL樹void print();private:// 獲取樹的高度int height(AVLTreeNode<T>* tree) ;// 前序遍歷"AVL樹"void preOrder(AVLTreeNode<T>* tree) const;// 中序遍歷"AVL樹"void inOrder(AVLTreeNode<T>* tree) const;// 后序遍歷"AVL樹"void postOrder(AVLTreeNode<T>* tree) const;// (遞歸實現)查找"AVL樹x"中鍵值為key的節點AVLTreeNode<T>* search(AVLTreeNode<T>* x, T key) const;// (非遞歸實現)查找"AVL樹x"中鍵值為key的節點AVLTreeNode<T>* iterativeSearch(AVLTreeNode<T>* x, T key) const;// 查找最小結點：返回tree為根結點的AVL樹的最小結點。AVLTreeNode<T>* minimum(AVLTreeNode<T>* tree);// 查找最大結點：返回tree為根結點的AVL樹的最大結點。AVLTreeNode<T>* maximum(AVLTreeNode<T>* tree);// LL：左左對應的情況(左單旋轉)。AVLTreeNode<T>* leftLeftRotation(AVLTreeNode<T>* k2);// RR：右右對應的情況(右單旋轉)。AVLTreeNode<T>* rightRightRotation(AVLTreeNode<T>* k1);// LR：左右對應的情況(左雙旋轉)。AVLTreeNode<T>* leftRightRotation(AVLTreeNode<T>* k3);// RL：右左對應的情況(右雙旋轉)。AVLTreeNode<T>* rightLeftRotation(AVLTreeNode<T>* k1);// 將結點(z)插入到AVL樹(tree)中AVLTreeNode<T>* insert(AVLTreeNode<T>* &tree, T key);// 刪除AVL樹(tree)中的結點(z)，并返回被刪除的結點AVLTreeNode<T>* remove(AVLTreeNode<T>* &tree, AVLTreeNode<T>* z);// 銷毀AVL樹void destroy(AVLTreeNode<T>* &tree);// 打印AVL樹void print(AVLTreeNode<T>* tree, T key, int direction); };

AVLTree是AVL樹對應的類。它包含AVL樹的根節點mRoot和AVL樹的基本操作接口。需要說明的是：AVLTree中重載了許多函數。重載的目的是區分內部接口和外部接口，例如insert()函數而言，insert(tree, key)是內部接口，而insert(key)是外部接口。

1.2 樹的高度

/** 獲取樹的高度*/ template <class T> int AVLTree<T>::height(AVLTreeNode<T>* tree) {if (tree != NULL)return tree->height;return 0; }template <class T> int AVLTree<T>::height() {return height(mRoot); }

關于高度，有的地方將"空二叉樹的高度是-1"，而本文采用維基百科上的定義：樹的高度為最大層次。即空的二叉樹的高度是0，非空樹的高度等于它的最大層次(根的層次為1，根的子節點為第2層，依次類推)。

1.3 比較大小

/** 比較兩個值的大小*/ template <class T> int AVLTree<T>::max(int a, int b) {return a>b ? a : b; }

2. 旋轉

如果在AVL樹中進行插入或刪除節點后，可能導致AVL樹失去平衡。這種失去平衡的可以概括為4種姿態：LL(左左)，LR(左右)，RR(右右)和RL(右左)。下面給出它們的示意圖：

上圖中的4棵樹都是"失去平衡的AVL樹"，從左往右的情況依次是：LL、LR、RL、RR。除了上面的情況之外，還有其它的失去平衡的AVL樹，如下圖：

上面的兩張圖都是為了便于理解，而列舉的關于"失去平衡的AVL樹"的例子?？偟膩碚f，AVL樹失去平衡時的情況一定是LL、LR、RL、RR這4種之一，它們都由各自的定義：

(1)?LL：LeftLeft，也稱為"左左"。插入或刪除一個節點后，根節點的左子樹的左子樹還有非空子節點，導致"根的左子樹的高度"比"根的右子樹的高度"大2，導致AVL樹失去了平衡。
? ? ?例如，在上面LL情況中，由于"根節點(8)的左子樹(4)的左子樹(2)還有非空子節點"，而"根節點(8)的右子樹(12)沒有子節點"；導致"根節點(8)的左子樹(4)高度"比"根節點(8)的右子樹(12)"高2。

(2)?LR：LeftRight，也稱為"左右"。插入或刪除一個節點后，根節點的左子樹的右子樹還有非空子節點，導致"根的左子樹的高度"比"根的右子樹的高度"大2，導致AVL樹失去了平衡。
? ? ?例如，在上面LR情況中，由于"根節點(8)的左子樹(4)的左子樹(6)還有非空子節點"，而"根節點(8)的右子樹(12)沒有子節點"；導致"根節點(8)的左子樹(4)高度"比"根節點(8)的右子樹(12)"高2。

(3)?RL：RightLeft，稱為"右左"。插入或刪除一個節點后，根節點的右子樹的左子樹還有非空子節點，導致"根的右子樹的高度"比"根的左子樹的高度"大2，導致AVL樹失去了平衡。
? ? ?例如，在上面RL情況中，由于"根節點(8)的右子樹(12)的左子樹(10)還有非空子節點"，而"根節點(8)的左子樹(4)沒有子節點"；導致"根節點(8)的右子樹(12)高度"比"根節點(8)的左子樹(4)"高2。

(4)?RR：RightRight，稱為"右右"。插入或刪除一個節點后，根節點的右子樹的右子樹還有非空子節點，導致"根的右子樹的高度"比"根的左子樹的高度"大2，導致AVL樹失去了平衡。
? ? ?例如，在上面RR情況中，由于"根節點(8)的右子樹(12)的右子樹(14)還有非空子節點"，而"根節點(8)的左子樹(4)沒有子節點"；導致"根節點(8)的右子樹(12)高度"比"根節點(8)的左子樹(4)"高2。

前面說過，如果在AVL樹中進行插入或刪除節點后，可能導致AVL樹失去平衡。AVL失去平衡之后，可以通過旋轉使其恢復平衡，下面分別介紹"LL(左左)，LR(左右)，RR(右右)和RL(右左)"這4種情況對應的旋轉方法。

2.1 LL的旋轉

LL失去平衡的情況，可以通過一次旋轉讓AVL樹恢復平衡。如下圖：

圖中左邊是旋轉之前的樹，右邊是旋轉之后的樹。從中可以發現，旋轉之后的樹又變成了AVL樹，而且該旋轉只需要一次即可完成。
對于LL旋轉，你可以這樣理解為：LL旋轉是圍繞"失去平衡的AVL根節點"進行的，也就是節點k2；而且由于是LL情況，即左左情況，就用手抓著"左孩子，即k1"使勁搖。將k1變成根節點，k2變成k1的右子樹，"k1的右子樹"變成"k2的左子樹"。

LL的旋轉代碼

/** LL：左左對應的情況(左單旋轉)。** 返回值：旋轉后的根節點*/ template <class T> AVLTreeNode<T>* AVLTree<T>::leftLeftRotation(AVLTreeNode<T>* k2) {AVLTreeNode<T>* 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; }

2.2 RR的旋轉

理解了LL之后，RR就相當容易理解了。RR是與LL對稱的情況！RR恢復平衡的旋轉方法如下：

圖中左邊是旋轉之前的樹，右邊是旋轉之后的樹。RR旋轉也只需要一次即可完成。

RR的旋轉代碼

/** RR：右右對應的情況(右單旋轉)。** 返回值：旋轉后的根節點*/ template <class T> AVLTreeNode<T>* AVLTree<T>::rightRightRotation(AVLTreeNode<T>* k1) {AVLTreeNode<T>* 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->right), k1->height) + 1;return k2; }

2.3 LR的旋轉

LR失去平衡的情況，需要經過兩次旋轉才能讓AVL樹恢復平衡。如下圖：

第一次旋轉是圍繞"k1"進行的"RR旋轉"，第二次是圍繞"k3"進行的"LL旋轉"。

LR的旋轉代碼

/** LR：左右對應的情況(左雙旋轉)。** 返回值：旋轉后的根節點*/ template <class T> AVLTreeNode<T>* AVLTree<T>::leftRightRotation(AVLTreeNode<T>* k3) {k3->left = rightRightRotation(k3->left);return leftLeftRotation(k3); }

2.4 RL的旋轉

RL是與LR的對稱情況！RL恢復平衡的旋轉方法如下：

第一次旋轉是圍繞"k3"進行的"LL旋轉"，第二次是圍繞"k1"進行的"RR旋轉"。

RL的旋轉代碼

/** RL：右左對應的情況(右雙旋轉)。** 返回值：旋轉后的根節點*/ template <class T> AVLTreeNode<T>* AVLTree<T>::rightLeftRotation(AVLTreeNode<T>* k1) {k1->right = leftLeftRotation(k1->right);return rightRightRotation(k1); }

3. 插入

插入節點的代碼

/* * 將結點插入到AVL樹中，并返回根節點** 參數說明：* tree AVL樹的根結點* key 插入的結點的鍵值* 返回值：* 根節點*/ template <class T> AVLTreeNode<T>* AVLTree<T>::insert(AVLTreeNode<T>* &tree, T key) {if (tree == NULL) {// 新建節點tree = new AVLTreeNode<T>(key, NULL, NULL);if (tree==NULL){cout << "ERROR: create avltree node failed!" << endl;return NULL;}}else if (key < tree->key) // 應該將key插入到"tree的左子樹"的情況 {tree->left = insert(tree->left, key);// 插入節點后，若AVL樹失去平衡，則進行相應的調節。if (height(tree->left) - height(tree->right) == 2){if (key < tree->left->key)tree = leftLeftRotation(tree);elsetree = leftRightRotation(tree);}}else if (key > tree->key) // 應該將key插入到"tree的右子樹"的情況 {tree->right = insert(tree->right, key);// 插入節點后，若AVL樹失去平衡，則進行相應的調節。if (height(tree->right) - height(tree->left) == 2){if (key > tree->right->key)tree = rightRightRotation(tree);elsetree = rightLeftRotation(tree);}}else //key == tree->key) {cout << "添加失敗：不允許添加相同的節點！" << endl;}tree->height = max( height(tree->left), height(tree->right)) + 1;return tree; }template <class T> void AVLTree<T>::insert(T key) {insert(mRoot, key); }

4. 刪除

刪除節點的代碼

/* * 刪除結點(z)，返回根節點** 參數說明：* tree AVL樹的根結點* z 待刪除的結點* 返回值：* 根節點*/ template <class T> AVLTreeNode<T>* AVLTree<T>::remove(AVLTreeNode<T>* &tree, AVLTreeNode<T>* z) {// 根為空或者沒有要刪除的節點，直接返回NULL。if (tree==NULL || z==NULL)return NULL;if (z->key < tree->key) // 待刪除的節點在"tree的左子樹"中 {tree->left = remove(tree->left, z);// 刪除節點后，若AVL樹失去平衡，則進行相應的調節。if (height(tree->right) - height(tree->left) == 2){AVLTreeNode<T> *r = tree->right;if (height(r->left) > height(r->right))tree = rightLeftRotation(tree);elsetree = rightRightRotation(tree);}}else if (z->key > tree->key)// 待刪除的節點在"tree的右子樹"中 {tree->right = remove(tree->right, z);// 刪除節點后，若AVL樹失去平衡，則進行相應的調節。if (height(tree->left) - height(tree->right) == 2){AVLTreeNode<T> *l = tree->left;if (height(l->right) > height(l->left))tree = leftRightRotation(tree);elsetree = leftLeftRotation(tree);}}else // tree是對應要刪除的節點。 {// tree的左右孩子都非空if ((tree->left!=NULL) && (tree->right!=NULL)){if (height(tree->left) > height(tree->right)){// 如果tree的左子樹比右子樹高；// 則(01)找出tree的左子樹中的最大節點// (02)將該最大節點的值賦值給tree。// (03)刪除該最大節點。// 這類似于用"tree的左子樹中最大節點"做"tree"的替身；// 采用這種方式的好處是：刪除"tree的左子樹中最大節點"之后，AVL樹仍然是平衡的。AVLTreeNode<T>* max = maximum(tree->left);tree->key = max->key;tree->left = remove(tree->left, max);}else{// 如果tree的左子樹不比右子樹高(即它們相等，或右子樹比左子樹高1)// 則(01)找出tree的右子樹中的最小節點// (02)將該最小節點的值賦值給tree。// (03)刪除該最小節點。// 這類似于用"tree的右子樹中最小節點"做"tree"的替身；// 采用這種方式的好處是：刪除"tree的右子樹中最小節點"之后，AVL樹仍然是平衡的。AVLTreeNode<T>* min = maximum(tree->right);tree->key = min->key;tree->right = remove(tree->right, min);}}else{AVLTreeNode<T>* tmp = tree;tree = (tree->left!=NULL) ? tree->left : tree->right;delete tmp;}}return tree; }template <class T> void AVLTree<T>::remove(T key) {AVLTreeNode<T>* z; if ((z = search(mRoot, key)) != NULL)mRoot = remove(mRoot, z); }

注意：關于AVL樹的"前序遍歷"、"中序遍歷"、"后序遍歷"、"最大值"、"最小值"、"查找"、"打印"、"銷毀"等接口與"二叉查找樹"基本一樣，這些操作在"二叉查找樹"中已經介紹過了，這里就不再單獨介紹了。當然，后文給出的AVL樹的完整源碼中，有給出這些API的實現代碼。這些接口很簡單，Please RTFSC(Read The Fucking Source Code)！

完整的實現代碼

AVL樹的實現文件(AVRTree.h)

?View Code

AVL樹的測試程序(AVLTreeTest.cpp)

?View Code

AVL樹的C++測試程序

AVL樹的測試程序代碼(AVLTreeTest.cpp)在前面已經給出。在測試程序中，首先新建一棵AVL樹，然后依次添加"3,2,1,4,5,6,7,16,15,14,13,12,11,10,8,9" 到AVL樹中；添加完畢之后，再將8從AVL樹中刪除。AVL樹的添加和刪除過程如下圖：

(01) 添加3,2
添加3,2都不會破壞AVL樹的平衡性。

(02) 添加1
添加1之后，AVL樹失去平衡(LL)，此時需要對AVL樹進行旋轉(LL旋轉)。旋轉過程如下：

(03) 添加4
添加4不會破壞AVL樹的平衡性。

(04) 添加5
添加5之后，AVL樹失去平衡(RR)，此時需要對AVL樹進行旋轉(RR旋轉)。旋轉過程如下：

(05) 添加6
添加6之后，AVL樹失去平衡(RR)，此時需要對AVL樹進行旋轉(RR旋轉)。旋轉過程如下：

(06) 添加7
添加7之后，AVL樹失去平衡(RR)，此時需要對AVL樹進行旋轉(RR旋轉)。旋轉過程如下：

(07) 添加16
添加16不會破壞AVL樹的平衡性。

(08) 添加15
添加15之后，AVL樹失去平衡(RR)，此時需要對AVL樹進行旋轉(RR旋轉)。旋轉過程如下：

(09) 添加14
添加14之后，AVL樹失去平衡(RL)，此時需要對AVL樹進行旋轉(RL旋轉)。旋轉過程如下：

(10) 添加13
添加13之后，AVL樹失去平衡(RR)，此時需要對AVL樹進行旋轉(RR旋轉)。旋轉過程如下：

(11) 添加12
添加12之后，AVL樹失去平衡(LL)，此時需要對AVL樹進行旋轉(LL旋轉)。旋轉過程如下：

(12) 添加11
添加11之后，AVL樹失去平衡(LL)，此時需要對AVL樹進行旋轉(LL旋轉)。旋轉過程如下：

(13) 添加10
添加10之后，AVL樹失去平衡(LL)，此時需要對AVL樹進行旋轉(LL旋轉)。旋轉過程如下：

(14) 添加8
添加8不會破壞AVL樹的平衡性。

(15) 添加9
但是添加9之后，AVL樹失去平衡(LR)，此時需要對AVL樹進行旋轉(LR旋轉)。旋轉過程如下：

添加完所有數據之后，得到的AVL樹如下：

接著，刪除節點8.刪除節點8并不會造成AVL樹的不平衡，所以不需要旋轉，操作示意圖如下：

程序運行結果如下：

== 依次添加: 3 2 1 4 5 6 7 16 15 14 13 12 11 10 8 9 == 前序遍歷: 7 4 2 1 3 6 5 13 11 9 8 10 12 15 14 16 == 中序遍歷: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 == 后序遍歷: 1 3 2 5 6 4 8 10 9 12 11 14 16 15 13 7 == 高度: 5 == 最小值: 1 == 最大值: 16 == 樹的詳細信息: is root is 7's left child is 4's left child is 2's left child is 2's right child is 4's right child is 6's left child is 7's right child is 13's left child is 11's left child is 9's left child is 9's right child is 11's right child is 13's right child is 15's left child is 15's right child== 刪除根節點: 8 == 高度: 5 == 中序遍歷: 1 2 3 4 5 6 7 9 10 11 12 13 14 15 16 == 樹的詳細信息: is root is 7's left child is 4's left child is 2's left child is 2's right child is 4's right child is 6's left child is 7's right child is 13's left child is 11's left child is 9's right child is 11's right child is 13's right child is 15's left child is 15's right child

總結

以上是生活随笔為你收集整理的AVL树(二)之 C++的实现的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。