admin 管理员组文章数量: 887032
RB
RB-tree性质理解
规则
- 每个节点的颜色非红即黑。
- 根节点的颜色必定为黑。
- 每个叶子节点是黑色的（指的是NIL节点）。
- 如果节点的颜色为红，其左右子节点的颜色必为黑。
- 任意节点到NULL（尾节点）的任意路径上包含的黑色节点数量必须一致。
根据以上规则，可以得出以下要求：
- 新增节点的颜色需要为红。
- 新增父节点的颜色需要为黑。
为了能达到以上的要求，需要对变化后的红黑树进行调整。调整的手段主要有两种：改变颜色、旋转。
新增节点一般步骤
第一步: 将红黑树当作一颗二叉查找树，将节点插入。
红黑树本身就是一颗二叉查找树，将节点插入后，该树仍然是一颗二叉查找树。
第二步：将插入的节点着色为”红色”。
为什么着色成红色，而不是黑色呢？为什么呢？根据规则5得出的要求。
第三步: 通过一系列的调整策略，使之重新成为一颗红黑树。
调整策略
改变颜色
应用场景：
当前节点的父节点是红色，且当前节点的祖父节点的另一个子节点（叔叔节点）也是红色。
解决办法：
(01) 将“父节点”设为黑色。
(02) 将“叔叔节点”设为黑色。
(03) 将“祖父节点”设为“红色”。
(04)将“祖父节点”设为“当前节点”(红色节点)；即，之后继续对“当前节点”进行操作。
见图1。
旋转
什么是左旋？右旋？ 见图2。
应用场景A：
当前节点的父节点是红色，叔叔节点是黑色，且当前节点是其父节点的右孩子
解决办法：
(01) 将“父节点”作为“新的当前节点”。
(02) 以“新的当前节点”为支点进行左旋。
见图3。
应用场景B：
当前节点的父节点是红色，叔叔节点是黑色，且当前节点是其父节点的左孩子
解决办法：
(01) 将“父节点”设为“黑色”。
(02) 将“祖父节点”设为“红色”。
(03) 以“祖父节点”为支点进行右旋。
见图4。
本文标签： RB
版权声明：本文标题：RB 内容由网友自发贡献，该文观点仅代表作者本人， 转载请联系作者并注明出处：http://www.freenas.com.cn/jishu/1687204637h75929.html， 本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌抄袭侵权/违法违规的内容，一经查实，本站将立刻删除。
发表评论