红黑树

由红、黑两类节点组成的 BST（统一增设外部节点 NULL，使之成为真二叉树）：

  • 树根：必为黑色
  • 外部节点：均为黑色
  • 其余节点：若为红，则只能有黑孩子。即红之子、之父必黑
  • 外部节点到根：途中黑节点数目相等。即黑深度

提升各红节点，使之与其（黑）父亲等高 —— 于是每棵红黑树，都对应于一棵 (2, 4) 树。

增加

删除