如何更好的建设和维护网站,如何购买网站域名,wordpress支付宝微信,医院的网络推广方案C 浅谈之 AVL 树和红黑树
HELLO#xff0c;各位博友好#xff0c;我是阿呆 #x1f648;#x1f648;#x1f648;
这里是 C 浅谈系列#xff0c;收录在专栏 C 语言中 #x1f61c;#x1f61c;#x1f61c;
本系列阿呆将记录一些 C 语言重要的语法特性 #x1f3…C 浅谈之 AVL 树和红黑树
HELLO各位博友好我是阿呆
这里是 C 浅谈系列收录在专栏 C 语言中
本系列阿呆将记录一些 C 语言重要的语法特性
OK兄弟们废话不多直接开冲 一 概述
AVL 树
上文提到对于二叉搜索树有单边树的缺陷那么对于 STL 关联容器 map、set 等底层结构对其进行了平衡处理采用平衡树实现
AVL 树当向二叉搜索树插入新结点后保证每个结点左右子树高度差绝对值不超过 1 降低树高度减少平均搜索长度 概念 AVL 树是空树或具有如下性质的二叉搜索树 ① 左右子树都是 AVL 树 ② 左右子树高度之差 ( 简称平衡因子 : 右子树高 - 左子树高 ) 绝对值不超过 1 一棵二叉搜索树高度平衡它就是 AVL 树。如果它有 n 个结点其高度可保持在 O(log2N)搜索时间复杂度 O(log2N) AVL 树节点定义
templateclass K,class V
struct AVLTreeNode
{AVLTreeNodeK, V* _left;AVLTreeNodeK, V* _right;AVLTreeNodeK, V* _parent;//定义成三叉链的形式int _bf;//balance factor平衡因子pairK, V _kv;//用pair同时存K和V两个数据AVLTreeNode(const pairK,V kv)//节点构造函数:_left(nullptr),_right(nullptr),_parent(nullptr),_bf(0)//平衡因子初始给0,_kv(kv){}
};AVL 树插入
AVL 树是在二叉搜索树基础上引入平衡因子插入过程如下
① 按照二叉搜索树方式找到空位置插入新节点
② 插入新节点后需要调整节点的平衡因子
③ 插入元素后可能导致 AVL 树左右子树高度不符合条件需要旋转 AVL 树旋转
AVL树的旋转分为多种具体举出一种如下图所示右单旋
Parent 平衡因子为 2 或 -2 分以下情况
① 平衡因子为 2说明右子树高需要往左边压高度设 Parent 右子树根为 SubR
当 SubR 平衡因子为 1 时执行左单旋
当 SubR 平衡因子为 -1 时执行右左双旋
② 平衡因子为 -2说明左子树高需要往右边压高度设 Parent 左子树根为 SubL
当 SubL 平衡因子为 -1 时执行右单旋
当 SubL 平衡因子为 1 时执行左右双旋
旋转完成后原 Parent 为根子树个高度降低已经平衡无需往上更新直接退出循环 AVL 树模拟实现
#pragma once
#includeiostream
#includeassert.h
#includestring
using namespace std;templateclass K,class V
struct AVLTreeNode
{AVLTreeNodeK, V* _left;AVLTreeNodeK, V* _right;AVLTreeNodeK, V* _parent;//定义成三叉链的形式int _bf;//balance factor平衡因子pairK, V _kv;//用pair同时存K和V两个数据AVLTreeNode(const pairK,V kv)//节点构造函数:_left(nullptr),_right(nullptr),_parent(nullptr),_bf(0)//平衡因子初始给0,_kv(kv){}
};templateclass K,class V
class AVLTree
{typedef AVLTreeNodeK, V Node;
public:AVLTree():_root(nullptr){}//拷贝构造和赋值拷贝也需要自己实现AVLTree(const AVLTreeK,V kv){_root Copy(kv._root);}AVLTreeK, V operator(AVLTreeK,V kv){swap(_root, kv._root);return *this;}~AVLTree(){Destroy(_root);_root nullptr;}Node* Copy(Node* root){if (root nullptr)return nullptr;Node* newroot new Node(root-_key);//建立新节点newroot-_left Copy(root-_left);//新节点的左右节点再去转换成子问题newroot-_right Copy(root-_right);return newroot;//最后返回新节点}void Destroy(Node* root){//利用后序遍历去释放节点if (root nullptr){return;}Destroy(root-_left);Destroy(root-_right);delete root;}V operator[](const K key)//重载operator[]{//operator[]的原则是://如果插入成功返回插入都value的引用//如果插入失败则返回V类型默认缺省值pairNode*, bool ret Insert(make_pair(key, V()));//V采用传匿名对象的方式return ret.first-_kv.second;}Node* Find(const pairK, V kv)//查找函数{Node* cur _root;while (cur){if (kv.first cur-_kv.first){cur cur-_right;}else if (kv.first cur-_kv.first){cur cur-_left;}else{return cur;}}return nullptr;}void RotateR(Node* parent)//右单旋{Node* subL parent-_left;Node* subLR subL-_right;parent-_left subLR;if (subLR ! nullptr)//注意:这里一定要判断不为空的因为下面可能会出现空指针的解引用{subLR-_parent parent;}subL-_right parent;Node* parentParent parent-_parent;//一定要在改变链接关系之前把这个指针存下来parent-_parent subL;//if (parentParent nullptr)或者采用这个条件也是可以的if(parent_root){_root subL;_root-_parent nullptr;}else{//这里注意:parent还有父母时链接之前需要注意判断到底是右孩子还是左孩子if (parentParent-_left parent)parentParent-_left subL;elseparentParent-_right subL;subL-_parent parentParent;//最后还要把父指针关系链接上}parent-_bf subL-_bf 0;//最后右单旋完成后平衡因子都要修改成0}void RotateL(Node* parent){Node* subR parent-_right;Node* subRL subR-_left;//先把subR的左孩子赋值给parent的右节点parent-_right subRL;if (subRL ! nullptr)//注意一定要判断是否为空的情况{subRL-_parent parent;//然后链接parent指针}//然后subR的左节点链接上parentsubR-_left parent;Node* parentParent parent-_parent;//提前记录parent-_parent subR;//if (parentParent nullptr)if (parent _root){_root subR;_root-_parent nullptr;}else{if (parentParent-_left parent)parentParent-_left subR;elseparentParent-_right subR;subR-_parent parentParent;}parent-_bf subR-_bf 0;}void RotateRL(Node* parent){Node* subR parent-_right;Node* subRL subR-_left;int bf subRL-_bf;//注意需要提前存subRL的平衡因子因为旋转可能引起改变//subRL的平衡因子是双旋的关键节点RotateR(parent-_right);//先进行右旋并注意旋转点为父节点的右节点RotateL(parent);//再进行左旋此时旋转点为父节点if (bf 0){parent-_bf 0;subR-_bf 0;subRL-_bf 0;}else if (bf 1){parent-_bf -1;subR-_bf 0;subRL-_bf 0;}else if (bf -1){parent-_bf 0;subR-_bf 1;subRL-_bf 0;}//注意这里处理完成过后sunRL的平衡因子一定都是等于0的else{assert(false);}}void RotateLR(Node* parent){Node* subL parent-_left;Node* subLR subL-_right;int bf subLR-_bf;RotateL(parent-_left);//先进行左旋并注意旋转点为父节点的左节点RotateR(parent);//再进行右旋此时旋转点为父节点if (bf 0){parent-_bf 0;subL-_bf 0;subLR-_bf 0;}else 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;}//注意这里处理完成过后sunRL的平衡因子一定都是等于0的else{assert(false);}}pairNode*,bool Insert(const pairK, V kv){if (_root nullptr)//根节点为空时先new一个新节点{_root new Node(kv);return make_pair(_root, true);}Node* cur _root;Node* parent nullptr;//先利用while循环去找cur的空位while (cur){if (kv.first cur-_kv.first){parent cur;cur cur-_right;}else if (kv.first cur-_kv.first){parent cur;cur cur-_left;}else{return make_pair(cur, false);}}//将cur插入到相应位置cur new Node(kv);Node* newnode cur;//用一个newnode记录一下新节点用以返回if (kv.first parent-_kv.first){parent-_right cur;//注意三叉链的链接逻辑顺序,等号左右方向不能反先把cur链接到父节点的右边cur-_parent parent;//然后再去把父指针知道父节点}else{parent-_left cur;cur-_parent parent;}//进行旋转调整//while(cur!_root)while (parent){//1.进入循环先对平衡因子进行调整if (cur parent-_right){parent-_bf;}else{parent-_bf--;}//分三种情况向上走if (parent-_bf 0)//平衡因子等于0不需要调整{//为什么不需调整//因为等于0的话说明底层子树高度不平衡添加进入新元素后平衡了只要平衡了高度并没发生变化不会影响上面的父节点break;}else if (parent-_bf -1 || parent-_bf 1){//平衡因子等于-1说明插入新节点后子树的高度不平衡了需要继续往上迭代查看父节点是否还满足平衡节点cur parent;parent parent-_parent;}else if (parent-_bf 2 || parent-_bf -2){if (parent-_bf -2)//父节点等于-2说明左边高触发右旋的情况{if (cur-_bf -1)//cur节点等于-1说明在cur的左边更高触发右单旋的情况{RotateR(parent);}else//cur等于-1,说明在cur的右边更高触发左右双旋{RotateLR(parent);}}else//父节点等于1说明右边更高触发左旋的情况{if (cur-_bf 1)//cur节点等于1时说明在cur的右边更高触发右单旋的情况{RotateL(parent);}else//cur等于-1,说明在cur的左边更高触发右左双旋{RotateRL(parent);}}//思考为什么上面在传参数的时候都是传parent的节点呢这样的好处是什么呢break;//调整完成后break退出循环//这里为什么调整完成过后就可以退出通过旋转调整平衡因子后parent节点的平衡因子都为0了调整过后不需要再向上继续查找了}else{assert(false);}}return make_pair(newnode,true);}void _Inorder(Node* root)//中序遍历打印每个节点{if (root nullptr)return;_Inorder(root-_left);cout root-_kv.first : root-_kv.second endl;_Inorder(root-_right);}void Inorder(){_Inorder(_root);cout endl;}//验证是否为平衡二叉树//1.左子树高度与右子树高度差必须小于1int _Height(Node* root)//求树的高度函数{if (root nullptr){return 0;}int leftHeight _Height(root-_left);//递归去子问题求解int rightHeight _Height(root-_right);return rightHeight leftHeight ? rightHeight 1 : leftHeight 1;}bool _IsBalance(Node* root){if (root nullptr){return true;}int leftHeight _Height(root-_left);int rightHeight _Height(root-_right);// 2.检查一下每颗树的平衡因子是否正确if (rightHeight - leftHeight ! root-_bf){cout 平衡因子异常: root-_kv.first endl;return false;}return abs(rightHeight - leftHeight) 2 _IsBalance(root-_left) _IsBalance(root-_right);//分别递归到各自的左右子树再去检查}bool IsAVLTree(){return _IsBalance(_root);}
private:Node* _root;
};二 核心
红黑树
红黑树的概念
一种二叉搜索树在每个结点上增加一个存储位表示结点颜色Red 或 Black。确保没有一条路径会比其他路径长 2 倍因而接近平衡 红黑树性质 红黑树的定义 每个结点不是红就是黑根节点是黑色一个节点是红则两个孩子是黑 ( 没有连续红节点 )每条路径上包含相同数量黑节点每个叶子结点都是黑 ( 此处指的是空结点即 NIL 节点 ) 为什么红黑树能保证最长路径中节点个数不会超过最短路径的两倍
假设黑节点数量 N 个最短路径为 logN最长路径为 2 * logN . 所以最长路径节点数不会超过最短路径的两倍 红黑树节点定义
enum Colour
{RED,BLACK
};//节点的颜色
templateclass K, class V
struct RBTreeNode
{RBTreeNodeK, V* _left;//节点左孩子RBTreeNodeK, V* _right;//节点右孩子RBTreeNodeK, V* _parent;//节点的父亲pairK, V _kv;//节点中存放的键值对Colour _col;//节点的颜色RBTreeNode(const pairK,V kv):_left(nullptr),_right(nullptr),_parent(nullptr),_kv(kv),_col(RED){}
};为什么节点默认颜色是红色
因为默认颜色黑色将破坏定义四其它每条路径都会因该路径增加一个黑节点而不满足红黑树性质这是一种全局的破坏默认颜色红色会破坏定义三但只会影响当前路径并不会对其它路径造成影响 红黑树插入操作 可分为两步 按照二叉搜索树规则插入新节点 检测新节点插入后红黑树性质是否造到破坏 如果父节点是黑色未违反红黑树任何性质则不需要调整
父节点为红色时违反了定义三不能有连在一起的红色节点
此时对红黑树有多种情况如下图为其中一种讨论 红黑树模拟实现
#pragma once
#includeiostream
using namespace std;enum Colour
{RED,BLACK
};//节点的颜色
templateclass K,class V
struct RBTreeNode
{RBTreeNodeK,V* _left;//节点左孩子RBTreeNodeK,V* _right;//节点右孩子RBTreeNodeK,V* _parent;//节点的父亲pairK,V _kv;//节点中存放的T类型的数据Colour _col;//节点的颜色RBTreeNode(const pairK,V kv):_left(nullptr),_right(nullptr),_parent(nullptr),_kv(kv),_col(RED){}
};templateclass K,class V
class RBTree
{typedef RBTreeNodeK, V Node;
public:RBTree():_root(nullptr){}//拷贝构造和赋值拷贝也需要自行实现这里不做赘述~RBTree(){Destory(_root);_root nullptr;}void Destory(Node* root){if (root nullptr){return;}//利用后序遍历释放节点Destory(root-_left);Destory(root-_right);delete root;}void RotateR(Node* parent)//右单旋{Node* subL parent-_left;Node* subLR subL-_right;parent-_left subLR;if (subLR ! nullptr)//注意:这里一定要判断不为空的因为下面可能会出现空指针的解引用{subLR-_parent parent;}subL-_right parent;Node* parentParent parent-_parent;//一定要在改变链接关系之前把这个指针存下来parent-_parent subL;//if (parentParent nullptr)或者采用这个条件也是可以的if (parent _root){_root subL;_root-_parent nullptr;}else{//这里注意:parent还有父母时链接之前需要注意判断到底是右孩子还是左孩子if (parentParent-_left parent)parentParent-_left subL;elseparentParent-_right subL;subL-_parent parentParent;//最后还要把父指针关系链接上}}void RotateL(Node* parent){Node* subR parent-_right;Node* subRL subR-_left;//先把subR的左孩子赋值给parent的右节点parent-_right subRL;if (subRL ! nullptr)//注意一定要判断是否为空的情况{subRL-_parent parent;//然后链接parent指针}//然后subR的左节点链接上parentsubR-_left parent;Node* parentParent parent-_parent;//提前记录parent-_parent subR;//if (parentParent nullptr)if (parent _root){_root subR;_root-_parent nullptr;}else{if (parentParent-_left parent)parentParent-_left subR;elseparentParent-_right subR;subR-_parent parentParent;}}pairNode*, bool Insert(const pairK, V kv){if (_root nullptr){_root new Node(kv);_root-_col BLACK;//根节点给黑色return make_pair(_root, true);}Node* cur _root;Node* parent nullptr;while (cur)//循环去找空位{if (kv.first cur-_kv.first){parent cur;cur cur-_right;}else if(kv.first cur-_kv.first){parent cur;cur cur-_left;}else{return make_pair(cur, false);}}Node* newnode new Node(kv);newnode-_col RED;//链接上新节点if (kv.first parent-_kv.first){parent-_right newnode;newnode-_parent parent;}else{parent-_left newnode;newnode-_parent parent;}cur newnode;//父节点存在且父节点为红色时需要继续处理while (parent parent-_col RED){Node* grandfather parent-_parent;//关键看叔叔的脸色if (parent grandfather-_left){Node* uncle grandfather-_right;if (uncle uncle-_col RED){//具体变色的情况需要画图分析:grandfather-_col RED;parent-_col uncle-_col BLACK;//注意需要继续向上处理,容易忘记cur grandfather;parent cur-_parent;}else{if (cur parent-_left){RotateR(grandfather);//右单旋parent-_col BLACK;grandfather-_col RED;}else{RotateL(parent);//先以父节点为旋转点左旋RotateR(grandfather);//再以g为旋转点右旋cur-_col BLACK;grandfather-_col RED;}break;//旋转变色过后一定是满足所有性质的直接退出循环}}else{Node* uncle grandfather-_left;if (uncle uncle-_col RED){uncle-_col parent-_col BLACK;grandfather-_col RED;cur grandfather;parent cur-_parent;}else // 情况2 情况3{if (cur parent-_right){RotateL(grandfather);parent-_col BLACK;grandfather-_col RED;}else // cur parent-_left{RotateR(parent);RotateL(grandfather);cur-_col BLACK;grandfather-_col RED;}break;}}}_root-_col BLACK;return make_pair(newnode, true);}void _InOrder(Node* root)//中序遍历递归打印{if (root nullptr){return;}_InOrder(root-_left);cout root-_kv.first :root-_kv.secondendl;_InOrder(root-_right);}void InOrder(){_InOrder(_root);cout endl;}bool _CheckBlance(Node* root, int blackNum, int count)//balckNum相当于一个标尺count就是用来记录每条路径的黑节点数目{if (root nullptr)//如果root走到空节点{if (count ! blackNum)//count不等于最左路径的黑色节点数{cout 黑色节点的数量不相等 endl;return false;//返回假}return true;//否则返回真}if (root-_col RED root-_parent-_col RED){cout 存在连续的红色节点 endl;return false;}if (root-_col BLACK){count;}return _CheckBlance(root-_left, blackNum, count) _CheckBlance(root-_right, blackNum, count);//再递归到各子树的子问题}bool CheckBlance(){if (_root nullptr){return true;}if (_root-_col RED){cout 根节点是红色的 endl;return false;}// 找最左路径做黑色节点数量参考值int blackNum 0;Node* left _root;while (left){if (left-_col BLACK){blackNum;}left left-_left;}int count 0;return _CheckBlance(_root, blackNum, count);}
private:Node* _root;
};红黑树与 AVL 树比较
都是高效平衡二叉树增删改查时间复杂度都是 O( log2N) 红黑树不追求绝对平衡其只需保证最长路径不超过最短路径 2 倍降低了插入和旋转次数所以在经常进行增删结构中性能比 AVL 树更优而且红黑树实现比较简单所以实际运用中红黑树更多 三 结语
身处于这个浮躁的社会却有耐心看到这里你一定是个很厉害的人吧
各位博友觉得文章有帮助的话别忘了点赞 关注哦你们的鼓励就是我最大的动力
博主还会不断更新更优质的内容加油吧技术人
