1. AVL树的概念
AVL树是一棵二叉搜索树，但它的每个节点的左右子树的高度差的绝对值不超过1，且它的子树也是平衡二叉树。左右子树的高度差也叫平衡因子，平衡因子 = 右子树叶的高度 - 左子树的高度。
将AVL树与满二叉树对比，看看AVL的效率如何？
2. AVL树的实现
2.1 节点的定义
//节点
template<class K, class V>
struct AVLTreeNode
{
AVLTreeNode<K, V>* _left;
AVLTreeNode<K, V>* _right;
AVLTreeNode<K, V>* _parent;
pair<K, V> _kv;
int _bf;//平衡因子
AVLTreeNode(const pair<K, V> kv)
:_left(nullptr)
, _right(nullptr)
, _parent(nullptr)
, _kv(kv)
, _bf(0)
{}
};
2.2 插入
- AVL树是二叉搜索树，所以首先按照二叉搜索树的规矩插入。插入后再考虑插入节点后，AVL树是否平衡。
- 有个例子
（1）更新后parent的平衡因子如果是1或者-1，说明parent所在子树的高度发生变化，会影响祖先，需要沿着到root的路径往上更新。
（2）更新后parent的平衡因子如果是0，说明parent所在子树的高度不变，不用继续沿着到root的路径往上更新。
（3）更新后parent的平衡因子如果是2或者-2，说明parent所在子树的高度变化且不平衡，对parent的子树进行旋转，使其平衡。
（4）如果parent是头节点，对parent进行旋转后，记得更新根节点。
- 旋转的原理
节点的插入可以分为以下几种情况
（1）左单旋：新节点插入在较高右子树的右侧
（2）右单旋：新节点插入较高左子树的左侧
（3）双旋：新节点插入较高右子树的左侧
（4）双旋：新节点插入较高左子树的右侧
代码
template<class K, class V>
class AVLTree
{
public:
typedef AVLTreeNode<K, V> Node;
bool insert(const pair<K, V>& kv)
{
if (_root == nullptr)
{
_root = new Node(kv);
return true;
}
Node* cur = _root;
Node* parent = cur;
while (cur)
{
if (cur->_kv.first < kv.first)
{
parent = cur;
cur = cur->_right;
}
else if (cur->_kv.first > kv.first)
{
parent = cur;
cur = cur->_left;
}
else
{
return false;
}
}
cur = new Node(kv);
if (parent->_kv.first < cur->_kv.first)
{
parent->_right = cur;
cur->_parent = parent;
}
else
{
parent->_left = cur;
cur->_parent = parent;
}
//更新平衡因子
while (parent)
{
if (parent->_left == cur)
{
--parent->_bf;
}
else
{
++parent->_bf;
}
//如果更新完平衡因子为0，说明其左右子树等高，已经平衡
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)
{
//新节点插入较高右子树的右侧，需要将parent左旋
if (parent->_bf == 2 && cur->_bf == 1)
{
RotateL(parent);
}
//新节点插入较高左子树的左侧，需要将parent右旋
else if (parent->_bf == -2 && cur->_bf == -1)
{
RotateR(parent);
}
//新节点插入较高右子树的左侧，需要先将cur右旋，再将parent左旋
else if (parent->_bf == 2 && cur->_bf == -1)
{
RotateRL(parent);
}
//新节点插入较高左子树的右侧，需要先将cur左旋，再将parent右旋
else if (parent->_bf == -2 && cur->_bf == 1)
{
RotateLR(parent);
}
else
{
assert(false);
}
break;
}
else
{
assert(false);
}
}
return true;
}
//左旋
void RotateL(Node* parent)
{
Node* cur = parent->_right;
Node* curleft = cur->_left;
parent->_right = curleft;
if (curleft)
{
curleft->_parent = parent;
}
cur->_left = parent;
//不要忘记父节点的链接
Node* pparent = parent->_parent;
parent->_parent = cur;
//要考虑parent的parent是否存在
if (pparent)
{
if (pparent->_left == parent)
{
pparent->_left = cur;
}
else
{
pparent->_right = cur;
}
cur->_parent = pparent;
}
else
{
_root = cur;
cur->_parent = nullptr;
}
//平衡因子置为0
parent->_bf = cur->_bf = 0;
}
//右旋
void RotateR(Node* parent)
{
Node* cur = parent->_left;
Node* curright = cur->_right;
parent->_left = curright;
if (curright)
{
curright->_parent = parent;
}
cur->_right = parent;
Node* pparent = parent->_parent;
parent->_parent = cur;
if (pparent)
{
if (pparent->_left == parent)
{
parent->_left = cur;
}
else
{
parent->_right = cur;
}
cur->_parent = pparent;
}
else
{
_root = cur;
cur->_parent = nullptr;
}
parent->_bf = cur->_bf = 0;
}
//双旋：新节点插入较高右子树的左侧
void RotateRL(Node* parent)
{
Node* cur = parent->_right;
Node* curleft = cur->_left;
//先右旋，再左旋
RotateR(cur);
RotateL(parent);
if (curleft->_bf == 0)
{
parent->_bf = 0;
cur->_bf = 0;
}
else if (curleft->_bf == 1)
{
parent->_bf = -1;
cur->_bf = 0;
}
else if (curleft->_bf == -1)
{
parent->_bf = 0;
cur->_bf = 1;
}
}
//双旋：新节点插入较高左子树的右侧
void RotateLR(Node* parent)
{
Node* cur = parent->_left;
Node* curright = cur->_right;
//先左旋再右旋
RotateL(cur);
RotateR(parent);
//更新平衡因子
if (curright->_bf == 0)
{
parent->_bf = 0;
cur->_bf = 0;
}
else if (curright->_bf == 1)
{
parent->_bf = 0;
cur->_bf = -1;
}
else if (curright->_bf == -1)
{
parent->_bf = 1;
cur->_bf = 0;
}
}
private:
Node* _root = nullptr;
};
2.3 是否是AVL树
如果一棵AVL树不平衡，那么它的左右子树的高度差的绝对值超过2，旋转出现问题。如果要判断一棵树是否是AVL树是否平衡，不能通过平衡因子判断，因为旋转出现问题，那么平衡因子也会出现问题，所以只能通过高度来判断。
代码
// 根据AVL树的概念验证pRoot是否为有效的AVL树
bool IsAVLTree()
{
return IsAVLTree(_root);
}
bool IsAVLTree(Node* pRoot)
{
//不能依赖平衡因子，容易监守自盗。如果旋转出现问题，平衡因子也会有问题
//所以直接通过高度来判断
if (pRoot == nullptr)
{
return true;
}
int leftHeight = Height(pRoot->_left);
int rightHeight = Height(pRoot->_right);
//abs返回参数的绝对值
return abs(leftHeight - rightHeight) < 2
&& IsAVLTree(pRoot->_left) && IsAVLTree(pRoot->_right);
}
int Height()
{
return Height(_root);
}
int Height(Node* root)
{
if (root == nullptr)
{
return 0;
}
int leftHeight = Height(root->_left);
int rightHeight = Height(root->_right);
return leftHeight > rightHeight ? leftHeight + 1 : rightHeight + 1;
}
3. AVL树与红黑树
插入时要维护其绝对平衡，旋转的次数比较多，如果需要一种查询高效且有序的数据结构，而且数据的个数为静态的(即不会改变)，可以考虑AVL树，但一个结构经常修改，就不太适合
红黑树不追
求绝对平衡，其只需保证最长路径不超过最短路径的2倍，相对而言，降低了插入和旋转的次数，
所以在经常进行增删的结构中性能比AVL树更优
- AVL树和红黑树都是平衡二叉树。在查询效率方面，AVL树追求绝对平衡，红黑树要求最长路径不超过最短路径的两倍，AVL查询数据效率比红黑树高，但是对于CPU而言，都是属于logN这个量级的。
- AVL树追求控制严格平衡是需要付出代价的，插入和删除已需要进行大量的旋转。红黑树不追求绝对平衡，其只需保证最长路径不超过最短路径的2倍，相对而言，降低了插入和旋转的次数，所以在插入和删除方面红黑树效率更高。
- 综上，红黑书更优，实际运用的多。
