西安h5响应式网站seo排名赚app官网

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

西安h5响应式网站,seo排名赚app官网,电脑版网站建设合同,店铺只做商品展示网站怎么做前言 各位读者朋友们大家好#xff0c;上期我们讲解了map和set这两大容器的使用#xff0c;这一期我们讲解最早的平衡二叉搜索树——AVL树。 目录 前言一. AVL树的概念二. AVL树的实现2.1 AVL树的结构2.2 AVL树的插入2.2.1 AVL树插入一个值的大致过程2.2.2 平衡因子的更新2…前言 各位读者朋友们大家好上期我们讲解了map和set这两大容器的使用这一期我们讲解最早的平衡二叉搜索树——AVL树。 目录 前言一. AVL树的概念二. AVL树的实现2.1 AVL树的结构2.2 AVL树的插入2.2.1 AVL树插入一个值的大致过程2.2.2 平衡因子的更新2.2.3 插入代码实现 2.3 旋转2.3.1 旋转的原则2.3.2 右单旋(单纯左子树高)2.3.3 右单旋的实现2.3.4 左单旋(单纯右子树高)2.3.5 左单旋的实现2.3.6 左右双旋(左子树的右子树高)2.3.7 左右双旋的实现2.3.8 右左双旋(右子树的左子树高)2.3.9 右左双旋的实现 2.4 AVL树的查找 三. AVL树的全体实现3.1 AVL树的平衡检测 结语 一. AVL树的概念 AVL树是最先发明的自平衡二叉查找树AVL是一棵空树或者具备下列性质的⼆叉搜索树它的左右子树都是AVL树且左右子树的高度差的绝对值不超过1。AVL树是一颗高度平衡搜索二叉树通过控制高度差去控制平衡。AVL树得名于它的发明者G.M.Adelson-Velsky和E.M.Landis是两个前苏联的科学家他们在1962年的论文中发表了它。AVL树实现这里我们引入一个平衡因子(balance factor)的概念每个节点都有一个平衡因子任何节点的平衡因子等于右子树的高度减去左子树的高度也就是说任何节点的平衡因子等于0/1/-1AVL树并不是必须要平衡因子但是有了平衡因子可以更方便我们去进行观察和控制树是否平衡就像一个风向标一样。 AVL树整体节点数量和分布和完全二叉树类似高度可控制在logN增删查改的效率也可以控制在O(logN)相比二叉搜索树有了本质的提升。
二. AVL树的实现 2.1 AVL树的结构 template class K, class V struct AVLTreeNode {pairK, T _kv;AVLTreeNode* _left;AVLTreeNode* _right;AVLTreeNode* _parent;int _bf;// 平衡因子AVLTreeNode(const pairK,V kv):_kv(kv),_left(nullptr),_right(nullptr),_parent(nullptr),_bf(0){} }; template class K,class V class AVLTree {typedef AVLTreeNodeK, V Node; public:private:Node* _root nullptr; };2.2 AVL树的插入 2.2.1 AVL树插入一个值的大致过程 按照二叉搜索树的规则插入一个值新增节点以后只会影响祖先节点的高度也就是可能会影响部分祖先节点的平衡因子所以更新插入节点到根路径上的平衡因子实际中最坏的情况下要更新到根有些情况更新到中间就可以停止了具体情况下面再详细分析。更新平衡因子过程中没有出现问题插入结束。更新平衡因子过程中出现不平衡对不平衡子树旋转旋转后调平衡的同时本质降低了子树的高度不会再影响上一层所以插入结束。 2.2.2 平衡因子的更新 更新原则 平衡因子 右子树高度 - 左子树高度 只有子树高度变化才会影响当前节点的平衡因子 插入节点会增加高度所以新增加节点在parent的右子树parent的平衡因子在左子树平衡因子– parent所在子树的高度是否变化决定了是否向上继续更新 更新停止条件 更新后parent的平衡因子等于0更新中parent的平衡因子的变化为1到0或者-1到0,说明更新前parent的子树一边高一边低新插入的节点在低的一侧插入后parent所在子树的高度不变不会影响parent父亲节点的平衡因子更新结束。 这种情况下就相当于将parent子树补齐 更新后parent的平衡因子等于1或者-1更新前更新中parent的平衡因子的变化为0到1或者0到-1说明更新前parent的左右子树同高新增的插入节点后parent所在子树一边高一边低parent所在子树的符合平衡要求但是高度增加了1会影响parent的平衡因子所以要继续向上调整。当更新到根节点的时候结束更新 更新后parent的平衡因子等于2或者-2parent的平衡因子的变化为1到2或者-1到-2说明更新前子树一边高一边低然后新插入的节点在高的那边parent所在子树高的那边更高了破坏了平衡parent所在的子树不符合平衡要求需要旋转处理。旋转的目标有两个1、把parent的子树旋转平衡。 2、降低parent子树的高度恢复到插入节点之前的高度。所以旋转之后也不需要向上更新插入结束。
2.2.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-_right cur;}else{parent-_left cur;}// 链接父亲cur-_parent parent;// 更新平衡因子while (parent){if (cur parent-_right)// 插入右边平衡因子parent-_bf;else–parent-_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; }插入前面的逻辑根二叉搜索树插入的逻辑一样只是插入完节点之后更新了平衡因子并调整树的平衡。 2.3 旋转 2.3.1 旋转的原则 保持搜索树的规则让旋转的树从不平衡变得平衡其次降低树的高度 旋转一共有四种左单旋/右单旋/左右双旋/右左双旋 2.3.2 右单旋(单纯左子树高) 旋转核心步骤因为5 b子树的值 10将b变成10的左子树10变成5的右子树5变成这棵树新的根符合搜索树的规则控制了平衡同时这棵树的高度恢复到了插入之前的h2符合旋转原则。如果插入之前10整棵树的⼀个局部子树旋转后不会再影响上一层插入结束了。 上图中是抽象图有a/b/c抽象为三棵高度为h的子树(h0)a/b/c均符合AVL树的要 求。10可能是整棵树的根也可能是⼀个整棵树中局部的子树的根。这里a/b/c是高度为h的子树上图适用于所有的右单旋情况下面我们展开几种情况来看一下 插入前a/b/c/的高度为0 插入前a/b/c/的高度为1 插入前a/b/c/的高度为2 a必须是x,否则就不能在10节点旋转了(可能在5的左孩子节点旋转也可能不会旋转)插入前a/b/c/的高度为3 只有a是4个节点或者三个节点插入到两个节点上才会旋转。 2.3.3 右单旋的实现 subL当根节点parent当subL的右子树subLR当parent的右子树也要注意所有的parent的处理每个节点要将对应的父亲节点调整好 void RotateR(Node* parent) {// subL当根节点parent当subL的右子树subLR当parent的右子树注意所有的parent的处理Node* subL parent-_left;Node* subLR subL-_right;subL-_right parent;parent-_left subLR;// 从下往上链接父节点if (subLR)// subL可能为空为空就不需要处理父亲节点subLR-_parent parent;Node* pParent parent-_parent;// 父节点的父亲便于后续链接parent-_parent subL;if (parent _root)// 如果调整的是整棵树的根{_root subL;subL-_parent nullptr;}else// 局部树链接祖先{if (parent pParent-_left)pParent-_left subL;elsepParent-_right subL;subL-_parent pParent;}// 更新平衡因子subL-_bf parent-_bf 0; }2.3.4 左单旋(单纯右子树高) 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整棵树的一个局部子树旋转后不会再影响上一层插入结束了。 2.3.5 左单旋的实现 void RotateL(Node* parent) {Node* subR parent-_right;Node* subRL subR-_left;parent-_right subRL;subR-_left parnet;// 从下往上链接父节点if (subRL)subRL-_parent parent;Node* pParent parent-_parent;parent-_parent subR;if (parent _root)// 调整的是整棵树的根{_root subR;subR-_parent nullptr;}else{if (parent pParent-_left)pParent-_left subR;elsepParent-_right subR;subR-_parent pParent;}subR-_bf parent-_bf 0; }2.3.6 左右双旋(左子树的右子树高) 我们先通过具体图来分析 情况1、a/b/c子树的高度为0 情况2、a/b/c子树的高度h1在b树的右边插入节点 情况3、a/b/c子树的高度h1在b树的左边插入节点 2.3.7 左右双旋的实现 void RotateLR(Node* parent) {Node* subL parent-_left;Node* subLR subL-_right;int bf subLR-_bf;// 记录其平衡因子看新节点是插入在左还是在右RotateL(subL);// 先左旋RotateR(parent);// 再右旋// 更新平衡因子if (bf 1)// 在右侧插入的节点{parent-_bf 0;subL-_bf -1;subLR-_bf 0;}else if (bf -1)// 左侧{parent-_bf 1;subL-_bf 0;subLR-_bf 0;}else if (bf 0)// 树为空直接插入{parent-_bf 0;subL-_bf 0;subLR-_bf 0;}elseassert(false); }2.3.8 右左双旋(右子树的左子树高) 这里和左右双旋一样也是有三种情况 2.3.9 右左双旋的实现 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 0;subR-_bf 1;subRL-_bf 0;}else if (bf 1){parent-_bf -1;subR-_bf 0;subRL-_bf 0;}else if (bf 0){parent-_bf 0;subR-_bf 0;subRL-_bf 0;}elseassert(false); }2.4 AVL树的查找 和二叉树搜索树的逻辑一样只是效率提升到O(logN) Node* Find(const K key) {Node* cur _root;while (cur){if (key cur-_kv.first)// 大的往右走cur cur-_right;else if (key cur-_kv.first)// 小的往左走cur cur-_left;elsereturn cur;}return nullptr; }三. AVL树的全体实现 AVL树的实现代码 3.1 AVL树的平衡检测 我们可以检查AVL树的高度差如果高度差2就说明不是AVL树 bool _IsBalanceTree(Node * root){if (root nullptr)return true;int leftHeight _Height(root-_left);int rightHeight _Height(root-_right);int diff rightHeight - leftHeight;if (abs(diff) 2){cout root-_kv.first 高度差异常不是AVL树 endl;return false;}if (diff ! root-_bf){cout root-_kv.first 平衡因子异常 endl;return false;}return _IsBalanceTree(root-_left) _IsBalanceTree(root-_right);}测试代码 void TestAVLTree2() {const int N 100000;vectorint v;v.reserve(N);srand(time(0));for (size_t i 0; i N; i){v.push_back(rand() i);}size_t begin2 clock();AVLTreeint, int t;for (auto e : v){t.Insert(make_pair(e, e));}size_t end2 clock();cout Insert: end2 - begin2 endl;if (t.IsBalanceTree())cout AVL endl;cout Height: t.Height() endl;cout Size: t.Size() endl;size_t begin1 clock();for (size_t i 0; i N; i){t.Find((rand() i));}size_t end1 clock();cout Find: end1 - begin1 endl; }int main() {TestAVLTree2();return 0; }结语 以上我们就讲完了AVL树的实现这部分需要好好消化感谢大家的阅读欢迎大家批评指正