目錄

1.什么是平衡二叉樹

2.平衡二叉樹的失衡調整

2.1?左旋

2.2 右旋

3. AVL樹的四種插入節點方式

4.平衡二叉樹完整代碼實現

5.紅黑樹與平衡二叉樹

5.1 紅黑樹的性質

5.2 旋轉和顏色變化規則

5.3 平衡二叉樹(AVL)的性質?

---

1.什么是平衡二叉樹

在AVL樹中，任一節點對應的兩棵子樹的最大高度差為1，因此它也被稱為高度平衡樹。查找、插入和刪除在平均和最壞情況下的時間復雜度都是O(log n)。

可以是空樹。

假如不是空樹，任何一個結點的左子樹與右子樹都是平衡二叉樹，并且高度之差的絕對值不超過 1。

增加和刪除元素的操作則可能需要借由一次或多次樹旋轉，以實現樹的重新平衡。

二叉搜索樹一定程度上可以提高搜索效率，但是當原序列有序時，例如序列 A = {1，2，3，4，5，6}，構造二叉搜索樹如圖 1.1。依據此序列構造的二叉搜索樹為右斜樹，同時二叉樹退化成單鏈表，搜索效率降低為 O(n)。

2.平衡二叉樹的失衡調整

主要是通過旋轉最小失衡子樹來實現的。根據旋轉的方向有兩種處理方式，左旋?與?右旋?。

旋轉的目的就是減少高度，通過降低整棵樹的高度來平衡。哪邊的樹高，就把那邊的樹向上旋轉。

2.1?左旋

當插入的新節點在節點右子樹的右子樹位置時。

簡稱：右右->左旋

（1）原節點的右孩子替代此節點位置

（2）原節點右孩子的左子樹變為該節點的右子樹

（3）原節點本身變為右孩子新節點的左子樹

2.2 右旋

當新插入是節點左子樹的左子樹時，需要右旋。

右旋操作與左旋類似，操作流程為：

（1）原節點的左孩子代表此節點

（2）原節點的左孩子的右子樹變為節點的左子樹

（3）將原節點作為左孩子新節點的右子樹。

3. AVL樹的四種插入節點方式

插入方式：LL
描述：在 A 的左子樹根節點的左子樹上插入節點而破壞平衡
旋轉方式：右旋轉

插入方式：RR
描述：在 A 的右子樹根節點的右子樹上插入節點而破壞平衡
旋轉方式：左旋轉

插入方式：LR
描述：在A的左子樹根節點的右子樹上插入節點而破壞平衡
旋轉方式：先左旋后右旋

插入方式：RL
描述：在 A 的右子樹根節點的左子樹上插入節點而破壞平衡
旋轉方式：先右旋后左旋

4.平衡二叉樹完整代碼實現

AvlTree.h

