AVL树的插入以及四种旋转解析

什么是AVL树呢？（概念）

一棵AVL树或者是空树，或者是具有以下性质的二叉搜索树：

1、它的左右子树都是AVL树

2、左子树和右子树高度之差(简称平衡因子)的绝对值不超过1(-1、0、1)

3、如果一棵二叉搜索树是高度平衡的，它就是AVL树。

4、时间复杂度：如果它有n个结点，其高度可保持在O(lgn)，平均搜索时间复杂度O(lg(n))

首先，创建AVL树

template<class K, class V> struct AVLTreeNode { AVLTreeNode(const K& key, const V& value) : _pRight(NULL) , _pLeft(NULL) , _pParent(NULL) , _key(key) , _value(value) , _bf(0) {} AVLTreeNode<K, V>* _pRight; AVLTreeNode<K, V>* _pLeft; AVLTreeNode<K, V>* _pParent; K _key; V _value; int _bf;//当前节点的平衡因子 };

二、再来分析如何插入结点，使得成为AVL树

在AVL树中插入结点(key，value)的算法：

1. 如果是空树，插入后即为根节点，插入后直接返回true；

2. 如果树不空，寻找插入位置，若在寻找的过程中找到key，则插入失败直接返回false；

3. 插入结点；

4. 更新平衡因子，对树进行调整；

相应代码：

bool Insert(const K& key, const V& value) { //空树 if (NULL == _pRoot) { _pRoot = new Node(key, value); return true; } //不为空，1 找插入位置 pNode pCur = _pRoot;//从根的位置开始找 pNode pParent = NULL;//刚开始根节点无双亲节点 while (pCur) { if (key < pCur->_key) { pParent = pCur; pCur = pCur->_pLeft; } else if (key>pCur->_key) { pParent = pCur; pCur = pCur->_pRight; } else return false; } //插入节点 pCur = new Node(key, value); if (key < pParent->_key) pParent->_pLeft = pCur; else pParent->_pRight = pCur; pCur->_pParent = pParent; //更新平衡因子 while (pParent) { //插入分情况 if (pParent->_pLeft == pCur) pParent->_bf--; else pParent->_bf++; //更新完成以后需要平衡（分情况） if (0 == pParent->_bf) break; else if (pParent->_bf == 1 || pParent->_bf == -1) { pCur = pParent; pParent = pCur->_pParent; } else//2或者-2 //需要单旋或者双旋完成平衡 { if (pParent->_bf == 2) { if (pCur->_bf == 1)//左旋 RoteteL(pParent); else RoteteRL(pParent);//右左旋 } else { if (pCur->_bf == -1) RoteteR(pParent); else RoteteLR(pParent); } break;//不再向上调整 } } return true; }

三、平衡化旋转

如果在一棵原本是平衡的二叉搜索树中插入一个新节点，可能造成不平衡，此时必须调整树的结构，使之平衡化。

下面一一介绍四种旋转

1.左单旋（插入点位于ptr的右子节点的右子树--右右）

代码实现：

void RoteteL(pNode pParent) { pNode pSubR = pParent->_pRight; pNode pSubRL = pSubR->_pLeft; //提升因子 pParent->_pRight = pSubRL; if (pSubRL) pSubRL->_pParent = pParent; pNode PParent = pParent->_pParent; pSubR->_pLeft = pParent; pSubR->_pParent = PParent; pParent->_pParent = pSubR; //pParent有三种情况（根/位于父亲的左，父亲的右） if (pParent == _pRoot) _pRoot = pSubR; if (PParent) { if (pParent == PParent->_pLeft) PParent->_pLeft = pSubR; else PParent->_pRight = pSubR; } //更新平衡因子 pParent->_bf = 0; pSubR->_bf = 0; } 2.右单旋（插入点位于ptr的左子结点的左子树--左左）

代码实现：

void RoteteR(pNode pParent) { pNode pSubL = pParent->_pLeft; pNode pSubLR = pSubL->_pRight; pParent->_pLeft = pSubLR; if (pSubLR) pSubLR->_pParent = pParent; pNode PParent = pParent->_pParent; pSubL->_pRight = pParent; pParent->_pParent = pSubL; pSubL->_pParent = PParent; if (pParent == _pRoot) _pRoot = pSubL; if (PParent) { if (pParent == PParent->_pLeft) PParent->_pLeft = pSubL; else PParent->_pRight = pSubL; } pParent->_bf = 0; pSubL->_bf = 0; }

3.左右双旋（插入点位于ptr左子节点的右子树--左右）

代码实现：

void RoteteLR(pNode pParent) { int bf = pParent->_pLeft->_pRight->_bf; RoteteL(pParent->_pLeft); RoteteR(pParent); //更新平衡因子 if (bf == 1) { pParent->_bf = 0; pParent->_pLeft->_bf = -1; pParent->_pLeft->_pRight->_bf = 0; } else if (bf == -1) { pParent->_bf = 1; pParent->_pLeft->_bf = 0; pParent->_pLeft->_pRight->_bf = 0; } }

4.右左双旋（插入点位于ptr右子节点的左子树--右左）

代码实现：

void RoteteRL(pNode pParent) { int bf = pParent->_pRight->_pLeft->_bf; RoteteR(pParent->_pRight); RoteteL(pParent); //更新平衡因子 if (bf == -1) { pParent->_pRight->_bf = 1; pParent->_bf = 0; pParent->_pRight->_pLeft->_bf = 0; } else if (bf == 1) { pParent->_bf = -1; pParent->_pRight->_bf = 0; pParent->_pParent->_pLeft->_bf=0; } }

四、判断是否平衡

代码实现：

bool Isblance(pNode pRoot) { if (pRoot == NULL) return true; size_t LeftHeight = Height(pRoot->_pLeft); size_t RightHeight = Height(pRoot->_pRight); int height = RightHeight - LeftHeight; return ((abs(height)<2) && Isblance(pRoot->_pLeft) && Isblance(pRoot->_pRight)); }

附录：完整代码（包含测试代码）

#pragma once #include <iostream> using namespace std; template<class K, class V> struct AVLTreeNode { AVLTreeNode(const K& key, const V& value) : _pRight(NULL) , _pLeft(NULL) , _pParent(NULL) , _key(key) , _value(value) , _bf(0) {} AVLTreeNode<K, V>* _pRight; AVLTreeNode<K, V>* _pLeft; AVLTreeNode<K, V>* _pParent; K _key; V _value; int _bf;//当前节点的平衡因子 }; template<class K, class V> class AVLTree { typedef AVLTreeNode<K, V> Node; typedef Node* pNode; public: AVLTree() :_pRoot(NULL) {} void PerInoder() { _PerInoder(_pRoot); cout << endl; } void _PerInoder(pNode pRoot) { if (pRoot) { cout << pRoot->_key << " "; _PerInoder(pRoot->_pLeft); _PerInoder(pRoot->_pRight); } } bool Insert(const K& key, const V& value) { //空树 if (NULL == _pRoot) { _pRoot = new Node(key, value); return true; } //不为空，1 找插入位置 pNode pCur = _pRoot;//从根的位置开始找 pNode pParent = NULL;//刚开始根节点无双亲节点 while (pCur) { if (key < pCur->_key) { pParent = pCur; pCur = pCur->_pLeft; } else if (key>pCur->_key) { pParent = pCur; pCur = pCur->_pRight; } else return false; } //插入节点 pCur = new Node(key, value); if (key < pParent->_key) pParent->_pLeft = pCur; else pParent->_pRight = pCur; pCur->_pParent = pParent; //更新平衡因子 while (pParent) { //插入分情况 if (pParent->_pLeft == pCur) pParent->_bf--; else pParent->_bf++; //更新完成以后需要平衡（分情况） if (0 == pParent->_bf) break; else if (pParent->_bf == 1 || pParent->_bf == -1) { pCur = pParent; pParent = pCur->_pParent; } else//2或者-2 //需要单旋或者双旋完成平衡 { if (pParent->_bf == 2) { if (pCur->_bf == 1)//左旋 RoteteL(pParent); else RoteteRL(pParent);//右左旋 } else { if (pCur->_bf == -1) RoteteR(pParent); else RoteteLR(pParent); } break;//不再向上调整 } } return true; } void RoteteL(pNode pParent) { pNode pSubR = pParent->_pRight; pNode pSubRL = pSubR->_pLeft; //提升因子 pParent->_pRight = pSubRL; if (pSubRL) pSubRL->_pParent = pParent; pNode PParent = pParent->_pParent; pSubR->_pLeft = pParent; pSubR->_pParent = PParent; pParent->_pParent = pSubR; //pParent有三种情况（根/位于父亲的左，父亲的右） if (pParent == _pRoot) _pRoot = pSubR; if (PParent) { if (pParent == PParent->_pLeft) PParent->_pLeft = pSubR; else PParent->_pRight = pSubR; } //更新平衡因子 pParent->_bf = 0; pSubR->_bf = 0; } void RoteteR(pNode pParent) { pNode pSubL = pParent->_pLeft; pNode pSubLR = pSubL->_pRight; pParent->_pLeft = pSubLR; if (pSubLR) pSubLR->_pParent = pParent; pNode PParent = pParent->_pParent; pSubL->_pRight = pParent; pParent->_pParent = pSubL; pSubL->_pParent = PParent; if (pParent == _pRoot) _pRoot = pSubL; if (PParent) { if (pParent == PParent->_pLeft) PParent->_pLeft = pSubL; else PParent->_pRight = pSubL; } pParent->_bf = 0; pSubL->_bf = 0; } void RoteteLR(pNode pParent) { int bf = pParent->_pLeft->_pRight->_bf; RoteteL(pParent->_pLeft); RoteteR(pParent); //更新平衡因子 if (bf == 1) { pParent->_bf = 0; pParent->_pLeft->_bf = -1; pParent->_pLeft->_pRight->_bf = 0; } else if (bf == -1) { pParent->_bf = 1; pParent->_pLeft->_bf = 0; pParent->_pLeft->_pRight->_bf = 0; } } void RoteteRL(pNode pParent) { int bf = pParent->_pRight->_pLeft->_bf; RoteteR(pParent->_pRight); RoteteL(pParent); //更新平衡因子 if (bf == -1) { pParent->_pRight->_bf = 1; pParent->_bf = 0; pParent->_pRight->_pLeft->_bf = 0; } else if (bf == 1) { pParent->_bf = -1; pParent->_pRight->_bf = 0; pParent->_pParent->_pLeft->_bf=0; } } void MidOrder() { cout << "MidOrder: "; _MidOrder(_pRoot); cout << endl; } bool _Isblance() { return Isblance(_pRoot); } bool Isblance(pNode pRoot) { if (pRoot == NULL) return true; size_t LeftHeight = Height(pRoot->_pLeft); size_t RightHeight = Height(pRoot->_pRight); int height = RightHeight - LeftHeight; return ((abs(height)<2) && Isblance(pRoot->_pLeft) && Isblance(pRoot->_pRight)); } size_t Height(pNode pRoot) { if (NULL == pRoot) return 0; else if (NULL == pRoot->_pLeft&&NULL == pRoot->_pRight) return 1; else return Height(pRoot->_pLeft) > Height(pRoot->_pRight) ? Height(pRoot->_pLeft) + 1 : Height(pRoot->_pRight) + 1; } private: pNode _pRoot; void _MidOrder(pNode& pRoot) { if (pRoot) { _MidOrder(pRoot->_pLeft); cout << pRoot->_key << " "; _MidOrder(pRoot->_pRight); } } }; int main() { int arr[] = {16,3,7,11,9,26,18,14,15}; AVLTree<int, int> avl; for (int i = 0; i < sizeof(arr) / sizeof(arr[0]); i++) { avl.Insert(arr[i], arr[i]); } if (avl._Isblance()) { cout << "blance\n" << endl; } else { cout << "noblance\n" << endl; } avl.MidOrder(); avl.PerInoder(); getchar(); return 0; }