江苏省和城乡建设门户网站js插件打开wordpress

当前位置： 首页 > news >正文

江苏省和城乡建设门户网站,js插件打开wordpress,编程网站scratch在线使用,深圳微信网站公司一、AVL树的概念 AVL树是最先发明的自平衡⼆叉查找树#xff0c;AVL是⼀颗空树#xff0c;或者具备下列性质的⼆叉搜索树#xff1a;它的 左右子树都是AV树#xff0c;且左右子树的高度差的绝对值不超过1。AVL树是⼀颗高度平衡搜索⼆叉树#xff0c; 通过控制高度差去控…一、AVL树的概念 AVL树是最先发明的自平衡⼆叉查找树AVL是⼀颗空树或者具备下列性质的⼆叉搜索树它的 左右子树都是AV树且左右子树的高度差的绝对值不超过1。AVL树是⼀颗高度平衡搜索⼆叉树 通过控制高度差去控制平衡。 AVL树得名于它的发明者G. M. Adelson-Velsky和E. M. Landis是两个前苏联的科学家他们在1962 年的论文《An algorithm for the organization of information》中发表了它。 AVL树实现这里我们引入⼀个平衡因子(balance factor)的概念每个结点都有⼀个平衡因子任何 结点的平衡因子等于右子树的高度减去左子树的高度也就是说任何结点的平衡因子等于0/1/-1 AVL树并不是必须要平衡因子但是有了平衡因子可以更方便我们去进行观察和控制树是否平衡 就像⼀个风向标⼀样。 思考⼀下为什么AVL树是高度平衡搜索⼆叉树要求高度差不超过1而不是高度差是0呢0不是更 好的平衡吗画画图分析我们发现不是不想这样设计而是有些情况是做不到高度差是0的。⽐ 如⼀棵树是2个结点4个结点等情况下高度差最好就是1无法作为高度差是0 AVL树整体结点数量和分布和完全⼆叉树类似高度可以控制在 那么增删查改的效率也可 以控制在 相比⼆叉搜索树有了本质的提升。 二、AVL树的实现 1、AVL树的结构 #pragma once #includeiostream using namespace std; templateclass K, class V struct AVLTreeNode {// 需要parent指针后续更新平衡因子可以看到pairK, V _kv;AVLTreeNodeK, V* _left;AVLTreeNodeK, V* _right;AVLTreeNodeK, V* _parent;int _bf; // balance factorAVLTreeNode(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: private:Node * _root nullptr; };2、插入 插入一个值按⼆叉搜索树规则进行插入。 新增结点以后只会影响祖先结点的高度也就是可能会影响部分祖先结点的平衡因子所以更新
从新增结点-根结点路径上的平衡因子实际中最坏情况下要更新到根有些情况更新到中间就可 以停止了具体情况我们下面再详细分析。 更新平衡因子过程中没有出现问题则插入结束 更新平衡因子过程中出现不平衡对不平衡子树旋转旋转后本质调平衡的同时本质降低了子树
的高度不会再影响上⼀层所以插入结束。 3、平衡因子更新 更新原则 平衡因子 右子树高度-左子树高度 只有子树高度变化才会影响当前结点平衡因子。 插入结点会增加高度所以新增结点在parent的右子树parent的平衡因子新增结点在 parent的左子树parent平衡因子– parent所在子树的高度是否变化决定了是否会继续往上更新 更新停止条件 更新后parent的平衡因子等于0更新中parent的平衡因子变化为-1-0 或者 1-0说明更新前 parent子树⼀边高⼀边低新增的结点插入在低的那边插入后parent所在的子树高度不变不会 影响parent的父亲结点的平衡因子更新结束。 更新后parent的平衡因子等于1 或 -1更新前更新中parent的平衡因子变化为0-1 或者 0–1说 明更新前parent子树两边⼀样高新增的插入结点后parent所在的子树⼀边高⼀边低parent所 在的子树符合平衡要求但是高度增加了1会影响arent的父亲结点的平衡因子所以要继续向上 更新。 更新后parent的平衡因子等于2 或 -2更新前更新中parent的平衡因子变化为1-2 或者 -1–2说 明更新前parent子树⼀边高⼀边低新增的插入结点在高的那边parent所在的子树高的那边更高 了破坏了平衡parent所在的子树不符合平衡要求需要旋转处理旋转的⽬标有两个1、把 parent子树旋转平衡。2、降低parent子树的高度恢复到插入结点以前的高度。所以旋转后也不 需要继续往上更新插入结束。 更新到10结点平衡因子为210所在的子树已经不平衡需要旋转处理 更新到中间结点3为根的子树高度不变不会影响上⼀层更新结束 最坏更新到根停⽌ 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;}else{return false;}}cur new Node(kv);if (parent-_kv-first kv.first){parent-_left cur;}else{parent-_right cur;}//更新平衡因子while (parent){if (cur parent-_left)parent-_bf–;elseparent-_bfif (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){//选转break;}}}4、旋转 a、右单旋 本图1展⽰的是10为根的树有a/b/c抽象为三棵高度为h的子树(h0)a/b/c均符合AVL树的要 求。10可能是整棵树的根也可能是⼀个整棵树中局部的子树的根。这里a/b/c是高度为h的子树 是⼀种概括抽象表示他代表了所有右单旋的场景实际右单旋形态有很多种具体图2/图3/图4/ 图5进行了详细描述。 在a子树中插入⼀个新结点导致a子树的高度从h变成h1不断向上更新平衡因子导致10的平 衡因子从-1变成-210为根的树左右高度差超过1违反平衡规则。10为根的树左边太高了需要 往右边旋转控制两棵树的平衡。 旋转核心步骤因为5 b子树的值 10将b变成10的左子树10变成5的右子树5变成这棵树新 的根符合搜索树的规则控制了平衡同时这棵的高度恢复到了插入之前的h2符合旋转原 则。如果插入之前10整棵树的⼀个局部子树旋转后不会再影响上⼀层插入结束了。 代码 void RotateR(Node* parent) {Node* Pparent 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 (Pparent nullptr)//parent是根时{_root subL;subL-_parent nullptr;}else{if (parent parentParent-_left){parentParent-_left subL;}else{parentParent-_right subL;}subL-_parent parentParent;}//更新平衡因子parent-_bf subL-_bf 0; }b、左单旋 本图6展示的是10为根的树有a/b/c抽象为三棵高度为h的子树(h0)a/b/c均符合AVL树的要 求。10可能是整棵树的根也可能是⼀个整棵树中局部的子树的根。这里a/b/c是高度为h的子树 是⼀种概括抽象表示他代表了所有右单旋的场景实际右单旋形态有很多种具体跟上⾯左旋类 似。 在a子树中插入⼀个新结点导致a子树的高度从h变成h1不断向上更新平衡因子导致10的平 衡因子从1变成210为根的树左右高度差超过1违反平衡规则。10为根的树右边太高了需要往 左边旋转控制两棵树的平衡。 旋转核心步骤因为10 b子树的值 15将b变成10的右子树10变成15的左子树15变成这棵 树新的根符合搜索树的规则控制了平衡同时这棵的高度恢复到了插入之前的h2符合旋转 原则。如果插入之前10整棵树的⼀个局部子树旋转后不会再影响上⼀层插入结束了。 代码 void RotateL(Node* parent) {Node* Pparent parent-_parent;Node* subR parent-_right;Node* subRL subL-_left;parent-_right subRL;if (subRL)subRL-_parent parent;subR-_left parent;parent-_parent subR;if (Pparent nullptr)//parent是根时{_root subR;subR-_parent nullptr;}else{if (parent parentParent-_left){parentParent-_left subR;}else{parentParent-_right subR;}subR-_parent parentParent;}parent-_bf subR-_bf 0; }c、左右双旋 通过图7和图8可以看到左边高时如果插入位置不是在a子树而是插入在b子树b子树高度从h变 成h1引发旋转右单旋无法解决问题右单旋后我们的树依旧不平衡。右单旋解决的纯粹的左边 高但是插入在b子树中10为跟的子树不再是单纯的左边高对于10是左边高但是对于5是右边 高需要用两次旋转才能解决以5为旋转点进行⼀个左单旋以10为旋转点进行⼀个右单旋这棵树 这棵树就平衡了 图7和图8分别为左右双旋中h0和h1具体场景分析下面我们将a/b/c子树抽象为高度h的AVL 子树进行分析另外我们需要把b子树的细节进⼀步展开为8和左子树高度为h-1的e和f子树因为 我们要对b的父亲5为旋转点进行左单旋左单旋需要动b树中的左子树。b子树中新增结点的位置 不同平衡因子更新的细节也不同通过观察8的平衡因子不同这里我们要分三个场景讨论。 场景1h 1时新增结点插⼊在e子树e子树高度从h-1变为h并不断更新8-5-10平衡因子 引发旋转其中8的平衡因子为-1旋转后8和5平衡因子为010平衡因子为1。 场景2h 1时新增结点插⼊在f子树f子树高度从h-1变为h并不断更新8-5-10平衡因子引 发旋转其中8的平衡因子为1旋转后8和10平衡因子为05平衡因子为-1。 场景3h 0时a/b/c都是空树b⾃⼰就是⼀个新增结点不断更新5-10平衡因子引发旋 转其中8的平衡因子为0旋转后8和10和5平衡因子均为0。 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){subL-_bf 0;subLR-_bf 0;parent-_bf 0;}else if (bf -1){subL-_bf 0;subLR-_bf 0;}else if (bf 1)parent-_bf 1;{subL-_bf -1;subLR-_bf 0;parent-_bf 0;}else{assert(false);} }d、右左双旋 跟左右双旋类似下⾯我们将a/b/c子树抽象为⾼度h的AVL子树进⾏分析另外我们需要把b子树的 细节进⼀步展开为12和左子树⾼度为h-1的e和f子树因为我们要对b的⽗亲15为旋转点进⾏右单 旋右单旋需要动b树中的右子树。b子树中新增结点的位置不同平衡因子更新的细节也不同通 过观察12的平衡因子不同这⾥我们要分三个场景讨论。 场景1h 1时新增结点插⼊在e子树e子树⾼度从h-1变为h并不断更新12-15-10平衡因 子引发旋转其中12的平衡因子为-1旋转后10和12平衡因子为015平衡因子为1。 场景2h 1时新增结点插⼊在f子树f子树⾼度从h-1变为h并不断更新12-15-10平衡因子 引发旋转其中12的平衡因子为1旋转后15和12平衡因子为010平衡因子为-1。• 场景3h 0时a/b/c都是空树b自己就是⼀个新增结点不断更新15-10平衡因子引发旋 转其中12的平衡因子为0旋转后10和12和15平衡因子均为0。 void RotateRL(Node* parent) {Node* subR parent-_right;Node* subRL subR-_left;int bf subRL-_bf;RotateR(parent-_right);RotateL(parent);if (bf 0){subR-_bf 0;subRL-_bf 0;parent-_bf 0;}else if (bf 1){subR-_bf 0;subRL-_bf 0;parent-_bf -1;}else if (bf -1){subR-_bf 1;subRL-_bf 0;parent-_bf 0;}else{assert(false);} }三、整体代码 #pragma once #includeiostream using namespace std; templateclass K, class V struct AVLTreeNode {// 需要parent指针后续更新平衡因⼦可以看到pairK, V _kv;AVLTreeNodeK, V* _left;AVLTreeNodeK, V* _right;AVLTreeNodeK, V* _parent;int _bf; // balance factorAVLTreeNode(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: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;}else{return false;}}cur new Node(kv);if (parent-_kv.first kv.first){parent-_right cur;}else{parent-_left cur;}// 链接父亲cur-_parent parent;if (parent-_kv-first kv.first){parent-_left cur;}else{parent-_right cur;}//更新平衡因子while (parent){if (cur parent-_left)parent-_bf–;elseparent-_bfif (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{RotateRL(parent);}break;}}}void RotateR(Node* parent){Node* Pparent 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 (Pparent nullptr)//parent是根时{_root subL;subL-_parent nullptr;}else{if (parent parentParent-_left){parentParent-_left subL;}else{parentParent-_right subL;}subL-_parent parentParent;}//更新平衡因子parent-_bf subL-_bf 0;}void RotateL(Node* parent){Node* Pparent parent-_parent;Node* subR parent-_right;Node* subRL subL-_left;parent-_right subRL;if (subRL)subRL-_parent parent;subR-_left parent;parent-_parent subR;if (Pparent nullptr)//parent是根时{_root subR;subR-_parent nullptr;}else{if (parent parentParent-_left){parentParent-_left subR;}else{parentParent-_right subR;}subR-_parent parentParent;}parent-_bf subR-_bf 0;}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){subL-_bf 0;subLR-_bf 0;parent-_bf 0;}else if (bf -1){subL-_bf 0;subLR-_bf 0;}else if (bf 1)parent-_bf 1;{subL-_bf -1;subLR-_bf 0;parent-_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){subR-_bf 0;subRL-_bf 0;parent-_bf 0;}else if (bf 1){subR-_bf 0;subRL-_bf 0;parent-_bf -1;}else if (bf -1){subR-_bf 1;subRL-_bf 0;parent-_bf 0;}else{assert(false);}} private:Node * _root nullptr; };