1.AVL 树

1.1AVL 树的概念

二叉搜索树虽可以缩短查找的效率，但如果数据有序或接近有序二叉搜索树将退化为单支树，查 找元素相当于在顺序表中搜索元素，效率低下。因此，两位俄罗斯的数学家G.M.Adelson-Velskii 和E.M.Landis在1962年 发明了一种解决上述问题的方法：当向二叉搜索树中插入新结点后，如果能保证每个结点的左右 子树高度之差的绝对值不超过1(需要对树中的结点进行调整)，即可降低树的高度，从而减少平均 搜索长度。

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

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

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

如果一棵二叉搜索树是高度平衡的，它就是AVL树。如果它有n个结点，其高度可保持在 O(log_2 n)，搜索时间复杂度O(log_2 n)。

2.AVL树节点的定义 

<code>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;//右子树高度-左子树高度,只有孩子发生变化，bf才有可能发生变化！！！！，若改变父亲，bf不变！！！！！！

AVLtreenode(const pair<K, V>& _kv) //初始化列表

:_left(nullptr)

,_right(nullptr)

,_parent(nullptr)

,kv(_kv)

,bf(0)

{}

};

3.AVL树的插入！！！！！！！ 

3.1初步插入

初步插入与bst的插入一致，不过里面的数据类型是pair<first,second>,并且是根据first进行比较

if (root == nullptr)

{

root = new node(_kv);

return true;

}

node* parent = nullptr; //比bst多了一个parent

node* cur = root; //

while (cur)

{

parent = cur;

if (cur->kv.first < _kv.first)

{

cur = cur->_right;

}

else if (cur->kv.first > _kv.first)

{

cur = cur->_left;

}

else

{

return false;

}

}

cur = new node(_kv);

if (parent->kv.first < _kv.first)

{

parent->_right = cur;

}

else

{

parent->_left = cur;

}

cur->_parent = parent; //记得连接parent和cur

3.2调整平衡因子 

<code>while (cur != root)

{

if (cur == parent->_left)

parent->bf--;//第一次！！！检查parent左边原来必为空

else {

parent->bf++;//第一次！！！检查parent右边原来必为空

}

if (parent->bf == 0) //相当于bf没改变，可直接退出

{

break;

}

else if (parent->bf == 1 || parent->bf == -1) //bf改变了继续向上找

{

cur = parent;

parent = parent->_parent;

}

else if(parent->bf == -2 || parent->bf == 2)

{ //-2||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)

{

rotateRL(parent);//先右旋再左旋

}

else if (parent->bf == -2 && cur->bf == 1)

{

rotateLR(parent);//先左旋再右旋

}

//旋转让子树变得平衡

//旋转降低了子树的高度，恢复到和插入前一样的高度，所以对上一层没有影响

break;//1次旋转完成后不需要再调整了

}

}

3.3旋转调整！！！！！！ 

1.新节点插入较高右子树的右侧---右右：左单旋

 由上述可知，c必定是x类型的avl树，如果是其他类型的，可能60这个节点的平衡因子就变成-2或2了，（当然，这只是单独举一个例子分析，便于分析代码，不代表所有情况）

<code>void rotateL(node* parent)//左旋，（新节点插入到较高右子树的右侧）// 1.右右

{

node* subr = parent->_right;

node* subrl = subr->_left;

parent->_right = subrl;

subr->_left= parent;

node* ppnode = parent->_parent;

parent->_parent = subr;

if (subrl) //subrl可能为空！！！！！！！！！！！！！！！

{

subrl->_parent = parent;

}

if (parent == root) // 即如果parent->_parent==nullptr

{

root = subr;

subr->_parent = nullptr;

}

else

{

if (ppnode->_left == parent) //需要再查找一下放左边还是右边

{

ppnode->_left = subr;

}

else if (ppnode->_right == parent)

{

ppnode->_right = subr;

}

subr->_parent = ppnode;

}

parent->bf = subr->bf = 0; //重置平衡因子

}

2.新节点插入较高左子树的左侧---左左：右单旋 

和左单旋分析方法一致

<code>void rotateR(node* parent)//右旋，（新节点插入到较高左子树的左侧）// 2.左左

{

node* subl = parent->_left;

node* sublr = subl->_right;

parent->_left = sublr;

if (sublr) //sublr可能为空！！！！！！！

sublr->_parent = parent;

node* ppnode = parent->_parent;

subl->_right = parent;

parent->_parent=subl;

if (root == parent)

{

root = subl;

subl->_parent = nullptr;

}

else

{

if (ppnode->_left == parent)

{

ppnode->_left = subl;

}

else if (ppnode->_right == parent)

{

ppnode->_right = subl;

}

subl->_parent = ppnode;

}

subl->bf = parent->bf = 0;//重置平衡因子

}

3. 新节点插入较高左子树的右侧---左右：先左单旋再右单旋

十分巧妙的是：经过一次左旋(parent->_left)后，就变成左左类型了，这样就能复用右单旋(parent)达成平衡 

