红黑树

在其他语言中阅读： 葡萄牙语

红黑树 是一种自平衡的二叉搜索树，在计算机科学中。二叉树的每个节点都有一个额外的位，这个位通常被解释为节点的颜色（红色或黑色）。这些颜色位用于确保在插入和删除过程中树保持大致平衡。

通过以某种满足一定属性的方式给树的每个节点涂上两种颜色来保持平衡，这些属性共同限制了树在最坏情况下可以变得多不平衡。当树被修改时，新树随后会被重新排列和重新着色以恢复涂色属性。这些属性被设计得如此高效，以至于这种重新排列和重新着色可以被有效地执行。

树的平衡并不是完美的，但足够好，允许它保证在O(log n)时间内进行搜索，其中n是树中元素的总数。插入、删除操作以及树的重新排列和重新着色也都在O(log n)时间内完成。

红黑树的一个例子：

红黑树

属性

除了对二叉搜索树所施加的要求外，红黑树还必须满足以下条件：

一些定义：从根节点到节点的黑节点数量是节点的黑深度；从根节点到叶子节点的所有路径中的黑节点均匀数量称为红黑树的黑高度。

这些约束强制红黑树具有一个关键属性：从根节点到最远叶子的路径长度不会超过从根节点到最近叶子节点路径长度的两倍。结果是树大致上是高度平衡的。由于插入、删除和查找值等操作的时间与树的高度成比例，这种理论上的最大高度上限允许红黑树在最坏情况下也是高效的，不同于普通的二叉搜索树。

红黑树平衡

红黑树平衡

红黑树平衡

红黑树平衡

红黑树平衡