红黑树，本质上是一棵二叉查找树。在二叉查找树的基础上增加了着色和相关的性质使得红黑树相对平衡，从而保证了红黑树的查找、插入、删除的时间复杂度最坏为O(logn)。

二叉查找树

二叉查找树的性质：

  • 若任意结点的左子树不空，则左子树上所有结点的值均小于它的根结点的值；
  • 若任意结点的右子树不空，则右子树上所有结点的值均大于它的根结点的值；
  • 任意结点的左、右子树也分别为二叉查找树。
  • 没有键值相等的结点（no duplicate nodes）。

因为，一棵由n个结点，随机构造的二叉查找树的高度为lgn，所以顺理成章，一般操作的执行时间为O（lgn）。

但二叉树若退化成了一棵具有n个结点的线性链后，则此些操作最坏情况运行时间为O（n）。后面我们会看到一种基于二叉查找树-红黑树，它通过一些性质使得树相对平衡，使得最终查找、插入、删除的时间复杂度最坏情况下依然为O（lgn）。

红黑树

如何保证一棵n个结点的红黑树的高度始终保持了在 h = logn 的呢？

红黑树的5条性质：

  • 每个结点要么是红的，要么是黑的；
  • 根结点是黑的；
  • 每个叶节点是黑的；
  • 如果一个结点是红的，那么它的两个儿子都是黑的；
  • 对于任一结点而言，其到叶节点的每一条路径都包含相同数目的黑结点。

image.png

树的旋转知识

https://github.com/julycoding/The-Art-Of-Programming-By-July/blob/master/ebook/zh/03.01.md