红黑树的模拟实现中的插入功能详细讲解，附模拟实现代码

本文主要是介绍红黑树的模拟实现中的插入功能详细讲解，附模拟实现代码，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

一、红黑树的基本性质

1-1 红黑树的概念

红黑树，是一种二叉搜索树，但不同于AVL树的点在于，红黑树维护树的平衡是通过颜色来判断，而不是通过平衡因子。红黑树的每一个节点通过增加一个存储位来表示结点的颜色，颜色分别是RED和BLACK，通过对任何一条路径上的各个结点着色方式的限制来确保其没有一条路径回避其他路径长出两倍，因而接近平衡（对于计算机来说，logN和2*logN的速度差别并不大）、

1-2 红黑树的性质

1.每个结点不是红色就是黑色，但是两个红色的结点不可以连在一起，黑色结点可以

2.根结点是保证为黑色

3.如果一个结点是红色的，那么其两个孩子的结点就必须是黑色的

4.对于每一个结点，从该结点到其后代的叶结点中，每一条路径包含的黑色结点必须是相同的

5.每个叶子结点都是黑色的（此处的叶子结点指的是空结点）

二、插入功能的讲解

红黑树的插入有多种情况，所以对于插入分析时，需要明确几个问题：

1.插入的结点是为什么颜色更加合理？

2.有什么情况，在什么情况下可以使用旋转来平衡，又是在什么情况下不用使用到旋转？

对于第一个问题，我们可以分析一下，如果插入的是红色，那么就可能会破坏规则3，也就是可能有两个红色结点相连，如果插入的是黑色，那么就一定会破会规则4，因为插入黑色结点，就一定会出现不是每一条路径上的黑色结点的数量是一样的问题。所以对于可能发生的错误和一定发生的错误之间，应该选择红色结点。

图示分析：

在这种情况下，插入红色结点不会引发错误

在这种情况下会引发错误，但是错误的引发不是一定的。

接着，对于第二个问题的解决，也就是情况的分析：

第一种情况：cur为插入的新结点，此时parent和uncle均为红色，grangfather为黑色的时候

分析：

这是一种针对于第一种情况的简单红黑树模型的分析，此时，cur可以当作是新插入的结点，那么这个时候需要调节颜色，因为红节点之间相连违背了规则，那么解决方案可以是：将parent和uncle转化为黑色，grandfather转化为红色，这一部分子树，就满足了红黑树的要求。

转化后变为：

对于第一种情况的一般化：

当cur不为新插入结点，而只是红黑树其中的一个子树部分的节点时，更新方式也是和上面一样，将parent和uncle变为黑色，grandfather变为红色，然后让cur=grandfather，继续向上更新，直到遇到了当grandfather为红色的时候，grandfather的父亲结点颜色为黑色的时候，就可以停止更新。

第二种情况：cur为红色，parent为红色，grandfather为黑色，但是uncle却为黑色或者不存在

（如果uncle变为黑色或者不存在，就说明在这一步之前，这个节点已经经历过了一次添加新的结点，在添加这个新的结点后，uncle就会变为黑色，那么，如果再加上一个结点，就说明这个子树的高度差已经是2了，需要调整了，也就是通过旋转来维持平衡了；对于unlce不存在，可能是因为之前旋转的时候将这个结点的左边或者右边的结点调走，使得其由于没有节点，但是parent处已经有一个结点了，这个时候高度差就已经是1了，如果再来添加上一个结点，这个时候，高度差就变为了2，因此，需要通过旋转来调整，使它变的平衡）

当uncle结点为黑的时候：