宁波做网站的专业公司,个人网站包含哪些内容,自媒体135软件,做的网站适应屏幕大小目录
前言#xff1a;
1 左右旋
2 右左旋
3 部分细节补充
3.1 单旋和插入
3.2 部分小函数 前言#xff1a;
AVL树作为一种结构#xff0c;理解树的本身是不大难的#xff0c;难的在于#xff0c;树旋转之后的连接问题#xff0c;写AVL树的代码大部分都是在旋转部分…目录
前言
1 左右旋
2 右左旋
3 部分细节补充
3.1 单旋和插入
3.2 部分小函数 前言
AVL树作为一种结构理解树的本身是不大难的难的在于树旋转之后的连接问题写AVL树的代码大部分都是在旋转部分所以连接问题是比较需要细心的那么这里来说呢把细心做好变量的位置放好连接的次序连接对就成功了。 1 左右旋
前文提及什么情况下需要左右旋即不是纯粹的左边高或者是右边高那么使用到左右旋的情况如下 如果我们固执的以为在b 或者 c插入数据之后90的平衡因子变为了-2右旋就能解决问题的话就完蛋啦这里我们直接对90右旋之后结果就是镜像的树还是没有平衡那么我们再左旋相当于旋转回来了整个树的结果是没有变的。
此时就需要左旋转后再右旋转可能有人会问这个图是什么意思我们使用的是抽象图来介绍这样更加方便长方形代表的就是高度为多少的子树。
选择b c作为例子当我们往b c插入数据的时候90的平衡因子变为了-2此时parent就是90那么我们需要一个操作让该树变成完全的左子树高这样再右旋转才可以保持平衡那么如何变成完全的左子树高呢?
记住那两个线30 -90 30 -60的这两条线只要60在30和90的中间就是完全的左子树高所以我们需要对30进行左旋所以现在已知的操作就是先左旋再右旋要记得参数不是一样的。
旋转的问题很好解决旋转中的问题可不止旋转这里还有平衡因子的问题我们不难发现在b 或者 c插入数据之后平衡因子的改变不是一样的甚至来说如果h 1即60是新插入的平衡因子的改变也是不一样的。
所以平衡因子的变化可以分为三个情况一是b插入二是c插入三是60是新插入的其中平衡因子的变化就留给读者自己发现啦这是比较简单的所以代码就可以出来了
void RotateLR(Node* parent)
{Node* subL parent-_left;Node* subLR subL-_right;int bf subLR-_bf;//先左旋 再右旋RotateL(subL);RotateR(parent);//更新平衡因子if (bf 1){subL-_bf -1;subLR-_bf 0;parent-_bf 0;}else if(bf -1){subL-_bf 0;subLR-_bf 0;parent-_bf 1;}//60自己就是新插入的节点else if(bf 0){subL-_bf 0;subLR-_bf 0;parent-_bf 0;}else{assert(false);}
我们知道以某个节点作为平衡节点平衡之后该节点的父节点平衡因子必定为0所以我们可以把subLR 0直接提取出来。所以双旋来说是很简单甚至比单旋都简单。 2 右左旋
有了左右旋的基础这里直接就给代码了 void RotateRL(Node* parent){Node* subR parent-_right;Node* subRL subR-_left;int bf subRL-_bf;//旋转完成RotateR(subR);RotateL(parent);//更新平衡因子subRL-_bf 0;//RL必平衡if (bf 1){subR-_bf 0;parent-_bf -1;}else if (bf -1){parent-_bf 0;subR-_bf 1;}else if (bf 0){parent-_bf 0;subR-_bf 0;}else{assert(false);}} 3 部分细节补充
是不是以为AVL树到这里就要结束了
错辣还有许多细节要注意
3.1 单旋和插入
单旋这里除了要注意旋转的时候的连接问题还要注意变量的声明次序问题 Node* subL parent-_left;Node* subLR subL-_right;subL-_right parent;parent-_left subLR;Node* pparent parent-_parent;parent-_parent subL;
以右旋为例子当parent节点不是根节点势必涉及到parent的父节点的连接问题所以我们先声明了pparent如果我们在这个if里面声明
if (parent _root){_root subL;_root-_parent nullptr;}else{if (parent pparent-_left){pparent-_left subL;}else{pparent-_right subL;}subL-_parent pparent;}
在此之前pparent的值就已经变为了subL所以pparent一定要在parent-_parent subL之前声明了。
其次插入这里
//更新平衡因子
cur-_parent parent;
while (parent)
{if (parent-_left cur){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){//右单旋if (parent-_bf -2 cur-_bf -1){RotateR(parent);}//左单旋else if (parent-_bf 2 cur-_bf 1){RotateL(parent);}else if (parent-_bf 2 cur-_bf -1){RotateRL(parent);}else if (parent-_bf -2 cur-_bf 1){RotateLR(parent);}break;}else{//理论而言不可能出现这种情况assert(false);}
}
为什么旋转之后就要break了呢按道理来说比如双旋之后parent的位置必然改变可能直接变成了叶子节点如果再走循环平衡因子必然改变此时树的结构就被破坏了所以一定要break了。
现在解释上文说的为什么旋转之后比如单旋平衡因子一定变为0了这里我们就借助抽象图来理解具象图没有那么好理解 以这个图作为例子c插入数据之后n成为了新的根节点此时左子树的高度是 h(m) h h 1右子树的高度是h 11是新插入的数据所以平衡因子必定为0该结论在左右双旋里面也有体现。
3.2 部分小函数
这里的函数就是用来测试的函数没有什么值得特别注意的 void InOrder(){_InOrder(_root);cout endl;}bool IsBalance(){return _IsBalance(_root);}int Height(){return _Height(_root);}int Size(){return _Size(_root);}private:void _InOrder(Node* root){if (root nullptr)return;_InOrder(root-_left);cout root-_kv.first ;_InOrder(root-_right);}int _Size(Node* root){return root nullptr ? 0 : _Size(root-_left) _Size(root-_right) 1;}int _Height(Node* root){if (root nullptr)return 0;return max(_Height(root-_left), _Height(root-_right)) 1;}bool _IsBalance(Node* root){if (root nullptr)return true;int leftHeight _Height(root-_left);int rightHeight _Height(root-_right);// 不平衡if (abs(leftHeight - rightHeight) 2){cout root-_kv.first endl;return false;}// 顺便检查一下平衡因子是否正确if (rightHeight - leftHeight ! root-_bf){cout root-_kv.first endl;return false;}return _IsBalance(root-_left) _IsBalance(root-_right);}
测试代码
void TestAVLTree1()
{int arr[] { 8, 3, 1, 10, 6, 4, 7, 14, 13 };//int arr[] { 4, 2, 6, 1, 3, 5, 15, 7, 16, 14 };AVLTreeint, int t1;for (auto e : arr){if (e 13){int i 0;}t1.Insert({ e,e });cout Insert: e - t1.IsBalance() endl;}t1.InOrder();cout t1.IsBalance() endl;
}void TestAVLTree2()
{const int N 100000000;vectorint v;v.reserve(N);srand((unsigned)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));cout Insert: e - t.IsBalance() endl;}size_t end2 clock();cout Insert: end2 - begin2 endl;cout Height: t.Height() endl;cout Size: t.Size() endl;size_t begin1 clock();// 确定在的值for (auto e : v){t.Find(e);}//随机值for (size_t i 0; i N; i){t.Find((rand() i));}size_t end1 clock();cout Find: end1 - begin1 endl;
}
下场剧透~因为AVL树的查找实在太快但是对于平衡因子的控制要求太严格了所以红黑树出现了红黑树是一种近似平衡的结构~ 感谢阅读
