Red-Black Tree

用途

  • Nginx Timer时间管理：服务器高并发IO的keep alive方案

    • 中序遍历：定时器将全部符合条件的结点都释放

  • 线程、进程调度(CFS)

  • Epoll事件的组织

  • stl中的std::set和std::map

  • key-value

    • 网络服务器长连接存放<id, fd>

结构

  • 可以使用宏定义将红黑树的key-value和性质分离
#define RBTREE_ENTRY(name, type)\
	struct name{
		strcut type *right;	 \
        struct type *left;   \
        struct type *parent; \
        unsigned char color; \
	} \