网站模板 可做采集站没经验可以做电商运营吗
目录
前言
一、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;
}四、AVL树删除
因为AVL树也是二叉搜索树，可按照二叉搜索树的方式将节点删除，然后再更新平衡因子，只不 错与删除不同的时，删除节点后的平衡因子更新，最差情况下一直要调整到根节点的位置。
具体实现可参考《算法导论》或《数据结构-用面向对象方法与C++描述》殷人昆版。
附录：AVL树实现参考代码
AVLTree · 梁羽赫/cpp_advanced - 码云 - 开源中国 (gitee.com)https://gitee.com/yuhe-liang/cpp_advanced/tree/master/AVLTree