红黑树

在计算机科学中，红黑树是一种自平衡二叉搜索树。每个节点存储一个表示"颜色"的额外位，用于确保在插入和删除过程中树保持平衡。

这些是2-3树（见下文）的一种转换形式。

在实践中：红黑树为插入时间、删除时间和搜索时间提供了最坏情况保证。这不仅使它们在时间敏感的应用程序（如实时应用程序）中很有价值，而且使它们成为其他提供最坏情况保证的数据结构中有价值的构建块；例如，计算几何中使用的许多数据结构可以基于红黑树构建，当前Linux内核中使用的完全公平调度器使用红黑树。在Java的版本8中，Collection HashMap已被修改，不再使用LinkedList来存储具有较差哈希码的相同元素，而是使用红黑树。