网站开发就业培训班,关于阅读类网站的建设规划书,手机网站做安卓客户端,谷歌sem推广目录
模拟插入节点
左单旋
右单旋
右左双旋
左右双旋
总结
实现
插入实现 左单旋实现
右单旋实现
右左双旋实现
左右双旋实现 AVL树 模拟实现#xff08;插入#xff09;
AVL 树#xff0c;是高度平衡二叉搜索树#xff0c;其主要通过旋转来控制其左右子树的高…目录
模拟插入节点
左单旋
右单旋
右左双旋
左右双旋
总结
实现
插入实现 左单旋实现
右单旋实现
右左双旋实现
左右双旋实现 AVL树 模拟实现插入
AVL 树是高度平衡二叉搜索树其主要通过旋转来控制其左右子树的高度不超过1这样就能达到搜索效率基本等同于满二叉树O(LogN)所以 AVL 并不会向普通的搜索树一样在极端情况下退化为单枝。
首先AVL在平衡的前提下还要保证其是一颗搜索树所以在插入的时候还是按照搜索树的插入规则来。
AVL 树的高度就是右子树减左子树的高度。
AVL 树的实现有几种其中一种是借用平衡因子来查看其是否平衡如果不适用平衡因子那么就需要使用高度查看是否平衡但是加入平衡因子会跟简单一些所以下面我们实现的AVL 树是借用平衡因子来维持平衡的。
模拟插入节点
如果是第一次插入以及第二次插入那么和搜索树是一摸一样的为什么呢
因为如果是第一次插入那么就是插入到根节点所以该是是平衡的无需做其他的操作来保持其平衡而第二次插入也是不需要我们做其他操作的同样是因为第二次插入也是平衡的左右子树的高度不超过1。
左单旋
插入两个节点如图所示 这时候6 节点的高度就为 0而 2 节点的高度为 1因为 6 节点的左右子树的高度都为 0而 2 节点的右子树的高度为 1而左子树的高度为 0.
如果是两个节点的话是无法达到完全平衡的所以并不是AVL树不想达到完全平衡而是只有在满二叉树的情况下才能达到完全平衡。
下面如果在插入一个节点那么就会引发旋转 如果这时候插入节点 8那么首先我们就能看到这棵树已经不平衡了但是我们要怎么使用平衡因子来控制
插入节点 8此时节点 8 的平衡因子肯定是 0那么现在 8 在节点 6 的右边所以 6 要对它的平衡因子进行1操作 此时节点 6 的平衡因子变为了 1现在我们想一下如果平衡因子由 0 变为 1表示的是什么
节点刚开始的平衡因子是 0 说明刚开始的时候该树是平衡的变为 1说明该树的右子树多增加了一个节点的高度所以说明该树的高度发生了变化所以既然该节点的高度发生了变化那么该节点的父亲节点的高度可能也会发生变化所以这时候我们需要向上检查父亲节点的高度 这时候父亲节点的高度变为了 2说明此时已经不平衡了那么要怎样旋转
我们发现这样的不平衡是单纯的右边高所以我们尽可能向左旋转将高度压下去也就是使用左单旋
1. 我们需要将父亲节点2的右子树连接到cur6 节点的左子树上
2. 我们将cur6节点的左子树连接成父亲节点2
所以旋转结束后就是这样 但是我们的平衡因子是不正确的所以如果我们使用左单旋转旋转之后我们需要将父亲节点2和cur节点6的平衡因子变为 0. 上面我们为什么要将cur 节点的左孩子给父亲节点呢
因为这里我们只是画了一个节点我们有可能右多个节点所以我们还需要处理好其他节点但是由于我们只是对cur 的左子树进行的调换位置我们并未使其高度发生变化所以我们也自然不需要对其的平衡因子进行调整 也就是像我们上图这样cur节点还有左子树 上图就是进行旋转之后的样子然后进行修正平衡因子parent 为 0cur 为 0: 右单旋
如果我们的方向不同呢也就是整个树是单纯的左边高 插入节点 修正平衡因子 这里我们发现节点 6 已经不平衡了需要旋转来维持平衡这时候我们发现它是单纯的左边高也就是我们需要像右旋转也就是右单旋
1. 将节点 4 的右子树连接到节点 6 的左子树上
2. 将节点 6 连接到节点 4 的右子树上
旋转结束后就就是这样 我们还是将parent节点6和 cur节点4的平衡因子修改为 0.
而这里处理cur节点的右子树的原因和处理左单旋时候的 cur 的左子树是一样的原因。
经过上面的左单旋和右单旋我们发现
1. 如果插入节点到当前节点的左子树那么就让当前节点的平衡因子进行 ‘减减’ 操作
2. 如果插入节点到当前节点的右子树那么就让当前节点的平衡因子进行 ‘加加’ 操作
3.如果平衡因子由 0 变为 1 或者由 0 变为 -1 那么就说明当前节点的左右子树的高度发生的变化需要对当前节点的父亲节点进行平衡因子的跟新。
4.如果当前节点的平衡因子被跟新为 2 或者 -2 那么说明当前节点的左右子树已经不平衡了需要旋转来调节平衡。
5. 什么时候插入结束
1当插入的节点是根节点那么插入后就可以结束了。
2插入的节点已经存在
3插入成功并且修正平衡因子后父亲的平衡因子变为 0 变为 0 说明父亲之前的平衡因子不为 0而变为 0 说明父亲的高度没有发生变化所以无需在向上调整插入也就结束。
4修正平衡因子后发现某一节点需要旋转而旋转并且修正平衡因子后插入结束。 上面说的修正平衡因子是一个循环的过程因为在修正平衡因子的时候可能将父亲的平衡因子由0 变为 1 或者 -1 说明父亲的高度变化了所以此时就需要将父亲给给 cur 然后继续向上调整还有一个插入结束的调节就是父亲为空也插入结束了父亲为空说明为根节点。
6. 判断是左单旋还是右单旋
1如果是单纯的左边高那么就进行右单旋那么怎么判断是单纯的左边高单纯的左边高就是父亲节点的平衡因子为 -2 而 cur 节点的平衡因子为 -1.
2如果是单纯的右边高那么就进行右单旋右单旋的特征是parent 的平衡因子是 2 cur 的平衡因子是 1
右左双旋
上面我们插入后总是一边高但是我们还是右其他的情况也就是下面这种 我们这种该怎么样旋转呢我们可以先试一下左单旋因为这里我们发现是右边高 在旋转后我们发现高度并没有被压缩而是调了个个所以如果是这种情况的话单纯的左或者右是不能完成任务的而是需要使用双旋。
我们可以先对cur 节点进行右单旋 经过我们前面对 cur 节点进行的右单旋我们此时已经变为一边高了所以此时我们在对 parent 节点进行左单旋就可以完成压缩高度任务 我们此时经过旋转后的 parent 和 cur 节点的平衡因子变为 0了 但是这只是我们节点 4 就是新插入的节点那么假设是其他情况呢 上图是抽象图可以表示该种情况下所有可能的情况如果当 h 0 的时候就表示的是 4 节点是新增但是无论 h 是多少我们都可以使用右左双旋。
首先对该树的cur 节点使用右单旋 旋转后就变为了这样也就是单纯的右边高所以我们在使用左单旋对parent节点 但是这时候 parent 和 cur 节点的平衡因子都是 0那么我们要怎么调节平衡因子呢对于这种情况来说我们是将parent 的平衡因子调整为 -1 cur 的平衡因子为 0即可但是我们要是插入的位置不是刚开始插入的位置呢 如果插入到该位置那么金国旋转后的结果是这样的 所以此时跟新平衡因子应该是 parent 为 0 ,cur 的平衡因子应该为 1所以我们插入位置不同的话我们的平衡因子的跟新策略是不同的所以我们还要记录插入位置的平衡因子。
我们为了更好的描述我们将节点 4 称为 curLeft。
我们发现我们在旋转结束后curLeft 的左右子树被parent 和 cur 代替而他自己的左子树被分给了parent 的 right 子树 而它的右子树被分给了cur 的 left 子树所以我们只需要知道 curRight 的平衡因子我们也就可以将parent 和 cur 的平衡因子跟新正确。
上面我们一直都没有说 curLeft 的平衡因子其实curLeft 的平衡因子在第一次右单旋的时候就被跟新为了 0 而旋转结束后curLeft 的平衡因子也就应该是 0. 左右双旋
这里我们就直接使用抽象图来描述了。 以上图为例我们要插入一个值 现在我们发现是左边高但是我们知道这种情况下我们单纯的使用右单旋是解决不了问题的所以我们还是选哟使用双旋也就是左右双旋我们先对cur 节点进行左单旋然后对parent 进行右单旋 旋转后我们发现现在是单纯的左边高所以我们对 parent 节点使用右单旋 这时候的 parent cur 以及 curRight 的平衡因子都被跟新为 0了 但是都是 0 并不正确而是也像我们前面的右左双一样需要看 curRight 的平衡因子
1. 如果插入到 curRight 的keft那么 cur 的平衡因子就是 0 parent 的平衡因子为 1。
2. 如果插入到 curRight 的 right 那么 cur 的平衡因子就是 -1parent 的平衡因子就是 0。
总结 如果 parent 的平衡因子为 2 cur 的平衡因子为 1那么使用的是左单旋将 parent 和 cur 的平衡因子都跟新为 0.如果 parent 的平衡因子为 -2 cur 的平衡因子为 -1那么使用的是右单将 parent 和 cur 的平衡因子都跟新为 0.。如果 parent 的平衡因子为 2 cur 的平衡因子为 -1那么使用的是右左双旋 平衡因子 如果curLeft 的平衡因子为 1 那么就将parent 的平衡因子置为 -1cur 的平衡因子置为 0curLeft 的平衡因子为 0 如果curLeft 的平衡因子为 -1 那么就将parent 的平衡因子置为 0cur 的平衡因子置为 1curLeft 的平衡因子为 0 如果curLeft 的平衡因子为 0 那么就将parent 的平衡因子置为 0cur 的平衡因子置为 0curLeft 的平衡因子为 0 如果 parent 的平衡因子为 -2 cur 的平衡因子为 1那么使用的是左右双旋 平衡因子 如果curRight的平衡因子为 1 那么就将parent 的平衡因子置为 0cur 的平衡因子置为 -1curRight的平衡因子为 0 如果curRight的平衡因子为 -1 那么就将parent 的平衡因子置为 1cur 的平衡因子置为 0curRight的平衡因子为 0 如果curRight的平衡因子为 0 那么就将parent 的平衡因子置为 0cur 的平衡因子置为 0curLeft 的平衡因子为 0 实现
上面大概率是把思路都说明白了下面开始看一下实现
插入实现
首先我们先看一下AVLTreeNode:
对于该节点我们需要一个存储值的变量我们还需要三个指针其中一个 left还有一个 right还有一个 parent这里需要parent 是因为我们需要找找到它的父亲节点还需要一个平衡因子
templateclass K, class V
struct TreeNode
{pairK, V _kv;TreeNodeK, V* _left;TreeNodeK, V* _right;TreeNodeK, V* _parent;int _balance;TreeNode(const pairK, V kv):_kv(kv), _left(nullptr), _right(nullptr), _parent(nullptr),_balance(0){}
};
这里我们将存储值的变量之间设置为了 kv 结构因为这样既可以适用于 set也适用于 map.
下面就是插入 插入的话先按照搜索树的插入节点也就是插入插入位置然后记录其父亲节点 if (_root nullptr){_root new Node(kv);return true;}Node* cur _root;Node* parent nullptr;while (cur){if (kv.first cur-_kv.first){parent cur;cur cur-_left;}else if (kv.first cur-_kv.first){parent cur;cur cur-_right;}else{// 重复了插入失败return false;}}// 插入数据cur new Node(kv);if (kv.first parent-_kv.first){//维护三叉链parent-_left cur;cur-_parent parent;}else{//维护三叉链parent-_right cur;cur-_parent parent;} 等 cur 节点插入后开始修正并检查平衡 //检查平衡while (parent){//维护平衡因子// 平衡因子右子树高度-左子树高度if (cur parent-_left){parent-_balance--;}else{parent-_balance;}// 检查 parent 的平衡因子// 如果为 0 说明parent 这颗树以及平衡无需检查// 如果为 1/-1 说明 parent 的平衡发生了变化说明需要检查 parent 的parent 的平衡因子// 如果为 2/-2 说明这棵树已经不平衡了需要旋转if (parent-_balance 0){//该树已经平衡break;}else if (parent-_balance 1 || parent-_balance -1){// 说明该树的高度发生变化,需要检查 parent 的 parent 的平衡因子所以需要向上传递cur parent;parent parent-_parent;}else if (parent-_balance 2 || parent-_balance -2){// 说明该树需要旋转保持平衡if (parent-_balance 2 cur-_balance 1){// 左单旋RotateL(parent);break;}else if (parent-_balance -2 cur-_balance -1){// 右单旋RotateR(parent);break;}else if (parent-_balance 2 cur-_balance -1){// 右左双旋RotateRL(parent);break;}else if (parent-_balance -2 cur-_balance 1){// 左右双旋RotateLR(parent);break;}else{assert(0);}}else{// 不能出现该种情况assert(0);}} 上面就是修正并且检查平衡那么我们看一下应该怎么样旋转 左单旋实现
实际上左单旋并不是像我们说的那样只有我们前面模拟插入的时候的两步
主要步骤
1. 将 parent 的 right 连接成 cur 的 left
2. 将 cur 的 left 连接成 parent
3. 维护三叉链
实际上我们还需要维护三叉链也就是他们的父亲节点。 // 左单旋void RotateL(Node* parent){Node* cur parent-_right;Node* curLeft cur-_left;parent-_right curLeft;if (curLeft){curLeft-_parent parent;}cur-_left parent;Node* pparent parent-_parent;parent-_parent cur;if (pparent nullptr){// parent 就是根节点_root cur;cur-_parent nullptr;}else{if (parent pparent-_left){pparent-_left cur;}else{pparent-_right cur;}cur-_parent pparent;}parent-_balance 0;cur-_balance 0;}
右单旋实现
主要步骤
1. 将 parent 的 left 链接到 cur 的 right
2.将 cur 的 left 链接到 parent
3. 维护其三叉链 //右单旋void RotateR(Node* parent){Node* cur parent-_left;Node* curRight cur-_right;parent-_left curRight;if (curRight){curRight-_parent parent;}cur-_right parent;Node* pparent parent-_parent;parent-_parent cur;if (pparent nullptr){// 说明 parent 是根节点_root cur;cur-_parent nullptr;}else{if (parent pparent-_left){pparent-_left cur;}else{pparent-_right cur;}cur-_parent pparent;}parent-_balance 0;cur-_balance 0;}
右左双旋实现
主要步骤
1. 对 cur 节点进行右旋
2. 对 parent 节点进行左旋
3. 修正平衡因子这个我们前面总结过了 void RotateRL(Node* parent){//先对 cur 节点进行右单旋//在对 parent 节点进行左单旋Node* cur parent-_right;Node* curLeft cur-_left;int balance curLeft-_balance;RotateR(cur);RotateL(parent);//旋转后维护平衡因子//这里右几种可能//1. curLeft 节点的平衡因子为 0//2. curLeft 节点的平衡因子为-1//3. curLeft 节点的平衡因子为 1// 这里发现每一次旋转结束后curRight 节点的左树给了parent右树给了 cur// 所以这里需要的以区分新增节点插入到了 curRight 节点的左是右// 记录该平衡因子主要是为了维护旋转后的平衡因子if (balance 0){// curRight 就是新增节点所以cur,parent,curRight 的平衡因子都为 0cur-_balance 0;parent-_balance 0;curLeft-_balance 0;}else if (balance 1){// 新增在了右边所以cur,parent,curRight 的平衡因子分别为 0-10cur-_balance 0;parent-_balance -1;curLeft-_balance 0;}else if (balance -1){// 新增在了左边所以cur,parent,curRight 的平衡因子分别为 100cur-_balance 1;parent-_balance 0;curLeft-_balance 0;}else{assert(0);}}
左右双旋实现
主要步骤
1. 对 cur 节点进行左旋
2. 对 parent 节点进行右旋
3. 修正平衡因子这个我们前面总结过了 // 左右双旋void RotateLR(Node* parent){Node* cur parent-_left;Node* curRight cur-_right;int balance curRight-_balance;RotateL(cur);RotateR(parent);if (balance 0){cur-_balance 0;parent-_balance 0;curRight-_balance 0;}else if (balance -1){cur-_balance 0;parent-_balance 1;curRight-_balance 0;}else if (balance 1){cur-_balance -1;parent-_balance 0;curRight-_balance 0;}}
