西安做网站哪家最便宜,长沙有什么好吃的,淄博网站公司电话,商丘市网络优化公司地址1.AVL的概念 1.AVL树属于二叉搜索树的一种#xff0c;但它不同与普通的二叉搜索树还具有以下的性质#xff1a; 每一个根的左右子树的高度差的绝对值不超过1。AVL树是通过高度差去控制平衡的#xff0c;所以又称作为平衡二叉搜索树。 2.AVL树实现我们引入了一个平衡因子的概…1.AVL的概念 1.AVL树属于二叉搜索树的一种但它不同与普通的二叉搜索树还具有以下的性质 每一个根的左右子树的高度差的绝对值不超过1。AVL树是通过高度差去控制平衡的所以又称作为平衡二叉搜索树。 2.AVL树实现我们引入了一个平衡因子的概念每一个结点都有它的平衡因子所谓平衡因子即结点的右子树的高度减去左子树的高度AVL树的平衡因子有0/1/-1三种如果平衡因子不属于这三种之一便不是AVL树。 3.AVL树整体结点数量和分布和完全二叉树类似高度可以控制在logN,那么增删查改的效率也可以控制在O(logN) 下图就为典型的AVL树 2.AVL树的实现 2.1AVL树的结构 templateclass K, class V struct AVLTreeNode { // 需要parent指针后续更新平衡因子可以看到 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: 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-_left) 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) { // 旋转 break; } else { assert(false); } } return true; } private: Node* _root nullptr; }; 上面为一个完整的AVL的结构接下来就是对AVL树的深层次了解 2.2 AVL树的插入 2.2.1 AVL树插入一个值的过程
1.插入一个值按二叉搜索树的规则进行插入
2.如果插入后平衡因子都符合AVL树的规则插入就结束
3.如果不符合AVL树的规则就更新平衡因子对不平衡子树进行旋转 2.2.2 平衡因子更新
更新的原则
1. 平衡因子 0/1/-1
2.插入的结点在右子树则parent的平衡因子在左子树则parent的平衡因子--
更新停止条件
1.更新后parent的平衡因子等于0更新前的平衡因子为1或者-1说明一边高一边低而插入的新结点插入在低的一边插入后parent所在的子树高度不变不会影响parent的父亲结点的平衡因子更新结束。
2.更新后parent的平衡因子等于1或者-1说明在更新前parent的平衡因子等于0parent的左右子树一样高但插入新结点后高度增加1了就会影响parent的父结点如果此时父结点不符合AVL树的规则就要去继续更新。
3.更新后parent的平衡因子等于2或者-2说明更新前parent的平衡因子等于1或者-1而新插入的结点恰好在较高的子树上。破坏了平衡,parent所在的子树不符合平衡要求则需要旋转处理。
旋转的目标有两个 1.把parent子树旋转平衡 2.降低parent子树的高度恢复到插入结点以前的高度所以旋转后插入 结束。 2.3 旋转 2.3.1 旋转的原则
1.保持搜索树的原则
2.让旋转的树从不满足变平衡其次降低旋转树的高度
旋转总共分为四种左单旋/右单旋/左右双旋/右左双旋 2.3.2 右单旋 在上图中就是右单旋的流程图 有a/b/c抽象为三颗高度为h的子树h0),a/b/c均符合AVL树的要求10可能是整数的根也可能是一个整颗树局部的子树的根该图也只是右单旋的形态之一但易于理解。
如上图所示在a点插入了一个新结点导致10的平衡因子变为了-2为让其符合平衡规则需要让10的过高的的左子树右旋如第三步所示从而控制两颗树的平衡。
核心步骤因为5 b子树的值 10,将b子树作为10结点的左子树然后将5变成这颗新树的根符合了搜索树的规则控制了平衡同时这颗树恢复到了之前的h2,符合旋转原则。 以下的情况就不细讲了根据第一张的思维可以理解下面的情况 2.3.3 右单旋代码的实现 void RotateR(Node* parent) { Node* subL parent-_left; Node* subLR subL-right; Node*Pparent parent -_parent; parent -left subLR; if(subLR) subLR-_parent parent; parent -_parent subL; if(Pparent nullptr) { _root subL; subL-_parent nullptr; } else { if (parent Pparent-_left) { Pparent-_left subL; } else { Pparent-_right subL; } subL-_parent Pparent; } subL-_parent subL-_bf 0; } 2.3.4 左单旋 左单旋与右单旋类似只是从原本过高的左子树的右旋变成现在的过高的右子树的左旋。 其他的情况也和右子树的情况类似这里就不一一列举了 2.3.5 左单旋代码的实现 void RotateRL(Node* parent) { Node*subR parent-right; Node*subRL parent-left; Node*Pparent parent-_parent; parent -_right subRL; if(subRL) subRL-_parent parent; subR-_left parent; parent-_parent subR; if(Pparent nullptr) { _root subR; subR-_parent nullptr; } else if(Pparent-_left parent) { Pparent -_left subR; } else { Pparent -_right subR; } subR-_parent Pparent; parent-_bf subR-_bf 0; } 2.3.6 左右双旋 从上图可以看出右单旋没有解决两颗树的平衡问题所以在这里就要使用左右双旋才能解决该问题。 在上图中有三个场景 场景1h1时新增结点插入在e子树e子树高度从h-1并为h并不断更新8-5-10平衡因子引发旋转其中8的平衡因子为1旋转后8和5平衡因子为0,10的平衡因子变为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。 2.3.7 左右双旋代码实现 void RotateLR(Node* parent) { Node*subL parent -_left; Node*subLR subL-_right; int bf subLR-_bf 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; parent-_bf 1; } else if(bf 1) { subL-_bf -1; subLR-_bf 0; parent-_bf 0; } else { assert(false); } } 2.3.8 右左双旋 同样分三个场景 场景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。 2.3.9 右左双旋代码实现 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); } }
