一、什么是红黑树?
红黑树是一种自平衡的二叉查找树,它在二叉查找树的基础上增加了颜色属性和平衡规则,确保树的高度始终保持在O(log n)级别,从而保证各种操作的时间复杂度为O(log n)。
二、红黑树的五大特性
红黑树必须满足以下五个核心特性:
- 节点颜色特性:每个节点要么是红色,要么是黑色
- 根节点特性:根节点必须是黑色
- 叶子节点特性:所有叶子节点(NIL节点)都是黑色
- 红色节点特性:红色节点的两个子节点都必须是黑色(即不能有连续的红色节点)
- 黑色高度特性:从任意节点到其所有后代叶子节点的路径上,黑色节点的数量必须相同