红黑树：一种自平衡二叉搜索树（self-balancing binary search tree）。它通过给每个节点赋予“红/黑”颜色并遵守一组规则（如根为黑、红节点不能相邻、从任一节点到其所有叶子路径包含相同数量的黑节点等），在插入与删除后通过旋转与重新着色保持树高接近对数级，从而使查找、插入、删除通常为 **O(log n)**。
（该术语也可在更广义上指“红黑树数据结构”及其实现。）
/ˌrɛd ˈblæk triː/
A red-black tree keeps operations efficient as data grows.
红黑树会在数据增长时保持操作高效。
In many standard libraries, ordered maps are implemented with a red-black tree to guarantee near-logarithmic performance for insertion and lookup.
在许多标准库中，有序映射常用红黑树实现，以保证插入与查找具有接近对数级的性能。
“red-black（红-黑）”来源于节点的两种颜色标记，并非真实颜色，而是用来表达结构约束的抽象属性；“tree（树）”在计算机科学中常用来比喻层级分支结构。红黑树作为平衡搜索树家族的一员，流行于教材与工程实现中，因其在保持平衡与实现复杂度之间取得了实用折中。
Select Language