数据结构理解与红黑树

谈红黑树之前，首先谈谈自己对于数据结构的理解：
数据结构中的物理结构只有数组和链表两种结构，对于其它的数据结构，基本都为逻辑结构。既然是逻辑结构，其实就是我们在编写程序中，为了满足某一类应用场景而设计出来的一套通用的标准逻辑结构。从此这一套逻辑结构就成实现该类应用场景的标准解决办法。既然是逻辑结构，自然需要为这套逻辑设计规则，以使得我们在对结构进行CURD时使得这套结构能永远的满足设计好的逻辑标准。

因此在学习一套数据结构时，就可分为以下几个步骤:
1.数据结构解决什么问题？
2.数据结构的规则时怎样的?
3.数据结构进行CURD操作时，数据结构需要怎样变化？

红黑树

1.红黑树为了解决什么问题？

了解红黑树之前首先要了解二叉查找树，二叉查找树的特征如下：

1. 某节点的左子树节点值仅包含小于该节点值
2. 某节点的右子树节点值仅包含大于该节点值

看个图就轻松理解上面三句话的意思了:

image.png

上图，结合二叉查找树的三条约束来看，非常好，没有什么问题。再来看一个图，依旧符合上面三条约束，感觉有问题吗？

image.png
因为一些特定的条件下导致树的深度变得很大，就会造成在查询的时间复杂度 O(h)无限增长。
红黑树的出现正是为了解决这个问题，通过为树的节点标记颜色，制定规则的方式，使得二叉查找树即使在特殊情况下，也不会出现深度无限变大的情况。

同时相对与其它的二叉查找树，红黑树在频繁的插入删除节点时时间复杂度更低

2.红黑树为解决树深度无限变大的问题，在二叉查找树的基础上又制定了那些规则？

红黑树，Red-Black Tree 「RBT」是一个自平衡(不是绝对的平衡，左右子树的高度差可能会大于1)的二叉查找树(BST)，树上的每个节点都遵循下面的规则:

1. 每个节点有一个颜色属性：红色或黑色
2. 树的根始终是黑色
3. 红色节点不可相邻（黑色节点可以相邻）
4. NULL节点看成黑色节点，从任一节点（包括根）到其任何后代NULL节点的每条路径都具有相同数量的黑色节点

3.红黑树在CRUD时如何根据规则进行变化？

红黑树的变化主要通过两种方式来实现：
1.recolor 节点重新着色
2.rotation 树的旋转 (树平衡的关键)

首先是增加节点：
1.新插入的节点均标记为红色（X为新插入节点）
2.插入节点为根节点时将节点变为黑色（红黑树规则2）
3.分为一下几种情况
3.1 插入节点父节点为黑色 （直接插入）
3.2 插入节点父节点为红色，父节点同级节点（叔叔节点）为红色 （直接插入违背红黑树规则3）
违背规则后的解决办法是recolor：
1.将父节点和叔叔节点变为黑色
2.将祖父节点变为红色
3.插入节点
4.检查根节点颜色，若为红色变为黑色

image.png
图中最后将根节点变为黑色
3.3 插入节点父节点为红色，父节点同级节点（叔叔节点）为黑色 （直接插入违背红黑树规则3）
违背规则后的解决办法是recolor+rotation：
左左情况（父节点是祖父节点的左节点，新节点为父节点的左节点）：
这种情况很简单，想象这是一根绳子，手提起 P 节点，然后变色即可
image.png
左右情况（父节点是祖父节点的左节点，新节点为父节点的右节点）：
先子树旋转变为左左情况，然后再执行左左情况
image.png
右右情况（父节点是祖父节点的右节点，新节点为父节点的右节点）：
和左左情况处理方法一样，看成一个绳子
image.png
右左情况（父节点是祖父节点的右节点，新节点为父节点的左节点）：
子树先旋转为右右情况，然后执行右右情况
image.png

常见应用场景：

1. Linux的的进程调度完全公平调度程序，用红黑树管理进程控制块，进程的虚拟内存区域都存储在一颗红黑树上，每个虚拟地址区域都对应红黑树的一个节点，左指针指向相邻的地址虚拟存储区域，右指针指向相邻的高地址虚拟地址空间;

2.IO多路复用的epoll的的的实现采用红黑树组织管理的的的sockfd，以支持快速的增删改查;

3.Nginx的的的中用红黑树管理定时器，因为红黑树是有序的，可以很快的得到距离当前最小的定时器;

参考链接：https://www.jianshu.com/p/104fa73c81b3