青岛做网站eoe,石家庄最新今天的消息,企业网站设计优化公司,关键词优化是什么意思前言
对于之前普通的二叉搜索树#xff0c;其搜索的效率依靠树的形状来决定#xff0c;如下#xff1a; 可以看到 A图 中的树比较彭亨#xff0c;搜索一个元素的效率接近 O(logN) #xff1b;而 B图 中的形状也符合搜索二叉树#xff0c;但是很不平衡#xff0c;这时的… 前言
对于之前普通的二叉搜索树其搜索的效率依靠树的形状来决定如下 可以看到 A图 中的树比较彭亨搜索一个元素的效率接近 O(logN) 而 B图 中的形状也符合搜索二叉树但是很不平衡这时的搜索效率就变成 O(N) 了如搜索值为4的节点 可以看到如果搜索二叉树不平衡他的搜索的效率不确定在 O(logN) 和 O(N) 之间可能有暴击 那么对此既然不平衡那我们就给出平衡的两种方法
1.构成AVL树
2.构成红黑树
这两种方法都是为了平衡搜索二叉树而生 AVL树 1. AVL树的概念和性质
它的出现是为了 搜索二叉树的平衡那就来了解AVL树的概念和性质也就是什么是AVL并且作为一颗AVL树的要求是什么
首先AVL树是一颗树它要求任何一个节点的左右子树的高度差不超过一以此来保证平衡是AVL树的核心
来看看它的做法
与搜索二叉树不同它将二叉链变成了三叉链多了指向父节点的指针并且引入了平衡因子这个东西这些都是为了方便并且为了树的一个平衡引入
三叉链和平衡因子和下面AVL树属性的图结合起来看更直观
三叉链也就是多了一个 parent指针 指向该节点的父节点这一操作可以让节点找到其祖先
平衡因子是指该节点的 右子树高度 减去 左子树高度的值而根据AVL树的性质要求任何一个节点的左右子树的高度差不超过一也就是平衡因子 _bf 的值域为 { -1, 0, 1 } 如果平衡因子 _bf 的值出现为 2 或者 -2 说明该树已经不平衡此时需要进行停止调整先进行旋转操作 2. AVL树类的属性
这里的节点值类型简化为了int类型原为 pair 3. AVL树的插入函数
而AVL树的重点呢也就是AVL树是如何让树达到平衡的呢就是每插入了一个节点后进行了一些调整如果插入节点后不平衡那么会将其调整成平衡
插入后对插入节点祖先的平衡因子进行调整当调整过程中有平衡因子出现异常时此时通过旋转的方式让树继续保持平衡
当平衡因子出现异常即是 平衡因子的值更新为 2 或者 -2 时说明树现在已经不平衡需要进行旋转
分情况讨论 现在平衡因子已经出现了不平衡为什么旋转之后树就可以继续平衡呢
具体看到旋转 这里以左单旋为例
定义节点指针 parent图中的节点值为30 cur图中的60
左单旋是将 cur 的左孩子给给 parent 的右 再把 parent 赋值给 cur 的左旋转完成
再进行平衡因子的更新parent 和 cur 的平衡因子 _bf 都变成 0 左单旋具体代码如下 void RotateL(Node* parent){assert(parent);Node* cur parent-_right;Node* cur_left cur-_left;// 改变节点之间的关系parent-_right cur_left;cur-_left parent;// 改变_parent的指向//原本 parent 的 _parentNode* ppNode parent-_parent;//若原本 ppNode原本 parent 的 _parent为空说明parent原本不是根现需把 ppNode 给到 cur 的 _parent并且把 ppNode 的子更新为 curif (ppNode){if (ppNode-_left parent){ppNode-_left cur;}else{ppNode-_right cur;}cur-_parent ppNode;}//若原本 parent-_parent 为空说明parent原本是根现需把_root更新为根else{_root cur;cur-_parent nullptr;}if (cur_left){cur_left-_parent parent;}parent-_parent cur;// 更新平衡因子cur-_bf parent-_bf 0;}
对左单旋的总结是当不平衡的树进行左单旋之后树又被调整为平衡然后再进行平衡因子的更新 那么右单旋的思路是一样的自己可以进行推理 而要进行双旋时候可以再进行讨论这里以右左旋进行讨论 右左旋定义 parent下图节点值为30 cur下图节点值为90 cur_left下图节点值为60
双旋都是两大步这里右左旋就是先进行右旋再进行左旋旋转结束对这里对刚刚实现的单旋代码进行了复用复用yyds
具体是对 cur 先进行右旋再对 parent 进行左旋如下 最后进行平衡因子的调整但是这里特别容易忘记第三种情况的讨论AVL树的这个细节得注意 右左旋的代码如下 void RotateRL(Node* parent){Node* cur parent-_right;Node* cur_left cur-_left;int bf cur_left-_bf;RotateR(parent-_right);RotateL(parent);parent-_bf 0;cur-_bf 0;cur_left-_bf 0;if (bf -1){cur-_bf 1;}if (bf 1){parent-_bf -1;}} 那么左右旋的思路是一样的自己可以进行推理 4. 总结
而进行何种旋转本质是取决于 parent cur 和 cur_left 或cur_right之间的关系若他们三个所连成的是直线那么进行单旋操作如果为折线那就进行双旋操作而这里的平衡因子刚好可以体现他们之间的关系所以上图中根据平衡因子来决定单双旋和左右旋转 AVL树构造和插入函数测试函数
这里的节点值类型简化为了int类型原为 pair
#pragma once#include iostreamusing namespace std;#include string#include array#include deque#include list#include map#include queue#include set#include stack#include unordered_map#include unordered_set#include vector#include algorithm#include assert.h#include windows.h#include ctimenamespace zhuandrong
{class AVLTreeNode{typedef AVLTreeNode Node;public:int _val;Node* _left;Node* _right;Node* _parent;int _bf;public:AVLTreeNode(const int val 0): _val(val), _left(nullptr), _right(nullptr), _parent(nullptr), _bf(0){}};class AVLTree{typedef AVLTreeNode Node;protected:void RotateL(Node* parent){assert(parent);Node* cur parent-_right;Node* cur_left cur-_left;// 改变节点之间的关系parent-_right cur_left;cur-_left parent;// 改变_parent的指向//原本 parent 的 _parentNode* ppNode parent-_parent;//若原本 ppNode原本 parent 的 _parent为空说明parent原本不是根现需把 ppNode 给到 cur 的 _parent并且把 ppNode 的子更新为 curif (ppNode){if (ppNode-_left parent){ppNode-_left cur;}else{ppNode-_right cur;}cur-_parent ppNode;}//若原本 parent-_parent 为空说明parent原本是根现需把_root更新为根else{_root cur;cur-_parent nullptr;}if (cur_left){cur_left-_parent parent;}parent-_parent cur;// 更新平衡因子cur-_bf parent-_bf 0;}//void RotateL(Node* parent)//{// Node* cur parent-_right;// Node* cur_left cur-_left;// parent-_right cur_left;// cur-_left parent;// Node* ppNode parent-_parent;// if (cur_left)//右孩子可能存在也可能不存在所以需要判断需要在parent改变前判断// {// cur_left-_parent parent;// }// parent-_parent cur;// if (parent _root)//parent可能是根节点也可能不是根节点// {// _root cur;// cur-_parent nullptr;// }// else// {// if (ppNode-_left parent)// {// ppNode-_left cur;// }// else// {// ppNode-_right cur;// }// cur-_parent ppNode;// }// cur-_bf parent-_bf 0;//将平衡因子调整//}void RotateR(Node* parent){assert(parent);Node* cur parent-_left;Node* cur_right cur-_right;// 改变节点之间的关系parent-_left cur_right;cur-_right parent;// 改变_parent的指向//原本 parent 的 _parentNode* ppNode parent-_parent;//若原本 ppNode原本 parent 的 _parent为空说明parent原本不是根现需把 ppNode 给到 cur 的 _parent并且把 ppNode 的子更新为 curif (ppNode){if (ppNode-_left parent){ppNode-_left cur;}else{ppNode-_right cur;}cur-_parent ppNode;}//若原本 parent-_parent 为空说明parent原本是根现需把_root更新为根else{_root cur;cur-_parent nullptr;}if (cur_right){cur_right-_parent parent;}parent-_parent cur;// 更新平衡因子cur-_bf parent-_bf 0;}//void RotateR(Node* parent)//{// Node* cur parent-_left;// Node* curRight cur-_right;// parent-_left curRight;// cur-_right parent;// Node* ppNode parent-_parent;// if (curRight)//右孩子可能存在也可能不存在所以需要判断需要在parent改变前判断// {// curRight-_parent parent;// }// parent-_parent cur;// if (parent _root)//parent可能是根节点也可能不是根节点// {// _root cur;// cur-_parent nullptr;// }// else// {// if (ppNode-_left parent)// {// ppNode-_left cur;// }// else// {// ppNode-_right cur;// }// cur-_parent ppNode;// }// cur-_bf parent-_bf 0;//将平衡因子调整//}void RotateRL(Node* parent){Node* cur parent-_right;Node* cur_left cur-_left;int bf cur_left-_bf;RotateR(parent-_right);RotateL(parent);/*parent-_bf cur_left-_bf 0;cur-_bf flag;*/parent-_bf 0;cur-_bf 0;cur_left-_bf 0;if (bf -1){cur-_bf 1;}if (bf 1){parent-_bf -1;}}void RotateLR(Node* parent){Node* cur parent-_left;Node* cur_right cur-_right;int bf cur_right-_bf;RotateL(parent-_left);RotateR(parent);/*parent-_bf parent-_parent-_bf 0;parent-_parent-_left-_bf -1;*/cur-_bf 0;parent-_bf 0;cur_right-_bf 0;if (bf 1){cur-_bf -1;}if (bf -1){parent-_bf 1;}}protected:Node* _root;public:AVLTree(): _root(nullptr){}AVLTree(vectorint v){for (auto e : v){if (e 8){int i 0;}insert(e);assert(IsBalance());}}bool insert(int val){// 判断是否有根节点if (_root){//先找到合适的插入位置Node* cur _root;Node* parent nullptr;while (cur){if (val cur-_val){parent cur;cur cur-_left;}else if (val cur-_val){parent cur;cur cur-_right;}else{cout 插入的元素值已重复 endl;return false;}}cur new Node(val);cur-_parent parent;if (val parent-_val){parent-_left cur;}else{parent-_right cur;}//对平衡因子进行更新while (parent){if (cur parent-_left){--parent-_bf;}else if (cur parent-_right){parent-_bf;}//若 parent-_bf 0表明平衡因子调整结束if (!parent-_bf){break;}else if (parent-_bf 1 || parent-_bf -1){cur parent;parent parent-_parent;}//若parent-_bf 2 cur-_bf 1将parent进行左单旋else if (parent-_bf 2 cur-_bf 1){RotateL(parent);break;}//若parent-_bf 2 cur-_bf -1将parent进行右左单旋else if (parent-_bf 2 cur-_bf -1){RotateRL(parent);break;}//若parent-_bf -2 cur-_bf -1将parent进行右单旋else if (parent-_bf -2 cur-_bf -1){RotateR(parent);break;}//若parent-_bf -2 cur-_bf 1将parent进行左右单旋else if (parent-_bf -2 cur-_bf 1){RotateLR(parent);break;}else{assert(false);}}}else{_root new Node(val);}return true;}int TreeHight(Node* root){if (root nullptr)return 0;int leftHight TreeHight(root-_left);int rightHight TreeHight(root-_right);return leftHight rightHight ? leftHight 1 : rightHight 1;}void Inorder(){_Inorder(_root);}bool IsBalance(){return _IsBalance(_root);}private:void _Inorder(Node* root){if (root nullptr)return;_Inorder(root-_left);cout root-_val endl;_Inorder(root-_right);}bool _IsBalance(Node* root){if (root nullptr)return true;int leftHight TreeHight(root-_left);int rightHight TreeHight(root-_right);//检查平衡因子对不对if (rightHight - leftHight ! root-_bf){cout 平衡因子出现异常 endl;cout rightHight - leftHight endl;return false;}//需要递归检查是否平衡return (leftHight - rightHight 1 leftHight - rightHight -1) _IsBalance(root-_left) _IsBalance(root-_right);}};void test_AVLTree(){/*vectorint v { 6, 4, 32, 2, 7, 8 };AVLTree avl_tree(v);assert(avl_tree.IsBalance());*/AVLTree avl_tree;srand((unsigned int)time(NULL));for (int i 1000; i 0; --i){avl_tree.insert(rand());//avl_tree.insert(i);assert(avl_tree.IsBalance());}//srand((unsigned int)time(0));//const size_t N 10000;//for (size_t i 0; i N; i)//{// size_t x rand();// avl_tree.insert(x);// //cout t.IsBalance() endl;//}//avl_tree.Inorder();//cout avl_tree.IsBalance() endl;}} 红黑树 1. 红黑树的概念和性质什么是红黑树并且作为一颗红黑树的要求 以上是红黑树的概念和性质在红黑树里不仅仅要考虑 cur 、curleft 、 parent 还要引入 grandfather具体为什么看到后面就知道了 2. 红黑树类的属性
是使用枚举枚举出 红 黑 两种情况 3. 红黑树的插入函数 还是分情况讨论 4. 总结
根据性质可以分为以下情况
可以看出第一种情况uncle存在且为黑只需要变色即可在看是否继续向上调整
第二种情况就要旋转了而如何旋转本质图中也详细说了取决于 grandfather、parent、cur 之间的关系其实AVL树的旋转的决定因素也在此只是转换成平衡因子进行描述 关于红黑具体的思想关键体现在插入函数中复习请自行分析出两种大情况和情况二的细分然后写出插入函数才算过关 总体代码
#pragma once#include iostreamusing namespace std;#include string#include array#include deque#include list#include map#include queue#include set#include stack#include unordered_map#include unordered_set#include vector#include algorithm#include assert.h#include windows.h#include ctimenamespace zhuandrong
{enum Color{RED,BLACK};templatetypename K, typename Tclass RBTreeNode{typedef RBTreeNode Node;public:pairK, T _t;Node* _left;Node* _right;Node* _parent;Color color;public:RBTreeNode(pairK, T t): _t(t), _left(nullptr), _right(nullptr), _parent(nullptr), color(RED){}};templatetypename K, typename Tclass RBTree{typedef RBTreeNodeK, T Node;protected:Node* _root;protected:void RotateL(Node* parent){assert(parent);Node* cur parent-_right;Node* cur_left cur-_left;// 改变节点之间的关系parent-_right cur_left;cur-_left parent;// 改变_parent的指向//原本 parent 的 _parentNode* ppNode parent-_parent;//若原本 ppNode原本 parent 的 _parent为空说明parent原本不是根现需把 ppNode 给到 cur 的 _parent并且把 ppNode 的子更新为 curif (ppNode){if (ppNode-_left parent){ppNode-_left cur;}else{ppNode-_right cur;}cur-_parent ppNode;}//若原本 parent-_parent 为空说明parent原本是根现需把_root更新为根else{_root cur;cur-_parent nullptr;}if (cur_left){cur_left-_parent parent;}parent-_parent cur;}void RotateR(Node* parent){assert(parent);Node* cur parent-_left;Node* cur_right cur-_right;// 改变节点之间的关系parent-_left cur_right;cur-_right parent;// 改变_parent的指向//原本 parent 的 _parentNode* ppNode parent-_parent;//若原本 ppNode原本 parent 的 _parent为空说明parent原本不是根现需把 ppNode 给到 cur 的 _parent并且把 ppNode 的子更新为 curif (ppNode){if (ppNode-_left parent){ppNode-_left cur;}else{ppNode-_right cur;}cur-_parent ppNode;}//若原本 parent-_parent 为空说明parent原本是根现需把_root更新为根else{_root cur;cur-_parent nullptr;}if (cur_right){cur_right-_parent parent;}parent-_parent cur;}void RotateRL(Node* parent){RotateR(parent-_right);RotateL(parent);}void RotateLR(Node* parent){RotateL(parent-_left);RotateR(parent);}public:RBTree(): _root(nullptr){}RBTree(vector pairK, T v){for (auto e : v){if (e.second 5){int i 0;}insert(e);}}bool insert(const pairK, T t){// 先判断根节点是否为空if (_root){// 若不为空先找到合适的插入位置Node* cur _root;Node* parent nullptr;while (cur){if (t.second cur-_t.second){parent cur;cur cur-_left;}else if (t.second cur-_t.second){parent cur;cur cur-_right;}else{//cout 该元素已经插入请重试 endl;return false;}}//找到该位置后进行插入并且链接关系cur new Node(t);cur-_parent parent;if (t.second parent-_t.second){parent-_left cur;}else{parent-_right cur;}// 进行调整while (parent parent-color RED){Node* grandfather parent-_parent;Node* uncle nullptr;if (parent grandfather-_left){uncle grandfather-_right;}else{uncle grandfather-_left;}// 第一种情况如果uncle存在且为红if (uncle uncle-color RED){//将p和u变黑g变红parent-color uncle-color BLACK;grandfather-color RED;//更新并且判断更新后的parent是否为根不为根就继续调整为根表明调整结束cur grandfather;parent cur-_parent;if (parent _root){break;}}// 第二种情况如果uncle存在且为黑色或者uncle不存在else{// 当 cur 为 parent 的左孩子时if (parent-_left cur){if (grandfather-_left parent){// g// p u// c//Node* uncle grandfather-_right;RotateR(grandfather);grandfather-color cur-color RED;parent-color BLACK;}else{// g g c// u p -- u c -- g p// c p u//Node* uncle grandfather-_left;RotateRL(grandfather);grandfather-color parent-color RED;cur-color BLACK;}}// 当 cur 为 parent 的右孩子时else{if (grandfather-_right parent){// g // u p // c//Node* uncle grandfather-_right;RotateL(grandfather);grandfather-color cur-color RED;parent-color BLACK;}else{// g g c// p u -- c u -- p g// c p u//Node* uncle grandfather-_left;RotateLR(grandfather);grandfather-color parent-color RED;cur-color BLACK;}}break;}}}// 若为空则该元素作为根节点else{_root new Node(t);}_root-color BLACK;return true;}bool judge_color(Node* root, int blacksum, int blacknum){if (!root){if (blacknum ! blacksum){return false;}return true;}if (root-color BLACK){blacknum;}if (root-color RED root-_parent root-_parent-color RED){return false;}return judge_color(root-_left, blacksum, blacknum) judge_color(root-_right, blacksum, blacknum);}bool isBalance(){if (!_root){cout 根为空 endl;return false;}if (_root-color RED){cout 根的颜色为红色非法 endl;return false;}Node* cur _root;int blacksum 0;while (cur){if (cur-color BLACK){blacksum;}cur cur-_right;}return judge_color(_root, blacksum, 0);}};void test_RBTree(){/*vectorpairint, int v;v.push_back(make_pair(1, 13));v.push_back(make_pair(2, 8));v.push_back(make_pair(3, 17));v.push_back(make_pair(4, 1));v.push_back(make_pair(5, 11));v.push_back(make_pair(6, 15));v.push_back(make_pair(7, 25));v.push_back(make_pair(8, 6));v.push_back(make_pair(9, 22));v.push_back(make_pair(10, 27));v.push_back(make_pair(11, 5));RBTreeint, int rb_tree(v);cout rb_tree.isBalance() endl;*/RBTreeint, int rb_tree;srand((unsigned int)time(NULL));for (int i 0; i 1000; i){rb_tree.insert(make_pair(i, rand()));}if (rb_tree.isBalance()){cout 本次测试成功 endl;}else{cout 本次测试失败 endl;}}}
