红黑树(B树)

红黑树的简单介绍

1. 红黑树是一中自平衡的二叉查找树
2. 它是一中特殊的二叉查找树，红黑树上的每一个结点都有储存结点的颜色、
3. 每一个节点可以是红或者黑，红黑树不是高度平衡的，他的平衡是通过“红黑规则”进行实现的

平衡二叉树和红黑树的区别

平衡二叉树

1. 高度平衡
2. 当左右子树的高度差超过1时通过旋转保持平衡

红黑树

1. 是一个二叉查找树
2. 但不是高度平衡的
3. 条件：特有的红黑原则

红黑树的模型

红黑树的红黑规则

解释问题

为什么红黑树要以红色为默认节点呢？
因为选择红色节点的话，整个结构查找的效率就会很高。

红黑树添加节点的规则

以以下结点构成的红黑树为例

这里的 $ 22 $ 违背了红黑规则

我先来解释一下什么是叔叔结点
叔叔节点就是当前节点的父结点的左边的那个结点
22的父节点是23，那么22的叔节点就是18

采取当前方案，因此将23和18都变成黑色，将祖父20变成红色，因为20为根因此将20再变为黑色

最后得到的红黑树是这个样子的

然后我们再来添加 $ 17 $ , $ 19 $ 和 $ 24 $结点

注意添加15结点的情况

添加节点15时进行完1的操作后 需要以18为当前节点重新来一次判断并进行操作

最后就是添加 $ 14 $ 结点的操作了，按照规则一步一步进行即可

假如添加的不是14结点而是16结点的话，就会是另外一种情况了

以上提到了那么多，那么红黑树到底是用来干嘛的呢？

1. 红黑树的增删改查的性能都非常好 因为它仅仅需要极少次数的旋转操作以及修改颜色操作就可以完成增删改查的功能