红黑树(R-B)-构造解释

• 概念

  • 是一棵近似平衡的树，整体性能会比绝对平衡的AVL树要好
  • 满足如下条件
    • 每个节点都有颜色，不是黑色，就是红色
    • 根节点必须是黑色
    • 不存在连续的的红色节点
    • 对于每个节点，从该节点到后代叶节点的简单路径上，均包含相同数目的黑色节点
  • 在上述条件下，会保证最长路径不超过最短路径的二倍，因此近似平衡

• 用途

  • Jave的 TreeMap和ConcurrentHashMap
  • C++的 map
  • epoll管理事件块
  • linux管理进程控制块