前情回顧：二叉搜索樹 👉傳送門
本章我們將學習AVL樹，來解決上一章節(jié)二叉搜索樹的查找時二叉樹不平衡的問題，搬好小板凳準備開講啦~~~ 🙋 🙋 🙋 🙋 🙋
兩位俄羅斯的數(shù)學家G.M.Adelson-Velskii和E.M.Landis（AVL樹就是以這兩位科學家的名字命名的）
在1962年發(fā)明了一種解決上述問題的方法：
當向二叉搜索樹中插入新結(jié)點后，如果能保證每個結(jié)點的左右子樹高度之差的絕對值不超過1(需要對樹中的結(jié)點進行調(diào)整)，即可降低樹的高度，從而減少平均搜索長度。
1.2 AVL樹的性質(zhì)：首先AVL樹是一棵二叉搜索樹，一棵AVL樹或者是空樹，或者是具有以下性質(zhì)的二叉搜索樹：
平衡不是相等，與滿二叉樹和完全二叉樹比較一下：（節(jié)點外數(shù)字代表平衡因子）
AVL樹又叫高度平衡二叉搜索樹。
如果一棵二叉搜索樹是高度平衡的，它就是AVL樹。如果它有n個結(jié)點，其高度可保持在 〇（logN）搜索時間復雜度 〇（logN）。
具體代碼如下：
重慶分公司
重慶分公司
templatestruct AVLTreeNode
{pair_kv;
AVLTreeNode* _left;
AVLTreeNode* _right;
AVLTreeNode* _parent;
int _bf;
AVLTreeNode(const pair& kv)
: _kv(kv)
, _left(nullptr)
, _right(nullptr)
, _parent(nullptr)
, _bf(0)
{}
}; 2.2 AVL樹的插入：（重點）AVL樹并沒有規(guī)定必須要設計平衡因子，只是一個實現(xiàn)的選擇，方便控制平衡。
這里鏈接是比較容易的，但是鏈接之后對各個結(jié)點中的平衡因子的調(diào)整則是比較費勁的。
2.2.1 插入結(jié)點后平衡因子的變化1. 首先我們來一段簡單的邏輯 —— 只考慮父子之間關(guān)系：
如圖所示：
2. 插入一個結(jié)點對整個樹的影響：
如圖所示：
3. 在鏈接新的結(jié)點的時候要滿足AVL樹的規(guī)則
(1)向上更新：
(2)如何向上更新：
具體過程如下：
- 子樹高度變了，就要繼續(xù)往上更新
- 子樹的高度不變, 則更新完成
- 子樹違反平衡規(guī)則，則停止更新, 旋轉(zhuǎn)子樹
情況一：
情況二：
情況三：
我們討論問題要將各個方面的都要考慮到位才行，即使前面都正確是不會走到這一步的，但是為了萬無一失還是要將這一步寫上。
情況四：
具體代碼如下：
bool Insert(const pair& kv)
{if (_root == nullptr)
{_root = new Node(kv);
_root->_bf = 0;
return true;
}
Node* parent = nullptr;
Node* cur = _root;
while (cur)
{if (cur->_kv.first< kv.first)
{ parent = cur;
cur = cur->_right;
}
else if (cur->_kv.first >kv.first)
{ parent = cur;
cur = cur->_left;
}
else
{ return false;
}
}
//找到符合規(guī)則的位置之后再插入
cur = new Node(kv);
if (parent->_kv.first< kv.first)
{parent->_right = cur;
}
else
{parent->_left = cur;
}
//三叉鏈的鏈接 -- 鏈上父節(jié)點
cur->_parent = parent;
while (parent)
{if (cur == parent->_right)
{ parent->_bf++;
}
else if (cur == parent->_left)
{ parent->_bf--;
}
//是否繼續(xù)更新
if (parent->_bf == 0) //原來是 1 or -1 -->0 （插入結(jié)點填在了矮的那一邊）
{ //高度不變，更新結(jié)束
break;
}
else if(parent->_bf == 1 || parent->_bf == -1)
//原來是 0 -->1 or -1 （插入結(jié)點導致一邊變高了）
{ //子樹的高度變了，繼續(xù)更新祖先
cur = cur->_parent;
parent = parent->_parent;
}
else if (parent->_bf == 2 || parent->_bf == -2)
//原來是 1 or -1 -->2 or -2 （插入結(jié)點導致本來高的一邊又變高了）
{ //子樹不平衡了 -- 需要旋轉(zhuǎn)處理（左單旋的特征 -- 右邊高）
if (parent->_bf == 2 && cur->_bf == 1)//左單旋
{ RatateL(parent);
}
//子樹不平衡了 -- 需要旋轉(zhuǎn)處理（右單旋的特征 -- 左邊高）
else if (parent->_bf == -2 && cur->_bf == -1)//右單旋
{ RatateR(parent);
}
else if (parent->_bf == -2 && cur->_bf == 1)//左右雙旋
{ RatateLR(parent);
}
else if (parent->_bf == 2 && cur->_bf == -1)//右左雙旋
{ RatateRL(parent);
}
//旋轉(zhuǎn)完之后ppNode為根的子樹高度不變 -- 所以對ppNode的平衡因子沒有影響
break;
}
else // 一定要檢查 -- 不保證其他地方不會出現(xiàn)錯誤
{ //插入之前AVL數(shù)就存在平衡子樹，|平衡因子| >= 2結(jié)點
assert(false);
}
}
return true;
} 上述我們已經(jīng)闡述了，在什么情況下需要對AVL樹進行旋轉(zhuǎn)操，接下來我們就來講一下具體的旋轉(zhuǎn)步驟。
旋轉(zhuǎn)原則：
旋轉(zhuǎn)一共分為四種旋轉(zhuǎn)方式：
當右子樹高的時候，這時就要向左旋轉(zhuǎn)。
旋轉(zhuǎn)過程：
旋轉(zhuǎn)詳情圖：
原理：
代表所有情況的抽象圖長方形條表示的是子樹
下面來討論一下h
此時有兩種情況，新增的節(jié)點有可能是鏈接在這棵樹最右邊結(jié)點的，左邊也有可能是鏈接在右邊
此時一共有36種情況
解釋：
具體代碼如下：
//右邊高就要左旋轉(zhuǎn)
//左單旋
void RatateL(Node* parent)
{Node* subR = parent->_right;
Node* subRL = subR->_left;
parent->_right = subRL;
if (subRL != nullptr)
{subRL->_parent = parent;
}
Node* ppNode = parent->_parent;
subR->_left = parent;
parent->_parent = subR;
if (parent == _root)
{_root = subR;
_root->_parent = nullptr;
}
else
{if (parent == ppNode->_left)
{ ppNode->_left = subR;
}
else if(parent == ppNode->_right)
{ ppNode->_right = subR;
}
subR->_parent = ppNode;
}
//更新平衡因子
parent->_bf = 0;
subR->_bf = 0;
}同時代碼的一些細節(jié)也是需要把控的
當左子樹高的時候，這時就要向右旋轉(zhuǎn)。
旋轉(zhuǎn)詳情圖：
旋轉(zhuǎn)過程：
與左單旋一樣當討論h時，也能分出很多種，h = 1時是2種，h = 2時36種。
具體代碼如下：
//左邊高就要右旋轉(zhuǎn)
//右單旋
void RatateR(Node* parent)
{Node* subL = parent->_left;
Node* subLR = subL->_right;
parent->_left = subLR;
if (subLR != nullptr)
{subLR->_parent = parent;
}
Node* ppNode = parent->_parent;
subL->_right = parent;
parent->_parent = subL;
if (parent == _root)
{_root = subL;
subL->_parent = nullptr;
}
else
{if (ppNode->_left == parent)
{ ppNode->_left = subL;
}
else if (ppNode->_right == parent)
{ ppNode->_right = subL;
}
subL->_parent = ppNode;
}
//更新平衡因子
subL->_bf = 0;
parent->_bf = 0;
}細節(jié)把控也與左單旋類似可以參考左單旋。
光有左右單旋是解決不了所有問題的，如圖所示就是特殊情況：
如圖所示，很顯然右單旋并沒有解決問題，旋轉(zhuǎn)之后仍然不是AVL樹，此時我們就引入了雙旋：
旋轉(zhuǎn)詳情圖：
同樣可以對h進行討論，也會對應很多種情況，不再一 一贅述。
具體代碼如下：
//左右雙旋
void RatateLR(Node* parent)
{Node* subL = parent->_left;
Node* subLR = subL->_right;
int bf = subLR->_bf;
RatateL(parent->_left);
RatateR(parent);
//更新平衡因子 -- 全是0的情況也要單獨寫，不要依賴單旋
if (bf == 0)
{parent->_bf = 0;
subL->_bf = 0;
subLR->_bf = 0;
}
else if (bf == 1)
{parent->_bf = 0;
subL->_bf = -1;
subLR->_bf = 0;
}
else if (bf == -1)
{parent->_bf = 1;
subL->_bf = 0;
subLR->_bf = 0;
}
else
{//subLR->_bf旋轉(zhuǎn)前就有問題
assert(false);
}
}兩種解決方案：
我們采用第一種方法，單獨將平衡因子拿出來處理。
旋轉(zhuǎn)詳情圖：
同樣的右左雙旋和左右雙旋差不多，可以參考上文。
具體代碼如下：
//右左雙旋
void RatateRL(Node* parent)
{Node* subR = parent->_right;
Node* subRL = subR->_left;
int bf = subRL->_bf;
RatateR(parent->_right);
RatateL(parent);
if (bf == 0)
{subRL->_bf = 0;
parent->_bf = 0;
subR->_bf = 0;
}
else if (bf == 1)
{subRL->_bf = 0;
parent->_bf = -1;
subR->_bf = 0;
}
else if (bf == -1)
{subRL->_bf = 0;
parent->_bf = 0;
subR->_bf = 1;
}
else
{//subLR->_bf旋轉(zhuǎn)前就有問題
assert(false);
}
}我們先增加幾個成員函數(shù)：
1.層序遍歷打印樹
void levelOrder()
{vector>vv;
if (_root == nullptr)
{return;
}
queueq;
int levelSize = 1;
q.push(_root);
while (!q.empty())
{//levelSize控制一層一層出
vectorlevelV;
while (levelSize--)
{ Node* front = q.front();
q.pop();
levelV.push_back(front->_kv.first);
if (front->_left != nullptr)
{ q.push(front->_left);
}
if (front->_right != nullptr)
{ q.push(front->_right);
}
}
vv.push_back(levelV);
for (auto e : levelV)
{ cout<< e<< " ";
}
cout<< endl;
//上一層出完，下一層就都進隊列
levelSize = q.size();
}
} 2.中序遍歷二叉樹：
void _InOrder(Node* root)
{if (root == nullptr)
return;
_InOrder(root->_left);
cout<< root->_kv.first<< " ";
_InOrder(root->_right);
}
void InOrder()
{_InOrder(_root);
cout<< endl;
}3.求二叉樹高度：
int _Height(Node* root)
{if (root == nullptr)
{return 0;
}
//后續(xù)的方式
int lh = _Height(root->_left);
int rh = _Height(root->_right);
return lh >rh ? lh + 1 : rh + 1;
}
int Height()
{return _Height(_root);
}驗證一：
void TestAVLTree()
{//升序 -- 右邊高左單旋
//int arr[] = { 1,2,3,4,5,6,7,8 };
//降序 -- 左邊高右單旋
int arr[] = {8,7,6,5,4,3,2,1 };
AVLTreet;
for (auto e : arr)
{t.Insert(make_pair(e, e));
}
t.levelOrder();
} 
如圖所示的兩棵樹均是滿足AVL樹，但是這這種驗證還是不太嚴謹。
bool _IsBalanceTree(Node* root)
{//空樹也是AVL樹
if (nullptr == root)
return true;
//計算pRoot節(jié)點的平衡因子：即pRoot左右子樹的高度差
int leftHeight = _Height(root->_left);
int rightHeight = _Height(root->_right);
//求差值
int diff = rightHeight - leftHeight;
//如果計算出的平衡因子與pRoot的平衡因子不相等，或者
//pRoot平衡因子的絕對值超過1，則一定不是AVL樹
if (abs(diff) >= 2)
{cout<< root->_kv.first<< "結(jié)點平衡因子異常"<< endl;
return false;
}
//平衡因子沒有異常但是和結(jié)點的對不上
if (diff != root->_bf)
{//說明更新有問題
cout<< root->_kv.first<< "結(jié)點平衡因子不符合實際"<< endl;
return false;
}
//pRoot的左和右如果都是AVL樹，則該樹一定是AVL樹
//把自己和自己的左右子樹都檢查了，遞歸檢查
return _IsBalanceTree(root->_left)
&& _IsBalanceTree(root->_right);
}
bool IsBalanceTree()
{return _IsBalanceTree(_root);
}驗證二：
void TestAVLTree()
{const size_t N = 1024 * 1024 * 10;
vectorarr;
arr.reserve(N);//避免頻繁擴容
srand(time(0));
for (size_t i = 0; i< N; i++)
{arr.push_back(rand());
//arr.push_back(i);
}
AVLTreet;
for (auto e : arr)
{t.Insert(make_pair(e, e));
}
cout<< "是否平衡？"<< t.IsBalanceTree()<< endl;
cout<< "高度："<< t.Height()<< endl;
//t.InOrder();
} 
你是否還在尋找穩(wěn)定的海外服務器提供商？創(chuàng)新互聯(lián)www.cdcxhl.cn海外機房具備T級流量清洗系統(tǒng)配攻擊溯源，準確流量調(diào)度確保服務器高可用性，企業(yè)級服務器適合批量采購，新人活動首月15元起，快前往官網(wǎng)查看詳情吧
