当我们插入值为66的节点的时候,示意图如下:
很明显,这个时候结构依然遵循着上述5大特性,无需启动自动平衡机制调整节点平衡状态。
如果再向里面插入值为51的节点呢,这个时候红黑树变成了这样。
这样的结构实际上是不满足性质4的,红色两个子节点必须是黑色的,而这里49这个红色节点现在有个51的红色节点与其相连。
这个时候我们需要调整这个树的结构来保证红黑树的平衡。
首先尝试将49这个节点设置为黑色,如下示意图。
这个时候我们发现黑高是不对的,其中 60-56-45-49-51-null 这条路径有 4 个黑节点,其他路径的黑色节点是 3 个。
接着调整红黑树,我们再次尝试把45这个节点设置为红色的,如下图所示: