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

文章插图

到这里，红黑树的插入操作就结束了，以上的操作，只是单纯的一步操作，这些操作只是在插入之后对被插入节点红黑树的一个平衡，我们在进行旋转变色之后，很有可能上层的节点就又不符合定义了，这个时候我们就需要进行递归的旋转变色，直到最后整个红黑树平衡。
下面扔代码

if (cmp < 0) h.left = put(h.left, h, key, val);else if (cmp > 0) h.right = put(h.right, h, key, val);else h.value = https://www.isolves.com/it/cxkf/sf/2022-08-15/val;//判断红黑，进行旋转，调整树的平衡if (isRed(h.right) && isRed(h.right.right)) {h.right.color = h.color;h.color = Red;h = rotateLeft(h);}if (isRed(h.right) && isRed(h.right.left)) {//RL问题，先右旋,将问题转换为RRh.right = rotateRight(h.right);//变色h.right.color = h.color;h.color = Red;//再左旋h = rotateLeft(h);}if (isRed(h.left) && isRed(h.left.left)) {h.left.color = h.color;h.color = Red;h = rotateRight(h);}if (isRed(h.left) && isRed(h.left.right)) {//LR问题，先左旋，将问题转换为LL问题h.left = rotateLeft(h.left);//变色h.left.color = h.color;h.color = Red;//再右旋h = rotateRight(h);}h.N = size(h.left) + size(h.right) + 1;return h;}

欢迎点赞关注+转发！