红黑树的原理以及实现

作者：Linux服务器开发

2022 年 3 月 16 日
本文字数：1525 字
阅读完需：约 5 分钟

红黑树

红黑树基于二叉查找树的附加特性

节点是红色或黑色。
根节点是黑色。
每个叶子节点都是黑色的空节点（叶子结点指为空的叶子结点）。
每个红色节点的两个子节点都是黑色的（从每个叶子到根的所有路径上不能有两个连续的红色节点）。
从任意节点到其每个叶子的所有路径都包含相同数目的黑色节点。

相关视频讲解：

C++后台开发架构师学习视频

从底层原理出发详解红黑树

B-树与B+树

1. 数据结构

class TreeNode{    private Boolean color;    private int val;    private TreeNode left;    private TreeNode right;    private TreeNode parent;    get,set...}class RBTree{    public boolean add(int val){...}    public boolean delete(int val){...}    public void display(){...}}

复制代码

2. 左旋以及右旋

2.1 左旋

2.2 右旋

3. 插入

新插入的节点（newNode）为红色。
按照二分查找树插入规则插入。
分情况讨论（以下情况基本都是为了保持上文所讲的的红黑树特性 4 和特 5）1、若 newNode 为根节点，则变为黑色，插入完毕，返回 true。2、若 newNode 父节点为黑色，则插入完毕，返回 true。3、如下图所示，若 newNode 父节点为红色，且叔叔节点存在且为红色，则父节点与叔叔节点变为黑色，祖父节点变为红色，newNode = 祖父节点。

4、如下图所示，若 newNode 父节点为红色，叔叔节点不存在或为黑色，且 newNode 为父节点右孩子，父节点为祖父节点左孩子，则以父节点为轴左旋，进入情况 6.

5、如下图所示，若 newNode 父节点为红色，叔叔节点不存在或为黑色，且 newNode 为父节点左孩子，父节点为祖父节点右孩子，则以父节点为轴右旋，进入情况 7

6、如下图，此时以祖父节点为轴进行右旋，将祖父节点变为红色，newNode 变为黑色。

7、如下图，此时以祖父节点为轴进行左旋，将祖父节点变为红色，newNode 变为黑色。

4. 删除

分情况讨论（和插入一样，以下情况基本都是为了保持上文所讲的的红黑树特性 4 和特 5）

如下图，如果待删除节点 B 有两个非空的孩子节点，转化成待删除节点只有右孩子（或没有孩子）的情况，习惯性选取待删除节点右子树最小节点 E 替换待删除节点（只是值替换，颜色不变），并将待删除节点变为 E。

想学习 C++工程化、高性能及分布式、深入浅出。性能调优、TCP，协程，Nginx 源码分析 Nginx，ZeroMQ，MySQL，Redis，MongoDB，ZK，Linux 内核，P2P，K8S，Docker，TCP/IP，协程，DPDK 学习资料视频获取点击：C++架构师学习资料

C++后台开发视频链接：C/C++Linux服务器开发高级架构师/Linux后台架构师

根据待删除节点和唯一子节点颜色，分情况处理：
自身 O 是红色，子节点 N 是黑色，直接删除。
自身 O 是黑色，子节点 N 是红色，直接删除并将子节点 N 变为黑色。
自身 O 是黑色，子节点 N 不存在(不存在即子节点为空黑色节点，也可以用来判断)或也是黑色，较为复杂，先删除，再分情况讨论：1、N 是根节点，则不需要调整。2、如下图，N 的父亲、兄弟、侄子都是黑色，则将兄弟变为红色，父亲视作 N，进行递归处理。