近期读《Linux内核设计与实现_第三版_清晰中文版》，发现Linux低层数据结构很多都用到红黑树，查查资料说说自己的理解。
红黑树:二叉树+高度限制
二叉树：确定了它的查找非常快。
高度限制：这个是取普通二叉树和平衡二叉树之间。
普通二叉树，只管插入不做调整，可能会出现单链很长。
平衡二叉树，所有的链高度相等，但存就需要调整，非常耗时。
红黑树，最长单链不会超过最短单链2倍，这样也确定它存的耗时也居中。
红黑树特点5条：
1.所有节点非红及黑。
2.根节点为黑节点。
3.所有叶子节（null）点为黑色。
4.所有节点到叶子节点中黑色节点数目相同。（确定最长单链不会超过最短单链2倍）
5.如果一个节点为红色，则它的子节点节点必须为黑色。
红黑树的操作：
查：二叉树的特性决定它高效。
增：加入红节点，根据旋转、着色来保持红黑树特性。
删：根据旋转、着色来保持红黑树特性。
细节逻辑没去实现，参考：https://www.cnblogs.com/nananana/p/10434549.html
原文：https://www.cnblogs.com/zhuyapeng/p/13750644.html