平衡二叉搜索树插入的实现

前言

因为二叉搜索树在插入的时候最坏的情况可能会变成一条单一链表，从而使查找或者插入的时候消耗大量的时间。所以为了解决这一情况诞生了平衡二叉搜索树，其作用是为了减少二叉搜索树的整体高度，从而使查找插入删除的效率提高。

一、平衡二叉搜索树插入的实现思路

平衡二叉搜索树是二叉搜索树的升级版，通过插入和删除时旋转子树的方法，提高了查找的效率。

那么对于插入的升级将会是本节的重点内容。主要思路如下：

a. 插入结点之后仍然是AVL树，；

b. 插入结点之后不再满足AVL树条件，则进行调整，根据导致不平衡的原因，分为：

（a） LL型――单旋转调整

（b） LR型――双旋转调整

（c）RL型――双旋转调整

（d） RR型――单旋转调整

那么如何确定子树需要旋转呢？我们会在树的节点中增加高度差计数，通常情况下为“右子树高度-左子树高度”。如果高度差超过2则需要进行调整。

1、插入节点后仍然是AVL树

如果插入节点之后向上修改节点记录高度的数据仍然能够报纸平衡，那么AVL树将不需要进行调整：

图1-1 节点平衡

节点平衡的情况很多，主要在于两种情况，插入的时候二叉树的高度没有改变。或者改变之后仍然在高度差的范围之内。

那么在代码中我们不难看出能够分为三种情况：

（1）没有父节点继续修改记录值。

（2）差入的时候子树高度没有改变，就不需要继续向上修改父节点的记录值。

（3）向上遍历的时候发现子树的高度改变了，就需要判断子树在父节点的哪一边，从而对父节点的记录值进行加减。并继续向上修改父节点记录值。

2、插入之后不是AVL树

这种情况我们通常就需要旋转子树节点以达到旋转之后使子树仍然保持是AVL树。

需要旋转的情况大致分为4种，左单旋、右单旋、左右双旋、右左双旋。

那么接下来分别讲讲需要旋转的4种情况。

2.1、左单旋

左单旋的情况出现在父节点右节点右子树超高的情况：

图1-2 需要左单旋的例图

其中右图为n=0的特殊情况。

左旋转就将图中的2节点改为1的父节点，b改为1的右子树，这样2的左子树是1。这样总体高度相较于插入之前没有改变都是n+2。就不需要继续向上查找父节点了。

图1-3 左单旋

2.2、右单旋

右单旋就相当于是左单旋镜面对称之后的情况，是父节点的左节点的左子树超高需要旋转。

图1-4 右单旋

和左单旋类似，将1移动为0的右子树，0成为1的父节点，把0的右子树b给1当成左子树。

2.3、左右双旋

左右双旋发生在父节点的左子树超高，但是左节点的右子树更高一点。

图1-5 需要左右双旋举例图

其中”A“为基本情况，当”n“等于0的时候会比较特殊，这个时候”-1“右子树的记录值为0。“B”、“C”是“n”不等于0的时候的两种状况，表示为0的节点记录值分别为1或者-1.

图1-6 左右双旋

需要注意的是根据“0”节点位置的记录值的不同，旋转完成后的子节点记录值会不同。例如当“b2”更高的时候，节点“-1”的右子树会矮一截。相反如果“b1”比“b2”更高，则节点“1”的左子树会矮一截。如果从左向右看方框形态的子树，会发现他们的顺序并没有改变，只是链接的节点改变了。

2.4、右左双旋

和左右双旋的情况正好相反。

图1-7 右左双旋

和左右双旋一样，根据节点“2”的记录值不同，旋转完成后子节点的记录值也会不同。如果记录值为0，那么“1”和“3”节点的记录值都为0，如果为1则节点“1”的记录值为-1，如果为-1则节点“3”的记录值为1。

二、平衡二叉搜索树实现

