乌兰浩特网站建设,网站建设倒计时模板,上海公共招聘网下载,企业所得税核定征收率前言 作者#xff1a;小蜗牛向前冲 名言#xff1a;我可以接受失败#xff0c;但我不能接受放弃 如果觉的博主的文章还不错的话#xff0c;还请点赞#xff0c;收藏#xff0c;关注#x1f440;支持博主。如果发现有问题的地方欢迎❀大家在评论区指正 目录
一、红黑树的… 前言 作者小蜗牛向前冲 名言我可以接受失败但我不能接受放弃 如果觉的博主的文章还不错的话还请点赞收藏关注支持博主。如果发现有问题的地方欢迎❀大家在评论区指正 目录
一、红黑树的基本知识 1、红黑树的概念
2、性质
二、红黑树的模拟实现
1、节点的定义
2、红黑树的插入
三、红黑树的测试
1、验证的准备工作
2、测试用例
3、完整代码实现
四、AVL树和红黑树的比较 本期学习目标什么是红黑树红黑树是怎么实现的红黑树的测试红黑树和AVL树的对比
一、红黑树的基本知识 1、红黑树的概念
红黑树是一种二叉搜索树但在每个结点上增加一个存储位表示结点的颜色可以是Red或 Black。 通过对任何一条从根到叶子的路径上各个结点着色方式的限制红黑树确保没有一条路 径会比其他路径长出俩倍最长路径吧会超过最短路径的2倍因而是接近平衡的。 2、性质 每个结点不是红色就是黑色。 根节点是黑色的 。 如果一个节点是红色的则它的两个孩子结点是黑色的。(没有连续的红节点)对于每个结点从该结点到其所有后代叶结点的简单路径上均包含相同数目的黑色结点 。(每条路径下都包含相同的黑节点) 每个叶子结点都是黑色的(此处的叶子结点指的是空结点)。 推论 最短路径全部由黑节点组成最长路径一黑一红红节点数量 黑节点数量 这里我们思考一下红黑树是如何保证最长路径不超过最短路径的2倍 由推论2可知对于最长路经就是一红一黑而且红节点数量等于黑节点数量在由推论1可知最短路径节点数量全为黑。在由性质4可知每条路径的黑节点数量都相同这就保证了最长路径不超过2倍的最短路径。 二、红黑树的模拟实现
1、节点的定义
enum Colour
{RED,BLACK,
};templateclass K,class V
struct RBTreeNode
{pairK, V _kv;RBTreeNodeK, V* _left;RBTreeNodeK, V* _right;RBTreeNodeK, V* _parent;Colour _col;RBTreeNode(const pairK, V kv):_kv(kv),_left(nullptr),_right(nullptr),_parent(nullptr),_col(RED){}
};
2、红黑树的插入
根据节点的定义我们上面定义了一个枚举类型了存放显色的类型RED和BLACK但是我们在插入节点的时候是定义红色还是黑色呢我们在上面定义的是红色为什么呢
这里分类讨论一下 定义新插入节点为黑色 就会破坏性质4导致每天路径的黑色节点数量不同 定义新插入节点为红色 可能会破坏性质3导致出现连续的红节点但是这样也仅仅影响的是一条路径影响有限。 综上所述所以我们选择插入节点为红色。
红黑树是在二叉搜索树的基础上加上其平衡限制条件因此红黑树的插入可分为两步
1. 按照二叉搜索的树规则插入新节点
2.检测新节点插入后红黑树的性质是否造到破坏
因为新节点的默认颜色是红色因此如果其双亲节点的颜色是黑色没有违反红黑树任何性质则不需要调整但当新插入节点的双亲节点颜色为红色时就违反了性质三不能有连在一起的红色节点此时需要对红黑树分情况来讨论
约定:cur为当前节点p为父节点g为祖父节点u为叔叔节点(pparent ggrandfather uuncle)
当p为g的左孩子时有3种情况需要讨论
情况1 情况2 情况3 当p为g的右孩子时也有3种情况需要讨论
这里的讨论和上面相似处理方法也相似
情况1 情况2: 情况3 代码实现
bool insert(const pairK, V kv)
{if (_root nullptr){_root new Node(kv);_root-_col BLACK;return true;}//找到插入位置Node* parent nullptr;Node* cur _root;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;}else{return false;}}//找到了cur new Node(kv);cur-_col RED;//默认颜色为红色//链接节点if (parent-_kv.first kv.first){parent-_left cur;cur-_parent parent;}else{parent-_right cur;cur-_parent parent;}//插入后要调整红黑树//如果父亲存在且为红色while (parent parent-_col RED){Node* grandparent parent-_parent;//情况1cur为红色p和u都为红色g为黑色,这里的u是存在的//解决方法:p和n都变黑,g变红,在把cur当做g继续调整if (parent grandparent-_left){Node* uncle grandparent-_right;if (uncle uncle-_col RED){parent-_col uncle-_col BLACK;grandparent-_col RED;cur grandparent;//更新parentparent cur-_parent;}else//情况23 uncle存在且为黑色或者uncle不存在{if (cur parent-_left){//情况2//解决方法:右单旋将p变黑g变红RotateR(grandparent);parent-_col BLACK;grandparent-_col RED;}else//情况3双旋转{RotateL(parent);RotateR(grandparent);grandparent-_col RED;cur-_col BLACK;//双旋转后cur变为了根}//这里类比根节点为色不需要在调整了break;}}else//grandparent-right parent{//这里也是和上面一样分为三种情况Node* grandparent parent-_parent;Node* uncle grandparent-_left;if (uncle uncle-_col RED){parent-_col uncle-_col BLACK;grandparent-_col RED;cur grandparent;//更新parentparent cur-_parent;}else{if (cur parent-_right){RotateL(grandparent);//左单旋转parent-_col BLACK;grandparent-_col RED;}else{RotateR(parent);RotateL(grandparent);grandparent-_col RED;cur-_col BLACK;//双旋转后cur变为了根}break;}}}//调整完成把根节点变黑_root-_col BLACK;return true;
}
//右单旋
void RotateR(Node* parent)
{Node* subL parent-_left;Node* subLR subL-_right;Node* grandparent parent-_parent;//让subLR变为parent的左,parent-_left subLR;//这里要判断一下subLR不为空if (subLR){subLR-_parent parent;}//parent变为subL的右subL-_right parent;parent-_parent subL;//parent就是为根if (grandparent nullptr){_root subL;subL-_parent grandparent;}else{//parnet是上grandparent的左子树if (grandparent-_left parent){grandparent-_left subL;}else{grandparent-_right subL;}subL-_parent grandparent;}
}//左单旋
void RotateL(Node* parent)
{Node* subR parent-_right;Node* subRL subR-_left;Node* ppNode parent-_parent;parent-_right subRL;if (subRL){subRL-_parent parent;}subR-_left parent;parent-_parent subR;//parnet为根,要更新根if (ppNode nullptr){_root subR;subR-_parent ppNode;}else{if (ppNode-_left parent){ppNode-_left subR;}else{ppNode-_right subR;}subR-_parent ppNode;}
}
三、红黑树的测试
1、验证的准备工作 检测其是否满足二叉搜索树(中序遍历是否为有序序列) 检测其是否满足红黑树的性质 检测方法 1、根节点是黑色否则不是红黑树 2、当前节点是红色去检测父亲节点父亲节点也是红色则不是红黑树 3、以最左侧路径的黑色节点为基准其它路径上的黑色节点与基准不相等不是红黑树 检验代码
void Inorder()
{_Inorder(_root);
}void _Inorder(Node* root)
{if (root nullptr)return;_Inorder(root-_left);cout root-_kv.first : root-_kv.second endl;_Inorder(root-_right);
}bool Check(Node* root, int blackNum, const int ref)
{if (root nullptr){//已经递归到最深处进行,本路径的黑节点树和ref数量对比if (blackNum ! ref){cout 违反规则本条路径的黑色节点的数量跟最左路径不相等 endl;return false;}return true;}if (root-_col RED root-_parent-_col RED){cout 违反规则出现连续红色节点 endl;return false;}if (root-_col BLACK){blackNum;}return Check(root-_left, blackNum, ref) Check(root-_right, blackNum, ref);
}bool IsBalance()
{if (_root nullptr){return true;}if (_root-_col ! BLACK){return false;}//求出最左路节点有多少个黑节点int ref 0;Node* left _root;while (left){if (left-_col BLACK){ref;}left left-_left;}return Check(_root, 0, ref);
}
2、测试用例
这里我们借用上面AVL树的测试用例即可
void TestRBTree1()
{//int a[] { 8, 3, 1, 10, 6, 4, 7, 14, 13 };int a[] { 16, 3, 7, 11, 9, 26, 18, 14, 15 };//int a[] { 4, 2, 6, 1, 3, 5, 15, 7, 16, 14 };RBTreehint, int t;for (auto e : a){/*if (e 18){int x 0;}*/t.insert(make_pair(e, e));cout insert e : t.IsBalance() endl;}t.Inorder();cout t.IsBalance() endl;
}void TestRBTree2()
{srand(time(0));const size_t N 100000;RBTreehint, int t;for (size_t i 0; i N; i){size_t x rand();t.insert(make_pair(x, x));//cout t.IsBalance() endl;}//t.Inorder();cout t.IsBalance() endl;
} 3、完整代码实现
#pragma onceenum Colour
{RED,BLACK,
};templateclass K,class V
struct RBTreeNode
{pairK, V _kv;RBTreeNodeK, V* _left;RBTreeNodeK, V* _right;RBTreeNodeK, V* _parent;Colour _col;RBTreeNode(const pairK, V kv):_kv(kv),_left(nullptr),_right(nullptr),_parent(nullptr),_col(RED){}
};templateclass K,class V
class RBTreeh
{typedef RBTreeNodeK,V Node;
public:bool insert(const pairK, V kv){if (_root nullptr){_root new Node(kv);_root-_col BLACK;return true;}//找到插入位置Node* parent nullptr;Node* cur _root;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;}else{return false;}}//找到了cur new Node(kv);cur-_col RED;//默认颜色为红色//链接节点if (parent-_kv.first kv.first){parent-_left cur;cur-_parent parent;}else{parent-_right cur;cur-_parent parent;}//插入后要调整红黑树//如果父亲存在且为红色while (parent parent-_col RED){Node* grandparent parent-_parent;//情况1cur为红色p和u都为红色g为黑色,这里的u是存在的//解决方法:p和n都变黑,g变红,在把cur当做g继续调整if (parent grandparent-_left){Node* uncle grandparent-_right;if (uncle uncle-_col RED){parent-_col uncle-_col BLACK;grandparent-_col RED;cur grandparent;//更新parentparent cur-_parent;}else//情况23 uncle存在且为黑色或者uncle不存在{if (cur parent-_left){//情况2//解决方法:右单旋将p变黑g变红RotateR(grandparent);parent-_col BLACK;grandparent-_col RED;}else//情况3双旋转{RotateL(parent);RotateR(grandparent);grandparent-_col RED;cur-_col BLACK;//双旋转后cur变为了根}//这里类比根节点为色不需要在调整了break;}}else//grandparent-right parent{//这里也是和上面一样分为三种情况Node* grandparent parent-_parent;Node* uncle grandparent-_left;if (uncle uncle-_col RED){parent-_col uncle-_col BLACK;grandparent-_col RED;cur grandparent;//更新parentparent cur-_parent;}else{if (cur parent-_right){RotateL(grandparent);//左单旋转parent-_col BLACK;grandparent-_col RED;}else{RotateR(parent);RotateL(grandparent);grandparent-_col RED;cur-_col BLACK;//双旋转后cur变为了根}break;}}}//调整完成把根节点变黑_root-_col BLACK;return true;}//右单旋void RotateR(Node* parent){Node* subL parent-_left;Node* subLR subL-_right;Node* grandparent parent-_parent;//让subLR变为parent的左,parent-_left subLR;//这里要判断一下subLR不为空if (subLR){subLR-_parent parent;}//parent变为subL的右subL-_right parent;parent-_parent subL;//parent就是为根if (grandparent nullptr){_root subL;subL-_parent grandparent;}else{//parnet是上grandparent的左子树if (grandparent-_left parent){grandparent-_left subL;}else{grandparent-_right subL;}subL-_parent grandparent;}}//左单旋void RotateL(Node* parent){Node* subR parent-_right;Node* subRL subR-_left;Node* ppNode parent-_parent;parent-_right subRL;if (subRL){subRL-_parent parent;}subR-_left parent;parent-_parent subR;//parnet为根,要更新根if (ppNode nullptr){_root subR;subR-_parent ppNode;}else{if (ppNode-_left parent){ppNode-_left subR;}else{ppNode-_right subR;}subR-_parent ppNode;}}void Inorder(){_Inorder(_root);}void _Inorder(Node* root){if (root nullptr)return;_Inorder(root-_left);cout root-_kv.first : root-_kv.second endl;_Inorder(root-_right);}bool Check(Node* root, int blackNum, const int ref){if (root nullptr){//已经递归到最深处进行,本路径的黑节点树和ref数量对比if (blackNum ! ref){cout 违反规则本条路径的黑色节点的数量跟最左路径不相等 endl;return false;}return true;}if (root-_col RED root-_parent-_col RED){cout 违反规则出现连续红色节点 endl;return false;}if (root-_col BLACK){blackNum;}return Check(root-_left, blackNum, ref) Check(root-_right, blackNum, ref);}bool IsBalance(){if (_root nullptr){return true;}if (_root-_col ! BLACK){return false;}//求出最左路节点有多少个黑节点int ref 0;Node* left _root;while (left){if (left-_col BLACK){ref;}left left-_left;}return Check(_root, 0, ref);}
private:Node* _root nullptr;};void TestRBTree1()
{//int a[] { 8, 3, 1, 10, 6, 4, 7, 14, 13 };int a[] { 16, 3, 7, 11, 9, 26, 18, 14, 15 };//int a[] { 4, 2, 6, 1, 3, 5, 15, 7, 16, 14 };RBTreehint, int t;for (auto e : a){/*if (e 18){int x 0;}*/t.insert(make_pair(e, e));cout insert e : t.IsBalance() endl;}t.Inorder();cout t.IsBalance() endl;
}//void TestRBTree2()
//{
// srand(time(0));
// const size_t N 100000;
// RBTreehint, int t;
// for (size_t i 0; i N; i)
// {
// size_t x rand();
// t.insert(make_pair(x, x));
// //cout t.IsBalance() endl;
// }
//
// //t.Inorder();
// cout t.IsBalance() endl;
//}
四、AVL树和红黑树的比较
AVL树Adelson-Velsky and Landis tree和红黑树都是自平衡的二叉搜索树它们在维持树的平衡性上采用了不同的策略。以下是它们之间的一些比较 平衡性维护策略 AVL树 通过保持任意节点的左右子树的高度差平衡因子不超过1来维护平衡。在每次插入或删除操作后可能需要旋转来恢复平衡。红黑树 通过引入额外的颜色信息和一些规则确保树的高度保持在较小的范围内。具体来说红黑树的平衡性维护是通过节点的颜色和一些颜色约束来实现的。 平衡因子和颜色信息 AVL树 使用平衡因子Balance Factor来表示每个节点左右子树的高度差。通常平衡因子为 -1、0、1。红黑树 使用颜色信息红色或黑色来表示树的平衡状态。通过遵循红黑树的性质确保了树的平衡。 旋转操作 AVL树 插入或删除可能需要执行多次旋转操作包括左旋、右旋、左右旋、右左旋等。红黑树 插入或删除通常只需要执行一到两次旋转操作因为红黑树引入了颜色信息更灵活地维持平衡。 性能影响 AVL树 由于 AVL 树对平衡的要求更为严格因此在插入和删除等操作时可能会导致更多的旋转相对来说更耗费性能。红黑树 由于其相对宽松的平衡条件红黑树在插入和删除等操作时通常执行的旋转较少因此性能可能相对更好。 应用场景 AVL树 适用于对搜索性能有较高要求的场景例如在数据库中需要快速检索数据。红黑树 通常在需要高效的插入和删除操作的情况下使用例如在集合类的实现中。 总体而言选择 AVL 树还是红黑树取决于应用的特定需求。如果搜索操作远远超过插入和删除可能更倾向于使用 AVL 树。而在插入和删除操作频繁的情况下红黑树可能更为适用。
