Java集合分析 (9)

但在通篇看完之后, 其操作与实现与想象并没有多少出入, 可以说一切的问题都在 parent这个属性下解决掉了, 再加上本来就是自底向上的归溯. 其实现方式在红黑树的讲解章节都已经提到过了, 就不再赘述. 但是有所区别的是, 在这里的实现方式中, 在左旋右旋的节点交换过程中, 并没有在 rotateLeft() 或 rotateRight() 中实现颜色的转换, 因此需要在左旋右旋之前对其节点的颜色做好先一步的调整.

同样的, 在一开始并没有注意, 以至于到 delete方法的时候就实在难以理解了, 在这里, 需要强调一下put的实现, 在这里的红黑树规定与之前又有所区别:

之前是, 红色链接必须是左链接, 而在这里, 红色链接却并没有做强制性的规定, 甚至于左右子节点均为红色链接也是可以的. 这一点并不难理解. 因为在之前仅仅是为了简化操作以及理解才做出那样的规定.

但有一条依然适用, 不允许出现两条连续的红色链接. 仅此而已. 通过左旋右旋,变色操作, 即可做到平衡调整.

并且无需重新赋值, 因为在调整的过程中将 父节点链接也直接进行了转换.

firstKey() lastKey()

final Entry<K,V> getFirstEntry() { Entry<K,V> p = root; if (p != null) while (p.left != null) p = p.left; return p; } final Entry<K,V> getLastEntry() { Entry<K,V> p = root; if (p != null) while (p.right != null) p = p.right; return p; }

在看到名字的时候以为是返回 root节点, 看了代码之后才发现事实上是返回 最小 最大节点.

remove()

public V remove(Object key) { Entry<K,V> p = getEntry(key); if (p == null) return null; V oldValue = p.value; deleteEntry(p); return oldValue; } private void deleteEntry(Entry<K,V> p) { modCount++; size--; /** *在这里如果左右子节点都为空, 取到的为叶节点. 否则的话取出以右子节点为根节点的最小节点. */ if (p.left != null && p.right != null) { Entry<K,V> s = successor(p); p.key = s.key; p.value = s.value; p = s; } /** *无论上面的方法执行与否, p节点的左子节点都为空.因此返回值有两种可能性: *红色右节点且为叶节点, 或者null; */ Entry<K,V> replacement = (p.left != null ? p.left : p.right); if (replacement != null) { //删除p节点, 且将其父节点与replacement节点相互关联. replacement.parent = p.parent; if (p.parent == null) root = replacement; else if (p == p.parent.left) p.parent.left = replacement; else p.parent.right = replacement; // Null out links so they are OK to use by fixAfterDeletion. p.left = p.right = p.parent = null; // 因为当前节点颜色为红色, 事实上就是删除p节点, 同时将replacement置为黑色即可. if (p.color == BLACK) fixAfterDeletion(replacement); } else if (p.parent == null) { // return if we are the only node. root = null; } else { //如果当前节点为2-节点, 才需要进行平衡处理, 否则直接删除. if (p.color == BLACK) fixAfterDeletion(p); if (p.parent != null) { if (p == p.parent.left) p.parent.left = null; else if (p == p.parent.right) p.parent.right = null; p.parent = null; } } } //补充一:successor /** *根据deleteEntry易知 t节点不为空, 且非叶节点.因此执行的是1处的代码. *其返回值为当前节点右子节点的最小节点. */ static <K,V> TreeMap.Entry<K,V> successor(Entry<K,V> t) { if (t == null) ...; //标注:1 else if (t.right != null) { Entry<K,V> p = t.right; while (p.left != null) p = p.left; return p; } else ...; return p; } }

补充二:这里的方法有点不同, 也是一种比较有趣的思路, 还记得在红黑树的学习章节, 我们是首先找到被删除节点, 然后删除右子树的最小节点, 而删除最小节点, 采取的方式是 自上而下遍历节点, 将所有的左子节点都变为3-节点或4-节点, 以备删除使用, 直到末级节点删除, 而后回溯所有节点, 拆解. 而在这之中, 所有变换的核心要点是:

内容版权声明:除非注明,否则皆为本站原创文章。

转载注明出处:https://www.heiqu.com/wpsdwy.html