无论如何都要维持以当前节点为根节点的总高度是不变的, 如果高度变化,则在当前根节点进行颜色变换, 维持高度不变. 直到 root节点. 进行高度加减操作.
而在这里我就看到了另一种操作思路. 找到最小节点之后, 此时必定是左子节点,如果为红色, 直接删除, 否则的话需要将右子节点的高度减一, 也就是将右子节点变成红色.如果右子节点为红色, 进行右旋操作, 而后继续关注新的父节点的右子节点. 直到不为红色.
这样使得右子树高度必然会减一, 那左子树呢? 左子树是要删除的, 因此高度也会减一. 这样就维持了当前父节点的平衡性.
那么父节点的父节点呢? 这时候需要关注, 如果当前父节点为红色, 则转黑, 高度+1, 子节点高度减一, 父节点高度+1, 总的高度保持不变.
如果节点为黑色呢? 继续向上重复刚刚的操作.不过此时 x = parent;然后变换右节点颜色, 以新的父节点为根节点的树高度减一. 新的父节点继续向上, 直到 父节点高度可以+1为止, 又或者 到达root节点. 转换root节点颜色即可.
但是仍存在一个问题: 如果当前右子节点直接变为红色, 如果右子节点的子节点依然存在红色节点呢? 岂不是出现了两个连续的红色节点, 违反了我们的规定? 而我们又不会在向下检查一遍, 因为这里是自底向上的操作, 所以有一段代码就是解决这个问题的, 直接单独拉出来讲解.
if (colorOf(rightOf(sib)) == BLACK) { setColor(leftOf(sib), BLACK); setColor(sib, RED); rotateRight(sib); sib = rightOf(parentOf(x)); } setColor(sib, colorOf(parentOf(x))); setColor(parentOf(x), BLACK); setColor(rightOf(sib), BLACK); rotateLeft(parentOf(x)); x = root;这是if (colorOf(leftOf(sib)) == BLACK && colorOf(rightOf(sib)) == BLACK) 判断的else 代码块.
我们可以看到, 第一个if语句是将红色左子节点进行右旋操作.给 sib进行赋值操作, 使得 sib 始终指向 x.parent.right节点.
而下面那段代码, 乍一看是左旋操作, 其实不尽然, 因为在每一次旋转操作的时候, 相应的子节点必须为红色. 必须要有对应的颜色转换, 否则会导致树平衡性出现问题.
因此这里并不是一次标准的左旋操作(其父节点的左右子节点均为黑色), 那么是什么呢? 就需要关注到另一个问题, 以当前节点为根节点. 从全局来看, 左旋操作 是令根节点左子树高度+1, 右子树高度-1的一种操作. 而在以往的过程中, 同时含有对应的颜色变换, 以维持高度不变.
那么这里呢? 首先我们知道, 在向上的过程中, 就是要令父节点高度 +1,以维持树的整体平衡性. 而这一步操作:
setColor(rightOf(sib), BLACK);如果是正常的右旋操作, 这里颜色不变, 根据上文来看, 依然是 RED, 但我们在这里令颜色变为黑色, 这就很巧妙了, 左子树因为左旋, 高度+1,右子树高度-1, 而右子树的红色节点颜色也由红色调整为黑色, 使得右子树高度+1, 这样就维持了右子树的高度不变, 而左子树高度+1的操作.
这是一种非常巧妙的红黑树变换操作. 自下而上, 核心在于 - + 先减后加操作, 通过这种方式就实现了树的平衡.
private void fixAfterDeletion(Entry<K,V> x) { while (x != root && colorOf(x) == BLACK) { if (x == leftOf(parentOf(x))) { Entry<K,V> sib = rightOf(parentOf(x)); //如果右节点为红色, 左旋, 使得整体节点下沉 if (colorOf(sib) == RED) { setColor(sib, BLACK); setColor(parentOf(x), RED); rotateLeft(parentOf(x)); sib = rightOf(parentOf(x)); } //使得右节点高度减一 if (colorOf(leftOf(sib)) == BLACK && colorOf(rightOf(sib)) == BLACK) { setColor(sib, RED); //同时向上, 最终令父节点高度+1 x = parentOf(x); } else { if (colorOf(rightOf(sib)) == BLACK) { setColor(leftOf(sib), BLACK); setColor(sib, RED); rotateRight(sib); sib = rightOf(parentOf(x)); } setColor(sib, colorOf(parentOf(x))); setColor(parentOf(x), BLACK); setColor(rightOf(sib), BLACK); rotateLeft(parentOf(x)); x = root; } } else { // symmetric Entry<K,V> sib = leftOf(parentOf(x)); if (colorOf(sib) == RED) { setColor(sib, BLACK); setColor(parentOf(x), RED); rotateRight(parentOf(x)); sib = leftOf(parentOf(x)); } if (colorOf(rightOf(sib)) == BLACK && colorOf(leftOf(sib)) == BLACK) { setColor(sib, RED); x = parentOf(x); } else { if (colorOf(leftOf(sib)) == BLACK) { setColor(rightOf(sib), BLACK); setColor(sib, RED); rotateLeft(sib); sib = leftOf(parentOf(x)); } setColor(sib, colorOf(parentOf(x))); setColor(parentOf(x), BLACK); setColor(leftOf(sib), BLACK); rotateRight(parentOf(x)); x = root; } } } setColor(x, BLACK); }至此delete操作,终于告一段落.
iterator()