红黑树是一种二叉搜索树。它是BST的一种变体，具有精细版本的插入和删除操作，这些操作在运行时重新组织树，使树永远不会变得“长而紧凑”。树变得越长和越紧凑，它就越像一个链接列表。平均而言，链接列表操作需要访问一半的列表（或在最坏情况下访问整个列表），因此运行时间与元素数量n呈线性变化（O(n)）。当树“丰满”或接近平衡时，每个操作则要便宜得多（ O(log n) ）。红黑算法保证树始终保持丰满。
为了使这更具体，这里有两棵存储A到G键的树。左边是长而紧凑的。注意它看起来像一个列表。在最坏的情况下，需要进行4次键比较才能找到元素。右边的树是丰满的。它只需要3次。这里的差异很小。对于一个包含1023个元素的树，紧凑的树需要512次比较，而丰满的树只需要10次。这就是log n的威力。
B _D_
/ \ / \
A D B F
/ \ / \ / \
C F A C E G
/ \
E G
红黑树并不能保证完全的“平衡”，但是红黑规则确保其以一种数学严格的方式足够“平衡”，从而使得操作时间随log n而变化，而不是随n线性变化。
红黑规则之所以如此出色，是因为它们是“局部的”。 在插入或删除破坏规则时，只需要调整每个节点所接触的常数数量的节点即可恢复规则。 因此，它们便宜而且相当容易实现。
然而，当红黑规则对整个树都成立时，可以通过巧妙的数学证明显示它足够“平衡”，如上所述。
那么树映射呢？ 映射是具有定义域称为键集K和值域称为值集V的函数。 为了实现树映射，每个节点存储一个键值对<k，v>，其中k \in K和v \in V。 在上面的图纸中（以及大多数演示文稿中），仅显示键（字母A-G）。在映射中，插入，查找和删除对这些对进行相当明显的处理。 例如，查找使用常规BST算法搜索键。 找到键后，由于它与值在同一个对中，因此也找到了值。返回值。 在java中，该对称为 Map.Entry 。 您可以在Java源代码中查看。
我不会详细介绍红黑规则的工作方式，因为我无法改进维基百科页面上的内容。 我猜测和希望您错过了“大局”，所以现在讨论会有意义。好消息是，几乎所有语言都提供了经过充分测试和性能优化的树实现，因此不必了解旋转的奥秘。 当然，如果您很好奇，只是想知道，请随意尝试！ 恭喜！
值得一提的是，Top Coder关于算法的解释并非总是最清晰的。 找寻其他解释，直到有一个“点击”为止。 CS领域的受人尊敬的教科书之所以受到尊重，是因为它们的解释非常出色。 Corman和Rivest是被广泛接受的喜欢的教科书。
O(n)。使用平衡二叉搜索树而不是非平衡二叉搜索树的主要优点是，在插入/删除节点时只涉及很少的开销，即可将所有操作的最坏情况下降到O(logn)。请看这里。