万网做网站吗,做网站建设怎么赚钱,html5旅游网页设计成品,建立一个网站的费用#x1f680;个人主页#xff1a;小羊 #x1f680;所属专栏#xff1a;C 很荣幸您能阅读我的文章#xff0c;诚请评论指点#xff0c;欢迎欢迎 ~ 目录 前言一、AVL树二、AVL树的实现2.1 平衡因子2.2 旋转处理2.2.1 左单旋#xff1a;插入新节点后单纯的右边高2.2.2 … 个人主页小羊 所属专栏C 很荣幸您能阅读我的文章诚请评论指点欢迎欢迎 ~ 目录 前言一、AVL树二、AVL树的实现2.1 平衡因子2.2 旋转处理2.2.1 左单旋插入新节点后单纯的右边高2.2.2 右单旋插入新节点后单纯的左边高2.2.3 左右旋插入新节点后不是单纯的左边高2.2.4 右左旋插入新节点后不是单纯的右边高 2.3 验证AVL树的平衡 三、完整代码 前言 本文仅适合了解二叉搜索树但不了解AVL树底层原理的同学阅读哦。 本篇文章不会带你从头到尾实现AVL树但会带你深入理解AVL树是怎么实现平衡的怎么通过旋转变换实现保持平衡以及实现平衡过程中的细节应该怎么处理等。 一、AVL树
前面的文章中我们分析过二叉搜索树的性能得到的结果是理想情况下二叉搜索树的时间复杂度为O(LogN)但在极端情况下即树蜕化为单边树时这些操作的时间复杂度会退化为O(n)即使情况不那么极端效率也不是特别高。
为了防止二叉搜索树出现一边偏高的情况就需要想办法让二叉搜索树尽量保持平衡所以两位苏联数学家或称为俄罗斯数学家G.M. Adelson-Velsky和E.M. Landis就发明了AVL树其任何节点的两个子树的高度最大差别为1。
AVL树是具有一下性质的二叉搜索树 其左右子树都是AVL树左右子树高度差不超过1 二、AVL树的实现 本篇文章将沿用之前文章中Key-Value模型的代码不再从底层开始实现主要介绍在插入新节点后如何保持二叉搜索树的平衡问题。 2.1 平衡因子
如何保证AVL树的左右子树高度差不超过1在AVL树的每个节点中存一个平衡因子本文我们定义平衡因子 此节点右子树的高度 - 左子树的高度。
插入在左子树平衡因子 - -插入在右子树平衡因子
更新祖先节点的平衡因子时我们首先需要找到祖先节点因此每个节点中还需要增加一个指向父节点的指针。 按照我们的需求其AVL树的节点可以定义为
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){}
}是否继续往上更新祖先节点的平衡因子要看parent所在子树的高度是否发生变化。 插入新节点后其父节点的平衡因子有以下几种情况
parent的平衡因子 0 parent的平衡因子更新前是 -1 / 1新节点插入在矮的那边高度不变不再往上更新parent的平衡因子 1 / -1 parent的平衡因子更新前是0parent所在子树高度都变化了需要往上更新parent的平衡因子 2 / -2 parent的平衡因子更新前是 -1 / 1插入新节点后树不再平衡需要旋转处理
pcur new Node(kv);
if (parent-_kv.first kv.first)//判断新节点应该插入左还是右
{parent-_left pcur;
}
else
{parent-_right pcur;
}
pcur-_parent parent;//与父节点链接关系while (parent)//有可能更新到根节点去
{parent-_bf parent-_left pcur ? parent-_bf - 1 : parent-_bf 1;if (parent-_bf 0)//插入前后高度不变{break;}else if (parent-_bf 1 || parent-_bf -1){//高度变了继续往上更新pcur parent;parent parent-_parent;}else if (parent-_bf 2 || parent-_bf -2){//插入节点后二叉树不平衡了需要旋转处理}else{assert(false);//检测AVL树是否异常}
}2.2 旋转处理
当二叉搜索树出现不平衡的情况时需要旋转处理对应插入后二叉搜索树的各种情况主要有四种旋转的方式来保持平衡。
其中 h代表子树的高度可以是0、1、2…我们用能代表所有情况的四种类型的抽象图来研究旋转方式单纯研究某几种情况没有意义 原则 保持搜索树的性质降低高度控制平衡 2.2.1 左单旋插入新节点后单纯的右边高 旋转处理过程中我们主要关注三个节点以上图为例10标记为parent、30标记为subR、b标记为subLR。 在旋转过程中有以下几种情况需要考虑
subR的左孩子可能存在也可能不存在parent可能是根节点也可能是子树。如果是根节点旋转完成后要更新根节点如果是子树可能是某个节点的左子树也可能是右子树
//左单旋
void RotateL(Node* parent)
{Node* subR parent-_right;Node* subRL subR-_left;//subRL是有可能为空的parent-_right subRL;subR-_left parent;Node* parentparent parent-_parent;parent-_parent subR;if (parentparent nullptr)//subR有可能变成根{_root subR;}else{if (parentparent-_left parent){parentparent-_left subR;}else{parentparent-_right subR;}}subR-_parent parentparent;if (subRL){subRL-_parent parent;}parent-_bf subR-_bf 0;//更新平衡因子
}旋转处理过程中主要是处理各节点的父节点指针的指向和平衡因子的更新。 2.2.2 右单旋插入新节点后单纯的左边高 其处理方式和左单旋相似可参考左单旋。
//右单旋
void RotateR(Node* parent)
{Node* subL parent-_left;Node* subLR subL-_right;parent-_left subLR;subL-_right parent;Node* parentparent parent-_parent;parent-_parent subL;if (parentparent nullptr){_root subL;}else{if (parentparent-_left parent){parentparent-_left subL;}else{parentparent-_right subL;}}subL-_parent parentparent;if (subLR){subLR-_parent parent;}subL-_bf parent-_bf 0;
}2.2.3 左右旋插入新节点后不是单纯的左边高 这种情况只用左旋或右旋只会原地打转不能降低平衡。 我们需要先对subL进行左单旋再对parent进行右单旋最后更新平衡因子。 双旋后平衡因子的更新要根据插入新节点后subLR的平衡因子来分情况讨论双旋最终结果是把subLR推到最上面让其平衡因子为0 //左右旋
void RotateLR(Node* parent)
{Node* subL parent-_left;Node* subLR subL-_right;int bf subLR-_bf;RotateL(parent-_left);RotateR(parent);if (bf 0){parent-_bf 0;subL-_bf 0;subLR-_bf 0;}else if (bf -1){parent-_bf 1;subL-_bf 0;subLR-_bf 0;}else if (bf 1){parent-_bf 0;subL-_bf -1;subLR-_bf 0;}else{assert(false);}
}2.2.4 右左旋插入新节点后不是单纯的右边高 可参考左右旋。
//右左旋
void RotateRL(Node* parent)
{Node* subR parent-_right;Node* subRL subR-_left;int bf subRL-_bf;RotateR(parent-_right);RotateL(parent);if (bf 0){parent-_bf 0;subR-_bf 0;subRL-_bf 0;}else if (bf -1){parent-_bf 0;subR-_bf 1;subRL-_bf 0;}else if (bf 1){parent-_bf -1;subR-_bf 0;subRL-_bf 0;}else{assert(false);}
}旋转完成后原parent为根的子树个高度降低已经平衡不需要再向上更新。 2.3 验证AVL树的平衡
我们可以分别计算出其左子树和右子树的高度将其相减的值与节点中记录的平衡因子的值比较看是否符合我们的预期。
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;
}bool _isBalanceTree(Node* root)
{if (root nullptr){return true;}int leftheight _Height(root-_left);int rightheight _Height(root-_right);int bf rightheight - leftheight;if (abs(bf) 1){cout root-_kv.first 高度差异常 endl;return false;}if (root-_bf ! bf){cout root-_kv.first 平衡因子异常 endl;return false;}return _isBalanceTree(root-_left) _isBalanceTree(root-_right);
}三、完整代码
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
class AVLTree
{typedef AVLTreeNodeK, V Node;
public:AVLTree() default;AVLTree(const AVLTreeK, V t){_root copy(t._root);}AVLTreeK, V operator(AVLTreeK, V t){swap(_root, t._root);return *this;}~AVLTree(){Destroy(_root);_root nullptr;}bool Find(const K key){Node* pcur _root;while (pcur){if (key pcur-_kv.first){pcur pcur-_left;}else if (key pcur-_kv.first){pcur pcur-_right;}else{return true;}}return false;}bool Insert(const pairK, V kv){//没有节点时需要单独处理if (_root nullptr){_root new Node(kv);return true;}Node* pcur _root;Node* parent nullptr;while (pcur){if (kv.first pcur-_kv.first){parent pcur;pcur pcur-_left;}else if (kv.first pcur-_kv.first){parent pcur;pcur pcur-_right;}else{return false;}}pcur new Node(kv);if (parent-_kv.first kv.first)//判断新节点应该插入左还是右{parent-_left pcur;}else{parent-_right pcur;}pcur-_parent parent;//与父节点链接关系//更新平衡因子while (parent)//有可能更新到根节点去{parent-_bf parent-_left pcur ? parent-_bf - 1 : parent-_bf 1;if (parent-_bf 0)//插入前后高度不变{break;}else if (parent-_bf 1 || parent-_bf -1){//高度变了继续往上更新pcur parent;parent parent-_parent;}else if (parent-_bf 2 || parent-_bf -2){//插入节点后二叉树不平衡了需要旋转处理if (parent-_bf 2 pcur-_bf 1){RotateL(parent);}else if (parent-_bf -2 pcur-_bf -1){RotateR(parent);}else if (parent-_bf 2 pcur-_bf -1){RotateRL(parent);}else if (parent-_bf -2 pcur-_bf 1){RotateLR(parent);}break;//不管是哪种情况旋转完后子树的高度没有变化所以不再调整}else{assert(false);//检测AVL树是否异常}}return true;}void InOrder(){_InOrder(_root);cout endl;}bool IsBalanceTree(){return _isBalanceTree(_root);}private://左单旋void RotateL(Node* parent){Node* subR parent-_right;Node* subRL subR-_left;//subRL是有可能为空的parent-_right subRL;subR-_left parent;Node* parentparent parent-_parent;parent-_parent subR;if (parentparent nullptr)//subR有可能变成根{_root subR;}else{if (parentparent-_left parent){parentparent-_left subR;}else{parentparent-_right subR;}}subR-_parent parentparent;if (subRL){subRL-_parent parent;}parent-_bf subR-_bf 0;//更新平衡因子}//右单旋void RotateR(Node* parent){Node* subL parent-_left;Node* subLR subL-_right;parent-_left subLR;subL-_right parent;Node* parentparent parent-_parent;parent-_parent subL;if (parentparent nullptr){_root subL;}else{if (parentparent-_left parent){parentparent-_left subL;}else{parentparent-_right subL;}}subL-_parent parentparent;if (subLR){subLR-_parent parent;}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 0){parent-_bf 0;subL-_bf 0;subLR-_bf 0;}else if (bf -1){parent-_bf 1;subL-_bf 0;subLR-_bf 0;}else if (bf 1){parent-_bf 0;subL-_bf -1;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 0){parent-_bf 0;subR-_bf 0;subRL-_bf 0;}else if (bf -1){parent-_bf 0;subR-_bf 1;subRL-_bf 0;}else if (bf 1){parent-_bf -1;subR-_bf 0;subRL-_bf 0;}else{assert(false);}}Node* copy(Node* root){if (root nullptr){return nullptr;}Node* copynode new Node(root-_kv);copynode-_left copy(root-_left);copynode-_right copy(root-_right);return copynode;}void Destroy(Node* root){if (root nullptr)return;Destroy(root-_left);Destroy(root-_right);delete 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 leftheight _Height(root-_left);int rightheight _Height(root-_right);return leftheight rightheight ? leftheight 1 : rightheight 1;}bool _isBalanceTree(Node* root){if (root nullptr){return true;}int leftheight _Height(root-_left);int rightheight _Height(root-_right);int bf rightheight - leftheight;if (abs(bf) 1){cout root-_kv.first 高度差异常 endl;return false;}if (root-_bf ! bf){cout root-_kv.first 平衡因子异常 endl;return false;}return _isBalanceTree(root-_left) _isBalanceTree(root-_right);}private:Node* _root nullptr;
};本篇文章的分享就到这里了如果您觉得在本文有所收获还请留下您的三连支持哦~
