This is my study note of Red-black tree.

红黑树的结构

Alt text

平衡属性

1
任意节点左右子树高度相差不大于1.红黑树保证最长路径不超过最短路径的两倍，因黑色节点相同时，最长路径刚好是最短路径的两倍。

红黑树的特点

  • 根节点是黑色 叶结点是不存储数据的黑色空节点（空节点）
  • 任何相邻的两个节点不能同时为红色
  • 任意节点到其可到达的叶结点间包括相同数量的黑色节点

时间复杂度

1
插入、删除、查找：时间复杂度logn