<code>void rotateLR(node* parent)//左旋一次，再右旋一次，还需要根据不同的_bf更新平衡因子

{

node* subl = parent->_left;

node* sublr= subl->_right;

int _bf = sublr->bf;

rotateL(parent->_left);

rotateR(parent);

if (_bf == 0)

{

//sublr自己就是新增加的节点

parent->bf = subl->bf = sublr->bf = 0;

}

else if (_bf == 1)

{

//sublr的右子树新增

parent->bf = 0;

subl->bf = -1;

sublr->bf = 0;

}

else if (_bf == -1)

{

//sublr的左子树新增

parent->bf = 1;

subl->bf = 0;

sublr->bf = 0;

}

}

4.新节点插入较高右子树的左侧---右左：先右单旋再左单旋  

与上方分析方法一致

<code>void rotateRL(node* parent) //右旋一次，再左旋一次，还需要根据不同的_bf更新平衡因子

{

node* subr = parent->_right;

node* subrl = subr->_left;

int _bf = subrl->bf;

rotateR(parent->_right);

rotateL(parent);

if (_bf == 0)

{

//subrl自己就是新增加的节点

parent->bf = subr->bf = subrl->bf = 0;

}

else if (_bf == -1)

{

//subrl的右子树新增

parent->bf = 0;

subr->bf = 1;

subrl->bf = 0;

}

else if (_bf == 1)

{

//subrl的左子树新增

parent->bf = -1;

subr->bf = 0;

subrl->bf = 0;

}

}

总结：

假如以pParent为根的子树不平衡，即pParent的平衡因子为2或者-2，分以下情况考虑

1. pParent的平衡因子为2，说明pParent的右子树高，设pParent的右子树的根为pSubR

当pSubR的平衡因子为1时，执行左单旋

当pSubR的平衡因子为-1时，执行右左双旋

2. pParent的平衡因子为-2，说明pParent的左子树高，设pParent的左子树的根为pSubL

当pSubL的平衡因子为-1是，执行右单旋

当pSubL的平衡因子为1时，执行左右双旋

旋转完成后，原pParent为根的子树个高度降低，已经平衡，不需要再向上更新。  

4.AVL树的判断 

 AVL树是在二叉搜索树的基础上加入了平衡性的限制，因此要验证AVL树，可以分两步：

1. 验证其为二叉搜索树

：如果中序遍历可得到一个有序的序列，就说明为二叉搜索树

2. 验证其为平衡树

（1）每个节点子树高度差的绝对值不超过1(注意节点中如果没有平衡因子)

（2）节点的平衡因子是否计算正确  

void inorder()

{

_inorder(root);

}

void _inorder(node* root)

{

if (root == nullptr)

return;

_inorder(root->_left);

cout << root->kv.first << " ";

_inorder(root->_right);

}

int _height(node* root)//取得高度

{

if (root == nullptr)

return 0;

int lh = _height(root->_left);

int rh = _height(root->_right);

return lh > rh ? lh + 1 : rh + 1;//记得+1

}

bool isbalance()

{

return _isbalance(root);

}

bool _isbalance(node* root)

{

if (root == nullptr)

return true;

int lh = _height(root->_left);

int rh = _height(root->_right);

if ((rh - lh) !=root->bf)//判断是否符合平衡因子计算公式

{

cout << "异常" << endl;

return false;

}

return (rh - lh) <2 && (rh - lh)>-2 && _isbalance(root->_left) && _isbalance(root->_right);//递归判断左右子树

}

5.完整代码 

 AVL.h：

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;//右子树高度-左子树高度,只有孩子发生变化，bf才有可能发生变化！！！！，若改变父亲，bf不变！！！！！！

AVLtreenode(const pair<K, V>& _kv)

:_left(nullptr)

,_right(nullptr)

,_parent(nullptr)

,kv(_kv)

,bf(0)

{}

};

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* parent = nullptr; //比bst多了一个parent

node* cur = root; //

while (cur)

{

parent = cur;

if (cur->kv.first < _kv.first)

{

cur = cur->_right;

}

else if (cur->kv.first > _kv.first)

{

cur = cur->_left;

}

else

{

return false;

}

}

cur = new node(_kv);

if (parent->kv.first < _kv.first)

{

parent->_right = cur;

}

else

{

parent->_left = cur;

}

cur->_parent = parent;

//开始调整

//调整平衡因子

while (cur != root)

{

if (cur == parent->_left)

parent->bf--;//第一次！！！检查parent左边原来必为空

else {

parent->bf++;//第一次！！！检查parent右边原来必为空

}

if (parent->bf == 0) //相当于bf没改变，可直接退出

{

break;

}

else if (parent->bf == 1 || parent->bf == -1) //bf改变了继续向上找

{

cur = parent;

parent = parent->_parent;

}

else if(parent->bf == -2 || parent->bf == 2)

{ //-2||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)

{

rotateRL(parent);//先右旋再左旋

}

else if (parent->bf == -2 && cur->bf == 1)

{

rotateLR(parent);//先左旋再右旋

}

//旋转让子树变得平衡

//旋转降低了子树的高度，恢复到和插入前一样的高度，所以对上一层没有影响

break;//1次旋转完成后不需要再调整了

}

}

