基于树的查找--------------红黑树(2)

http://blog.chinaunix.net/uid-27033491-id-3305959.html

void rb_insert_color(struct rb_node *node, struct rb_root *root)
//将node节点插入到root为根的树中
{
struct rb_node *parent, *gparent;//定义parent为父节点，gparent为爷爷节点。

while ((parent = rb_parent(node)) && rb_is_red(parent)) //循环出口是父节点颜色不是红色。
{
gparent = rb_parent(parent);//给爷爷节点初始化。

if (parent == gparent->rb_left)//如果parent是左子树。
{
{
register struct rb_node *uncle = gparent->rb_right;//定义node的叔叔节点
//case 1
if (uncle && rb_is_red(uncle))//如果叔叔节点存在，而且是红色。
{
rb_set_black(uncle);//设置叔叔节点为黑色。
rb_set_black(parent);//设置父节点为黑色
rb_set_red(gparent);//设置爷爷节点为红色。
node = gparent;//让node指向爷爷节点，不断从低向上迭代。
continue;
}
}
//case 2
if (parent->rb_right == node) //如果node为右节点。
{
register struct rb_node *tmp;
__rb_rotate_left(parent, root);//以node的父节点为轴，左旋。
tmp = parent;//如果node和parent交换位置。
parent = node;
node = tmp;
}
//case 3
rb_set_black(parent);//设置父节点为黑色。
rb_set_red(gparent);//设置爷爷节点为红色。
__rb_rotate_right(gparent, root);//将爷爷节点右旋。
} else { //如果parent是右子树。和上面的都是对称的。
{
register struct rb_node *uncle = gparent->rb_left;
if (uncle && rb_is_red(uncle))
{
rb_set_black(uncle);
rb_set_black(parent);
rb_set_red(gparent);
node = gparent;
continue;
}
}

if (parent->rb_left == node)
{
register struct rb_node *tmp;
__rb_rotate_right(parent, root);
tmp = parent;
parent = node;
node = tmp;
}

rb_set_black(parent);
rb_set_red(gparent);
__rb_rotate_left(gparent, root);
}
}

rb_set_black(root->rb_node);//最后设置根节点为黑节点。
}

--------------------------------------------------------------------------------------------

 325 /*
 326 * Enqueue an entity into the rb-tree:
 327 */
 328 static void __enqueue_entity(struct cfs_rq *cfs_rq, struct sched_entity *se)
 329 {
 330     struct rb_node **link = &cfs_rq->tasks_timeline.rb_node;//获取红黑树的根。
 331     struct rb_node *parent = NULL;
 332     struct sched_entity *entry;
 333     s64 key = entity_key(cfs_rq, se);//获取该节点的key值。
 334 int leftmost = 1;
 335
 336 /*
 337 * Find the right place in the rbtree:
 338 */
 339 while (*link) { //根据该节点的key值找红黑树中应插入的位置。
 340         parent = *link;
 341         entry = rb_entry(parent, struct sched_entity, run_node);
         //由红黑树的节点返回到调度实体。
 342 /*
 343 * We dont care about collisions. Nodes with
 344 * the same key stay together.
 345 */
 346 if (key < entity_key(cfs_rq, entry)) {
 347 link = &parent->rb_left;
 348 } else {
 349 link = &parent->rb_right;
 350             leftmost = 0;//一旦有朝右走，则将该leftmost标志设置为0
 351 }
 352 }
 353
 354 /*
 355 * Maintain a cache of leftmost tree entries (it is frequently
 356 * used):
 357 */
 358 if (leftmost) //如果在插入新节点的时候，一直都在往左走，
         //则说明新插入的节点插在树的最左边， 则需要更新leftmost值，只要有向右走，该值就不需要更新。
 359         cfs_rq->rb_leftmost = &se->run_node;
     //如果插入节点的插在最左边，则将CFS的运行队列中维护的leftmost指针更新为当前节点。
 360
 361     rb_link_node(&se->run_node, parent, link);
     //将该节点，与parent这个节点链接起来。实际上有两道链接，类似于“双向链表”
 362     rb_insert_color(&se->run_node, &cfs_rq->tasks_timeline);
        //调整红黑树。保证插入一个节点后仍然是红黑树。
 363 }

   my_rb_tree.rar
---------------------------------------------------------------------------------------------