深圳网站开发培训价格,西安个人网站建设,企业微信官方网站,西联移动运营系统数据结构进阶——AVL树 0. 前言1. AVL树的概念2. AVL树节点#xff0c;和树的定义3. AVL树的插入4. AVL树的旋转5. AVL树的验证6. AVL树的删除#xff08;了解#xff09;7. AVL树实现完整代码8. AVL树的性能 0. 前言 学习本章#xff0c;需要大家先掌握搜索二叉树#xf… 数据结构进阶——AVL树 0. 前言1. AVL树的概念2. AVL树节点和树的定义3. AVL树的插入4. AVL树的旋转5. AVL树的验证6. AVL树的删除了解7. AVL树实现完整代码8. AVL树的性能 0. 前言 学习本章需要大家先掌握搜索二叉树了解键值对pair。
学习搜索二叉树点击此处https://blog.csdn.net/weixin_73870552/article/details/138686066?spm1001.2014.3001.5501 1. AVL树的概念 1. 搜索二叉树的弊端
搜索二叉树虽可以缩短查找的效率但如果数据有序或接近有序二叉搜索树将退化为单支树查找元素相当于在顺序表中搜索元素效率低下。因此两位俄罗斯的数学家G.M.Adelson-Velskii和E.M.Landis在1962年发明了一种解决上述问题的方法当向二叉搜索树中插入新结点后如果能保证每个结点的左右子树高度之差的绝对值不超过1(需要对树中的结点进行调整)就可以降低树的高度从而减少平均搜索长度。
2. AVL树的性质 左右子树都是AVL树左右子树高度之差简称平衡因子的绝对值不超过1空树是AVL树。
如果一棵二叉搜索树是高度平衡的它就是AVL树。如果它有n个结点其高度可保持在 O ( l o g 2 n ) O(log_2 n) O(log2n)搜索时间复杂度 O ( l o g 2 n ) O(log_2 n) O(log2n)。 2. AVL树节点和树的定义 1. 节点
templateclass K, class V
struct AVLTreeNode
{AVLTreeNodeK, V* _left;AVLTreeNodeK, V* _right;AVLTreeNodeK, V* _parent;pairK, V _kv;int _bf; // balance factor 平衡因子AVLTreeNode(const pairK, V kv): _left(nullptr), _right(nullptr), _parent(nullptr), _kv(kv), _bf(0){}
};该节点的定义是一个三叉链_left和_right分别指向左右子树_parent指向父节点节点中存储的有效数据为pairK, V类型的键值对_bf为平衡因子在此我们定义为右树高度减去左树高度用来控制左右子树的高度注意平衡因子只是其中一种控制平衡的手段并不是唯一的定义了一个模版构造函数以便后续使用。
2. 树
templateclass K, class V
class AVLTree
{typedef AVLTreeNodeK, V Node;
public:...private:Node* _root nullptr;size_t _size 0;
};_size记录树中一共有多少数据多少节点。 3. AVL树的插入 1. 思路
AVL树就是在搜索二叉树的基础上引入了平衡因子因此AVL树也可以看成是搜索二叉树。那么AVL树的插入过程可以分为两步 按照二叉搜索树的方式插入新节点调整节点的平衡因子。 调整平衡因子的过程又可以细分为两部分 平衡因子的更新节点的调整旋转 平衡因子的更新。
1. 模拟插入过程红色节点表示新插入节点 插入新节点后第一件事是更新该新节点的父亲的平衡因子 新增节点在左父亲bf--新增节点在右父亲bf。 更新完该新节点的父亲后还要判断是否需要往上更新新增节点可能会影响祖先但是一定不会影响兄弟 更新后父亲bf 0父亲所在的子树高度不变不用再继续往上更新了插入结束。 ps在插入节点前父亲bf 1 or -1子树一边高一边低新插入节点填补低的那边更新后父亲bf 1 or -1父亲所在的子树高度变了需要继续往上更新。ps在插入节点前父亲bf 0两边一样高插入新节点导致高度变化更新后父亲bf 2 or -2父亲所在的子树不平衡需要旋转调整。
templateclass K, class V
class AVLTree
{typedef AVLTreeNodeK, V Node;
public:bool Insert(const pairK, V kv){// 插入类比搜索二叉树插入if (_root nullptr){_root new Node(kv);_size;return true;}// 通过parent向上找父节点Node* parent nullptr;Node* cur _root;while (cur){if (kv.first cur-_kv.first){parent cur;cur cur-_right;}else if (kv.first cur-_kv.first){parent cur;cur cur-_left;}else{return false;}}cur new Node(kv);if (kv.first parent-_kv.first){parent-_right cur;cur-_parent parent;}else{parent-_left cur;cur-_parent parent;}_size;// 调整AVL树的核心部分while (parent){// 平衡因子的更新if (cur parent-_left){// 插入在左节点_bf--parent-_bf--;}else{// 插入在右节点_bfparent-_bf;}// 判断是否要继续向上更新和是否旋转调整if (parent-_bf 0){// 更新后 _bf 0说明子树高度不变不需要往上更新break;}else if (parent-_bf 1 || parent-_bf -1){// 更新后子树高度改变需要往上更新cur parent;parent parent-_parent;}else if (parent-_bf 2 || parent-_bf -2){// 旋转调整...}else{// 平衡因子绝对值大于2直接报错assert(false);}}return true;}...private:Node* _root nullptr;size_t _size 0;
};4. AVL树的旋转
如果在一棵原本是平衡的AVL树中插入一个新节点可能造成不平衡此时必须调整树的结构使之平衡化。根据节点插入位置的不同AVL树的旋转分为四种 1. 新节点插入较高左子树的左侧—右右左单旋 先考虑一种最简单的场景场景1 直接将8节点链接到9节点的左边即可。 再看一种更复杂的场景场景2 需要将13节点链接到9节点的右子树将9节点链接到15节点的左子树。 还有更加复杂的情况但是我们可以对所有的情况进行一个归类画出抽象图 abc 都是高度为h的AVL平衡树只需要将b框中的节点subRL链接到30节点parent的右子树将60节点的左子树链接到30节点的右边再将30节点parent连接到60节点subR的左子树即可。别忘了是三叉链要同步更新父节点旋转完后别忘了更新平衡因子左单旋后parent和subR节点的_bf都为0其余节点的平衡因子均不会受到印象。h 0时就对应场景1的情况h 1时就对应场景2的情况。 代码实现 注意在更新subRL节点的父节点时需要先判断subRL是否为空h0的情况如果为空就不要访问subRL了还需要记录parent的父节点方便旋转后将subR链接给parent-_parent和整棵树链接起来当parent就是根节点时需要特殊处理要更新根节点为subR。
templateclass K, class V
class AVLTree
{typedef AVLTreeNodeK, V Node;
public:// 左单旋void RotateL(Node* parent){Node* subR parent-_right;Node* subRL subR-_left;// 更新左右节点parent-_right subRL;subR-_left parent;// 提前记录parent的parentNode* parentParent parent-_parent;// 更新_parentparent-_parent subR;if (subRL) // 判断为不为空subRL是唯一一个可能为空的节点{subRL-_parent parent;}// 处理根if (_root parent){_root subR;subR-_parent nullptr;}else if (parentParent-_left parent){parentParent-_left subR;subR-_parent parentParent;}else{parentParent-_right subR;subR-_parent parentParent;}// 更新平衡因子parent-_bf subR-_bf 0;}...private:Node* _root nullptr;size_t _size 0;
};2. 新节点插入较高左子树的左侧—左左右单旋
这里不带着大家一步一步分析了直接上抽象图 abc 均为高度为h的AVL平衡树只需要将subLR给parent的左再将parent给subL的右即可随后更新平衡因子subL和parent的_bf都更新为0。 类比左单旋直接上代码
templateclass K, class V
class AVLTree
{typedef AVLTreeNodeK, V Node;
public:// 右单旋void RotateR(Node* parent){Node* subL parent-_left;Node* subLR subL-_right;// 更新左右节点subL-_right parent;parent-_left subLR;Node* parentParent parent-_parent;// 更新_parentparent-_parent subL;if (subLR){subLR-_parent parent;}if (_root parent){_root subL;subL-_parent nullptr;}else if (parentParent-_left parent){parentParent-_left subL;subL-_parent parentParent;}else{parentParent-_right subL;subL-_parent parentParent;}parent-_bf subL-_bf 0;}...private:Node* _root nullptr;size_t _size 0;
};3. 新节点插入较高左子树的右侧—左右先左单旋再右单旋左右双旋 注意该抽象图只是左右双旋中的一种情况为在60的左子树新增。还有两种情况没有画出来分别是160作为新增节点的情况2在60的右子树新增的情况。不同的情况旋转后得到的平衡因子有差别。 h 0 的情况60就是新插入节点。此时bc子树不存在注意是不存在连空都不是。此时parentsubLsubLR的平衡因子均为0。 h 1的情况该情况又分两种 在60的左子树新增注意此时subL和subLR的平衡因子均为0只有parent的平衡因子为1和h 0的情况不一样。 在60的右子树新增这种情况最后的到的子树和上图只有一处区别就是b变成了NULLc变成了50故此时subL的平衡因子为-1parentsubLR的平衡因子均为0。和在60左子树新增的情况平衡因子又不一样。 代码实现 我们可以根据新节点插入后subLR的平衡因子来确定到底是上述哪种情况。1subLR-_bf 0说明subLR就是新增节点2subLR-_bf -1说明是在subLR的左子树新增3subLR-_bf 1说明是在subLR的右子树新增。
templateclass K, class V
class AVLTree
{typedef AVLTreeNodeK, V Node;
public:// 左右双旋void RotateLR(Node* parent){Node* subL parent-_left;Node* subLR subL-_right;int bf subLR-_bf; // 提前记录subLR的平衡因子避免单旋操作后值丢失// 先左旋再右旋RotateL(parent-_left);RotateR(parent);// 更新平衡因子if (bf 0){// subLR自己就是新增节点subL-_bf subLR-_bf parent-_bf 0;}else if (bf -1){// subLR的左子树新增parent-_bf 1;subL-_bf subLR-_bf 0;}else if (bf 1){// subLR的右子树新增parent-_bf subLR-_bf 0;subL-_bf -1;}else{assert(false); // 检查点}}...private:Node* _root nullptr;size_t _size 0;
};4. 新节点插入较高右子树的左侧—右左先右单旋再左单旋右左双旋
注意该抽象图只是右左双旋中的一种情况为在60的右子树新增。还有两种情况没有表示出来分别是160就是新增节点2在60的左子树新增。 类比左右双旋上代码 还是要注意可以通过subRL的平衡因子区分上述三种情况。1subRL-_bf 0说明subRL就是新增节点2 subRL-_bf 1说明是在subRL的右子树新增parent-_bf -13subRL-_bf -1说明是在subRL的左子树新增subR-_bf 1。
templateclass K, class V
class AVLTree
{typedef AVLTreeNodeK, V Node;
public:// 右左双旋void RotateRL(Node* parent){Node* subR parent-_right;Node* subRL subR-_left;int bf subRL-_bf; // 提前记录subRL的平衡因子避免单旋操作后值丢失// 先右旋再左旋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;}else{assert(false); // 检查点}}...private:Node* _root nullptr;size_t _size 0;
};5. 完善插入
旋转完成后是不需要继续向上更新平衡因子的因为1旋转让这棵树平衡了2旋转降低了这棵子树的高度恢复到更插入前一样的高度所以对上一层没有影响不用更新。
templateclass K, class V
class AVLTree
{typedef AVLTreeNodeK, V Node;
public:bool Insert(const pairK, V kv){// 插入类比搜索二叉树插入if (_root nullptr){_root new Node(kv);_size;return true;}Node* parent nullptr;Node* cur _root;while (cur){if (kv.first cur-_kv.first){parent cur;cur cur-_right;}else if (kv.first cur-_kv.first){parent cur;cur cur-_left;}else{return false;}}cur new Node(kv);if (kv.first parent-_kv.first){parent-_right cur;cur-_parent parent;}else{parent-_left cur;cur-_parent parent;}_size;// 调整AVL树的核心部分while (parent){// 平衡因子的更新if (cur parent-_left){// 插入在左节点_bf--parent-_bf--;}else{// 插入在右节点_bfparent-_bf;}// 判断是否要继续向上更新和是否旋转调整if (parent-_bf 0){// 更新后 _bf 0说明子树高度不变不需要往上更新break;}else if (parent-_bf 1 || parent-_bf -1){// 更新后子树高度改变需要往上更新cur parent;parent parent-_parent;}else if (parent-_bf 2 || parent-_bf -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);}else{assert(false);}// 完成旋转后不需要再往上更新平衡因子了直接break// 1、旋转让这棵树平衡了// 2、旋转降低了这棵子树的高度恢复到更插入前一样的高度所以对上一层没有影响不用更新break;}else{// 平衡因子绝对值大于2直接报错assert(false);}}return true;}...private:Node* _root nullptr;size_t _size 0;
};5. AVL树的验证 1. 验证其为二叉搜索树
如果中序遍历可得到一个有序的序列就说明为二叉搜索树。
2. 验证其为平衡树
每个节点子树高度差的绝对值不超过1节点的平衡因子是否计算正确。
3. 相关函数实现
templateclass K, class V
class AVLTree
{typedef AVLTreeNodeK, V Node;
public:void _InOrder(Node* root){if (root nullptr)return;_InOrder(root-_left);cout root-_kv.first ;_InOrder(root-_right);}void InOrder(){_InOrder(_root);cout endl;}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;}int Height(){return _Height(_root);}bool IsBalance(){return _IsBalance(_root);}bool _IsBalance(Node* root){if (root nullptr)return true;int leftHeight _Height(root-_left);int rightHeight _Height(root-_right);if (rightHeight - leftHeight ! root-_bf){cout root-_kv.first 平衡因子异常 endl;return false;}return abs(rightHeight - leftHeight) 2 _IsBalance(root-_left) _IsBalance(root-_right);}size_t Size() const {return _size;}...private:Node* _root nullptr;size_t _size 0;
};4. 测试代码
void Test()
{const int N 100;srand(time(0));vectorint v;for (int i 0; i N; i){v.push_back(rand());}AVLTreeint, int tree;for (auto e : v){tree.Insert(make_pair(e, e));}tree.InOrder(); // 检查是否有序cout tree.IsBalance() endl; // 检查是否平衡cout tree.Height() endl; // 看看高度cout tree.Size() endl; // 看看数据量
}6. AVL树的删除了解 1. 思路
因为AVL树也是二叉搜索树可按照二叉搜索树的方式将节点删除然后再更新平衡因子。只不过平衡因子更新最差情况下要一直调整到根节点的位置。
2. 例 假如我们要删除根节点可以先在右子树找到替换节点6进行替换删除然后更新平衡因子得到的树如下图所示 更新7这个节点的平衡因子更新为2不用继续向上更新了对7节点进行左单旋调整即可。 删除的代码不再写了面试时也几乎不会考察最多考察思路。 7. AVL树实现完整代码 #pragma once#includeiostream
#includeassert.husing namespace std;templateclass K, class V
struct AVLTreeNode
{AVLTreeNodeK, V* _left;AVLTreeNodeK, V* _right;AVLTreeNodeK, V* _parent;pairK, V _kv;int _bf; // balance factor 平衡因子AVLTreeNode(const pairK, V kv): _left(nullptr), _right(nullptr), _parent(nullptr), _kv(kv), _bf(0){}
};templateclass K, class V
class AVLTree
{typedef AVLTreeNodeK, V Node;
public:bool Insert(const pairK, V kv){// 插入类比搜索二叉树插入if (_root nullptr){_root new Node(kv);_size;return true;}Node* parent nullptr;Node* cur _root;while (cur){if (kv.first cur-_kv.first){parent cur;cur cur-_right;}else if (kv.first cur-_kv.first){parent cur;cur cur-_left;}else{return false;}}cur new Node(kv);if (kv.first parent-_kv.first){parent-_right cur;cur-_parent parent;}else{parent-_left cur;cur-_parent parent;}_size;// 调整AVL树的核心部分while (parent){// 平衡因子的更新if (cur parent-_left){// 插入在左节点_bf--parent-_bf--;}else{// 插入在右节点_bfparent-_bf;}// 判断是否要继续向上更新和是否旋转调整if (parent-_bf 0){// 更新后 _bf 0说明子树高度不变不需要往上更新break;}else if (parent-_bf 1 || parent-_bf -1){// 更新后子树高度改变需要往上更新cur parent;parent parent-_parent;}else if (parent-_bf 2 || parent-_bf -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);}else{assert(false);}// 完成旋转后不需要再往上更新平衡因子了直接break// 1、旋转让这棵树平衡了// 2、旋转降低了这棵子树的高度恢复到更插入前一样的高度所以对上一层没有影响不用更新break;}else{// 平衡因子绝对值大于2直接报错assert(false);}}return true;}// 左单旋void RotateL(Node* parent){Node* subR parent-_right;Node* subRL subR-_left;// 更新左右节点parent-_right subRL;subR-_left parent;// 提前记录parent的parentNode* parentParent parent-_parent;// 更新_parentparent-_parent subR;if (subRL) // 判断为不为空subRL是唯一一个可能为空的节点{subRL-_parent parent;}// 处理根if (_root parent){_root subR;subR-_parent nullptr;}else if (parentParent-_left parent){parentParent-_left subR;subR-_parent parentParent;}else{parentParent-_right subR;subR-_parent parentParent;}// 更新平衡因子parent-_bf subR-_bf 0;}// 右单旋void RotateR(Node* parent){Node* subL parent-_left;Node* subLR subL-_right;// 更新左右节点subL-_right parent;parent-_left subLR;Node* parentParent parent-_parent;// 更新_parentparent-_parent subL;if (subLR){subLR-_parent parent;}if (_root parent){_root subL;subL-_parent nullptr;}else if (parentParent-_left parent){parentParent-_left subL;subL-_parent parentParent;}else{parentParent-_right subL;subL-_parent parentParent;}parent-_bf subL-_bf 0;}// 右左双旋void RotateRL(Node* parent){Node* subR parent-_right;Node* subRL subR-_left;int bf subRL-_bf; // 提前记录subRL的平衡因子避免单旋操作后值丢失// 先右旋再左旋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;}else{assert(false); // 检查点}}// 左右双旋void RotateLR(Node* parent){Node* subL parent-_left;Node* subLR subL-_right;int bf subLR-_bf; // 提前记录subLR的平衡因子避免单旋操作后值丢失// 先左旋再右旋RotateL(parent-_left);RotateR(parent);// 更新平衡因子if (bf 0){// subLR自己就是新增节点subL-_bf subLR-_bf parent-_bf 0;}else if (bf -1){// subLR的左子树新增parent-_bf 1;subL-_bf subLR-_bf 0;}else if (bf 1){// subLR的右子树新增parent-_bf subLR-_bf 0;subL-_bf -1;}else{assert(false); // 检查点}}Node* Find(const K key){Node* cur _root;while (cur){if (cur-_kv.first key){cur cur-_right;}else if (cur-_kv.first key){cur cur-_left;}else{return cur;}}return nullptr;}void _InOrder(Node* root){if (root nullptr)return;_InOrder(root-_left);cout root-_kv.first ;_InOrder(root-_right);}void InOrder(){_InOrder(_root);cout endl;}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;}int Height(){return _Height(_root);}bool IsBalance(){return _IsBalance(_root);}bool _IsBalance(Node* root){if (root nullptr)return true;int leftHeight _Height(root-_left);int rightHeight _Height(root-_right);if (rightHeight - leftHeight ! root-_bf){cout root-_kv.first 平衡因子异常 endl;return false;}return abs(rightHeight - leftHeight) 2 _IsBalance(root-_left) _IsBalance(root-_right);}size_t Size() const {return _size;}private:Node* _root nullptr;size_t _size 0;
};8. AVL树的性能 AVL树是一棵绝对平衡的二叉搜索树其要求每个节点的左右子树高度差的绝对值都不超过1这样可以保证查询时高效的时间复杂度即 l o g 2 ( N ) log_2 (N) log2(N)。但是如果要对AVL树做一些结构修改的操作性能非常低下比如
插入时要维护其绝对平衡旋转的次数比较多更差的是在删除时有可能一直要让旋转持续到根的位置。
因此如果需要一种查询高效且有序的数据结构而且数据的个数为静态的(即不会改变)可以考虑AVL树。但是一个经常修改的结构就不太适合用AVL树。