return true;

}

void rotateL(node* parent)//左旋，（新节点插入到较高右子树的右侧）// 1.右右

{

node* subr = parent->_right;

node* subrl = subr->_left;

parent->_right = subrl;

subr->_left= parent;

node* ppnode = parent->_parent;

parent->_parent = subr;

if (subrl) //subrl可能为空！！！！！！！

{

subrl->_parent = parent;

}

if (parent == root) //即如果parent->_parent==nullptr

{

root = subr;

subr->_parent = nullptr;

}

else

{

if (ppnode->_left == parent)

{

ppnode->_left = subr;

}

else if (ppnode->_right == parent)

{

ppnode->_right = subr;

}

subr->_parent = ppnode;

}

parent->bf = subr->bf = 0; //重置平衡因子

}

void rotateR(node* parent)//右旋，（新节点插入到较高左子树的左侧）// 2.左左

{

node* subl = parent->_left;

node* sublr = subl->_right;

parent->_left = sublr;

if (sublr) //sublr可能为空！！！！！！！

sublr->_parent = parent;

node* ppnode = parent->_parent;

subl->_right = parent;

parent->_parent=subl;

if (root == parent)

{

root = subl;

subl->_parent = nullptr;

}

else

{

if (ppnode->_left == parent)

{

ppnode->_left = subl;

}

else if (ppnode->_right == parent)

{

ppnode->_right = subl;

}

subl->_parent = ppnode;

}

subl->bf = parent->bf = 0;

}

void rotateRL(node* parent) //右旋一次，再左旋一次，还需要根据不同的_bf更新平衡因子

{

node* subr = parent->_right;

node* subrl = subr->_left;

int _bf = subrl->bf;

rotateR(parent->_right);

rotateL(parent);

if (_bf == 0)

{

//subrl自己就是新增加的节点

parent->bf = subr->bf = subrl->bf = 0;

}

else if (_bf == -1)

{

//subrl的右子树新增

parent->bf = 0;

subr->bf = 1;

subrl->bf = 0;

}

else if (_bf == 1)

{

//subrl的左子树新增

parent->bf = -1;

subr->bf = 0;

subrl->bf = 0;

}

}

void rotateLR(node* parent)//左旋一次，再右旋一次，还需要根据不同的_bf更新平衡因子

{

node* subl = parent->_left;

node* sublr= subl->_right;

int _bf = sublr->bf;

rotateL(parent->_left);

rotateR(parent);

if (_bf == 0)

{

//sublr自己就是新增加的节点

parent->bf = subl->bf = sublr->bf = 0;

}

else if (_bf == 1)

{

//sublr的右子树新增

parent->bf = 0;

subl->bf = -1;

sublr->bf = 0;

}

else if (_bf == -1)

{

//sublr的左子树新增

parent->bf = 1;

subl->bf = 0;

sublr->bf = 0;

}

}

void inorder()

{

_inorder(root);

}

void _inorder(node* root)

{

if (root == nullptr)

return;

_inorder(root->_left);

cout << root->kv.first << " ";

_inorder(root->_right);

}

int _height(node* root)

{

if (root == nullptr)

return 0;

int lh = _height(root->_left);

int rh = _height(root->_right);

return lh > rh ? lh + 1 : rh + 1;

}

bool isbalance()

{

return _isbalance(root);

}

bool _isbalance(node* root)

{

if (root == nullptr)

return true;

int lh = _height(root->_left);

int rh = _height(root->_right);

if ((rh - lh) !=root->bf)

{

cout << "异常" << endl;

return false;

}

return (rh - lh) <2 && (rh - lh)>-2 && _isbalance(root->_left) && _isbalance(root->_right);

}

private:

node* root = nullptr;

};

test.c:

#define _CRT_SECURE_NO_WARNINGS

#include<iostream>

#include<map>

using namespace std;

#include"AVL.h"

int main()

{

int arr[] = { 4, 2, 6, 1, 3, 5, 15, 7, 16, 14 };

//int arr[] = { 16, 3, 7, 11, 9, 26, 18, 14, 15 };

AVLtree<int, int> it;

for (auto i : arr)

{

it.insert(make_pair(i,i));

}

it.inorder();

cout << endl<<it.isbalance() << endl;

return 0;

}

6.AVL树的性能

AVL树是一棵绝对平衡的二叉搜索树，其要求每个节点的左右子树高度差的绝对值都不超过1，这 样可以保证查询时高效的时间复杂度，即$og_2 (N)。但是如果要对AVL树做一些结构修改的操 作，性能非常低下，比如：插入时要维护其绝对平衡，旋转的次数比较多，更差的是在删除时， 有可能一直要让旋转持续到根的位置。因此：如果需要一种查询高效且有序的数据结构，而且数 据的个数为静态的(即不会改变)，可以考虑AVL树，但一个结构经常修改，就不太适合。