数据结构-红黑树（数据结构红黑树重要吗）

红黑树（Red Black Tree）：也是一种自平衡的二叉搜索树（BST），之前叫做平衡二叉B数（Symmetric Binary B-Tree）。

红黑树的性质（防止旋转，保持平衡）：

1、节点要么是红色，要么是黑色

2、根节点是黑色

3、叶子节点都是黑色的空节点

4、红黑树中红色节点的子节点都是黑色

5、从任一节点到叶子节点的所有路径都保持相同数目的黑色节点

红黑树的复杂度：

查找

红黑树也是一棵BST(二次搜索树)树，查找操作的时间复杂度为：O(log n )

添加

添加先要从根节点开始找到元素添加的位置，时间复杂度O(log n)

添加完成后涉及到复杂度为O(1)的旋转调整操作

故整体复杂度为：O(log n)

删除

首先从根节点开始找到被删除元素的位置，时间复杂度O(log n )

删除完成后涉及到复杂度为O(1)的旋转调整操作

故整体复杂度为：O(log n )

回答总结：

红黑树（Red Black Tree）：也是一种平衡二叉搜索树（BST）

所有的红黑规则都是希望红黑树能够保存平衡

红黑树的时间复杂度：查找、添加、删除都是O(log n)