#include <iostream>
#include <string>
#include <assert.h>
#include <utility>
#include <algorithm>
#include <cmath>using namespace std;template<class T>
struct AVLTreeNode
{AVLTreeNode(const T& data = T()): _pLeft(nullptr), _pRight(nullptr), _pParent(nullptr), _data(data), _bf(0){}AVLTreeNode<T>* _pLeft;AVLTreeNode<T>* _pRight;AVLTreeNode<T>* _pParent;T _data;int _bf;   // 节点的平衡因子
};// AVL: 二叉搜索树 + 平衡因子的限制
template<class T>
class AVLTree
{typedef AVLTreeNode<T> Node;
public:AVLTree(): _pRoot(nullptr){}// 在AVL树中插入值为data的节点bool Insert(const T& data){// 根节点为空直接插入并修改if(nullptr == _pRoot){_pRoot = new Node(data);return true;}Node* parent = nullptr;Node* cur = _pRoot;// 找到对应的插入节点while(cur){parent = cur;if(data < cur->_data){cur = cur->_pLeft;}else if(data > cur->_data){cur = cur->_pRight;}else{return false;}}// 插入节点cur = new Node(data);if(data < parent->_data){parent->_pLeft = cur;cur->_pParent = parent;}else if(data > parent->_data){parent->_pRight = cur;cur->_pParent = parent;}else{assert(false);return false;}// AVL树向上检查，修改平衡因子while(parent){// 修改平衡因子if(parent->_pLeft == cur){parent->_bf--;}else if(parent->_pRight == cur){parent->_bf++;}else{// 节点存储的有问题assert(false);}// 考虑是否旋转子树// 1. 为0不需要继续向上修改if(0 == parent->_bf){break;}// 2. 等于1或者-1需要继续向上修改平衡因子else if(1 == parent->_bf || -1 == parent->_bf){cur = parent;parent = parent->_pParent;}// 3. 因子等于2或者-2就说明需要旋转else if(-2 == parent->_bf || 2 == parent->_bf){// 继续分为4种情况// 3.1. 左子树的左子树超高if(-2 == parent->_bf && -1 == cur->_bf){RotateR(parent);}// 3.2. 右子树的右子树超高else if(2 == parent->_bf && 1 == cur->_bf){RotateL(parent);}// 3.3. 左子树的右子树超高else if(-2 == parent->_bf && 1 == cur->_bf){RotateLR(parent);}// 3.4. 右子树的左子树超高else if(2 == parent->_bf && -1 == cur->_bf){RotateRL(parent);}break;}}return true;}// AVL树的验证bool IsAVLTree(){return _IsAVLTree(_pRoot).second;}private:// 根据AVL树的概念验证pRoot是否为有效的AVL树pair<int, bool> _IsAVLTree(Node* pRoot){if(pRoot == nullptr){return make_pair(0, true);}pair<int, bool> lson = _IsAVLTree(pRoot->_pLeft);cout << pRoot->_data << " ";pair<int, bool> rson = _IsAVLTree(pRoot->_pRight);int hight = max(rson.first, lson.first) + 1;bool Is = rson.second && lson.second && abs(rson.first - lson.first) <= 1;return make_pair(hight, Is);}// size_t _Height(Node* pRoot)// {//     if(nullptr == pRoot)//     {//         return 0;//     }//     else{//         return max<size_t>(_Height(pRoot->_pLeft), _Height(pRoot->_pRight)) + 1;//     }// }// 右单旋void RotateR(Node* pParent){Node* SubL = pParent->_pLeft;Node* SubLR = SubL->_pRight;Node* parent = pParent->_pParent;pParent->_pLeft = SubLR;pParent->_pParent = SubL;if(SubLR)SubLR->_pParent = pParent;SubL->_pRight = pParent;SubL->_pParent = parent;if(pParent == _pRoot){_pRoot = SubL;}else{if(parent->_pLeft == pParent){parent->_pLeft = SubL;}else if(parent->_pRight == pParent){parent->_pRight = SubL;}else{assert(false);}}pParent->_bf = SubL->_bf = 0;}// 左单旋void RotateL(Node* pParent){Node* SubR = pParent->_pRight;Node* SubRL = SubR->_pLeft;Node* parent = pParent->_pParent;pParent->_pRight= SubRL;pParent->_pParent = SubR;if(SubRL)SubRL->_pParent = pParent;SubR->_pLeft = pParent;SubR->_pParent = parent;if(pParent == _pRoot){_pRoot = SubR;}else{if(parent->_pLeft == pParent){parent->_pLeft = SubR;}else if(parent->_pRight == pParent){parent->_pRight = SubR;}else{assert(false);}}pParent->_bf = SubR->_bf = 0;}// 右左双旋void RotateRL(Node* pParent){Node* SubR = pParent->_pRight;Node* SubRL = SubR->_pLeft;int bf = SubRL->_bf;RotateR(SubR);RotateL(pParent);if(0 == bf){SubR->_bf = SubRL->_bf = pParent->_bf = 0;}else if(-1 == bf){SubRL->_bf = pParent->_bf = 0;SubR->_bf = 1;}else if(1 == bf){SubRL->_bf = SubR->_bf = 0;pParent->_bf = -1;}else{assert(false);}}// 左右双旋void RotateLR(Node* pParent){Node* SubL = pParent->_pLeft;Node* SubLR = SubL->_pRight;int bf = SubLR->_bf;RotateL(SubL);RotateR(pParent);if(0 == bf){SubL->_bf = SubLR->_bf = pParent->_bf = 0;}else if(1 == bf){SubLR->_bf = pParent->_bf = 0;SubL->_bf = -1;}else if(-1 == bf){SubLR->_bf = SubL->_bf = 0;pParent->_bf = 11;}else{assert(false);}}private:Node* _pRoot;
};

需要注意的是旋转之后改变了节点的顺序，那么需要重新连接父节点或者改变根节点。

三、测试

#include "AVLtree.hpp"int main()
{AVLTree<int> avltree;for(int i = 0; i < 100; ++i){if(i == 2){int j = 0;}avltree.Insert(i);}if(avltree.IsAVLTree()){cout << "avltree是二叉搜索树" << endl;}else{cout << "avltree不是二叉搜索树" << endl;}return 0;
}