第一步: 将红黑树当作一颗二叉查找树,将节点插入。
第二步:将插入的节点着色为"红色"。

根据被插入节点的父节点的情况,可以将"当节点 z 被着色为红色节点,并插入二叉树"划分为三种情况来处理。

  1. 情况说明:被插入的节点是根节点。
    处理方法:直接把此节点涂为黑色。

  2. 情况说明:被插入的节点的父节点是黑色。
    处理方法:什么也不需要做。节点被插入后,仍然是红黑树。

  3. 情况说明:被插入的节点的父节点是红色。这种情况下,被插入节点是一定存在非空祖父节点
    的;进一步的讲,被插入节点也一定存在叔叔节点(即使叔叔节点为空,我们也视之为存在,空节
    点本身就是黑色节点)。理解这点之后,我们依据"叔叔节点的情况",将这种情况进一步划分为 3
    种情况(Case)。

第三步: 通过一系列的旋转或着色等操作,使之重新成为一颗红黑树。