Linux理论与编程：红黑树

使用案例：如 linux内核中，完全公平调度策略CFS的运行队列使用"红黑树"方法管理属于其的进程。红黑树是“半平衡二叉树”！效率好！！！使用rb_entry、rb_insert_color、rb_erase等。Linux代码关键结构体如下：struct rq { ------------ 每个CPU都有一个。
   struct cfs_rq cfs;
   struct rt_rq rt;    ...}
/* CFS-related fields in a runqueue */
struct cfs_rq {
    struct rb_root tasks_timeline;    ------ 红黑树的根，完全公平调度策略使用红黑树存储所有相关进程。
   struct rb_node *rb_leftmost;      ------- 查找下一个待执行进程的快捷方式。
    ...
} struct rt_rq {
   struct rt_prio_array active;   ---- 双向指针的数组，用来分别链接不同优先级的进程链表。
    ...}

每个进程都对应为一个红黑树节点。
struct sched_entity {
   struct rb_node       run_node;    ...
}struct sched_rt_entity {
   struct list_head run_list;
    ...
}
struct task_struct {;
   struct sched_entity se;
   struct sched_rt_entity rt;    ...}