本文主要是介绍【C++练级之路】【Lv.15】AVL树(双子旋转,领略绝对平衡之美),希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
文章目录
- 引言
- 一、AVL树的概念
- 二、AVL树的模拟实现
- 2.1 结点
- 2.2 成员变量
- 2.3 插入
- 2.4 旋转
- 2.4.1 左单旋
- 2.4.2 右单旋
- 2.4.3 左右旋
- 2.4.4 右左旋
- 三、AVL树的验证
- 四、AVL树的性能
- 4.1 优势
- 4.2 缺陷
- 4.3 适用场景
引言
之前讲解了二叉搜索树,最优情况下它具有非常好的搜索性能,但是在极端场景下,它可能退化为单支树,可以形象地称为歪脖子树~
这样的话,它搜索的时间复杂度会从O(log2N)退化为O(N2),完全丧失了其优良的搜索性能。那么AVL树就可以登场了,它就是为解决这类问题而生的!
一、AVL树的概念
两位俄罗斯的数学家G.M.Adelson-Velskii和E.M.Landis在1962年发明了AVL树,AVL树满足两条性质:
- 它的左右子树都是AVL树
- 任意结点的左右子树高度差的绝对值不超过1
这样通过控制子树高度差,让AVL树几乎完美接近于平衡,便不会出现单支树的情况,保证了优良的搜索性能,因此AVL树又称为高度平衡二叉搜索树。
二、AVL树的模拟实现
2.1 结点
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;//balance factorAVLTreeNode(const pair<K, V>& kv): _left(nullptr), _right(nullptr), _parent(nullptr), _kv(kv), _bf(0){}
};
细节:
- 使用三叉链,增加了指向parent的指针
- 使用KV模型,数据存储键值对pair
- 结点存储平衡因子,用来记录左右子树高度差
注:平衡因子计算高度差,是 右子树高度 - 左子树高度
2.2 成员变量
template<class K, class V>
class AVLTree
{
protected:typedef AVLTreeNode<K, V> Node;
public:
protected:Node* _root = nullptr;
};
2.3 插入
因为AVL树也是二叉搜索树,所以默认成员函数和遍历与之前写的没什么不同,这里重点讲解AVL树的插入。
bool Insert(const pair<K, V>& kv)
{if (_root == nullptr){_root = new Node(kv);return true;}Node* parent = nullptr;Node* cur = _root;while (cur){if (cur->_kv.first < kv.first){parent = cur;cur = cur->_right;}else if (cur->_kv.first > kv.first){parent = cur;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 (parent)//讨论平衡因子{if (cur == parent->_right){++parent->_bf;}else{--parent->_bf;}if (parent->_bf == 1 || parent->_bf == -1){parent = parent->_parent;cur = cur->_parent;}else if (parent->_bf == 0){break;}else if (parent->_bf == 2 || parent->_bf == -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){RotateLR(parent);}else if (parent->_bf == 2 && cur->_bf == -1){RotateRL(parent);}else{assert(false);}break;}else{assert(false);}}return true;
}
思路:
- 以二叉搜索树的方式正常插入
- 讨论平衡因子,以及调整结构
这里的重点在于如何讨论和调整平衡因子(bf)。
- 首先,插入cur结点,调整parent结点的bf,左减右加
- 讨论parent的bf
- bf为0
- bf为1或-1
- bf为2或-2
bf为0时:
分析:此时没有增加高度,而是补上缺口,整棵树是平衡的,直接break即可
bf为1或-1时:
分析:此时增加了局部子树的高度,不确定有没有影响整体的高度差,所以要继续向上调整
parent = parent->_parent;
cur = cur->_parent;
bf为2或-2时:
此时bf已经超出平衡限制区间,需要进行结构调整,我们称之为旋转。
2.4 旋转
旋转分为两大类:单旋和双旋。而单旋分为左单旋和右单旋,双旋分为左右旋和右左旋。
2.4.1 左单旋
场景:右部外侧插入
过程:
- parent接过subR的左子树subRL
- subR左边再链接parent
void RotateL(Node* parent)//左单旋
{Node* grandparent = parent->_parent;Node* subR = parent->_right;Node* subRL = subR->_left;parent->_right = subRL;if (subRL){subRL->_parent = parent;}subR->_left = parent;parent->_parent = subR;if (grandparent){if (grandparent->_right == parent){grandparent->_right = subR;}else{grandparent->_left = subR;}}else{_root = subR;}subR->_parent = grandparent;parent->_bf = subR->_bf = 0;
}
细节:
- 大体是三步链接,注意双向链接
- 注意判空(subRL,grandparent)
- 如果判空,注意_root的传递
- 最后调整平衡因子_bf
2.4.2 右单旋
场景:左部外侧插入
过程:
- parent接过subL的右子树subLR
- subL右边再链接parent
void RotateR(Node* parent)//右单旋
{Node* grandparent = parent->_parent;Node* subL = parent->_left;Node* subLR = subL->_right;parent->_left = subLR;if (subLR){subLR->_parent = parent;}subL->_right = parent;parent->_parent = subL;if (grandparent){if (grandparent->_right == parent){grandparent->_right = subL;}else{grandparent->_left = subL;}}else{_root = subL;}subL->_parent = grandparent;parent->_bf = subL->_bf = 0;
}
细节:同左单旋
2.4.3 左右旋
场景:左部内侧插入
过程:
- 先对subL进行左单旋
- 再对parent进行右单旋
void RotateLR(Node* parent)//左右旋
{Node* subL = parent->_left;Node* subLR = subL->_right;int bf = subLR->_bf;RotateL(subL);RotateR(parent);if (bf == 1){subL->_bf = -1;subLR->_bf = 0;parent->_bf = 0;}else if (bf == -1){subL->_bf = 0;subLR->_bf = 0;parent->_bf = 1;}else if (bf == 0){subL->_bf = 0;subLR->_bf = 0;parent->_bf = 0;}else{assert(false);}
}
细节:
- 这里旋转直接复用前面单旋的代码
- 主要的重点,在于平衡因子bf的讨论
- bf为1,在subLR的右侧插入
- bf为-1,在subLR的左侧插入
- bf为0,插入subLR(之前为空)
2.4.4 右左旋
场景:右部内侧插入
过程:
- 先对subR进行右单旋
- 再对parent进行左单旋
void RotateRL(Node* parent)//右左旋
{Node* subR = parent->_right;Node* subRL = subR->_left;int bf = subRL->_bf;RotateR(subR);RotateL(parent);if (bf == 1){parent->_bf = -1;subRL->_bf = 0;subR->_bf = 0;}else if (bf == -1){parent->_bf = 0;subRL->_bf = 0;subR->_bf = 1;}else if (bf == 0){parent->_bf = 0;subRL->_bf = 0;subR->_bf = 0;}else{assert(false);}
}
细节:同左右旋
综上所述,旋转的目的:保证平衡,同时降低树的高度。
三、AVL树的验证
我们主要验证左右子树高度是否平衡,即高度差是否小于等于1
bool IsBalance()
{return _IsBalance(_root);
}int Height(Node* root)
{if (root == nullptr){return 0;}int leftH = Height(root->_left);int rightH = Height(root->_right);return leftH > rightH ? leftH + 1 : rightH + 1;
}bool _IsBalance(Node* root)
{if (root == nullptr){return true;}int leftH = Height(root->_left);int rightH = Height(root->_right);if (rightH - leftH != root->_bf){cout << root->_kv.first << "节点平衡因子异常" << endl;return false;}return abs(rightH - leftH) <= 1&& _IsBalance(root->_left)&& _IsBalance(root->_right);
}
细节:
- 为了方便计算高度,写一个Height函数
- 在子函数递归中,计算高度差是否小于等于1
- 与此同时,还要检查平衡因子是否正常
四、AVL树的性能
4.1 优势
AVL树是一棵绝对平衡的二叉搜索树,其要求每个节点的左右子树高度差的绝对值都不超过1,这样可以保证查询时高效的时间复杂度,即 l o g 2 ( N ) log_2 (N) log2(N)。
4.2 缺陷
但是如果要对AVL树做一些结构修改的操作,性能非常低下,比如:插入时要维护其绝对平衡,旋转的次数比较多,更差的是在删除时,有可能一直要让旋转持续到根的位置。
4.3 适用场景
因此,如果需要一种查询高效且有序的数据结构,而且数据的个数为静态的(即不会改变),可以考虑AVL树,但一个结构经常修改,就不太适合。
这篇关于【C++练级之路】【Lv.15】AVL树(双子旋转,领略绝对平衡之美)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!