STL之AVL模拟的实现
AVL树的概念
为什么会有AVL树？在STL中对map/multimap/set/multiset其底层都是按照二叉搜索树来实现的，但是二叉搜索树有其自身的缺陷，假如往树中 插入的元素有序或者接近有序，二叉搜索树就会退化成单支树，时间复杂度会退化成O(N)，
因此 map、set等关联式容器的底层结构是对==二叉树进行了平衡处理，即采用平衡树来实现==
二叉搜索树虽可以缩短查找的效率，==但如果数据有序或接近有序二叉搜索树将退化为单支树，查找元素相当于在顺序表中搜索元素，效率低下。==
因此，两位俄罗斯的数学家G.M.Adelson-Velskii 和E.M.Landis在1962年 发明了一种解决上述问题的方法：==当向二叉搜索树中插入新结点后，如果能保证每个结点的左右子树高度之差的绝对值不超过1(需要对树中的结点进行调整)，即可降低树的高度，从而减少平均搜索长度。==
一棵AVL树或者是空树，或者是具有以下性质的二叉搜索树：
- 它的左右子树都是AVL树
- 左右子树高度之差(简称平衡因子)的绝对值不超过1(-1/0/1)
如果一棵二叉搜索树是高度平衡的，它就是AVL树。如果它有n个结点，其高度可保持在 $O(log_2 n)$，搜索时间复杂度O($log_2 n$)。
所以AVL树又被叫做==高度平衡二叉搜索树==——是通过高度来进行平衡的！
节点的左右两个子树高度可以相等，也可以一边比另一边高1！——因为节点数量的原因，很难做到次次都是左右子树两边相等！（例如2个节点，4个节点....）所以允许高度差为1！
这里我们使用平衡因子来控制高度差的！
==平衡因子 = 右子树高度- 左子树高度==
AVL树不是必须加平衡因子也可以控制高度差！但是有了平衡因子我们就可以去评估树的状态！如果每一个平衡因子都是 0 /1 /-1 那么就说明这个树是没有问题的！如果为 2的话那么就说明这颗树需要进行调整了！
AVL树的实现
节点类
namespace MySTL { template<class K,class V> struct AVLTreeNode { AVLTreeNode(const std::pair<K,V>& kv)//构造函数 :_kv(kv) ,_left(nullptr) ,_right(nullptr) ,_parent(nullptr) ,_bf(0) {} std::pair<K, V> _kv; AVLTreeNode* _left;//左节点 AVLTreeNode* _right;//右节点 AVLTreeNode* _parent;//父节点 int _bf;//balance factory//平衡因子！ }; }
成员变量
namespace MySTL { template<class K,class V> class AVLTree { typedef AVLTreeNode<K, V> Node; public: private: Node* _root = nullptr;//一个根节点！ }; }
insert
插入方法
namespace MySTL { template<class K,class V> class AVLTree { typedef AVLTreeNode<K, V> Node; public: bool insert(const std::pair<K, V>& kv) { if (_root == nullptr) { _root = new Node(kv); return true; } Node* cur = _root; Node* parent = nullptr; //为什么不使用cur-> _parent而是搞了一个新的parent呢？ //因为当cur走到最后就是一个nullptr！如果此时使用cur->_parent那么就出现了空指针的解引用！ while (cur) { parent = cur; if (kv.first > cur->_kv.first) { cur = cur->_right; } else if (kv.first < cur->_kv.first) { cur = cur->_l eft; } else { return false; } } cur = new Node(kv); if (cur->_kv.first > parent->_kv.first) { parent->_right = cur; cur->_parent = parent; } else { parent->_left = cur; cur->_parent = parent; } ///////////////////////////////////////////////////////// //上面的插入逻辑就是二叉搜索树的插入逻辑！ return true; } private: Node* _root = nullptr; }; }==AVL树的插入逻辑与二叉搜索树的插入逻辑是一致的！==
如果插入在左边 那么根据父节点的 ==平衡因子 = 右子树高度 - 左子树高度==，此时平衡因子为 0 -1 = -1
如果插入在右边 那么就是 1- 0 = 1
我们需不需要对这颗树进行==处理首先就是要看更新后的平衡因子！==——一旦平衡因子绝对值大于1，就要开始处理这颗树
更新平衡因子
==那么该如何更新平衡因子呢==
==所以我们发现平衡因子停止更新的有三种情况！==
- 平衡因子更新后变成 0 ，那么停止向上更新！
- 平衡因子更新后变成 2/-2 ，二叉树出问题！要进行平衡处理！停止向上更新！
- 平衡因子一直更新！直到平衡因子更新到根节点位置！
#include<iostream> #include<cassert> namespace MySTL { template<class K,class V> class AVLTree { typedef AVLTreeNode<K, V> Node; public: bool insert(const std::pair<K, V>& kv) { ///插入操作 /////////////////////////////////////////////// //更新平衡因子 while (parent)//parent为空就结束！因为根节点的parent就是nullptr { if (cur == parent->_left)//如果插入的是左树就-- parent->_bf--; else if (cur == parent->_right)//如果插入右树就++ parent->_bf++; // 是否继续更新依据：子树的高度是否变化 // 1、parent->_bf == 0说明之前parent->_bf是 1 或者 -1 // 说明之前parent一边高一边低，这次插入填上矮的那边，parent所在子树高度不变，不需要继续往上更新 // 2、parent->_bf == 1 或 -1 说明之前是parent->_bf == 0，两边一样高，现在插入一边更高了， // parent所在子树高度变了，继续往上更新 // 3、parent->_bf == 2 或 -2，说明之前parent->_bf == 1 或者 -1，现在插入严重不平衡，违反规则 // 就地处理--旋转 if (parent->_bf == 0)//平衡因子为0更新结束 { break; } else if (parent->_bf == 1 || parent->_bf == -1)//平衡因子为1继续向上更新！ { cur = parent; parent = parent->_parent;//这时候父节点指针的作用就凸显出来了，如果父节点指针，我们就很难去找到原来的父节点！ } else if (parent->_bf == 2 || parent->_bf == -2) { //平衡处理！ } else { assert(false);//如果到意味着在我们插入更新树之前就出问题了！ } } return true; } //我们也可以使用cur->_parent代替parent //但是这样子可读性相比parent比较差一点 private: Node* _root = nullptr; }; }
左单旋
要处理旋转的情况——重点
要旋转的情况可以说有==无限多种情况下面我们可以先看几种==！
==因为几乎有无限多种的情况！我们就必须使用抽象图来表示这所有的情况！==
==这是需要左单旋的所有情况！==
==这个抽象图不是说40就一定会是根节点！也有可能是某个树的子树！==
我们可以举几个例子理解一下抽象图
到h =2 的时候，就已经有36种可能会发生单旋的情况！所以这就是为什么我们必须使用抽象图来表示的原因，如果不归类那么就没有办法去总结方法
==但是我们也看出来了！虽然有足足36种情况！但是我们进行左单旋使用的方法都是一样的！==
==需要进行左单旋的条件就是==
if(parent-> _bf == 2 && cur -> _bf == 1);//这时就要进行左单旋！
进行旋转的方法——重点
==旋转的目标==
- ==让这颗子树的左右高度差不超过1==
- ==旋转过程中，继续保持它是平衡搜索树！==
- ==更新调整子节点的平衡因子==
- ==降低子树的高度，让子树的高度跟插入前保持一致！==
所以进行==左旋转==的时候我们要保持一下几个原则！
- 让问题节点（平衡因子为2的节点）的右孩子的左节点，变成问题节点的右节点
- 让问题节点成为==问题节点的原右子节点的左节点！==
我们还是以上面的例子进行举例说明！
- 60节点的左节点要变成40节点的右节点！
- 然后40节点变成60节点的左节点！
==这样的处理依旧让整棵树能够依旧保持设二叉搜索树！因为问题节点平衡因子为2，说明是右边高！所以要左单旋==
让问题节点的右孩子的左节点，变成问题节点的右节点
因为==问题节点的右孩子的左子节点==，依旧在问题节点的右边，仍然大于问题节点！所以可以让其成为问题节点右节点！
让问题节点成为问题节点的右孩子的左节点！
再经过上一步之后，问题节点的右孩子的左节点位置已经空出来了！==因为问题节点（平衡因子为2）小于问题节点右孩子！ 经过上一步处理后的问题节点的左右子树上的所有节点也都小于问题节点原先的右子节点！==所以根据二叉搜索树，左小右大的规则，我们可以让==问题节点==成为==问题节点的原先右子节点的的左子节点！==
==我们可以发现！旋转操作只对问题节点和问题节点的右节点进行了操作！其他节点都没有动过！==
==而且旋转之后，进行平衡因子更新，然后问题节点的原右孩子就变成了平衡因子为0的节点！——即如果是子树就让这颗子树的高度和之间保持一致！这样子就不用继续往上更新了！==
namespace MySTL { template<class K,class V> class AVLTree { typedef AVLTreeNode<K, V> Node; private: void RotateL(Node* parent)//左单旋 { Node* subR = parent->_right;//父节点的右子节点 Node* subRL = subR->_left;.//右子节点的左子节点 //让右孩子的左节点成为parent的右节点！ parent->_right = subRL; //有3个节点_parent需要进行更新！ //以及一个节点的子节点需要进行更新！ if (subRL) subRL->_parent = parent;//如果右子节点的左子节点不是一个空节点！那么它的parent也要更新！ Node* ppNode = parent->_parent; if (ppNode) //如果这个颗树是一个子树！那么要跟更新parent的父节点的子节点！ { if (ppNode->_left == parent) ppNode->_left = subR; else ppNode->_right = subR; } else { _root = subR;//如果不是一个子树，那么subR此时就是根！ } //更新subR的父节点！ subR->_parent = ppNode;//这里如果是根节点ppNode就是nullptr！所以不需要在为空的情况多写一次！ //让parent 成为右子节点的左节点 subR->_left = parent; //此时parent是subR的左节点！ parent->_parent = subR; //更新平衡因子！ subR->_bf = parent->_bf = 0; } private: Node* _root = nullptr; }; }写左单旋的时候要注意——==因为很容易丢节点！==
parent的父节点如果是空！那么60就会成为新的根节点！——此时要更新_root，如果不为空！那么parent的父节点要更新子节点！(因为这时候60成为了子树的新根！)
如果b子树为空则其父节点就不要更新
==更新平衡因子！因为40节点本来的左子树的高度为 h，右子树高度为 h+2所以是 2，但是将右子树，换成是60节点的左子树（高度为h）后，那么平衡因子就变成 0==
==60节点的右子树高度为 h +1 ，左子树成为40节点的左子树后！以40节点为根的整个子树高度变成了h+1，然后40节点成为了60节点的左子树，所以此时平衡因子也变成了 0==
==至此我们的左单旋才是真正结束了！==
右单旋！
要处理旋转的情况——重点
==理解了上面的左旋转后我们理解右旋转就很容易了！==
我们先看一下右旋转的抽象图！
==很明显我们从抽象图中可以看出来！需要进行右单旋的条件==
if(parent->_bf == -2 && cur->_bf == -1);
进行旋转的方法——重点
右单旋的旋转其实和左单旋是思路是一一样的！
- ==将问题节点的左子节点的右子节点，变成问题节点的左节点！==
- ==然后将问题节点变成，问题节点原左节点的右节点！==
用上面的抽象图进行举例
将40的右子树变成70的左子树！
然后将以70为根的整个子树都变成40节点的右子树！
namespace MySTL { template<class K,class V> class AVLTree { typedef AVLTreeNode<K, V> Node; private: void RotateL(Node* parent) { Node* subL = parent->_left;//父节点的左子节点 Node* subLR = subL->_right;//父节点的左子节点的右子节点 //将父节点的左子节点的右子节点变成父节点的新左子节点！ parent->_left = subLR; //将父节点的原左子节点的右子节点的父节点进行更新为parent if (subLR) subLR->_parent = parent; //更新parent的父节点该指向的新节点！ Node* ppNode = parent->_parent; if (ppNode) { //改树是一个子树 //将ppNode指向新的子树根节点！ if (ppNode->_left == parent) ppNode->_left = subL; else ppNode->_right = subL; } else { //如果不是子树，直接更新，新的根节点 _root = subL; } //更新原父节点的左子节点的父节点 subL->_parent = ppNode; //将父节点变成原父节点的左子节点的右节点！ subL->_right = parent; //将父节点的父节点进行更新 parent->_parent = subL; //更新平衡因子 subL->_bf = parent_bf = 0; } private: Node* _root = nullptr; }; }==也要注意不要丢失节点！==
==无论是左单旋还是右单旋都是那边低，就往那边压==
左右双旋
需要左右双旋的情况——重点
如果是折线的右边高，我们发现依旧无法平衡！只是变成了一个左边高的折线了！虽然依旧是搜索树！但是还是无法平衡！
这时候单旋转依旧解决不了问题了！所以我们就必须用到==双旋转==了！
==下面是左右双旋的抽象图==
为了方便理解我们还是画几个具体的图来
==所以我们可以判断出需要进行左右双旋的情况条件为==
if(parent->_bf == -2 && cur->_bf == 1)
左右双旋的操作——重点
namespace MySTL { template<class K,class V> class AVLTree { typedef AVLTreeNode<K, V> Node; private: void RotateLR(Node* parent) { Node* subL = parent->_left; Node* subLR = subL->_right;//这个是重点！最后会是树的新根！ int old_bf = subLR->_bf; RotateL(subL); RotateR(parent); //左右双旋的问题在于更新平衡因子！ if (old_bf == 1)//在右边插入 { parent->_bf = 0; subL->_bf = -1; subLR->_bf = 0; //这个是最终旋转后是子树的新根！所以bf一定会为 0 } else if(old_bf == -1)//左边插入！ { parent->_bf = 1; subL->_bf = 0; subLR->_bf = 0; } else if(old_bf == 0)//这个节点就是新插入的节点！ { parent->_bf = 0; subL->_bf = 0; subLR->_bf = 0; } else { assert(false); } } private: Node* _root = nullptr; }; }左右双旋的重点在于==平衡因子的更新！==
以上面的为例子！
==第一次左单旋后将40节点与60节点的平衡因子都变成0了！==
==第二次右单旋将90节点与60节点的平衡也都变成0了！==
==所以一共有三种情况！==
右左双旋
需要右左双旋的情况——重点
我们先看一下==右左双旋抽象图==
有了上面的左右双旋！对于右左双旋我们就很好理解！
插入在b子树或者c子树的不同在于平衡因子的调整不一样！
==从图中我们也可以看出需要右左双旋的条件就是==
if(parent->_bf == 2 && cur->_bf == -1);
右左双旋的操作——重点
namespace MySTL { template<class K,class V> class AVLTree { typedef AVLTreeNode<K, V> Node; private: void RotateRL(Node* parent) { Node* subR = parent->_right; Node* subRL = subR->_left;//这个是重点！最后会是树的新根！ int old_bf = subRL->_bf; RotateR(subR); RotateL(parent); if (old_bf == 1)//在右边插入 { subR->_bf = 0; parent->_bf = -1; subRL->_bf = 0;//！！！！！千万不要更新错误！博主就因为更新错了节点，检查了一个小时o(╥﹏╥)o } else if (old_bf == -1)//在左边插入！ { subR->_bf = 1; parent->_bf = 0; subRL->_bf = 0; } else if (old_bf == 0)//该节点就是新增节点！ { subR->_bf = 0; parent->_bf = 0; subRL->_bf = 0; } else { assert(false);//说明其他地方出问题了！ } } private: Node* _root = nullptr; }; }==右左双旋也要注意平衡因子的更新！==
==同样是分三种情况！==
insert总代码
#pragma once
#include<iostream>
#include<cassert>
#include<algorithm>
namespace MySTL
{
template<class K,class V>
struct AVLTreeNode
{
AVLTreeNode(const std::pair<K,V>& kv)
:_kv(kv)
,_left(nullptr)
,_right(nullptr)
,_parent(nullptr)
,_bf(0)
{}
std::pair<K, V> _kv;
AVLTreeNode* _left;
AVLTreeNode* _right;
AVLTreeNode* _parent;
int _bf;//balance factory
};
template<class K,class V>
class AVLTree
{
typedef AVLTreeNode<K, V> Node;
public:
bool insert(const std::pair<K, V>& kv)
{
if (_root == nullptr)
{
_root = new Node(kv);
return true;
}
Node* cur = _root;
Node* parent = nullptr;
while (cur)
{
parent = cur;
if (kv.first > cur->_kv.first)
{
cur = cur->_right;
}
else if (kv.first < cur->_kv.first)
{
cur = cur->_left;
}
else
{
return false;
}
}
cur = new Node(kv);
if (cur->_kv.first > parent->_kv.first)
{
parent->_right = cur;
cur->_parent = parent;
}
else
{
parent->_left = cur;
cur->_parent = parent;
}
///////////////////////////////////////////////
//更新平衡因子
while (parent)//parent为空就结束！因为根节点的parent就是nullptr
{
if (cur == parent->_left)
parent->_bf--;
else if (cur == parent->_right)
parent->_bf++;
if (parent->_bf == 0)
{
break;
}
else if (parent->_bf == 1 || parent->_bf == -1)
{
cur = parent;
parent = parent->_parent;
}
else if (parent->_bf == 2 || parent->_bf == -2)
{
//平衡处理！
if (parent->_bf == 2 && cur->_bf == 1)
{
RotateL(parent);//调用左单旋
}
else if (parent->_bf == -2 && cur->_bf == -1)
{
RotateR(parent);//调用右单旋！
}
else if (parent->_bf == -2 && cur->_bf == 1)
{
RotateLR(parent);
}
else if(parent->_bf == 2 && cur->_bf == -1)
{
RotateRL(parent);
}
else
{
assert(false);
}
break;
//旋转完后高度不变就不用继续更新了！
}
else
{
assert(false);//如果到意味着在我们插入更新树之前就出问题了！
}
}
return true;
}
private:
void RotateL(Node* parent)//左单旋
{
Node* subR = parent->_right;//父节点的右子节点
Node* subRL = subR->_left;//右子节点的左子节点
//让右孩子的左节点成为parent的右节点！
parent->_right = subRL;
//有3个节点_parent需要进行更新！
//以及一个节点的子节点需要进行更新！
if (subRL)
subRL->_parent = parent;//如果右子节点的左子节点不是一个空节点！那么它的parent也要更新！
Node* ppNode = parent->_parent;
if (ppNode) //如果这个颗树是一个子树！那么要跟更新parent的父节点的子节点！
{
if (ppNode->_left == parent)
ppNode->_left = subR;
else
ppNode->_right = subR;
}
else
{
_root = subR;//如果不是一个子树，那么subR此时就是根！
}
//更新subR的父节点！
subR->_parent = ppNode;
//让parent 成为右子节点的左节点
subR->_left = parent;
//此时parent是subR的左节点！
parent->_parent = subR;
//更新平衡因子！
subR->_bf = parent->_bf = 0;
}
void RotateR(Node* parent)
{
Node* subL = parent->_left;//父节点的左子节点
Node* subLR = subL->_right;//父节点的左子节点的右子节点
//将父节点的左子节点的右子节点变成父节点的新左子节点！
parent->_left = subLR;
//将父节点的原左子节点的右子节点的父节点进行更新为parent
if (subLR)
subLR->_parent = parent;
//更新parent的父节点该指向的新节点！
Node* ppNode = parent->_parent;
if (ppNode)
{
//改树是一个子树
//将ppNode指向新的子树根节点！
if (ppNode->_left == parent)
ppNode->_left = subL;
else
ppNode->_right = subL;
}
else
{
//如果不是子树，直接更新，新的根节点
_root = subL;
}
//更新原父节点的左子节点的父节点
subL->_parent = ppNode;
//将父节点变成原父节点的左子节点的右节点！
subL->_right = parent;
//将父节点的父节点进行更新
parent->_parent = subL;
//更新平衡因子
subL->_bf = parent->_bf = 0;
}
void RotateLR(Node* parent)
{
Node* subL = parent->_left;
Node* subLR = subL->_right;//这个是重点！最后会是树的新根！
int old_bf = subLR->_bf;
RotateL(subL);
RotateR(parent);
//左右双旋的问题在于更新平衡因子！
if (old_bf == 1)//在右边插入
{
parent->_bf = 0;
subL->_bf = -1;
subLR->_bf = 0; //这个是最终旋转后是子树的新根！所以bf一定会为 0
}
else if(old_bf == -1)//左边插入！
{
parent->_bf = 1;
subL->_bf = 0;
subLR->_bf = 0;
}
else if(old_bf == 0)//这个节点就是新插入的节点！
{
parent->_bf = 0;
subL->_bf = 0;
subLR->_bf = 0;
}
else
{
assert(false);
}
}
void RotateRL(Node* parent)
{
Node* subR = parent->_right;
Node* subRL = subR->_left;
int old_bf = subRL->_bf;
RotateR(subR);
RotateL(parent);
if (old_bf == 1)//在右边插入
{
subR->_bf = 0;
parent->_bf = -1;
subRL->_bf = 0;
}
else if (old_bf == -1)
{
subR->_bf = 1;
parent->_bf = 0;
subRL->_bf = 0;
}
else if(old_bf == 0)
{
subR->_bf = 0;
parent->_bf = 0;
subRL->_bf = 0;
}
else
{
assert(false);
}
}
private:
Node* _root = nullptr;
};
}
avl树测试
对于avl的平衡测试！我们可以采用如下代码
#pragma once #include<iostream> #include<cassert> #include<algorithm> namespace MySTL { template<class K,class V> class AVLTree { typedef AVLTreeNode<K, V> Node; public: bool Isbalance() { return _Isbalace(_root); } private: int Height(Node* root) { if (root == nullptr) return 0; int left = Height(root->_left) + 1; int right = Height(root->_right) + 1; return std::max(left, right); } bool _Isbalace(Node* root) { if (root == nullptr) return true; int leftHeight = Height(root->_left); int rightHeight = Height(root->_right); if (rightHeight -leftHeight!= root->_bf) { cout << "该平衡因子异常：" << root->_kv.first << endl; } return std::abs(leftHeight - rightHeight) < 2 && _Isbalace(root->_left) && _Isbalace(root->_right); } private: Node* _root = nullptr; }; }对于AVL树是否真的平衡我们不能采用去查看平衡因子来判断是不是平衡！——这样有坚守自盗的嫌疑，我们每次旋转完后都会修改平衡因子，但是我们不能保证旋转就一定正确
所以我们必须通过查看两个树的高度对比来判断这个颗树是不是真的平衡！
==可以使用随机数来进行测试！==
void AVLTreetest() { const size_t N = 10000; srand(time(0)); AVLTree<int, int> avl; std::vector<int> v; for (int i = 0; i < N; i++) { size_t x = rand(); v.push_back(x);//记录插入的顺序 avl.insert(std::make_pair(x, 1)); } avl.inorder(); avl.Isbalance(); int i = 0; }
AVL树的删除
因为AVL树也是二叉搜索树，==可按照二叉搜索树的方式将节点删除==，然后==再更新平衡因子==，只不过与删除不同的时，删除节点后的平衡因子更新，最差情况下一直要调整到根节点的位置。
==如果兴趣读者可以选择自己去实现！要但是要记住删除的旋转后的平衡因子要进行重新调整！==
AVL树的性能
AVL树是一棵绝对平衡的二叉搜索树，其要求每个节点的左右子树高度差的绝对值都不超过1，这 样可以保证查询时高效的时间复杂度，即$log_2 (N)$。
但是如果要对AVL树做一些结构修改的操 作，性能非常低下==，比如：插入时要维护其绝对平衡，旋转的次数比较多，更差的是在删除时， 有可能一直要让旋转持续到根的位置。==
因此：==如果需要一种查询高效且有序的数据结构，而且数据的个数为静态的(即不会改变)，可以考虑AVL树，但一个结构经常修改，就不太适合。==