目錄

• AVL樹的概念
• AVL樹平衡因子的更新
• AVL樹的插入
• AVL樹的旋轉(zhuǎn)
• 代碼
• • 初版

AVL樹的概念

二叉搜索樹雖可以縮短查找的效率，但如果數(shù)據(jù)有序或接近有序二叉搜索樹將退化為單支樹，查找元素相當(dāng)
于在順序表中搜索元素，效率低下。因此，兩位俄羅斯的數(shù)學(xué)家G.M.Adelson-Velskii和E.M.Landis在1962年
發(fā)明了一種解決上述問題的方法：當(dāng)向二叉搜索樹中插入新結(jié)點后，如果能保證每個結(jié)點的左右子樹高度之 差的絕對值不超過1(需要對樹中的結(jié)點進(jìn)行調(diào)整)，即可降低樹的高度，從而減少平均搜索長度。 一棵AVL樹或者是空樹，或者是具有以下性質(zhì)的二叉搜索樹：

• 它的左右子樹都是AVL樹
• 左右子樹高度之差(簡稱平衡因子)的絕對值不超過1(-1/0/1)
  
  如果一棵二叉搜索樹是高度平衡的，它就是AVL樹。如果它有n個結(jié)點，其高度可保持在，搜索時
  間復(fù)雜度O(log2N)

AVL樹平衡因子的更新

• AVL樹就是在二叉搜索樹的基礎(chǔ)上引入了平衡因子
• 具體情況分以下幾種情況：

向上更新的過程中，cur也有可能是高度變換子樹的根
1，新增節(jié)點結(jié)點在parent的右邊

cur=parent->right
parent->bf++;

2，新增節(jié)點結(jié)點在parent的左邊

cur=parent->left
parent->bf–;

3、更新parent的平衡因子

• parent->bf=0，說明prent所在子樹的高度不變(沒更新前parent->bf為1或-1現(xiàn)在變成了0,現(xiàn)在變成了0，說明把缺的那一邊填上了不會對上層影響,更新結(jié)束，插入結(jié)束)
  

• parent->bf==1或-1， 說明parent所在子樹的高度變了對上一層有影響繼續(xù)向上更新

• parrent-> bf==2||-2， 說明parent所在子樹已經(jīng)不平衡，要及時旋轉(zhuǎn)

AVL樹的插入

AVL樹的旋轉(zhuǎn)

AVL的旋轉(zhuǎn)采用抽象圖演示：

抽象圖->無數(shù)多種情況都用旋轉(zhuǎn)處理
1，abc三棵沒有具有畫出來的樹的特點：
a、它們肯定都是高度平衡樹
b、他們的高度都是h（h>=0）

當(dāng)h=0

在30的左右子樹插入節(jié)點時都會旋轉(zhuǎn)

當(dāng)h=1

當(dāng)h=2就會有27中情況

h=3，h=4…可以看出組合的情況更多，但是我們實際不關(guān)心，因為a，b，c三棵子樹高度多少形態(tài)如何，我們的旋轉(zhuǎn)處理都是一樣的。

右單旋

b成了60的左子樹
60成了30的右子樹
30成了這棵樹根

左單旋

b成了30的右子樹
30成了60的左子樹
60成了這棵樹根

先左旋在右旋

如果在b插入節(jié)點或c插入，導(dǎo)致b或者c的高度變成1，就會引發(fā)雙旋，并且要分開討論，b插入或者c插入，樹的平衡因子更新是要分開看待的

先左旋在右旋
新節(jié)點插入較高右子樹的左側(cè)—右左：先右單旋再左單旋

代碼

初版

