C語言平衡二叉樹詳解
平衡二叉樹（Balanced Binary Tree）又被稱為AVL樹（有別于AVL算法），且具有以下性質(zhì)：它是一 棵空樹或它的左右兩個子樹的高度差的絕對值不超過1，并且左右兩個子樹都是一棵平衡二叉樹。這個方案很好的解決了二叉查找樹退化成鏈表的問題，把插入，查找，刪除的時間復(fù)雜度最好情況和最壞情況都維持在O(logN)。但是頻繁旋轉(zhuǎn)會使插入和刪除犧牲掉O(logN)左右的時間，不過相對二叉查找樹來說，時間上穩(wěn)定了很多。
平衡二叉樹大部分操作和二叉查找樹類似，主要不同在于插入刪除的時候平衡二叉樹的平衡可能被改變，并且只有從那些插入點到根結(jié)點的路徑上的結(jié)點的平衡性可能被改變，因為只有這些結(jié)點的子樹可能變化。
平衡二叉樹不平衡的情形：
把需要重新平衡的結(jié)點叫做α，由于任意兩個結(jié)點最多只有兩個兒子，因此高度不平衡時，α結(jié)點的兩顆子樹的高度相差2.容易看出，這種不平衡可能出現(xiàn)在下面4中情況中：
1.對α的左兒子的左子樹進(jìn)行一次插入
2.對α的左兒子的右子樹進(jìn)行一次插入
3.對α的右兒子的左子樹進(jìn)行一次插入
4.對α的右兒子的右子樹進(jìn)行一次插入
情形1和情形4是關(guān)于α的鏡像對稱，二情形2和情形3也是關(guān)于α的鏡像對稱，因此理論上看只有兩種情況，但編程的角度看還是四種情形。
第一種情況是插入發(fā)生在“外邊”的情形（左左或右右），該情況可以通過一次單旋轉(zhuǎn)完成調(diào)整；第二種情況是插入發(fā)生在“內(nèi)部”的情形（左右或右左），這種情況比較復(fù)雜，需要通過雙旋轉(zhuǎn)來調(diào)整。
調(diào)整措施：
一、單旋轉(zhuǎn)
上圖是左左的情況，k2結(jié)點不滿足平衡性，它的左子樹k1比右子樹z深兩層，k1子樹中更深的是k1的左子樹x，因此屬于左左情況。
為了恢復(fù)平衡，我們把x上移一層，并把z下移一層，但此時實際已經(jīng)超出了AVL樹的性質(zhì)要求。為此，重新安排結(jié)點以形成一顆等價的樹。為使樹恢復(fù)平衡，我們把k2變成這棵樹的根節(jié)點，因為k2大于k1，把k2置于k1的右子樹上，而原本在k1右子樹的Y大于k1，小于k2，就把Y置于k2的左子樹上，這樣既滿足了二叉查找樹的性質(zhì)，又滿足了平衡二叉樹的性質(zhì)。
這種情況稱為單旋轉(zhuǎn)。
二、雙旋轉(zhuǎn)
對于左右和右左兩種情況，單旋轉(zhuǎn)不能解決問題，要經(jīng)過兩次旋轉(zhuǎn)。
對于上圖情況，為使樹恢復(fù)平衡，我們需要進(jìn)行兩步，第一步，把k1作為根，進(jìn)行一次右右旋轉(zhuǎn)，旋轉(zhuǎn)之后就變成了左左情況，所以第二步再進(jìn)行一次左左旋轉(zhuǎn)，最后得到了一棵以k2為根的平衡二叉樹。
AVL樹的刪除操作：
同插入操作一樣，刪除結(jié)點時也有可能破壞平衡性，這就要求我們刪除的時候要進(jìn)行平衡性調(diào)整。
刪除分為以下幾種情況：
首先在整個二叉樹中搜索要刪除的結(jié)點，如果沒搜索到直接返回不作處理，否則執(zhí)行以下操作：
1.要刪除的節(jié)點是當(dāng)前根節(jié)點T。
如果左右子樹都非空。在高度較大的子樹中實施刪除操作。
分兩種情況：
(1)、左子樹高度大于右子樹高度，將左子樹中最大的那個元素賦給當(dāng)前根節(jié)點，然后刪除左子樹中元素值最大的那個節(jié)點。
(1)、左子樹高度小于右子樹高度，將右子樹中最小的那個元素賦給當(dāng)前根節(jié)點，然后刪除右子樹中元素值最小的那個節(jié)點。
如果左右子樹中有一個為空，那么直接用那個非空子樹或者是NULL替換當(dāng)前根節(jié)點即可。
2、要刪除的節(jié)點元素值小于當(dāng)前根節(jié)點T值，在左子樹中進(jìn)行刪除。
遞歸調(diào)用，在左子樹中實施刪除。
這個是需要判斷當(dāng)前根節(jié)點是否仍然滿足平衡條件，
如果滿足平衡條件，只需要更新當(dāng)前根節(jié)點T的高度信息。
否則，需要進(jìn)行旋轉(zhuǎn)調(diào)整：
如果T的左子節(jié)點的左子樹的高度大于T的左子節(jié)點的右子樹的高度，進(jìn)行相應(yīng)的單旋轉(zhuǎn)。否則進(jìn)行雙旋轉(zhuǎn)。
3、要刪除的節(jié)點元素值大于當(dāng)前根節(jié)點T值，在右子樹中進(jìn)行刪除。
下面給出詳細(xì)代碼實現(xiàn)：
AvlTree.h
#include <iostream>
#include <algorithm>
using namespace std;
#pragma once
//平衡二叉樹結(jié)點
template <typename T>
struct AvlNode
{
T data;
int height; //結(jié)點所在高度
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;
//插入結(jié)點
void Insert(AvlNode<T> *&t, T x);
//刪除結(jié)點
bool Delete(AvlNode<T> *&t, T x);
//查找是否存在給定值的結(jié)點
bool Contains(AvlNode<T> *t, const T x) const;
//中序遍歷
void InorderTraversal(AvlNode<T> *t);
//前序遍歷
void PreorderTraversal(AvlNode<T> *t);
//最小值結(jié)點
AvlNode<T> *FindMin(AvlNode<T> *t) const;
//最大值結(jié)點
AvlNode<T> *FindMax(AvlNode<T> *t) const;
private:
//求樹的高度
int GetHeight(AvlNode<T> *t);
//單旋轉(zhuǎn) 左
AvlNode<T> *LL(AvlNode<T> *t);
//單旋轉(zhuǎn) 右
AvlNode<T> *RR(AvlNode<T> *t);
//雙旋轉(zhuǎn) 右左
AvlNode<T> *LR(AvlNode<T> *t);
//雙旋轉(zhuǎn) 左右
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;
else
return t->height;
}
//單旋轉(zhuǎn)
//左左插入導(dǎo)致的不平衡
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;
}
//單旋轉(zhuǎn)
//右右插入導(dǎo)致的不平衡
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;
}
//雙旋轉(zhuǎn)
//插入點位于t的左兒子的右子樹
template <typename T>
AvlNode<T> * AvlTree<T>::LR(AvlNode<T> *t)
{
//雙旋轉(zhuǎn)可以通過兩次單旋轉(zhuǎn)實現(xiàn)
//對t的左結(jié)點進(jìn)行RR旋轉(zhuǎn)，再對根節(jié)點進(jìn)行LL旋轉(zhuǎn)
RR(t->left);
return LL(t);
}
//雙旋轉(zhuǎn)
//插入點位于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);
else
t = RL(t);
}
}
else
;//數(shù)據(jù)重復(fù)
t->height = max(GetHeight(t->left), GetHeight(t->right)) + 1;
}
template <typename T>
bool AvlTree<T>::Delete(AvlNode<T> *&t, T x)
{
//t為空 未找到要刪除的結(jié)點
if (t == NULL)
return false;
//找到了要刪除的結(jié)點
else if (t->data == x)
{
//左右子樹都非空
if (t->left != NULL && t->right != NULL)
{//在高度更大的那個子樹上進(jìn)行刪除操作
//左子樹高度大，刪除左子樹中值最大的結(jié)點，將其賦給根結(jié)點
if (GetHeight(t->left) > GetHeight(t->right))
{
t->data = FindMax(t->left)->data;
Delete(t->left, t->data);
}
else//右子樹高度更大，刪除右子樹中值最小的結(jié)點，將其賦給根結(jié)點
{
t->data = FindMin(t->right)->data;
Delete(t->right, t->data);
}
}
else
{//左右子樹有一個不為空，直接用需要刪除的結(jié)點的子結(jié)點替換即可
AvlNode<T> *old = t;
t = t->left ? t->left: t->right;//t賦值為不空的子結(jié)點
delete old;
}
}
else if (x < t->data)//要刪除的結(jié)點在左子樹上
{
//遞歸刪除左子樹上的結(jié)點
Delete(t->left, x);
//判斷是否仍然滿足平衡條件
if (GetHeight(t->right) - GetHeight(t->left) > 1)
{
if (GetHeight(t->right->left) > GetHeight(t->right->right))
{
//RL雙旋轉(zhuǎn)
t = RL(t);
}
else
{//RR單旋轉(zhuǎn)
t = RR(t);
}
}
else//滿足平衡條件 調(diào)整高度信息
{
t->height = max(GetHeight(t->left), GetHeight(t->right)) + 1;
}
}
else//要刪除的結(jié)點在右子樹上
{
//遞歸刪除右子樹結(jié)點
Delete(t->right, x);
//判斷平衡情況
if (GetHeight(t->left) - GetHeight(t->right) > 1)
{
if (GetHeight(t->left->right) > GetHeight(t->left->left))
{
//LR雙旋轉(zhuǎn)
t = LR(t);
}
else
{
//LL單旋轉(zhuǎn)
t = LL(t);
}
}
else//滿足平衡性 調(diào)整高度
{
t->height = max(GetHeight(t->left), GetHeight(t->right)) + 1;
}
}
return true;
}
//查找結(jié)點
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);
else
return 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 << "請輸入整數(shù)建立二叉樹(-1結(jié)束)：" << 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請輸入要查找的結(jié)點：";
cin >> tmp;
if (tree.Contains(tree.root, tmp))
cout << "已查找到" << endl;
else
cout << "值為" << tmp << "的結(jié)點不存在" << endl;
cout << "請輸入要刪除的結(jié)點：";
cin >> tmp;
tree.Delete(tree.root, tmp);
cout << "刪除后的中序遍歷：";
tree.InorderTraversal(tree.root);
cout << "\n刪除后的前序遍歷：";
tree.PreorderTraversal(tree.root);
}
測試結(jié)果：
總結(jié)
本篇文章就到這里了，希望能夠給你帶來幫助，也希望您能夠多多關(guān)注腳本之家的更多內(nèi)容!
相關(guān)文章
這篇文章主要為大家詳細(xì)介紹了如何利用C++實現(xiàn)一個反射類，文中的示例代碼講解詳細(xì)，具有一定的參考價值，感興趣的小伙伴可以跟隨小編一起學(xué)習(xí)一下2023-03-03
這篇文章主要介紹了關(guān)于Dev-C++安裝及使用方式,具有很好的參考價值,希望對大家有所幫助,如有錯誤或未考慮完全的地方,望不吝賜教2023-09-09
C語言驅(qū)動開發(fā)內(nèi)核特征碼掃描PE代碼段
這篇文章主要為大家介紹了C語言驅(qū)動開發(fā)內(nèi)核特征碼掃描PE代碼段，有需要的朋友可以借鑒參考下，希望能夠有所幫助，祝大家多多進(jìn)步，早日升職加薪2022-10-10
這篇文章主要介紹了C語言實現(xiàn)最簡單的剪刀石頭布小游戲,涉及C語言數(shù)組、隨機(jī)數(shù)與數(shù)值運算等相關(guān)操作技巧,需要的朋友可以參考下2017-09-09
這篇文章主要為大家介紹了C語言的指針，具有一定的參考價值，感興趣的小伙伴們可以參考一下，希望能夠給你帶來幫助2022-01-01
這篇文章主要介紹了C++函數(shù)對象詳解附帶實例，文中通過示例代碼介紹的非常詳細(xì)，對大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價值，需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧2021-03-03
C++數(shù)據(jù)結(jié)構(gòu)之文件壓縮（哈夫曼樹）實例詳解
這篇文章主要介紹了C++數(shù)據(jù)結(jié)構(gòu)之文件壓縮（哈夫曼樹）實例詳解的相關(guān)資料,利用哈夫曼編碼的方式對文件進(jìn)行壓縮，并且對壓縮文件可以解壓，需要的朋友可以參考下2017-07-07
C++中4種強(qiáng)制類型轉(zhuǎn)換的區(qū)別總結(jié)
C++風(fēng)格的類型轉(zhuǎn)換提供了4種類型轉(zhuǎn)換操作符來應(yīng)對不同場合的應(yīng)用。下面這篇文章主要給大家介紹了C++中4種強(qiáng)制類型轉(zhuǎn)換的區(qū)別，有需要的朋友們可以參考借鑒，下面來一起看看吧。2016-12-12
c++中虛函數(shù)和純虛函數(shù)的作用與區(qū)別
這篇文章主要介紹了c++中虛函數(shù)和純虛函數(shù)的作用與區(qū)別,需要的朋友可以參考下2014-07-07
這篇文章主要為大家詳細(xì)介紹了opengl繪制五星紅旗的方法，文中示例代碼介紹的非常詳細(xì)，具有一定的參考價值，感興趣的小伙伴們可以參考一下2019-09-09