红黑树（rbtree）、以及epoll的实现原理
epoll的实现原理，查看此篇博客
先明确：
在红黑树中，叶子节点指的是，没有子节点的节点的两个空节点，或者只有一个子节点的节点的另外一个空儿子，如下图所示：
1、定义
任意一棵红黑树，都要满足下列5个条件：
- ① 所有节点，要么是红色，要么是黑色
- ② 根节点是黑色
- ③ 所有叶子节点都是黑色（这其实算是一条定义，不过这5条描述的本来就是定义😂）
本条换个说法：从任意叶子节点到根的所有路径上不能有两个连续的红色节点 - ④ 每个红色结点的两个子节点都是黑色
- ⑤ 从根到任意一个叶子节点的路径中，包含的黑色节点数都相同
2、性质
从根到叶子的最长的可能路径 不多于 最短的可能路径的两倍长。
3、红黑树的操作
3.1 插入
3.2 删除
4、优点
使用O(logN)的时间复杂度查找任意节点。 且可以随时添加节点。
使用中序遍历可以进行范围查询，能够查询到比某个节点小的所有节点。
5、红黑树在epoll中的应用
这是
epoll的源码：
https://github.com/torvalds/linux/blob/master/fs/eventpoll.c
5.1
内核事件表里的每个文件描述符都对应红黑树中的一个节点，每个节点里都有一个epoll_event结构体成员。
当调用epoll_ctl()增加或删除文件描述符时，就是增加或删除红黑树的节点。
调用epoll_create时，内核除了帮我们在epoll文件系统里建了个file结点，还在内核cache里建了棵红黑树。
调用epoll_wait时，内核只把就绪的文件描述符存到一个链表里，并返回给应用程序。
5.2 epoll为什么不用hash(O(1)的查找)，而用红黑树
epoll“管理”的文件描述符数量不确定
如果使用hash，不管是用拉链法，还是用开放寻址法，都需要提前创建一个数组，但由于无法确定epoll管理的文件描述符数量，所以不知道数组要创建多大，所以没办法使用hash