#pragma once #include<iostream> #include<assert.h> using namespace std;template<class K, class V> struct TreeNode {TreeNode<K, V>* left;TreeNode<K, V>* right;TreeNode<K, V>* parent;pair<K, V> kv;int bf;//平衡因子TreeNode(const pair<K, V>& kv) :left(nullptr),right(nullptr),parent(nullptr), kv(kv), df(0) {} }; template<class K, class V> class AVLtree {typedef TreeNode<K, V> Node; private:Node * root=nullptr; public:AVLtree() = default;AVLtree(const TreeNode<K, V>& k);pair<Node*, bool> Insert(cosnt pair<K,V>&kv) {if (root == nullptr) {Node cur = new Node(kv);return make_pair(root, true);}Node* _parent = nullptr;Node* cur = root;while (cur) {if (cur->kv.first>kv.first) {_parent = cur;cur = cur->left;}else if (cur->kv.first < kv.first) {_parent = cur;cur = cur->right;}else {return make_pair(cur, false);}}Node *node = new Node(kv);if (_parent->kv.first>kv.first) {_parent->left = kv;cur->parent = _parent;}else {_parent->right = kv;cur->parent = _parent;}while (_parent) {if (cur == _parent->left) {_parent->bf--；}else if (cur == _parent->right) {_parent->bf++;}if (_parent->bf==0) {break;}else if (abs(_parent->bf) == 1) {cur = _parent;_parent = _parent->parent;}else if(abs(_parent->bf) == 2){//旋轉(zhuǎn)if (_parent->_bf == -2)//左邊高{if (cur->_bf == -1)//是在當(dāng)前節(jié)點的左側(cè)插入了節(jié)點 ->右單旋{Avr(_parent);}else//cur->_bf=1 ->曲線影響{Avlr(_parent);}}else//右邊高{if (cur->_bf == 1)//在當(dāng)前節(jié)點的右側(cè)插入了節(jié)點 -> 左單旋{Avl(_parent);}else//cur->_bf=-1 曲線影響{Avl(_parent);}}break;//旋轉(zhuǎn)過后當(dāng)前的樹就是平衡的了，立即退出}else {assert(false);}}//1.更新平衡因子//新增節(jié)點會影響他的到根節(jié)點這條路徑的祖先return make_pair(node, true);}void Avl(Node *parent) {Node* subL = parent->left;Node* subLR = subL->right;parent->left = subLR;if (subLR) {subLR->parent = parent;}Node *ne =parent->parent//保存parent的parentsubL->right = parent;parent->parent = subL;//parent 是原來的跟if (parent == root) {root = parent;parent->parent = nullptr; //把新樹的parent置為空}//parent 是原來的子樹的根else {if (ne->left == parent) {ne->left = subL;subL->parent = parent;}else {ne->right = subL;subL->parent = parent;}}subL->bf = parent->bf = 0;}void Avr(Node *parent){Node* subL = parent->_left;//此時p->bf=-2，左邊肯定不為空Node* subLR = subL->_right;Node* pparent = parent->_parent;//保存一份//將子樹鏈接到parent的左側(cè)parent->_left = subLR;if (subLR)subLR->_parent = parent;//將parent連接到subL的右側(cè)subL->_right = parent;parent->_parent = subL;//將subL與ppretn鏈接起來if (pparent == nullptr)//subL變成新的根{_root = subL;subL->_parent = nullptr;}else//不為根{subL->_parent = pparent;if (parent == pparent->_left)//在上一級節(jié)點的左側(cè){pparent->_left = subL;}else{pparent->_right = subL;}}//平衡因子的更新parent->_bf = 0;subL->_bf = 0;}void AvLR(Node* parent) {Node* subL = parent->left;Node* subLR= parent->left->right;int bf = parent->bf;Avl(parent->left);Avr(parent);if (bf == 1) {// 說明subL的右數(shù)插入subL->bf = -1;subLR->bf = 0;parent->bf = 0;}else if (bf==-1) {//說明subL的左數(shù)插入subL->bf = 0;subLR->bf = 0;parent->bf = 1;}else if (bf == 0) {//說明SUBLR是新增節(jié)點subL->bf = subLR->bf = parent->bf = 0;}}void AvRL(Node* parent) {Node* subR = parent->_right;Node* subRL = subR->_left;int bf = subRL->_bf;RotateR(subR);//先右旋RotateL(parent);//再左旋//平衡因子出來if (bf == 1)//在subRL右側(cè)插入時{subRL->_bf = 0;parent->_bf = -1;subR->_bf = 0;}else if (bf == -1)//在左側(cè)插入時{subRL->_bf = 0;parent->_bf = 0;subR->_bf = 1;}else//bf==0,新增的{subRL->_bf = parent->_bf = subR->_bf = 0;}}bool _isBlace(Node* root) {if (root == NULL) {return true;}int lheight = Height(root->left);int rheight = Height(root->left);if (rheight - lheight != root->bf) {cout << "平衡因子出錯" << root->kv.first << endl;}return abc(lheight - rheight) > 2 && _isBlace(root->left) && _isBlace(root->right);}//驗證是否平衡bool isBalance() {_isBalace(root)} };

總結(jié)

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

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。