企业服务工作站,网站代备案公司名称,台州椒江网站建设,久久建筑网怎么赚金币目录 一、认识红黑树1.1 概念1.2 定义 二、实现红黑树2.1 插入2.2 与AVL树对比 一、认识红黑树
1.1 概念
红黑树是一个二叉搜索树#xff0c;与AVL树相比#xff0c;红黑树不再使用平衡因子来控制树的左右子树高度差#xff0c;而是用颜色来控制平衡#xff0c;颜色为红色… 目录 一、认识红黑树1.1 概念1.2 定义 二、实现红黑树2.1 插入2.2 与AVL树对比 一、认识红黑树
1.1 概念
红黑树是一个二叉搜索树与AVL树相比红黑树不再使用平衡因子来控制树的左右子树高度差而是用颜色来控制平衡颜色为红色或者黑色。控制任意一条从根到叶子节点的路径的节点颜色就可以确保没有一条路径会比其他路径长出俩倍因而是接近平衡的。 红黑树的规则
根节点是黑色的不能有连续的红色节点从某个节点出发每条路径上的黑色节点的数量相同
1.2 定义
红黑树也是三叉链结构左指针、右指针和父亲指针有一个新的存储位来记录节点的颜色这里实现的红黑树是kv模型。
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)//默认的新节点都是红色的{}
};二、实现红黑树
2.1 插入
红黑树的插入的与普通二叉搜索树的插入逻辑是一样的不同的是插入新节点后要进行变色处理符合前面的规则才行。 红黑树的插入一共分为两大类
新插入的节点的父节点是黑色的插入结束新插入的节点的父节点是红色的要变色处理
也就是说要看新插入的节点的父节点的颜色来确定是否本次插入结束。但是有个问题新插入的节点说什么颜色的其实看图就可以知道插入的新节点必须是红色的因为如果插入的是黑色节点那么必然会导致每条路径上的黑色节点数量不相同违反规则。
接下来看红黑树插入节点时是怎样变色的 首先按照前面插入的两大类如果插入节点的父节点是黑色的就不需要进入变色调整反之如果插入节点的父节点存在且是红色的说明此时有连续的红色节点要变色处理。
这里需要定义几个节点的名字方便叙述和画图
ccur——当前新插入的节点pparent——插入节点的父节点ggrandfather——父节点的父节点uuncle——叔叔节点父节点的另一边的节点 这4个节点主要看叔叔节点根据叔叔节点分为两种情况。
情况一叔叔存在且为红 p和u要变成黑色g变成红色。如果g不是根节点要向上更新把g当成c如果g是根节点要把g变成黑色的因为根节点必须是黑的。
1️⃣g是根节点 注意不管p或者u是g的左边还是右边都是一样的c在p的左边/右边都是一样的操作不影响。 2️⃣g不是根节点
情况二叔叔不存在或者叔叔存在且为黑
情况二里面又有4种变色方式其实与其说是变色方式不如直接说是旋转方式不同然后根据旋转情况来变色
1️⃣p是g的左孩子c是p的左孩子 进行右单旋p变黑g变红 上图的c不是新增表示的是当它的叔叔节点u存在且为黑时的c不是新增。 注意 这里u存在或者不存在也有两种情况第一张图的c是新增的节点u必然是不存在的如果存在会导致每条路径的黑色节点数量不相同同理第二张图的c刚开始是黑色的节点它有自己的子树是通过后面的向上变色处理才变红的所以第二张图的u是必须存在的。总之一句话u存不存在要符合规则 后面就以u不存在的情况处理 2️⃣p是g的右孩子c是p的右孩子 进行左单旋p变黑g变红
3️⃣p是g的左孩子c是p的右孩子 先左单旋§再右单旋(g)g变红c变黑
4️⃣p是g的右孩子c是p的左孩子 先右单旋§再左单旋(g)g变红c变黑 代码
//插入
bool Insert(const pairK, V kv)
{//为空if (_root nullptr){_root new Node(kv);_root-_col BLACK;//根节点都是黑色的特殊处理return true;}//非空Node* cur _root;Node* parent nullptr;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 parent-_col RED){Node* grandfather parent-_parent;//爷爷节点//父节点在爷爷节点的左边那么叔叔节点在右边if (parent grandfather-_left){Node* uncle grandfather-_right;//情况一叔叔存在且为红if (uncle uncle-_col RED){grandfather-_col RED;uncle-_col parent-_col BLACK;cur grandfather;//爷爷不是根向上更新parent cur-_parent;}//情况二叔叔不存在/存在且为黑else{//单旋if (cur parent-_left){RotateR(grandfather);//右单旋parent-_col BLACK;//变色grandfather-_col RED;}//左右双旋 // cur parent-_rightelse{RotateL(parent);//先左单旋RotateR(grandfather);//再右单旋grandfather-_col RED;//变色cur-_col BLACK;}}}else//父节点在右边叔叔在左边{Node* uncle grandfather-_left;//情况一叔叔存在且为红if (uncle uncle-_col RED){grandfather-_col RED;uncle-_col parent-_col BLACK;cur grandfather;//爷爷不是根向上更新parent cur-_parent;}//情况二叔叔不存在/存在且为黑else{//单旋if (cur parent-_right){RotateL(grandfather);//左单旋parent-_col BLACK;//变色grandfather-_col RED;}//右左双旋 // cur parent-_leftelse{RotateR(parent);//先右单旋RotateL(grandfather);//再左单旋grandfather-_col RED;//变色cur-_col BLACK;}break;//经过情况二后跳出}}}_root-_col BLACK;//统一处理根必须是黑的return true;
}//左单旋
void RotateL(Node* parent)
{RotateSize;Node* subR parent-_right;Node* subRL subR-_left;parent-_right subRL;//不为空if (subRL){subRL-_parent parent;}subR-_left parent;Node* ppnode parent-_parent;parent-_parent subR;//处理parent如果为根if (parent _root){_root subR;subR-_parent nullptr;}//不为根处理与ppnode的连接else{if (ppnode-_left parent){ppnode-_left subR;}else{ppnode-_right subR;}subR-_parent ppnode;}
}//右单旋
void RotateR(Node* parent)
{RotateSize;Node* subL parent-_left;Node* subLR subL-_right;parent-_left subLR;//不为空if (subLR){subLR-_parent parent;}subL-_right parent;Node* ppnode parent-_parent;parent-_parent subL;if (parent _root){_root subL;subL-_parent nullptr;}else{if (ppnode-_left parent){ppnode-_left subL;}else{ppnode-_right subL;}subL-_parent ppnode;}
}2.2 与AVL树对比
红黑树与AVL树都是平衡二叉树那为什么现实中绝大部分是使用红黑树很少使用AVL树下面我们来作数据对比从两者的旋转次数、插入时间、平衡状态和高度来作分析。
测试代码
RBTreeint, int t1;
AVLTreeint, int t2;const int N 10000000;
vectorint v;
v.reserve(N);
srand(time(0));for (size_t i 0; i N; i)
{v.push_back(rand() i);
}size_t begin1 clock();
for (auto e : v)
{t1.Insert(make_pair(e, e));
}
size_t end1 clock();size_t begin2 clock();
for (auto e : v)
{t2.Insert(make_pair(e, e));
}
size_t end2 clock();
//旋转次数
cout RBTree RoateSize: t1.getRotateSize() endl;
cout AVLTree RoateSize: t2.getRotateSize() endl;
//插入时间
cout RBTree Insert: end1 - begin1 endl;
cout AVLTree Insert: end2 - begin2 endl;
//平衡状态
cout RBTree IsBalance: t1.IsBalance() endl;
cout AVLTree IsBalance: t2.IsBalance() endl;
//树的高度
cout RBTree Height: t1.Height() endl;
cout AVLTree Height: t2.Height() endl;
//树的节点个数
cout RBTree Size: t1.Size() endl;
cout AVLTree Size: t2.Size() endl;插入一千万个数据运行结果 可以发现红黑树的旋转次数比AVL树少插入时间相差不大两种树都是平衡的红黑树的高度略高一些。
总结 由于高度上红黑树不会高出多少所以搜索效率影响不大。从树的高度可知AVL树是极致追求平衡的所以要频繁的进行旋转这也导致旋转次数明显比红黑树多因此在旋转上开销较大不及红黑树的性能更优越些同时红黑树实现比较简单所以实际运用中红黑树更多。
