红黑树(一):构建红黑树

每天学Java

发布于 2020-06-01 10:50:24

1.6K0

发布于 2020-06-01 10:50:24

文章被收录于专栏：每天学Java每天学Java

前两篇文章谈了B-Tree和B+Tree，它们属于多路平衡树，所有叶子结点都在同一层，除了这两种平衡树，我们熟知的还有平衡二叉树和红黑树。这一篇文章就来看看如何构建红黑树

对于平衡二叉树的构建，可以参考小程序中的文章(C++版)。

平衡二叉树

红黑树

红黑树属于平衡二叉树，但是并非严格意义上的平衡二叉树，因为平衡二叉树要求节点的左右子树高度差不超过1，而红黑树放弃了这种高度平衡，利用对结点上色的操作来保证树相对平衡，这其中原因大概是维护一个绝对平衡的二叉树代价太大，在插入操作比较频繁的情况下，其性能上的收益并不大(HashMap采用红黑树而不是平衡二叉树的原因)。

但如果插入频率小或者只有一次构建，那么平衡二叉树的查询性能还是比红黑树高。

性质

1> 所有结点颜色是黑色或者红色

2> 根结点为黑色

3> 每个叶子结点为黑色(这里的叶子结点指的是为null的结点)

4> 红色结点的孩子结点必须是黑色结点

5> 任意一结点到每个叶子结点所经过的黑结点个数相同

从上面的性质我们大概知道红黑树的结构，树根为黑色，不存在连续的两个红色结点，每个子树分支的黑结点个数相同，如下图

平衡操作

同平衡二叉树一样，构建过程中，平衡逻辑是最关键的，通常情况下，我们插入的结点默认是红色，因为这样不会打破性质五，使得任一结点到每个叶子结点所经过的黑结点个数相同。

此时红黑树构建平衡分为4种情况:

情况一:红黑树为空树，此时插入结点充当根结点，上色为黑

情况二:插入结点已经存在，此时替换插入结点值即可

情况三:插入结点的位置，其父结点是黑色，此时平衡未打破，插入完成

情况四:插入结点的父结点是红色，此时平衡打破，需要进行平衡操作。

当情况四出现时候，说明需要进行平衡操作，此时操作逻辑如下：

情况4.1:插入结点的父结点，不存在兄弟结点，且插入结点与父结点在方向上相同(同为左子树或右子树)，此时需要进行右旋转或者左旋(根据父结点位置来决定，图一是右旋转，图二是左旋)

图一的平衡过程是将-1设置为黑色，1设置为红色，以1结点为基准进行右旋

图二的平衡过程是将2设置为黑色，1设置为红色，然后以1结点为基本进行左旋。

注:也可以将-2/5设置为黑色，然后以1右旋/左旋，但是此时-1/2为红色，如果父结点为红色，那么需要继续平衡

平衡结果:

情况4.2:插入结点与父结点在结点方向上不同，父结点是右子树，插入结点是左子树或者父结点是左子树，插入结点是右子树，如下图，需要先调整父结点，然后按照情况4.1进行调整

情况4.3:插入结点的父结点，存在兄弟结点，此时由于性质5，那么改兄弟结点必然为红色，因为如果是黑色，叔叔结点所在的子树的黑色结点就比插入结点的父结点所在子树的多了黑结点, 如下，如果1为黑色，那么性质5就被打破。此时平衡操作是:如果-1不是根结点，将-1设置为红色， -2和1设置为黑色，完成平衡，如果-1是根结点，那么只需要将-1和-2设置为红色即可。