红黑树

红黑树是一种自平衡的二叉查找树，它的每个节点都有一个颜色属性（红色或黑色）。红黑树的主要特性是：每个节点要么是红色，要么是黑色；根节点是黑色；每个叶子节点都是黑色的空节点（NIL）；如果一个节点是红色的，则它的两个子节点都是黑色的；从任一节点到其每个叶子节点的所有简单路径都包含相同数量的黑色节点。红黑树通过旋转和重新着色来保持平衡，从而确保了对数时间复杂度的插入、删除和查找操作。