【数据结构】平衡二叉树（AVL树）

前言

一、AVL树概念

二、AVL树节点定义

三、AVL树插入

1. 按照二叉搜索树的方式插入新节点

2. 维护节点的平衡因子与调整树的结构

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

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

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

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

四、AVL树删除

附录：AVL树实现参考代码

前言

二叉搜索树虽可以缩短查找的效率，但如果数据有序或接近有序二叉搜索树将退化为单支树，查找元素相当于在顺序表中搜索元素，效率低下。

因此，两位俄罗斯的数学家G.M.Adelson-Velskii 和E.M.Landis在1962年发明了一种方法，用以解决上述问题。

一、AVL树概念

AVL 树是一种平衡二叉树，得名于其发明者的名字（ Adelson-Velskii 以及 Landis）。（可见名字长的好处，命名都能多占一个字母出来）。平衡二叉树递归定义如下：

左右子树的高度差小于等于 1。
其每一个子树均为平衡二叉树。

为了使AVL树保持平衡，在节点中增加了一个平衡因子作为节点属性。当树发生变化时，就通过维护平衡因子与改变树的结构来使树保持平衡。

二、AVL树节点定义

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

三、AVL树插入

AVL树就是在二叉搜索树的基础上引入了平衡因子，因此AVL树也可以看成是二叉搜索树。那么 AVL树的插入过程可以分为两步：

1. 按照二叉搜索树的方式插入新节点

参考二叉搜索树。

【数据结构】二叉搜索树-CSDN博客https://blog.csdn.net/lyhv_v/article/details/139243506

2. 维护节点的平衡因子与调整树的结构

cur插入后，pParent的平衡因子一定需要调整，在插入之前，pParent 的平衡因子分为三种情况：-1，0, 1, 分以下两种情况：

如果pCur插入到pParent的左侧，只需给pParent的平衡因子-1即可
如果pCur插入到pParent的右侧，只需给pParent的平衡因子+1即可

此时：pParent的平衡因子可能有三种情况：0，正负1，正负2

如果pParent的平衡因子为0，说明插入之前pParent的平衡因子为正负1，插入后被调整成0，此时满足 AVL树的性质，插入成功
如果pParent的平衡因子为正负1，说明插入前pParent的平衡因子一定为0，插入后被更新成正负1，此时以pParent为根的树的高度增加，需要继续向上更新
如果pParent的平衡因子为正负2，则pParent的平衡因子违反平衡树的性质，需要对其进行旋转处理

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

Node* RotateR(Node* parent)
{Node* sub = parent->_left;Node* subR = sub->_right;if (parent == _root){_root = sub;sub->_parent = nullptr;}else{Node* up = parent->_parent;if (up->_kv.first > sub->_kv.first)up->_left = sub;elseup->_right = sub;sub->_parent = up;}parent->_left = subR;if (subR != nullptr)subR->_parent = parent;sub->_right = parent;parent->_parent = sub;parent->_bf = 0;sub->_bf = 0;return sub;
}

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

Node* RotateL(Node* parent)
{Node* sub = parent->_right;Node* subL = sub->_left;if (parent == _root){_root = sub;sub->_parent = nullptr;				}else{Node* up = parent->_parent;if (up->_kv.first > sub->_kv.first)up->_left = sub;elseup->_right = sub;sub->_parent = up;}parent->_right = subL;if (subL != nullptr)subL->_parent = parent;sub->_left = parent;parent->_parent = sub;parent->_bf = 0;sub->_bf = 0;return sub;
}

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

Node* RotateLR(Node* parent)
{Node* child = parent->_left;Node* sub = child->_right;Node* subL = sub->_left;Node* subR = sub->_right;if (parent == _root){_root = sub;sub->_parent = nullptr;}else{Node* up = parent->_parent;if (up->_kv.first > sub->_kv.first)up->_left = sub;elseup->_right = sub;sub->_parent = up;}sub->_right = parent;parent->_parent = sub;sub->_left = child;child->_parent = sub;parent->_left = subR;if (subR != nullptr)subR->_parent = parent;child->_right = subL;if (subL != nullptr)subL->_parent = child;if (sub->_bf == 1){parent->_bf = 0;child->_bf = -1;}else if (sub->_bf == -1){parent->_bf = 1;child->_bf = 0;}else{parent->_bf = 0;child->_bf = 0;}sub->_bf = 0;return sub;
}

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

Node* RotateRL(Node* parent)
{Node* child = parent->_right;Node* sub = child->_left;Node* subL = sub->_left;Node* subR = sub->_right;if (parent == _root){_root = sub;sub->_parent = nullptr;}else{Node* up = parent->_parent;if (up->_kv.first > sub->_kv.first)up->_left = sub;elseup->_right = sub;sub->_parent = up;}sub->_left = parent;parent->_parent = sub;sub->_right = child;child->_parent = sub;parent->_right = subL;if (subL != nullptr)subL->_parent = parent;child->_left = subR;if (subR != nullptr)subR->_parent = child;if (sub->_bf == 1){parent->_bf = -1;child->_bf = 0;}else if (sub->_bf == -1){parent->_bf = 0;child->_bf = 1;}else{parent->_bf = 0;child->_bf = 0;}sub->_bf = 0;return sub;
}