河北省住房城乡建设厅网站,竞价销售是什么意思,建设网站开发的语言有哪些,做网站需要钱吗#x1f308;感谢阅读East-sunrise学习分享——[进阶数据结构]AVL树 博主水平有限#xff0c;如有差错#xff0c;欢迎斧正#x1f64f;感谢有你 码字不易#xff0c;若有收获#xff0c;期待你的点赞关注#x1f499;我们一起进步#x1f680; #x1f308;我们上一篇… 感谢阅读East-sunrise学习分享——[进阶数据结构]AVL树 博主水平有限如有差错欢迎斧正感谢有你 码字不易若有收获期待你的点赞关注我们一起进步 我们上一篇博客分享了搜索二叉树在文中也铺垫了搜索二叉树的一些结构局限性 而今天分享的一种特殊的搜索二叉树——AVL树便是一种结构优异的搜索二叉树那么我们就开始吧 目录一、AVL树的概念二、AVL树结点的定义三、AVL树的插入四、AVL树的旋转1.左单旋2.右单旋3.左右双旋4.右左双旋五、最终代码展示一、AVL树的概念 二叉搜索树虽可以缩短查找的效率但如果数据有序或接近有序二叉搜索树将退化为单支树查找元素相当于在顺序表中搜索元素效率低下。 因此两位俄罗斯的数学家G.M.Adelson-Velskii和E.M.Landis在1962年发明了一种解决上述问题的方法当向二叉搜索树中插入新结点后如果能保证每个结点的左右子树高度之差的绝对值不超过1(需要对树中的结点进行调整)即可降低树的高度从而减少平均搜索长度。 一棵AVL树可以是一棵空树或者是一棵具有以下性质的二叉搜索树
它的左右子树都是AVL树左右子树高度之差(简称平衡因子)的绝对值不超过1 这里的平衡因子是指右子树高度-左子树高度⭕ 注意平衡因子只是博主分享的这种实现方法的一种自定义名字不是必须的除了使用平衡因子之外还有许多实现AVL树的方法 如果一棵二叉搜索树是高度平衡的它就是AVL树。如果它有n个结点其高度可保持在O(logN)搜索时间复杂度O(logN) 二、AVL树结点的定义
AVL树的结点我们定义了一个三叉链结构便于后续的操作并且在每个结点中都引入了平衡因子
templateclass K, class V
struct AVLTreeNode
{//存储键值对的pair类pairK, V _kv;//含有父节点的三叉链AVLTreeNodeK, V* _left;AVLTreeNodeK, V* _right;AVLTreeNodeK, V* _parent;//平衡因子int _bf;AVLTreeNode(const pairK, V kv):_kv(kv),_left(nullptr),_right(nullptr),_parent(nullptr),_bf(0){}
};//AVL树
templateclass K,class V
struct AVLTree
{typedef AVLTreeNodeK, V Node;
public://插入bool Insert(const pairK, V kv){}private:Node* _root nullptr;
};三、AVL树的插入
AVL树就是在二叉搜索树的基础上引入了平衡因子因此AVL树也可以看成是二叉搜索树。那么AVL树的插入过程可以分为两步
按照二叉搜索树的方式插入新节点调整平衡因子若不平衡则需要旋转调整AVL树
⭕⭕当有新节点插入后我们就需要判断此时的树是否仍然平衡仍然是AVL树了 插入后平衡因子的变化类型
我们知道假如平衡则每个结点的平衡因子只有三种可能-101
而插入新结点肯定会使得高度的变化假如插入新节点后仍平衡则父节点的平衡因子的变化有
0 -- 10 -- -11 -- 0-1 -- 0
知道了平衡因子的变化情况后又抛出了一个问题
插入新节点影响父节点的平衡因子那是否会影响祖先结点的平衡因子
⭕最简单的情况就是插入了新节点只影响了其父结点只需更新父节点的平衡因子 插入新节点后改变了其父结点(8)的子树高度所以需要更新父节点的平衡因子但是插入之后并不会改变其祖先结点的子树高度所以不需要往上更新平衡因子
因此我们可以总结出是否持续更新平衡因子取决于其结点的子树高度是否变化
再结合一开始的平衡因子变化情况我们可以得出插入新结点后
parent - _bf 0 —— 说明之前parent - _bf 是 1 或者 -1一边高一边低新节点刚好插入填上矮的那边parent所在子树高度不变 —— 祖先的子树高度也不会变 —— 只需更新parent的平衡因子不需要继续往上更新parent - _bf 1 或 -1 —— 说明之前parent - _bf 0两边一样高新结点插入使得parent所在子树的高度变得一高一低 —— 祖先的子树高度也产生变化 —— 更新parent的平衡因子之外还需要继续往上更新祖先结点的平衡因子parent - _bf 2 或 -2 —— 说明本就一高一低的子树插入新节点后造成更加不平衡此时违反了AVL树的平衡规则 —— 就地处理 ——旋转调整
⭕最坏的情况就是插入了新节点直接影响到了root根结点所以需要持续更新到root根结点的平衡因子 更新结点的平衡因子时假若我们需要持续向上更新平衡因子一开始我们更新的是最下面的parent结点更新后则可向上迭代直到parent为空就停止
✏️代码实现
bool Insert(const pairK, 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;}elsereturn false;}//插入cur new Node(kv);if (parent-_kv.first kv.first){parent-_right cur;cur-_parent parent;}else{parent-_left cur;cur-_parent parent;}//调整平衡因子while (parent){if (cur parent-_right)parent-_bf;elseparent-_bf--;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){//旋转调整}elseassert(false);}return true;}四、AVL树的旋转
如果在一棵原本是平衡的AVL树中插入一个新节点可能造成不平衡此时必须调整树的结构使之平衡化。
因此旋转的要求即是
旋转后仍保持二叉搜索树的结构旋转后整棵树保持平衡平衡因子不超过1
而根据节点插入位置的不同AVL树的旋转分为四种
1.左单旋
1️⃣新节点插入较高右子树的右侧 —— 左单旋 此处我们给出左单旋过程的抽象图
我们发现当parent的平衡因子是2cur是1时便进行左单旋 —— 将cur的左子树给parent的右子树然后将parent及其子树一整棵树变为cur的左子树
左单旋真就如此吗不信我们可以画出具象图看看
✨当 h 0 ✨当 h 1 ✨当 h 2 有的兄弟看到这就有疑问为什么h 2时子树c一定就得是z的模样呢? 因为假如子树c是x或y的模样插入新节点时并不会引发节点30的旋转那样最多只是变成以节点60为parent的树进行左单旋那就和h 1是同样的情况了因此以上的情况其实是笼盖了所有需要进行左单旋的子情况了然后以上的情况可能是某棵树的子树
最后我们发现所有需要进行左单旋的情况最后的操作都是如一开始所说
✏️代码实现对照图更清晰易懂
void RotateL(Node* parent)
{Node* subR parent-_right;//parent的右孩子Node* subRL subR-_left;//parent的右孩子的左孩子//旋转后subR的左孩子作为parent的右孩子parent-_right subRL;//subR的左孩子有可能为空也有可能存在//如果存在则需要更新父子关系if (subRL)subRL-_parent parent;//subR的左孩子变为以parent为根的子树结构//同时更新父子关系subR-_left parent;parent-_parent subR;//parent也可能只是一棵子树的根其pparent可能为空也可能存在Node* pparent parent-_parent;if (pparent){//如果pparent不为空则说明parent是一棵子树//可能是存在于其父节点的左子树or右子树if (parent pparent-_left)pparent-_left subR;elsepparent-_right subR;subR-_parent pparent;}else{//若pparent为空则说明parent是整棵树的根节点//旋转后根节点已经换人了需要更新_root subR;subR-_parent nullptr;}//最后更新平衡因子parent-_bf subR-_bf 0;
}看完以上的代码实现发现旋转的代码实现起来也有许多细节需要注意啊… 因为旋转后也要保持一棵正常的树的结构因此那些父子链接关系也需要正确更新 2.右单旋
2️⃣新节点插入较高左子树的左侧 - 右单旋 ✏️实现及情况考虑可参考左单旋
void RotateR(Node* parent)
{Node* subL parent-_left;Node* subLR subL-_right;parent-_left subLR;if (subLR)subLR-_parent parent;Node* pparent parent-_parent;subL-_right parent;parent-_parent subL;if (pparent){if (parent pparent-_left)pparent-_left subL;elsepparent-_right subL;subL-_parent pparent;}else{_root subL;subL-_parent nullptr;}subL-_bf parent-_bf 0;
}3.左右双旋
3️⃣新节点插入较高左子树的右侧 - 先左单旋再右单旋 左右双旋我们可以复用上面的左单旋和右单旋的代码但是需要注意的是左右双旋完各个节点的平衡因子有不同的情况正是因为左右双旋会因为新节点插入的位置不同而影响不同的旋转结果因此我们总结出了以下三种情况 h 0 —— 节点60即是新插入节点 新节点插入在b 新节点插入在c
综上所述当我们在实现左右双旋时的最后可根据插入新节点后节点60的平衡因子大小来确定不同的情况
void RotateLR(Node* parent)
{Node* subL parent-_left;Node* subLR subL-_right;int bf subLR-_bf;RotateL(parent-_left);RotateR(parent);//更新平衡因子if (bf 1) //新增在sublr右子树{parent-_bf 0;subL-_bf -1;subLR-_bf 0;}else if (bf -1) //新增在sublr左子树{subL-_bf 0;parent-_bf 1;subLR-_bf 0;}else //本身就是新增{parent-_bf 0;subL-_bf 0;subLR-_bf 0;}
}4.右左双旋
4️⃣新节点插入较高右子树的左侧——先右单旋再左单旋 ✏️实现及情况考虑可参考左右双旋
void RotateRL(Node* parent)
{Node* subR parent-_right;Node* subRL subR-_left;int bf subRL-_bf;RotateR(parent-_right);RotateL(parent);if (bf 1){subR-_bf 0;parent-_bf -1;subRL-_bf 0;}else if (bf -1){parent-_bf 0;subR-_bf 1;subRL-_bf 0;}else if(bf 0){parent-_bf 0;subR-_bf 0;subRL-_bf 0;}
}五、最终代码展示
templateclass K, class V
struct AVLTreeNode
{pairK, V _kv;AVLTreeNodeK, V* _left;AVLTreeNodeK, V* _right;AVLTreeNodeK, V* _parent;int _bf;AVLTreeNode(const pairK, V kv):_kv(kv),_left(nullptr),_right(nullptr),_parent(nullptr),_bf(0){}
};templateclass K,class V
struct AVLTree
{typedef AVLTreeNodeK, V Node;
public:AVLTree():_root(nullptr){}bool Insert(const pairK, 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;}elsereturn false;}//插入cur new Node(kv);if (parent-_kv.first kv.first){parent-_right cur;cur-_parent parent;}else{parent-_left cur;cur-_parent parent;}//调整平衡因子while (parent){if (cur parent-_right)parent-_bf;elseparent-_bf--;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)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);elseassert(false);break;}elseassert(false);}return true;}void RotateL(Node* parent){Node* subR parent-_right;Node* subRL subR-_left;parent-_right subRL;if (subRL)subRL-_parent parent;Node* pparent parent-_parent;subR-_left parent;parent-_parent subR;if (pparent){if (parent pparent-_left)pparent-_left subR;elsepparent-_right subR;subR-_parent pparent;}else{_root subR;subR-_parent nullptr;}parent-_bf subR-_bf 0;}void RotateR(Node* parent){Node* subL parent-_left;Node* subLR subL-_right;parent-_left subLR;if (subLR)subLR-_parent parent;Node* pparent parent-_parent;subL-_right parent;parent-_parent subL;if (pparent){if (parent pparent-_left)pparent-_left subL;elsepparent-_right subL;subL-_parent pparent;}else{_root subL;subL-_parent nullptr;}subL-_bf parent-_bf 0;}void RotateLR(Node* parent){Node* subL parent-_left;Node* subLR subL-_right;int bf subLR-_bf;RotateL(parent-_left);RotateR(parent);if (bf 1) //新增在sublr右子树{parent-_bf 0;subL-_bf -1;subLR-_bf 0;}else if (bf -1) //新增在sublr左子树{subL-_bf 0;parent-_bf 1;subLR-_bf 0;}else if (bf 0) //本身就是新增{parent-_bf 0;subL-_bf 0;subLR-_bf 0;}else{assert(false);}}void RotateRL(Node* parent){Node* subR parent-_right;Node* subRL subR-_left;int bf subRL-_bf;RotateR(parent-_right);RotateL(parent);if (bf 1){subR-_bf 0;parent-_bf -1;subRL-_bf 0;}else if (bf -1){parent-_bf 0;subR-_bf 1;subRL-_bf 0;}else if(bf 0){parent-_bf 0;subR-_bf 0;subRL-_bf 0;}else{assert(false);}}void Inorder(){_Inorder(_root);}void _Inorder(Node* root){if (root nullptr)return;_Inorder(root-_left);cout root-_kv.first : root-_kv.second endl;_Inorder(root-_right);}int Height(Node* root){if (root nullptr)return 0;int hl Height(root-_left);int hr Height(root-_right);return hl hr ? hl 1 : hr 1;}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 平衡因子异常 endl;return false;}return abs(rightHeight - leftHeight) 2 IsBalance(root-_left) IsBalance(root-_right);}private:Node* _root nullptr;
};写在最后 我们今天的学习分享之旅就到此结束了 感谢能耐心地阅读到此 码字不易感谢三连 关注博主我们一起学习、一起进步
