你了解红黑树么？告诉你一个不一样的红黑树，说点有意思的吧！

冬夜先生

修改于 2021-09-06 10:48:56

3980

修改于 2021-09-06 10:48:56

文章被收录于专栏：csico

先看如下两个问题：

问题1、红黑树的键值可以重复么？ 问题2、红黑树必须有键值么？

关于红黑树的介绍网上非常多，红黑树的应用也非常广泛。问一下度娘，她会告诉你各种各样的实现方法，C和C++版本都有，linux内核使用的版本也有。代码都大同小异，就是插入或删除时如何修正，如何搞平衡。很多文章图文并茂、写实而生动，当你在脑海里试图左旋一把，右旋一把搞平衡时，基本也到了精神崩溃的边缘。

如何维护祖孙三代父、祖父、叔叔以及兄弟间的平衡，如何搞好家庭关系，是个头疼的问题。如果把红黑树比作一个族谱的话，可能开始你是高祖，下个节点插进去后就变成了太宗，随着族系的繁衍最后你可能变成个哀帝。开始A是B爸爸，过会B又变成A爸爸，甚至是爷爷，叔叔、兄弟，你说乱不乱，烧脑烧脑，气人不气人。套用郭德纲在相声中对于谦说的话：到了咱们这个年纪，谁是谁爸爸都无所谓了。台上无大小，台下立规矩，送给台上的各种二叉树。

这里先介绍一个朴实无华的网站：可视化的数据结构和算法教学，非常不错，里面有经典数据结构的动态展现，可以将你从各种旋转中解救出来。如下图：

说了这么多回到本文开头的两个问题：

问题1：红黑树的键值可以重复么？

大部分人可能认为不可以重复，因为重复的键值会冲突或没有现实意义。其实是可以重复的。为了表达对二叉树的敬意，这里连续插入多个2。使用上面安利的网站，建立了一个很2的红黑树。如下图：

上面的红黑树键值都相等，非常不可思议，但它确实是棵红黑树。 那么这颗很2的红黑树的现实意义是什么，能应用到什么地方？当然有，而且很广泛，这个地方就是定时器，对于大部分服务器程序，基本都要实现自己的定时器，从而完成一些特殊的重复性工作，比如nodejs的引擎libuv库中的定时器，nginx中的定时器、以及redis的键值有效期判断等。。。。

当管理多个定时器时就会存在键值相等的节点，也就是到期时间相等的节点。这时候如何判断谁先执行呢？ 下面是libuv定时器实现的部分关键代码：

// libuv定时器使用回调函数来比较key的大小，这里的key就是到期时间timeout
static int timer_less_than(const struct heap_node* ha,
                           const struct heap_node* hb) {
  const uv_timer_t* a;
  const uv_timer_t* b;

  a = container_of(ha, uv_timer_t, heap_node);
  b = container_of(hb, uv_timer_t, heap_node);

  if (a->timeout < b->timeout)
    return 1;
  if (b->timeout < a->timeout)
    return 0;

  /* Compare start_id when both have the same timeout. start_id is
   * allocated with loop->timer_counter in uv_timer_start().
   */
   // 如果两者过期时间相同，则采用start_id来判断谁先执行
   // 这个start_id是个自增变量，后加入堆中的定时器的start_id要大于早加入堆中的定时器
  return a->start_id < b->start_id;
}

// 定时器启动并加入到堆中的函数
int uv_timer_start(uv_timer_t* handle,
                   uv_timer_cb cb,
                   uint64_t timeout,
                   uint64_t repeat) {
  uint64_t clamped_timeout;

  if (uv__is_closing(handle) || cb == NULL)
    return UV_EINVAL;

  if (uv__is_active(handle))
    uv_timer_stop(handle);

  clamped_timeout = handle->loop->time + timeout;
  if (clamped_timeout < timeout)
    clamped_timeout = (uint64_t) -1;

  handle->timer_cb = cb;
  handle->timeout = clamped_timeout;
  handle->repeat = repeat;
  /* start_id is the second index to be compared in timer_less_than() */
  handle->start_id = handle->loop->timer_counter++;

  // 将定时器插入堆中，并使用timer_less_than函数进行堆排序
  heap_insert(timer_heap(handle->loop),
              (struct heap_node*) &handle->heap_node,
              timer_less_than);
  uv__handle_start(handle);

  return 0;
}

libuv使用的是最小堆来保存和管理多个定时器，在排序的过程中如果发现时间相等的节点（见上面函数 timer_less_than），则采用start_id来比较大小，这个start_id是个自增变量，后加入堆中的定时器的start_id要大于早加入堆中的定时器。从而来判断键值相等的到期事件谁先执行。

回到上面很2的红黑树，如果你仔细观察这颗树的创建过程就会发现，对于键值相同的节点是有时间顺序的，插入晚的默认为大值，放在后面，也就是说红黑树自动实现了按时间轴存储键值的功能。即使到期事件相等（键值Key相等），我们也可以根据其插入红黑树的时间顺序来取出最小到期事件去执行。

nginx使用的就是红黑树的方式来存储和管理多个定时器。这里就不再介绍了，可以问度娘要源码分析。

问题2、红黑树必须有键值么？

这棵树也是可以创建的，只不过看上去比上面很2的树还难理解。上面libuv的定时器节点大小比较函数 timer_less_than已经告诉我们了，你是可以在比较节点的时候不依赖于key值，在你的插入节点时，通过回调函数来告诉节点谁是“大”的谁是“小”的，这个大小不是数学意义上的大小，可能是业务上一个逻辑业务的大小。通过一系列多个指标而非单一key，来评估一个节点的在业务上而非数学上的前后顺序。比如个人信用的评估，可能要根据多项指标（年龄、工龄、消费记录等）来计算出一个所谓的“大小”值。

写的太多了，赶紧上班就此打住，权当抛砖引玉吧。

感谢您的阅读！

本文系转载，前往查看

如有侵权，请联系 cloudcommunity@tencent.com 删除。

二叉树