#include <iostream> #include <algorithm> using namespace std; #pragma once//平衡二叉樹結點 template <typename T> struct AvlNode {T data;int height; //結點所在高度AvlNode<T> *left;AvlNode<T> *right;AvlNode<T>(const T theData) : data(theData), left(NULL), right(NULL), height(0){} };//AvlTree template <typename T> class AvlTree { public:AvlTree<T>(){}~AvlTree<T>(){}AvlNode<T> *root;//插入結點void Insert(AvlNode<T> *&t, T x);//刪除結點bool Delete(AvlNode<T> *&t, T x);//查找是否存在給定值的結點bool Contains(AvlNode<T> *t, const T x) const;//中序遍歷void InorderTraversal(AvlNode<T> *t);//前序遍歷void PreorderTraversal(AvlNode<T> *t);//最小值結點AvlNode<T> *FindMin(AvlNode<T> *t) const;//最大值結點AvlNode<T> *FindMax(AvlNode<T> *t) const; private://求樹的高度int GetHeight(AvlNode<T> *t);//單旋轉 左AvlNode<T> *LL(AvlNode<T> *t);//單旋轉 右AvlNode<T> *RR(AvlNode<T> *t);//雙旋轉 右左AvlNode<T> *LR(AvlNode<T> *t);//雙旋轉 左右AvlNode<T> *RL(AvlNode<T> *t); };template <typename T> AvlNode<T> * AvlTree<T>::FindMax(AvlNode<T> *t) const {if (t == NULL)return NULL;if (t->right == NULL)return t;return FindMax(t->right); }template <typename T> AvlNode<T> * AvlTree<T>::FindMin(AvlNode<T> *t) const {if (t == NULL)return NULL;if (t->left == NULL)return t;return FindMin(t->left); }template <typename T> int AvlTree<T>::GetHeight(AvlNode<T> *t) {if (t == NULL)return -1;elsereturn t->height; }//單旋轉 //左左插入導致的不平衡 template <typename T> AvlNode<T> * AvlTree<T>::LL(AvlNode<T> *t) {AvlNode<T> *q = t->left;t->left = q->right;q->right = t;t = q;t->height = max(GetHeight(t->left), GetHeight(t->right)) + 1;q->height = max(GetHeight(q->left), GetHeight(q->right)) + 1;return q; }//單旋轉 //右右插入導致的不平衡 template <typename T> AvlNode<T> * AvlTree<T>::RR(AvlNode<T> *t) {AvlNode<T> *q = t->right;t->right = q->left;q->left = t;t = q;t->height = max(GetHeight(t->left), GetHeight(t->right)) + 1;q->height = max(GetHeight(q->left), GetHeight(q->right)) + 1;return q; }//雙旋轉 //插入點位于t的左兒子的右子樹 template <typename T> AvlNode<T> * AvlTree<T>::LR(AvlNode<T> *t) {//雙旋轉可以通過兩次單旋轉實現//對t的左結點進行RR旋轉，再對根節點進行LL旋轉RR(t->left);return LL(t); }//雙旋轉 //插入點位于t的右兒子的左子樹 template <typename T> AvlNode<T> * AvlTree<T>::RL(AvlNode<T> *t) {LL(t->right);return RR(t); }template <typename T> void AvlTree<T>::Insert(AvlNode<T> *&t, T x) {if (t == NULL)t = new AvlNode<T>(x);else if (x < t->data){Insert(t->left, x);//判斷平衡情況if (GetHeight(t->left) - GetHeight(t->right) > 1){//分兩種情況 左左或左右if (x < t->left->data)//左左t = LL(t);else //左右t = LR(t);}}else if (x > t->data){Insert(t->right, x);if (GetHeight(t->right) - GetHeight(t->left) > 1){if (x > t->right->data)t = RR(t);elset = RL(t);}}else;//數據重復t->height = max(GetHeight(t->left), GetHeight(t->right)) + 1; }template <typename T> bool AvlTree<T>::Delete(AvlNode<T> *&t, T x) {//t為空 未找到要刪除的結點if (t == NULL)return false;//找到了要刪除的結點else if (t->data == x){//左右子樹都非空if (t->left != NULL && t->right != NULL){//在高度更大的那個子樹上進行刪除操作//左子樹高度大，刪除左子樹中值最大的結點，將其賦給根結點if (GetHeight(t->left) > GetHeight(t->right)){t->data = FindMax(t->left)->data;Delete(t->left, t->data);}else//右子樹高度更大，刪除右子樹中值最小的結點，將其賦給根結點{t->data = FindMin(t->right)->data;Delete(t->right, t->data);}}else{//左右子樹有一個不為空，直接用需要刪除的結點的子結點替換即可AvlNode<T> *old = t;t = t->left ? t->left: t->right;//t賦值為不空的子結點delete old;}}else if (x < t->data)//要刪除的結點在左子樹上{//遞歸刪除左子樹上的結點Delete(t->left, x);//判斷是否仍然滿足平衡條件if (GetHeight(t->right) - GetHeight(t->left) > 1){if (GetHeight(t->right->left) > GetHeight(t->right->right)){//RL雙旋轉t = RL(t);}else{//RR單旋轉t = RR(t);}}else//滿足平衡條件 調整高度信息{t->height = max(GetHeight(t->left), GetHeight(t->right)) + 1;}}else//要刪除的結點在右子樹上{//遞歸刪除右子樹結點Delete(t->right, x);//判斷平衡情況if (GetHeight(t->left) - GetHeight(t->right) > 1){if (GetHeight(t->left->right) > GetHeight(t->left->left)){//LR雙旋轉t = LR(t);}else{//LL單旋轉t = LL(t);}}else//滿足平衡性 調整高度{t->height = max(GetHeight(t->left), GetHeight(t->right)) + 1;}}return true; }//查找結點 template <typename T> bool AvlTree<T>::Contains(AvlNode<T> *t, const T x) const {if (t == NULL)return false;if (x < t->data)return Contains(t->left, x);else if (x > t->data)return Contains(t->right, x);elsereturn true; }//中序遍歷 template <typename T> void AvlTree<T>::InorderTraversal(AvlNode<T> *t) {if (t){InorderTraversal(t->left);cout << t->data << ' ';InorderTraversal(t->right);} }//前序遍歷 template <typename T> void AvlTree<T>::PreorderTraversal(AvlNode<T> *t) {if (t){cout << t->data << ' ';PreorderTraversal(t->left);PreorderTraversal(t->right);} }

