平衡树以及AVL树
平衡樹是計(jì)算機(jī)科學(xué)中的一類數(shù)據(jù)結(jié)構(gòu)。?平衡樹是計(jì)算機(jī)科學(xué)中的一類改進(jìn)的二叉查找樹。一般的二叉查找樹的查詢復(fù)雜度是跟目標(biāo)結(jié)點(diǎn)到樹根的距離（即深度）有關(guān)，因此當(dāng)結(jié)點(diǎn)的深度普遍較大時(shí)，查詢的均攤復(fù)雜度會(huì)上升，為了更高效的查詢，平衡樹應(yīng)運(yùn)而生了。
在這里，平衡指所有葉子的深度趨于平衡，更廣義的是指在樹上所有可能查找的均攤復(fù)雜度偏低。
幾乎所有平衡樹的操作都基于樹操作，通過旋轉(zhuǎn)操作可以使得樹趨于平衡。 對(duì)一棵查找樹（search tree）進(jìn)行查詢/新增/刪除 等動(dòng)作, 所花的時(shí)間與樹的高度h 成比例, 并不與樹的容量 n 成比例。如果可以讓樹維持矮矮胖胖的好身材, 也就是讓h維持在O(lg n)左右, 完成上述工作就很省時(shí)間。能夠一直維持好身材, 不因新增刪除而長(zhǎng)歪的搜尋樹, 叫做balanced search tree（平衡樹）。 旋轉(zhuǎn)Rotate —— 不破壞左小右大特性的小手術(shù) 平衡樹有很多種, 其中有幾類樹維持平衡的方法, 都是靠整形小手術(shù)。
各種平衡樹：AVL樹，經(jīng)典平衡樹，所有操作的最壞復(fù)雜度是O(lgN)的。
Treap，利用隨機(jī)堆的期望深度來優(yōu)化樹的深度，達(dá)到較優(yōu)的期望復(fù)雜度。
伸展樹、紅黑樹，節(jié)點(diǎn)大小平衡樹。2-3樹、AA樹。
?
AVL樹：
AVL樹是一棵自平衡的二叉搜索樹，在AVL樹中任何節(jié)點(diǎn)的兩個(gè)子樹的高度最大差別為一，所以它也被稱為高度平衡樹。查找、插入和刪除在平均和最壞情況下都是O(lgN)
?
為什么需要AVL樹：
大多數(shù)二叉查找操作（搜索、最大、最小、插入、刪除...)會(huì)花費(fèi)O(h)，h是二叉搜索樹的高度。對(duì)于不平衡的二叉查找樹，這些操作的時(shí)間復(fù)雜度為O(n)。如果我們保證在每一次插入和刪除之后樹的高度為O(lgN)，那么我們就能保證對(duì)于所有的操作都有O(lgN)的上界。AVL樹的高度總是O(logN)，n是樹中節(jié)點(diǎn)的數(shù)量。
?
2. 旋轉(zhuǎn)
如果在AVL樹中進(jìn)行插入或刪除節(jié)點(diǎn)后，可能導(dǎo)致AVL樹失去平衡。這種失去平衡的可以概括為4種姿態(tài)：LL(左左)，LR(左右)，RR(右右)和RL(右左)。下面給出它們的示意圖：
上圖中的4棵樹都是"失去平衡的AVL樹"，從左往右的情況依次是：LL、LR、RL、RR。除了上面的情況之外，還有其它的失去平衡的AVL樹，如下圖：
上面的兩張圖都是為了便于理解，而列舉的關(guān)于"失去平衡的AVL樹"的例子。總的來說，AVL樹失去平衡時(shí)的情況一定是LL、LR、RL、RR這4種之一，它們都由各自的定義：
(1)?LL：LeftLeft，也稱為"左左"。插入或刪除一個(gè)節(jié)點(diǎn)后，根節(jié)點(diǎn)的左子樹的左子樹還有非空子節(jié)點(diǎn)，導(dǎo)致"根的左子樹的高度"比"根的右子樹的高度"大2，導(dǎo)致AVL樹失去了平衡。
? ? ?例如，在上面LL情況中，由于"根節(jié)點(diǎn)(8)的左子樹(4)的左子樹(2)還有非空子節(jié)點(diǎn)"，而"根節(jié)點(diǎn)(8)的右子樹(12)沒有子節(jié)點(diǎn)"；導(dǎo)致"根節(jié)點(diǎn)(8)的左子樹(4)高度"比"根節(jié)點(diǎn)(8)的右子樹(12)"高2。
?
(2)?LR：LeftRight，也稱為"左右"。插入或刪除一個(gè)節(jié)點(diǎn)后，根節(jié)點(diǎn)的左子樹的右子樹還有非空子節(jié)點(diǎn)，導(dǎo)致"根的左子樹的高度"比"根的右子樹的高度"大2，導(dǎo)致AVL樹失去了平衡。
? ? ?例如，在上面LR情況中，由于"根節(jié)點(diǎn)(8)的左子樹(4)的左子樹(6)還有非空子節(jié)點(diǎn)"，而"根節(jié)點(diǎn)(8)的右子樹(12)沒有子節(jié)點(diǎn)"；導(dǎo)致"根節(jié)點(diǎn)(8)的左子樹(4)高度"比"根節(jié)點(diǎn)(8)的右子樹(12)"高2。
?
(3)?RL：RightLeft，稱為"右左"。插入或刪除一個(gè)節(jié)點(diǎn)后，根節(jié)點(diǎn)的右子樹的左子樹還有非空子節(jié)點(diǎn)，導(dǎo)致"根的右子樹的高度"比"根的左子樹的高度"大2，導(dǎo)致AVL樹失去了平衡。
? ? ?例如，在上面RL情況中，由于"根節(jié)點(diǎn)(8)的右子樹(12)的左子樹(10)還有非空子節(jié)點(diǎn)"，而"根節(jié)點(diǎn)(8)的左子樹(4)沒有子節(jié)點(diǎn)"；導(dǎo)致"根節(jié)點(diǎn)(8)的右子樹(12)高度"比"根節(jié)點(diǎn)(8)的左子樹(4)"高2。
?
(4)?RR：RightRight，稱為"右右"。插入或刪除一個(gè)節(jié)點(diǎn)后，根節(jié)點(diǎn)的右子樹的右子樹還有非空子節(jié)點(diǎn)，導(dǎo)致"根的右子樹的高度"比"根的左子樹的高度"大2，導(dǎo)致AVL樹失去了平衡。
? ? ?例如，在上面RR情況中，由于"根節(jié)點(diǎn)(8)的右子樹(12)的右子樹(14)還有非空子節(jié)點(diǎn)"，而"根節(jié)點(diǎn)(8)的左子樹(4)沒有子節(jié)點(diǎn)"；導(dǎo)致"根節(jié)點(diǎn)(8)的右子樹(12)高度"比"根節(jié)點(diǎn)(8)的左子樹(4)"高2。
?
前面說過，如果在AVL樹中進(jìn)行插入或刪除節(jié)點(diǎn)后，可能導(dǎo)致AVL樹失去平衡。AVL失去平衡之后，可以通過旋轉(zhuǎn)使其恢復(fù)平衡，下面分別介紹"LL(左左)，LR(左右)，RR(右右)和RL(右左)"這4種情況對(duì)應(yīng)的旋轉(zhuǎn)方法。
?
2.1 LL的旋轉(zhuǎn)
LL失去平衡的情況，可以通過一次旋轉(zhuǎn)讓AVL樹恢復(fù)平衡。如下圖：
圖中左邊是旋轉(zhuǎn)之前的樹，右邊是旋轉(zhuǎn)之后的樹。從中可以發(fā)現(xiàn)，旋轉(zhuǎn)之后的樹又變成了AVL樹，而且該旋轉(zhuǎn)只需要一次即可完成。
對(duì)于LL旋轉(zhuǎn)，你可以這樣理解為：LL旋轉(zhuǎn)是圍繞"失去平衡的AVL根節(jié)點(diǎn)"進(jìn)行的，也就是節(jié)點(diǎn)k2；而且由于是LL情況，即左左情況，就用手抓著"左孩子，即k1"使勁搖。將k1變成根節(jié)點(diǎn)，k2變成k1的右子樹，"k1的右子樹"變成"k2的左子樹"。
?
LL的旋轉(zhuǎn)代碼
1 template<typename T> 2 void AVLTree<T>::RotateWithLeftChild(AVLTreeNode* &z) { 3 AVLTreeNode* y = z->left; 4 z->left = y->right; 5 y->right = z; 6 z->height = max(GetHeight(z->left), GetHeight(z->right)) + 1; 7 y->right = max(GetHeight(y->left), z->height)) + 1; 8 z = y; 9 }?
?
2.2 RR的旋轉(zhuǎn)
理解了LL之后，RR就相當(dāng)容易理解了。RR是與LL對(duì)稱的情況！RR恢復(fù)平衡的旋轉(zhuǎn)方法如下：
圖中左邊是旋轉(zhuǎn)之前的樹，右邊是旋轉(zhuǎn)之后的樹。RR旋轉(zhuǎn)也只需要一次即可完成。
?
RR的旋轉(zhuǎn)代碼
1 template<typename T> 2 void AVLTree<T>::RotateWithRightChild(AVLTreeNode* &z) { 3 AVLTreeNode* y = z->right; 4 z->right = y->left; 5 y->left = z; 6 z->height = max(GetHeight(z->left), GetHeight(z->right)) + 1; 7 y->right = max(GetHeight(y->right), z->height)) + 1; 8 z = y; 9 }?
?
2.3 LR的旋轉(zhuǎn)
LR失去平衡的情況，需要經(jīng)過兩次旋轉(zhuǎn)才能讓AVL樹恢復(fù)平衡。如下圖：
第一次旋轉(zhuǎn)是圍繞"k1"進(jìn)行的"RR旋轉(zhuǎn)"，第二次是圍繞"k3"進(jìn)行的"LL旋轉(zhuǎn)"。
?
LR的旋轉(zhuǎn)代碼
1 template<typename T> 2 void AVLTree<T>::DoubleWithLeftChild(AVLTreeNode* &z) { 3 RotateWithRightChild(z->left); 4 RotateWithLeftChild(z); 5 }?
?
?
2.4 RL的旋轉(zhuǎn)
RL是與LR的對(duì)稱情況！RL恢復(fù)平衡的旋轉(zhuǎn)方法如下：
第一次旋轉(zhuǎn)是圍繞"k3"進(jìn)行的"LL旋轉(zhuǎn)"，第二次是圍繞"k1"進(jìn)行的"RR旋轉(zhuǎn)"。
RL的旋轉(zhuǎn)代碼
?
插入：
向AVL樹插入，可以透過如同它是未平衡的二叉查找樹一樣，把給定的值插入樹中，接著自底往上向根節(jié)點(diǎn)折回，于在插入期間成為不平衡的所有節(jié)點(diǎn)上進(jìn)行旋轉(zhuǎn)來完成。因?yàn)檎刍氐礁?jié)點(diǎn)的路途上最多有1.44乘log?n個(gè)節(jié)點(diǎn)，而每次AVL旋轉(zhuǎn)都耗費(fèi)固定的時(shí)間，所以插入處理在整體上的耗費(fèi)為O(log?n) 時(shí)間。
?
?刪除：
從AVL樹中刪除，可以通過把要?jiǎng)h除的節(jié)點(diǎn)向下旋轉(zhuǎn)成一個(gè)葉子節(jié)點(diǎn)，接著直接移除這個(gè)葉子節(jié)點(diǎn)來完成。因?yàn)樵谛D(zhuǎn)成葉子節(jié)點(diǎn)期間最多有l(wèi)og?n個(gè)節(jié)點(diǎn)被旋轉(zhuǎn)，而每次AVL旋轉(zhuǎn)耗費(fèi)固定的時(shí)間，所以刪除處理在整體上耗費(fèi)O(log?n) 時(shí)間。
?查找
可以像普通二叉查找樹一樣的進(jìn)行，所以耗費(fèi)O(log?n)時(shí)間，因?yàn)锳VL樹總是保持平衡的。不需要特殊的準(zhǔn)備，樹的結(jié)構(gòu)不會(huì)由于查找而改變。
?
代碼：
頭文件：
1 #ifndef AVL_TREE_H_ 2 #define AVL_TREE_H_ 3 4 template<typename T> 5 class AVLTree { 6 public: 7 AVLTree():root_(NULL){} 8 AVLTree(const AVLTree &rhs){} 9 AVLTree& operator=(const AVLTree &rhs){} 10 ~AVLTree(){} 11 12 void Insert(const T& k) { 13 Insert(root_, k); 14 } 15 16 void Remove(const T& k) { 17 Remove(root_, k); 18 } 19 20 private: 21 struct AVLTreeNode { 22 T key; 23 int height; 24 AVLTreeNode* left; 25 AVLTreeNode* right; 26 27 AVLTreeNode(const T& k, AVLTreeNode* l = NULL, AVLTreeNode * r = NULL, int h = 0) 28 : key(k), left(l), right(r), height(h) {} 29 }; 30 31 AVLTreeNode *root_; //根節(jié)點(diǎn) 32 33 int GetHeight(AVLTreeNode* p) const { 34 return p == NULL ? -1 : p->height; 35 } 36 37 void Insert(AVLTreeNode* &p, const T& k); 38 void Remove(AVLTreeNode* &p, const T& k); 39 40 void RotateWithLeftChild(AVLTreeNode* &z); 41 void RotateWithRightChild(AVLTreeNode* &z); 42 43 void DoubleWithLeftChild(AVLTreeNode* &z); 44 void DoubleWithRightChild(AVLTreeNode* &z); 45 46 AVLTreeNode* FindMin(AVLTreeNode* p) const; 47 }; 48 #endif?
源文件：
1 #include "avl_tree.h" 2 3 //LL 4 template<typename T> 5 void AVLTree<T>::RotateWithLeftChild(AVLTreeNode* &z) { 6 AVLTreeNode* y = z->left; 7 z->left = y->right; 8 y->right = z; 9 z->height = max(GetHeight(z->left), GetHeight(z->right)) + 1; 10 y->right = max(GetHeight(y->left), z->height) + 1; 11 z = y; 12 } 13 14 //RR 15 template<typename T> 16 void AVLTree<T>::RotateWithRightChild(AVLTreeNode* &z) { 17 AVLTreeNode* y = z->right; 18 z->right = y->left; 19 y->left = z; 20 z->height = max(GetHeight(z->left), GetHeight(z->right)) + 1; 21 y->right = max(GetHeight(y->right), z->height) + 1; 22 z = y; 23 } 24 25 //LR 26 template<typename T> 27 void AVLTree<T>::DoubleWithLeftChild(AVLTreeNode* &z) { 28 RotateWithRightChild(z->left); 29 RotateWithLeftChild(z); 30 } 31 32 //RL 33 template<typename T> 34 void AVLTree<T>::DoubleWithRightChild(AVLTreeNode* &z) { 35 RotateWithRightChild(z->right); 36 RotateWithLeftChild(z); 37 } 38 39 template<typename T> 40 void AVLTree<T>::Insert(AVLTreeNode* &p, const T& k) { 41 if (p == NULL) { 42 t = new AVLTreeNode(k); 43 } else if (k < p->key) { //左子樹中插入 44 Insert(p->left, k); 45 if (GetHeight(p->left) - GetHeight(p->right) == 2) { //雖然每次都檢查，但是只調(diào)整最后一次 46 if (k < p->left->key) { //LL 47 RotateWithLeftChild(p); 48 } else { //LR 49 DoubleWithLeftChild(p); 50 } 51 } 52 } else if (k > p->val) {//在右子樹中插入 53 Insert(p->right, k); 54 if (GetHeight(p->right) - GetHeight(p->left) == 2) { 55 if (x > p->right->key) {//RR 56 RotateWithRightChild(p); 57 } else { //RL 58 DoubleWithRightChild(p); 59 } 60 } 61 }else 62 ; //重復(fù) 63 64 p->height = max(GetHeight(p->left), GetHeight(p->right)) + 1; 65 } 66 67 68 template<typename T> 69 void AVLTree<T>::Remove(AVLTreeNode* &p, const T& k) { 70 if (p == NULL) return; 71 if (p->key > k) { 72 Remove(p->left, k); 73 if (GetHeight(p->right) - GetHeight(p->left) == 2) { 74 if (p->right->right != NULL) { 75 RotateWithRightChild(p); 76 } else { 77 DoubleWithRightChild(p); 78 } 79 } 80 }else if (p->key < k) { 81 Remove(p->right, k); 82 if (GetHeight(p->left) - GetHeight(p->right) == 2) { 83 if (p->left->left != NULL) { 84 RotateWithLeftChild(p); 85 } else { 86 DoubleWithLeftChild(p); 87 } 88 } 89 } else if (p->left != NULL && p->right != NULL) { 90 p->key = FindMin(p->right)->key; //用右子樹最小節(jié)點(diǎn)鍵值代替要?jiǎng)h除節(jié)點(diǎn)的鍵值，與二叉搜索樹類似 91 Remove(p->right, p->key); 92 if (GetHeight(p->left) - GetHeight(p->right) == 2) { 93 if (p->left->left != NULL) { 94 RotateWithLeftChild(p); 95 } else { 96 DoubleWithLeftChild(p); 97 } 98 } 99 } else { 100 AVLTreeNode* temp = p; 101 p = p->left ? p->left : p->right; 102 delete temp; 103 } 104 105 if (p != NULL) { 106 p->height = max(GetHeight(p->left), GetHeight(p->right)) + 1; 107 } 108 } 109 110 111 template<typename T> 112 typename AVLTree<T>::AVLTreeNode* AVLTree<T>::FindMin(AVLTreeNode* p) const { 113 AVLTreeNode* t = p; 114 while (t != NULL && t->left != NULL) { 115 t = t->left; 116 } 117 118 return t; 119 }
?
參考文獻(xiàn)：1.《數(shù)據(jù)結(jié)構(gòu)與算法分析C++描述》(第三版）——Mark Allen Weiss， 人民郵電出版社
2. http://blog.csdn.net/pyang1989/article/details/22697121
轉(zhuǎn)載于:https://www.cnblogs.com/vincently/p/4225976.html
總結(jié)
- 上一篇： C 语言第6节课
- 下一篇： 计算机保研夏令营预推免