红黑树

1. 友情博客链接

• 重点解读
  1. 红黑树是近视平衡。插入 删除比平衡二叉树要快，相对查找要略低。但是相对于其他树来说稳定。在极端情况下也不会蜕变为单边树
  2. 红黑树中包含最多黑色节点的路径不会超过 log2n，所以加入红色节点之后，最长路径不会超过 2log2n，也就是说，红黑树的高度近似 2log2n
  3. 高度和查找性能成反比。高度高查找慢
     

redis的zset为何用跳表，不用红黑树

1. Redis 中的有序集合支持的核心操作主要有以下几个：

       1.插入一个数据
       1.删除一个数据
       1.查找一个数据
       1.按照区间查找数据
       1.迭代输出有序序列
   其中，插入、删除、查找以及迭代输出有序序列这几个操作，红黑树也可以完成，时间复杂度和跳表是一样的。
   但是，按照区间查找数据这个操作，红黑树的效率没有跳表高。跳表可以在 O(logn)
   时间复杂度定位区间的起点，然后在原始链表中顺序向后查询就可以了，这样非常高效。
   此外，相比于红黑树，跳表还具有代码更容易实现、可读性好、不容易出错、更加灵活等优点，因此 Redis 用跳表来实现有序集合

二叉树遍历

理解二叉树中4种遍历方法