main.cpp

#include "AvlTree.h"int main() {AvlTree<int> tree;int value;int tmp;cout << "請輸入整數建立二叉樹(-1結束)：" << endl;while (cin >> value){if (value == -1)break;tree.Insert(tree.root,value);}cout << "中序遍歷";tree.InorderTraversal(tree.root);cout << "\n前序遍歷:";tree.PreorderTraversal(tree.root);cout << "\n請輸入要查找的結點：";cin >> tmp;if (tree.Contains(tree.root, tmp))cout << "已查找到" << endl;elsecout << "值為" << tmp << "的結點不存在" << endl;cout << "請輸入要刪除的結點：";cin >> tmp;tree.Delete(tree.root, tmp);cout << "刪除后的中序遍歷：";tree.InorderTraversal(tree.root);cout << "\n刪除后的前序遍歷：";tree.PreorderTraversal(tree.root); }

5.紅黑樹與平衡二叉樹

5.1 紅黑樹的性質

性質1.節點是紅色或黑色。

性質2.根節點是黑色。

性質3.每個葉子節點都是黑色的空節點（NIL節點）。

性質4 每個紅色節點的兩個子節點都是黑色。(從每個葉子到根的所有路徑上不能有兩個連續的紅色節點)

性質5.從任一節點到其每個葉子的所有路徑都包含相同數目的黑色節點。

這些約束強制了紅黑樹的關鍵性質:?從根到葉子的最長的可能路徑不多于最短的可能路徑的兩倍長。結果是這個樹大致上是平衡的。因為操作比如插入、刪除和查找某個值的最壞情況時間都要求與樹的高度成比例，這個在高度上的理論上限允許紅黑樹在最壞情況下都是高效的，而不同于普通的二叉查找樹。

5.2 旋轉和顏色變化規則

1、添加的節點必須為紅色

2、變色的情況：當前結點的父親是紅色，且它的叔結點也是紅色：

　　2.1?把父節點設置為黑色

　　2.2?把叔節點設置為黑色

　　2.3?把祖父節點設置為紅色

　　2.4?把當前指針定義到祖父節點，設為當前要操作的

3、左旋的情況：當前父節點是紅色，叔節點是黑色，且當前的節點是右子樹。

　　3.1?以父節點作為左旋。

4、右旋的情況：當前父節點是紅色，叔節點是黑色，且當前的節點是左子樹。

　　4.1?把父節點變成黑色

　　4.2?把祖父節點變為紅色

　　4.3?以祖父節點右旋轉

5.3 平衡二叉樹(AVL)的性質?

它是一 棵空樹或它的左右兩個子樹的高度差的絕對值不超過1，并且左右兩個子樹都是一棵平衡二叉樹。這個方案很好的解決了二叉查找樹退化成鏈表的問題，把插入，查找，刪除的時間復雜度最好情況和最壞情況都維持在O(logN)。但是頻繁旋轉會使插入和刪除犧牲掉O(logN)左右的時間，不過相對二叉查找樹來說，時間上穩定了很多。

區別：?

1、紅黑樹放棄了追求完全平衡，追求大致平衡，在與平衡二叉樹的時間復雜度相差不大的情況下，保證每次插入最多只需要三次旋轉就能達到平衡，實現起來也更為簡單。

2、平衡二叉樹追求絕對平衡，條件比較苛刻，實現起來比較麻煩，每次插入新節點之后需要旋轉的次數不能預知。

總結

以上是生活随笔為你收集整理的详解平衡二叉树（AVL），红黑树与平衡二叉树的区别的全部內容，希望文章能夠幫你解決所遇到的問題。

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