红黑树

红黑树

R-B Tree，全称是Red-Black Tree，又称为“红黑树”，它一种特殊的二叉查找树。红黑树的每个节点上都有存储位表示节点的颜色，可以是红(Red)或黑(Black)。

红黑树的特性

  1. 每个节点或者是黑色，或者是红色。
  2. 根节点是黑色。
  3. 每个叶子节点（NIL）是黑色。
  4. 如果一个节点是红色的，则它的子节点必须是黑色的。
  5. 从一个节点到该节点的子孙节点的所有路径上包含相同数目的黑节点。

image

几个名词

parent: 父节点

sibling: 兄弟节点

uncle：叔父节点（parent的兄嘚节点）

grand: 祖父节点（父节点的父节点）

红黑树类比2-3-4树

红黑树和4阶B树(2-3-4)树具有等级性

BLACK节点与他的RED节点融合在一起，形成一个B数节点

红黑树的BLACK节点个数与4阶B树的节点总个数相等

image

红黑树类比2-3-4树的几种情况

image-20210616183039420