红黑树

红黑树什么用

• 查找key-value，查找性能快
  • 服务器管理连接socketfd（key）与客户端id（value）的映射关系
  • 内核内存管理
• 通过中序遍历，得到顺序结果
  • 进程调度，就绪队列

红黑树性质

5条

• 每个节点是红的或黑的
• 根节点是黑的
• 每个叶子节点是黑的
• 如果一个节点是红的，那他的两个儿子是黑的
• 对每个节点，从该节点到其子孙节点的所有路径上的包含相同数目的黑节点（黑高相同）