数据结构 | 红黑树

二叉搜索树

节点的左边比节点的值小，右边比节点的值大。

红黑树

红黑树的性质

• 节点要么是红色，要么是黑色
• 根节点是黑色
• 叶子节点都是黑色的空节点
• 红黑树中红色节点的子节点都是黑色
• 从任一节点到叶子节点的所有路径都包含相同数目的黑色节点

在添加或者删除节点的时候，如果不满足这些性质会进行旋转，这些性质就是为了保证平衡。

什么是红黑树

• 红黑树： 也是一种自平衡二叉搜索树
• 所有的红黑规则都是希望红黑树能够保证平衡
• 红黑树的时间复杂度： 查找、添加、删除都是O(log n)。