定义

红黑树的英文是“Red-Black Tree”，简称 R-B Tree。它是一种不严格的平衡二叉查找树。
红黑树是一种平衡二叉查找树。它是为了解决普通二叉查找树在数据更新的过程中，复杂度退化的问题而产生的。红黑树的高度近似 log2n，所以它是近似平衡，插入、删除、查找操作的时间复杂度都是 O(logn)。
红黑树不是完全平衡的二叉树：它从根节点到各个叶子节点的最长路径，有可能会比最短路径大一倍。
红黑树中的节点，一类被标记为黑色，一类被标记为红色。除此之外，一棵红黑树还需要满足这样几个要求：

  • 根节点是黑色的；
  • 每个叶子节点都是黑色的空节点（NIL），也就是说，叶子节点不存储数据；
  • 任何相邻的节点都不能同时为红色，也就是说，红色节点是被黑色节点隔开的；
  • 每个节点，从该节点到达其可达叶子节点的所有路径，都包含相同数目的黑色节点；

image.png

// todo