hello树先生——AVL树

一.什么是AVL树

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

• 它的左右子树都是AVL树
• 左右子树高度之差(简称平衡因子)的绝对值不超过1(-1/0/1）
• 如果一棵二叉搜索树是高度平衡的，它就是AVL树。如果它有n个结点，其高度可保持在$O(lo{g}_{2}n)$
  

二.AVL树的结构

1.AVL树的节点结构

template<class K, class V>
struct AVLTreeNode
{AVLTreeNode* _left;AVLTreeNode* _right;AVLTreeNode* _parent;pair<K, V> _kv;int _bf;AVLTreeNode(const pair<K,V>& kv):_left(nullptr),_right(nullptr),_parent(nullptr),_kv(kv),_bf(0){}
};

这里的数据存储使用pair类型的数据对，将key索引与对应数据value存储，增加了_parent保存父亲节点，增加了_bf平衡因子来衡量左右子树是否平衡。

2.插入函数

bool insert(const pair<K, V>& kv)

这里插入方式与搜索二叉树一致，只是在后面增加了平衡调整的步骤

//如果根为空if (_root == nullptr){_root = new node(kv);return true;}//找到目标值node* parent = nullptr;node* cur = _root;while (cur){//key < curif (kv.first < cur->_kv.first){parent = cur;cur = cur->_left;}else if (kv.first > cur->_kv.first){parent = cur;cur = cur->_right;}else{//查重return false;}}//插入目标值cur = new node(kv);if (parent->_kv.first < kv.first){parent->_right = cur;}else{parent->_left = cur;}cur->_parent = parent;

调节平衡因子

while(parent)
{
//向上更新
}

如果插在左子树，则平衡因子–，否则++

if (parent->_left == cur){parent->_bf--;}else{parent->_bf++;}

判断平衡因子是否正常倘若>=2则需要旋转

			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){rotater(parent);}//右右高，左单旋else if(parent->_bf == 2 && cur->_bf == 1){rotatel(parent);}//右左高，先右旋成为右右高,再左旋else if (parent->_bf == 2 && cur->_bf == -1){rotaterl(parent);}else{rotatelr(parent);}break;}else{//大问题assert(false);}

3.旋转调整

AVL树的旋转分为四种，左单旋，右单旋，左右双旋和右左双旋。

1.右单旋

	void rotater(node* parent)

当插入new节点时，60节点会左右失衡，我们称60为parent，30为subl,则平衡因子会分别变为-2，-1，成为左左高模型，此时使用右单旋。
由于搜索树特性：30<b<60<c,所以可以将右方降下去，从而达到平衡。

• 传入旋转点parent

• 记录关键节点，防止旋转后丢失
  

		node* subl = parent->_left;node* sublr = subl->_right;

• 将parent的左指向sublr,若sublr为空节点，则不链接父亲节点否则链接
• 将subl的右指向parent,同时链接父亲节点

		parent->_left = sublr;if (sublr)sublr->_parent = parent;subl->_right = parent;parent->_parent = subl;//保存父节点node* ppnode = parent->_parent;subl->_parent = ppnode;

• 考虑parent是否为根，是否链接parent的父亲节点

		//考虑parent是否为根if (ppnode == nullptr){_root = subl;subl->_parent = nullptr;}else{subl->_parent = ppnode;if (ppnode->_left == parent){ppnode->_left = subl;}else{ppnode->_right = subl;}}

• 修改平衡因子

parent->_bf = subl->_bf = 0;

2.左单旋
大体思路与右单旋相同

	void rotatel(node* parent){node* subr = parent->_right;node* subrl = subr->_left;parent->_right = subrl;if (subrl)subrl->_parent = parent;subr->_left = parent;//保存父节点node* ppnode = parent->_parent;parent->_parent = subr;subr->_parent = ppnode;//考虑parent是否为根if (ppnode == nullptr){_root = subr;subr->_parent = nullptr;}else{subr->_parent = ppnode;if (ppnode->_left == parent){ppnode->_left = subr;}else{ppnode->_right = subr;}}//调节平衡因子parent->_bf = subr->_bf = 0;}

3.左右双旋

void rotatelr(node* parent)

通常双旋有三种情况，在b里插入新节点，在c里插入新节点，或者b,c都为空

记录sul的平衡因子，方便判断是哪种情况

		node* subl = parent->_left;node* sublr = subl->_right;int bf = subl->_bf;rotatel(subl);rotater(parent);

		if (bf == -1){subl->_bf = 0;parent = 1;}else if (bf == 1){subl->_bf = -1;parent->_bf = 0;}else if (bf == 0){subl->_bf = 0;parent->_bf = 0;}sublr->_bf = 0;

每一种情况平衡因子不同，所以需要画图分别讨论
** 4.右左双旋**

void rotaterl(node* parent){node* subr = parent->_right;node* subrl = subr->_left;int bf = subr->_bf;rotater(subr);rotater(parent);if (bf == -1){subr->_bf = 1;parent = 0;}else if (bf == 1){subr->_bf = 0;parent->_bf = -1;}else if (bf == 0){subr->_bf = 0;parent->_bf = 0;}subrl->_bf = 0;}

三.平衡测试

判断是否平衡

    bool _IsBalance(node* root){if (root == nullptr){return true;}int leftheight = _height(root->_left);int rightheight = _height(root->_right);if (abs(leftheight - rightheight) >= 2){return false;}//判断节点平衡因子是否正确if (root->_bf != (rightheight - leftheight)){return false;}return _IsBalance(root->_left) && _IsBalance(root->_right);}