dnf网站上怎么做商人,wordpress 首页轮播,辽宁海星建设集团有限公司网站,网站开发宣传图目录 前言一#xff0c;红黑树的概念二#xff0c;红黑树的性质三#xff0c;红黑树节点的定义四#xff0c;红黑树的插入操作4.1 第一步4.2 第二步4.3 插入操作的完整代码 五#xff0c;红黑树的验证六#xff0c;实现红黑树的完整代码五#xff0c;红黑树与AVL树的比较… 目录 前言一红黑树的概念二红黑树的性质三红黑树节点的定义四红黑树的插入操作4.1 第一步4.2 第二步4.3 插入操作的完整代码 五红黑树的验证六实现红黑树的完整代码五红黑树与AVL树的比较 点击跳转至上一篇文章
【C】AVL树的深度解析及其实现 点击跳转至文章【C】二叉树进阶 — 搜索二叉树
前言
上一篇文章介绍了什么是AVL树和AVL树的实现AVL树也有它的缺点就是太过追求绝对平衡比如在插入时要维护其绝对平衡旋转次数太多在删除时甚至有可能要一直旋转到根位置使之性能低下。
本篇文章介绍的红黑树也是一种平衡树是通过改变节点颜色以及旋转操作使之接近平衡。
红黑树比AVL树的用途更加广泛在一些方面效率甚至要优于AVL树并且 map/set 的底层封装用的也是红黑树。
一红黑树的概念
红黑树是一种二叉搜索树但在每个结点上增加一个存储位表示结点的颜色可以是Red或Black。 通过对任何一条从根到叶子的路径上各个结点着色方式的限制红黑树确保没有一条路径会比其他路径长出两倍因而是接近平衡的。 二红黑树的性质
(1) 每个结点不是红色就是黑色 (2) 根节点是黑色的 (3) 如果一个节点是红色的则它的两个孩子结点是黑色的重点 (4) 对于每个结点从该结点到其所有后代叶结点的简单路径上均包含相同数目的黑色结点重点 (5) 每个叶子结点都是黑色的(此处的叶子结点指的是空结点这条性质可有可无平时不关注)。
三红黑树节点的定义
红黑树的节点结构与AVL树的大致相同只是AVL树中有节点的颜色没有平衡因子。
//枚举颜色
enum Colour
{RED,BLACK
};template class 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(BLACK){}
};四红黑树的插入操作
首先我们要思考一个问题插入节点时到底是插入红色节点还是黑色节点为什么
答案插入红色节点。
因为我们知道红黑树最重要的两条性质是第(3)(4)条通过维护这两条规则使之成为红黑树而当新插入一个节点时必定会破坏两条规则之一。
假设插入节点为黑色节点则所有路径的黑色节点数量均不相同如何让它们相同将是一个巨大的难题而插入红色节点(此时一定是作为孩子节点)就破坏规则(3)但是只要根据其父亲和叔叔节点进行适当的变色就可以继续恢复规则(3)。
显而易见规则(3)(4)就好比慈父严母非要选择得罪其中一人那当然是慈父了。
红黑树是在二叉搜索树的基础上加上其平衡限制条件因此红黑树的插入可分为两步
4.1 第一步
按照二叉搜索的树规则插入新节点
bool Insert(const pairK, V kv)
{if (_root nullptr){_root new Node(kv);return true;}Node* cur _root;Node* parent nullptr;while (cur){if (cur-_kv.first kv.first){parent cur;cur cur-_left;}else if (cur-_kv.first kv.first){parent cur;cur cur-_right;}elsereturn false;}cur new Node(kv);//新增节点颜色为红色cur-_col RED;//链接时要判断链接在parent的左还是右if (parent-_kv.first kv.first)parent-_left cur;elseparent-_right cur;cur-_parent parent;//检测新节点插入后红黑树的性质是否造到破坏//……}4.2 第二步
检测新节点插入后红黑树的性质是否造到破坏
因为新节点的默认颜色是红色因此如果其双亲节点的颜色是黑色没有违反红黑树任何性质则不需要调整但当新插入节点的双亲节点颜色为红色时就违反了性质三不能有连在一起的红色节点此时需要对红黑树分情况来讨论
约定 (1) cur 为当前节点p为父节点g为祖父节点u为叔叔节点
(2) 下面的抽象图中a/b/c/d/e 表示具有 n 个节点的红黑树n 0。
(一) 情况一: cur为红p为红g为黑u存在且为红 解决方式将p,u改为黑g改为红然后把g当成cur继续向上调整。
(二) 情况二: cur为红p为红g为黑u不存在/u存在且为黑 下面我们根据 u 的情况用具象图分别解释单旋与双旋操作
(1) u 不存在a/b/c/d/e都是空cur 是新增
p为g的左孩子cur为p的左孩子则进行右单旋转再 p 变黑g 变红 相反p为g的右孩子cur为p的右孩子则进行左单旋转再 p 变黑g 变红 p为g的左孩子cur为p的右孩子先针对p做左单旋转再针对 g 做右单旋cur 变黑g 变红 (2) u 存在且为黑
单旋情况 双旋情况
4.3 插入操作的完整代码
bool Insert(const pairK, V kv)
{if (_root nullptr){_root new Node(kv);return true;}Node* cur _root;Node* parent nullptr;while (cur){if (cur-_kv.first kv.first){parent cur;cur cur-_left;}else if (cur-_kv.first kv.first){parent cur;cur cur-_right;}elsereturn false;}cur new Node(kv);//新增节点颜色为红色cur-_col RED;//链接时要判断链接在parent的左还是右if (parent-_kv.first kv.first)parent-_left cur;elseparent-_right cur;cur-_parent parent;while (parent parent-_col RED){Node* grandfather parent-_parent;// g// p uif (parent grandfather-_left){//找到u的位置Node* uncle grandfather-_right;if (uncle uncle-_col RED){//u存在且为红,把p/u变黑g变红,继续向上调整parent-_col uncle-_col BLACK;grandfather-_col RED;cur grandfather;parent cur-_parent;}else{//u不存在或存在且为黑if (cur parent-_left){// g// p u //c//单旋RotateR(grandfather);parent-_col BLACK;grandfather-_col RED;}else{// g// p u // c//双旋RotateL(parent);RotateR(grandfather);cur-_col BLACK;grandfather-_col RED;}break;}}else{// g// u pNode* uncle grandfather-_left;//u存在且为红,把p/u变黑g变红,继续向上调整if (uncle uncle-_col RED){parent-_col uncle-_col BLACK;grandfather-_col RED;cur grandfather;parent cur-_parent;}else{//u不存在或存在且为黑if (cur parent-_right){// g// u p// c//单旋RotateL(grandfather);parent-_col BLACK;grandfather-_col RED;}else{// g// u p// c//双旋RotateR(parent);RotateL(grandfather);cur-_col BLACK;grandfather-_col RED;}break;}}}_root-_col BLACK;return true;
}五红黑树的验证
红黑树的检测分为两步
(1) 检测其是否满足二叉搜索树(中序遍历是否为有序序列) (2) 检测其是否满足红黑树的性质
这里重点检测的是性质(3)与性质(4)。
检测性质(3)只要判断当前节点与其父亲节点是否为连续的红色节点
检测性质(4)先计算出任意一条路径上的黑色节点作为参考值再用这个参考值与其他路径上的黑色节点数量比较。
private://中序遍历void InOrder(){_Inorder(_root);cout endl;}//判断是否平衡bool IsBalance(){if (_root nullptr)return true;//检查根节点if (_root-_col RED)return false;// 参考值int refNum 0;Node* cur _root;while (cur){if (cur-_col BLACK)refNum;cur cur-_left;}return Check(_root, 0, refNum);}private:bool Check(Node* root, int blackNum, const int refNum){//每条路径走到空后与参考值进行比较if (root nullptr){//cout blackNum endl;if (refNum ! blackNum){cout 存在黑色节点的数量不相等的路径 endl;return false;}return true;}//检查是否存在连续的红色节点if (root-_col RED root-_parent-_col RED){cout root-_kv.first 存在连续的红色节点 endl;return false;}//blackNum表示根节点到当前节点的路径上黑色节点的数量if (root-_col BLACK)blackNum;return Check(root-_left, blackNum, refNum) Check(root-_right, blackNum, refNum);}六实现红黑树的完整代码
RBTree.h
#pragma once#include iostream
#include assert.h
using namespace std;//枚举颜色
enum Colour
{RED,BLACK
};template class 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(BLACK){}
};template class K, class V
class RBTree
{typedef RBTreeNodeK, V Node;
public:Node* Find(const pairK, V kv){Node* cur _root;while (cur){if (cur-_kv.first kv.first)cur cur-_left;else if (cur-_kv.first kv.first)cur cur-_right;elsereturn cur;}return nullptr;}bool Insert(const pairK, V kv){if (_root nullptr){_root new Node(kv);return true;}Node* cur _root;Node* parent nullptr;while (cur){if (cur-_kv.first kv.first){parent cur;cur cur-_left;}else if (cur-_kv.first kv.first){parent cur;cur cur-_right;}elsereturn false;}cur new Node(kv);//新增节点颜色为红色cur-_col RED;//链接时要判断链接在parent的左还是右if (parent-_kv.first kv.first)parent-_left cur;elseparent-_right cur;cur-_parent parent;while (parent parent-_col RED){Node* grandfather parent-_parent;// g// p uif (parent grandfather-_left){//找到u的位置Node* uncle grandfather-_right;if (uncle uncle-_col RED){//u存在且为红,把p/u变黑g变红,继续向上调整parent-_col uncle-_col BLACK;grandfather-_col RED;cur grandfather;parent cur-_parent;}else{//u不存在或存在且为黑if (cur parent-_left){// g// p u //c//单旋RotateR(grandfather);parent-_col BLACK;grandfather-_col RED;}else{// g// p u // c//双旋RotateL(parent);RotateR(grandfather);cur-_col BLACK;grandfather-_col RED;}break;}}else{// g// u pNode* uncle grandfather-_left;//u存在且为红,把p/u变黑g变红,继续向上调整if (uncle uncle-_col RED){parent-_col uncle-_col BLACK;grandfather-_col RED;cur grandfather;parent cur-_parent;}else{//u不存在或存在且为黑if (cur parent-_right){// g// u p// c//单旋RotateL(grandfather);parent-_col BLACK;grandfather-_col RED;}else{// g// u p// c//双旋RotateR(parent);RotateL(grandfather);cur-_col BLACK;grandfather-_col RED;}break;}}}_root-_col BLACK;return true;}//中序遍历void InOrder(){_Inorder(_root);cout endl;}//判断是否平衡bool IsBalance(){if (_root nullptr)return true;//检查根节点if (_root-_col RED)return false;// 参考值int refNum 0;Node* cur _root;while (cur){if (cur-_col BLACK)refNum;cur cur-_left;}return Check(_root, 0, refNum);}private://每个节点的位置记录一个值blackNum//blackNum表示根节点到当前节点的路径上黑色节点的数量bool Check(Node* root, int blackNum, const int refNum){//每条路径走到空后与参考值进行比较if (root nullptr){//cout blackNum endl;if (refNum ! blackNum){cout 存在黑色节点的数量不相等的路径 endl;return false;}return true;}//检查是否存在连续的红色节点if (root-_col RED root-_parent-_col RED){cout root-_kv.first 存在连续的红色节点 endl;return false;}if (root-_col BLACK)blackNum;return Check(root-_left, blackNum, refNum) Check(root-_right, blackNum, refNum);}//右单旋void RotateR(Node* parent){Node* subL parent-_left;Node* subLR subL-_right;if (subLR)subLR-_parent parent;parent-_left subLR;subL-_right parent;//改变之前记录Node* ppNode parent-_parent;parent-_parent subL;//parent为根if (parent _root){_root subL;_root-_parent nullptr;}else{//parent为一颗子树if (ppNode-_left parent)ppNode-_left subL;elseppNode-_right subL;subL-_parent ppNode;}}//左单旋void RotateL(Node* parent){Node* subR parent-_right;Node* subRL subR-_left;if (subRL)subRL-_parent parent;parent-_right subRL;subR-_left parent;Node* ppNode parent-_parent;parent-_parent subR;//parent为根if (parent _root){_root subR;_root-_parent nullptr;}else{//parent为一颗子树if (ppNode-_left parent)ppNode-_left subR;elseppNode-_right subR;subR-_parent ppNode;}}void _Inorder(Node* root){if (root nullptr)return;_Inorder(root-_left);cout root-_kv.first : root-_kv.second endl;_Inorder(root-_right);}
private:Node* _root nullptr;
};//测试代码
void Test1()
{//int a[] { 8, 3, 1, 10, 6, 4, 7, 14, 13 };int a[] { 16,3,7,11,9,26,18,14,15 };RBTreeint, int t;for (auto e : a)t.Insert({ e ,e });t.InOrder();cout t.IsBalance() endl;
}Test.cpp
#include RBTree.hint main()
{Test1();return 0;
}
运行结果如下
中序遍历是有序的说明是搜索二叉树返回1说明满足红黑树的性质是平衡树。 五红黑树与AVL树的比较
红黑树和AVL树都是高效的平衡二叉树增删改查的时间复杂度都是O( l o g 2 N log_2 N log2N)红黑树不追求绝对平衡其只需保证最长路径不超过最短路径的2倍相对而言降低了插入和旋转的次数所以在经常进行增删的结构中性能比AVL树更优而且红黑树实现比较简单所以实际运用中红黑树更多。
