数据结构-红黑树

红黑树的条件

  * 节点都有颜色标记，且只能是红色或黑色。

  * 根节点只能是黑色

  * 所有叶子都是黑色（叶子是NIL/nill 节点，不保存实际的数据）。

  * 从每个叶子到根的所有路径上不能有两个连续的红色节点。

  * 从任一节点到其每个叶子的所有简单路径都包含相同数目的黑色节点。

新增节点

  * 新增节点必为红色

注意：在红黑树中null节点相当于黑节点

 

 1.插入0002这个节点（父节点为黑：无需操作）

2.插入0003节点（父节点为红，叔节点为黑，且为右右类型）

 

 左旋：

 变色：

3.插入0004节点（父节点，叔节点都为红）

 

 

0002为根节点

所以：

 

 4.插入0011节点（父节点为红，叔节点为黑（null）且为右左类型）

 右旋：

 变为了右右类型：

左旋：

变色：

 

 

 

左旋理解：

相关节点中父节点左旋：就变为了（相关节点有1，2，3  旋转前父节点为1）

 

 右旋理解：

同理相关节点的父节点右旋。也就是3右旋就变为

 

视频链接：

https://www.bilibili.com/video/BV1Pp4y1D7u1?spm_id_from=333.880.my_history.page.click&vd_source=2c8d3b8b4e9d03424a43fa463ee9dc24 

  数据结构——红黑树简谈_shintyan的博客-CSDN博客_红黑树数据结构