C++实现平衡二叉树
1.概念
平衡二叉樹(AVL Tree)首先要滿足二叉樹的定義,如下
- 二叉排序樹或者是一棵空樹，或者是具有下列性質(zhì)的二叉樹：
- 若左子樹不空，則左子樹上所有結(jié)點(diǎn)的值均小于它的根結(jié)點(diǎn)的值；
- 若右子樹不空，則右子樹上所有結(jié)點(diǎn)的值均大于它的根結(jié)點(diǎn)的值；
- 左、右子樹也分別為二叉排序樹；
- 沒有鍵值相等的節(jié)點(diǎn)。
- 平衡度是左子樹高度減去右子樹高度，平衡度只能是-1,+1,0
- 危機(jī)結(jié)點(diǎn)是指平衡度為1，有可能破壞平衡樹的結(jié)點(diǎn)
- 左改組是指新結(jié)點(diǎn)插入到危機(jī)結(jié)點(diǎn)的左樹下
- 右改組是指新新結(jié)點(diǎn)插入到危機(jī)結(jié)點(diǎn)的右子樹下
- LL是新結(jié)點(diǎn)插入在危機(jī)節(jié)點(diǎn)的左子樹的左子樹上
- LR是新結(jié)點(diǎn)插入在危機(jī)節(jié)點(diǎn)的左子樹的右子樹上
- RR是新結(jié)點(diǎn)插入在危機(jī)節(jié)點(diǎn)的右子樹的右子樹上
- RL是新結(jié)點(diǎn)插入在危機(jī)節(jié)點(diǎn)的右子樹的左子樹上
2.代碼實(shí)現(xiàn)
當(dāng)前樹的結(jié)構(gòu)
?? ??? ???? 11
?? ??? ?? /?? \
?? ??? ?7?? ??? 15
?? ??? / \??? /? \
?? ?? 3?? ?? 9? 14?? ?? 18
???? / \???? /??? / \
??? 1?? 5?? ?12?? 16?? ? 20
?? ??? ??? ??? ????? /
?? ??? ??? ??? ??? 26
2.1 定義平衡樹結(jié)點(diǎn)：
平衡因子可以是右子樹高度減去左子樹高度，不同的教材定義不一樣，我這里按照左樹-右樹來做
template<class K, class V> struct AVLTreeNode {K _key; //樹權(quán)值 V _value;int _bf; //平衡因子 -1,0,1 (每個(gè)節(jié)點(diǎn)的平衡因子等于左子樹的高度減去右子樹的高度) //有的教材定義平衡度是左子樹高度減去右子樹，都是可以的AVLTreeNode<K, V>* _parent; //指向父節(jié)點(diǎn)的指針AVLTreeNode<K, V>* _left; //指向左孩子的指針AVLTreeNode<K, V>* _right; //指向右孩子的指針 AVLTreeNode(const K& key = K(), const V& value = V()):_key(key), _value(value), _bf(0), _parent(NULL), _left(NULL), _right(NULL){} };2.2 左改組圖解
左右改組是為了方便我們插入刪除的時(shí)候保持二叉樹平衡而引入的概念
左改組LL型和LR(a),LR(b),LR(c)型圖解
2.3 左改組LL型
首先聲明一個(gè)構(gòu)造的左子樹，subL其實(shí)就是危機(jī)結(jié)點(diǎn)，subLR是危機(jī)節(jié)點(diǎn)的右子樹，ppNode是祖先節(jié)點(diǎn)
構(gòu)建parent子樹，將parent和subL連接起來
如果祖先結(jié)點(diǎn)為空，將當(dāng)前結(jié)點(diǎn)subL置為根節(jié)點(diǎn)，請(qǐng)參見上圖(a‘)的情況，B是危機(jī)結(jié)點(diǎn)，調(diào)整過后變成了根節(jié)點(diǎn)
否則祖父結(jié)點(diǎn)賦給subL的父結(jié)點(diǎn)，判斷父節(jié)點(diǎn)是否是祖先結(jié)點(diǎn)的左子樹，是的話，用構(gòu)造的左子樹替代之
不是就用subL替代祖先節(jié)點(diǎn)的右子樹
//左改組LL型 template<class K, class V> void AVLTree<K, V>::_RotateLL(AVLTreeNode<K, V>*& parent) {AVLTreeNode<K, V>* subL = parent->_left; //構(gòu)造的左子樹AVLTreeNode<K, V>* subLR = subL->_right;//subL的右子樹AVLTreeNode<K, V>* ppNode = parent->_parent;//標(biāo)記祖先節(jié)點(diǎn)//1.構(gòu)建parent子樹 將parent和subLR鏈接起來parent->_left = subLR;if (subLR) subLR->_parent = parent;//2.構(gòu)建subL子樹 將subL與parent鏈接起來subL->_right = parent;parent->_parent = subL;//3.將祖先節(jié)點(diǎn)與subL鏈接起來if (ppNode == NULL){ //如果祖先為NULL，說明當(dāng)前subL節(jié)點(diǎn)為根節(jié)點(diǎn)subL->_parent = NULL;_root = subL;}else{subL->_parent = ppNode;if (ppNode->_left == parent)ppNode->_left = subL;else if (ppNode->_right == parent)ppNode->_right = subL;}//4.重置平衡因子parent->_bf = 0;subL->_bf = 0;//5.更新subL為當(dāng)前父節(jié)點(diǎn)parent = subL; }2.4 左改組LR(a)、LR(b)和LR(c)型
pNode是當(dāng)前父節(jié)點(diǎn)，subR是構(gòu)造的右子樹，subLR是subR的左子樹
對(duì)當(dāng)前父節(jié)點(diǎn)LL左改組，再右改組
根據(jù)平衡因子判斷是LR什么類型，請(qǐng)參見上圖圖解(b),(c),(d)的情況
//左改組LR型 template<class K, class V> void AVLTree<K, V>::_RotateLR(AVLTreeNode<K, V>*& parent) {AVLTreeNode<K, V>* pNode = parent;AVLTreeNode<K, V>* subR = parent->_right;AVLTreeNode<K, V>* subLR = subR->_left;int bf = subLR->_bf;_RotateLL(parent->_right);_RotateRR(parent);//LR(b)型if (bf == -1){pNode->_bf = 0;subR->_bf = 1;}//LR(a)型else if (bf == 1){pNode->_bf = -1;subR->_bf = 0;}//LR(c)型else{pNode->_bf = 0;subR->_bf = 0;} }?右改組和左改組鏡像對(duì)稱，反過來就行了
2.5 插入函數(shù)
AVL樹是空，將當(dāng)前結(jié)點(diǎn)直接置為根節(jié)點(diǎn)
AVL樹在滿足平衡度的要求下，和二叉排序樹一致，key小于當(dāng)前結(jié)點(diǎn)，轉(zhuǎn)到當(dāng)前結(jié)點(diǎn)左子樹，key大于當(dāng)前結(jié)點(diǎn)，轉(zhuǎn)到當(dāng)前結(jié)點(diǎn)右子樹
將parent的左子樹賦予當(dāng)前結(jié)點(diǎn)，更新平衡因子，_bf++
將parent的右子樹賦予當(dāng)前結(jié)點(diǎn)，更新平衡因子，_bf--
如果合法，即平衡因子=0，終止當(dāng)前循環(huán)
如果當(dāng)前結(jié)點(diǎn)是危機(jī)結(jié)點(diǎn)，即平衡度絕對(duì)值等于1，當(dāng)前結(jié)點(diǎn)往上回溯，變成父節(jié)點(diǎn)，繼續(xù)檢查它的平衡度
接下來是平衡異常的情況，父結(jié)點(diǎn)平衡度為2，當(dāng)前結(jié)點(diǎn)（危機(jī)結(jié)點(diǎn)）平衡度為1，進(jìn)入左改組LL,LL介紹參考2.2 左改組LL
當(dāng)前結(jié)點(diǎn)平衡度為-1，進(jìn)入左改組LR，LR介紹參考2.3 左改組LR
右改組的情況類似
template<class K, class V> bool AVLTree<K, V>::Insert(const K& key, const V& value) {//1.空樹if (_root == NULL){_root = new AVLTreeNode<K, V>(key, value);return true;}//2.AVL樹不為NULLAVLTreeNode<K, V>* parent = NULL;AVLTreeNode<K, V>* cur = _root;//找到數(shù)據(jù)插入位置while (cur){if (cur->_key < key){parent = cur;cur = cur->_right;}else if (cur->_key > key){parent = cur;cur = cur->_left;}else{return false;}}//插入數(shù)據(jù)cur = new AVLTreeNode<K, V>(key, value);cur->_parent = parent;if (parent->_key > key)parent->_left = cur;elseparent->_right = cur;while (parent){//更新平衡因子if (cur == parent->_left)parent->_bf++;else if (cur == parent->_right)parent->_bf--;//檢驗(yàn)平衡因子是否合法if (parent->_bf == 0)break;else if (parent->_bf == -1 || parent->_bf == 1){ // 回溯上升 更新祖父節(jié)點(diǎn)的平衡因子并檢驗(yàn)合法性cur = parent;parent = cur->_parent;}// 2 -2 平衡因子不合法 需要進(jìn)行旋轉(zhuǎn) 降低高度else {if (parent->_bf == -2){if (cur->_bf == -1)_RotateRR(parent);else_RotateLR(parent);}else if (parent->_bf == 2){if (cur->_bf == 1)_RotateLL(parent);else_RotateRL(parent);}break;}} }?2.6 遍歷方法
//中序遍歷 template<class K, class V> void AVLTree<K, V>::_InOrder(AVLTreeNode<K, V>* root) {if (root == NULL)return;_InOrder(root->_left);cout << root->_key << " ";_InOrder(root->_right); } //前序遍歷 template<class K, class V> void AVLTree<K, V>::_PreOrder(AVLTreeNode<K, V>* root) {if (root == NULL)return;cout << root->_key << " ";_PreOrder(root->_left);_PreOrder(root->_right); } //后序遍歷 template<class K, class V> void AVLTree<K, V>::_PostOrder(AVLTreeNode<K, V>* root) {if (root == NULL)return;_PostOrder(root->_left);_PostOrder(root->_right);cout << root->_key << " "; }3.運(yùn)行和源碼
運(yùn)行效果如下
源代碼：https://github.com/cjy513203427/C_Program_Base/tree/master/61.%E5%B9%B3%E8%A1%A1%E4%BA%8C%E5%8F%89%E6%A0%91/61.%E5%B9%B3%E8%A1%A1%E4%BA%8C%E5%8F%89%E6%A0%91
?
轉(zhuǎn)載于:https://www.cnblogs.com/Java-Starter/p/10192034.html
總結(jié)
以上是生活随笔為你收集整理的C++实现平衡二叉树的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。
- 上一篇： Java-流程控制
- 下一篇： python中并发编程基础1