什么是红黑树？
红黑树是一种自平衡的二叉查找树，是一种高效的查找树。它是由 Rudolf Bayer 于1972年发明，在当时被称为对称二叉 B 树(symmetric binary B-trees)。后来，在1978年被 Leo J. Guibas 和 Robert Sedgewick 修改为如今的红黑树。红黑树具有良好的效率，它可在 O (logN) 时间内完成查找、增加、删除等操作。因此，红黑树在业界应用很广泛，比如 Java 中的 TreeMap，JDK 1.8中的 HashMap、C++ STL 中的 map 均是基于红黑树结构实现的。
简单介绍一下什么是O(logN)
当我们谈论算法的效率时，我们通常使用时间复杂度来描述算法的运行时间与输入规模之间的关系。时间复杂度以大O符号（O）表示。
时间复杂度 O(logN)
在时间复杂度中，O(logN) 是一种非常高效的情况。它表示算法的运行时间与输入规模的对数成正比。这意味着随着输入规模的增加，算法的运行时间将以对数的速度增长。
具体来说，假设一个算法的时间复杂度是 O(logN)，其中 N 代表输入规模。当 N 增加时，该算法的运行时间将以对数的速度增加。这意味着随着输入规模的翻倍，该算法的运行时间仅会略微增加。
O(logN) 的高效性来自于对数函数的特性。对数函数具有一个很快的增长速度，但在开始时增长很快，随着输入的增加，增长速度逐渐减缓。这使得算法能够在处理大规模输入时保持相对较低的运行时间。
红黑树的基本概念（应付面试官）
红黑树是一种特殊的二叉查找树，它除了满足二叉查找树的基本性质外，还具有以下几个特点：
- 每个节点都有一个颜色属性，要么是红色，要么是黑色。
- 根节点的颜色是黑色。
- 所有叶子节点（NIL节点）的颜色都是黑色。
- 如果一个节点是红色，那么它的两个子节点都是黑色。
- 从任意一个节点到其所有后代叶子节点的简单路径上，包含相同数量的黑色节点。
这些性质保证了红黑树在插入和删除操作后能够自动调整，使得树保持平衡状态。平衡状态指的是从根节点到叶子节点的最长路径不超过最短路径的两倍。这样就避免了二叉查找树在极端情况下退化成链表，导致效率降低。
红黑树的性质
为了方便分析，我们定义以下几个概念：
- 黑高（black-height）：从某个节点出发（不包括该节点）到达一个叶子节点的任意一条路径上，黑色节点的个数称为该节点的黑高，记为 bh(x)。
- 红黑性质（red-black property）：指红黑树满足上述五个性质。
- 红黑树（red-black tree）：一棵满足红黑性质的二叉查找树。
有了这些定义，我们可以推导出以下几个重要的性质：
- 性质1：一棵有 n 个内部节点（非 NIL 节点）的红黑树，其高度 h 不超过 2log(n+1)。证明：设 x 是红黑树中任意一个内部节点，h(x) 是以 x 为根的子树的高度，n(x) 是以 x 为根的子树内部节点的个数。由于 x 的两个子节点至少有一个是黑色（性质4），所以 h(x) >= bh(x)。另一方面，由于从 x 到其后代叶子节点的任意路径上至少有一半是黑色（性质5），所以 bh(x) >= h(x)/2。综合起来，有 h(x) >= bh(x) >= h(x)/2。由此可得 h(x) = 2^bh(root) - 1。综合起来，有 h
