红黑树以及JAVA实现( 四 ) _红黑树

文章插图

当然，这个结果明显是错误的，其结构明显不符合我们我们在2.2.2中展示的任何一种形式,所以我们要通过旋转和变色变换为2.2.2中的哪几种形式。

文章插图

首先这个组合在2-3-4树种是一个4节点，但是他的形态并不符合红黑树的节点，所以我们需要将它转换为已个合法的形态，先进行旋转，1节点左旋，这个时候结构对了，但是颜色不对，需要将2变色为黑色，而1变色为红色，这样我们的这个红黑树就完全符合定义了。

文章插图

这就是一个最简单的旋转变色的红黑树自动平衡过程。
下面是左旋和右旋的JAVA代码实现，并没有添加变色，因为变色的逻辑并不是固定的故而我们将其解耦到其他方法中

//左旋Node rotateLeft(Node h) {Node x = h.right;h.right = x.left;if(h.right!=null){h.right.parent = h;}x.parent = h.parent;h.parent = x;x.left = h;if(x.left!=null){x.left.parent = x;}if(x.parent!=null){int cmp = x.parent.key.compareTo(x.key);if(cmp>0) x.parent.left = x;else x.parent.right = x;}x.N = h.N;h.N = 1 + size(h.left) + size(h.right);show();return x;}//右旋Node rotateRight(Node h) {Node x = h.left;h.left = x.right;if(h.left!=null){h.left.parent = h;}x.parent = h.parent;h.parent = x;x.right = h;if(x.right!=null){x.right.parent = x;}if(x.parent!=null){int cmp = x.parent.key.compareTo(x.key);if(cmp>0) x.parent.left = x;else x.parent.right = x;}x.N = h.N;h.N = 1 + size(h.left) + size(h.right);show();return x;}

2.4 红黑树的添加红黑树的添加分为以下几种情况
2.4.1 在黑色节点下面插入这种情况无论是插入在左还是右，都可以直接插入，红黑树的正确性不会受到影响
2.4.2 在红色节点下插入且被插入节点无兄弟节点2.4.2.1 当被插入的节点是右子节点

文章插图

在右侧插入

文章插图

操作步骤：

节点1左旋
变色，1变色为红色，2变色为黑色

在左侧插入

文章插图

这种情况会比上面那种多一个步骤

节点3右旋，无需变色，这个操作主要是为了将情况转换为上面在右侧插入的情况，然后下面按照在右侧的情况处理即可
)
节点1左旋
变色，1变色为红色，2变色为黑色

2.4.2.2 当被插入节点是左子节点其实这种情况和上面的处理逻辑是一样的，只不过左右是反过来的，就不再赘述了，大家自己举一反三即可。
2.4.3 在红色节点下插入且被插入节点有兄弟节点这种时候，我们需要先进行变色，再插入，如下图（这里，我们默认，1节点是有父节点的，1节点非根节点）

文章插图

2和3节点变黑色，1节点变红色，这个变化其实对应着2-3-4树的4节点插入，其实就是将一个4节点拆分开来，中间的节点向上和父节点组合，左右两边的节点分裂为两个单独的节点，然后再正常插入一个新的节点。红黑树也是这么个道理。
2、3节点变黑，形成单独的节点，而1节点则变红和父节点结合，那么这里我们要注意的是，1节点和父节点结合的时候，也相当于一次新的插入，相当于在1的父节点新插入一个红色，所以这个过程是递归的，一直向上传递，直到红黑树的结构符合定义为止。