（4-15）红黑树
16lz
2021-04-15
也是一种搜索二叉树，但在每个节点给他标注了颜色，可以是red或者black，通过red和black确保
最长路径不超过最短路径的2倍。
性质：
1、每个节点不是红就得是黑
2、根节点是黑的
3、对于任一个节点，该节点到所有后代叶节点的路径上，均含有相同数目的黑色节点。
4、红红不能相连。（红色节点的孩子节点一定为黑色）。
所以：最短路径就是全是黑色的节点，最长路径也就是一黑一红，这也就是红黑树的嘴真长路径不超过最短路径的2倍。
红黑树的插入操作
1、按照搜索二叉树的插入步骤，找到合适的位置，建立节点插入数据，将新插入节点变为红色，
2、检查插入后是否违反红黑树的性质。
分为3种情况:
第一种情况：如果父亲节点为黑色，则插入成功，没有违反红黑树的性质。
第二种：如果父亲p为红，且叔叔u为红，祖父g为黑，则需要变色。将p和u变黑，那样就是将g的左右都增加了一个黑，所以需要减少一个黑，于是将g变为红。也就是p和u变黑，g变红，再向上调整，以g位置调整。
第三种：p为红，但是u不存在或者u存在为黑色，那么需要旋转加变色，怎么旋转具体插入路径，如果为直线，则是单旋转，如果是折线，则双旋转，（直线指的是p和cur的方向一致，折线指的是不一致），变色是将g变为红色，p变为黑色，并且调整结束，因为不管是怎么调整到这种情况，最终在这种情况下旋转加变色后其结果都没有改变原有的黑色节点个数。
每一份赞赏源于懂得
赞赏
0人进行了赞赏支持
更多相关文章
- 【DB笔试面试732】在Oracle中，Oracle Cluster Health Monitor（CHM）
- js基础知识：JS对DOM元素的基本操作，遍历、增删改查。
- 内容分发网络（Content Delivery Network，CDN）
- Kubernetes容器集群管理环境 - 完整部署（上篇）
- ElasticSearch实战系列四: ElasticSearch理论知识介绍
- ZooKeeper 分布式锁
- C#中的几个简单技术点
- 技术问答-23 javabean创建一个二叉树，左右两个叶子节点 （1）要求每
- Linux宝塔负载均衡使用教程