0

我对以下方法有点困惑java.util.TreeMap:

static <K,V> TreeMap.Entry<K,V> successor(Entry<K,V> t) {
        if (t == null)
            return null;
        else if (t.right != null) {
            Entry<K,V> p = t.right;
            while (p.left != null)
                p = p.left;
            return p;
        } else {
            Entry<K,V> p = t.parent;
            Entry<K,V> ch = t;
            while (p != null && ch == p.right) {
                ch = p;
                p = p.parent;
            }
            return p;
        }
    }

此方法用于 TreeMap 的containsValue方法。并被告知检索第一个条目的后继者和先前检索到的后继者的后继者，依此类推。因此，上述方法检索整个 TreeMap 的条目。但我不是很明白它是如何运作的，它是如何寻找继任者的？

谢谢！

4

3 回答 3

5

这适用于二叉搜索树，它使用以下事实：

  1. 子树中的“最左”叶表示最小的键。
  2. 父节点总是大于其左子树的任何节点（二叉搜索树的定义）。

所以，这正是算法正在做的事情：

  1. 它搜索是否有右子树，如果有，最左边的叶子就是继承者，因为它是比给定节点大的最小值。
  2. 如果没有右子树，则表示后继树不在t其根节点所在的子树中，因此它会搜索t其左子树中节点所在的第一个父节点。

例子：

           4
          / \
         /   \ 
        /     \
       /       \
      2         6
     /         / \
    /         /   \
   1         5     7
  • 2 的继任者：由于 2 没有右子树，因此它是 2 在左子树中的第一个父级，即 4 - 正如预期的那样（else代码中的情况）。
  • 4的后继是右子树的“最左叶”，也就是预期的5。

此外，作为“测验”，请确保您了解何时不满足条件p != null。while (p != null && ch == p.right)

于 2013-08-05T16:54:18.893 回答
3

该方法背后的逻辑如下：

  • 节点的后继null节点不存在
  • 任何具有右子树的节点的后继节点都是其右子树的最左边的叶节点（即“向右走，然后尽可能地向下和向左走；这就是后继节点）。
  • 任何没有右子树的节点的后继节点都是其当前节点位于左子树中的第一个祖先节点。

这个逻辑在条件链的三个分支中表达：第一个if处理null，第二个遍历右分支的左子树，它else沿着树结构向上搜索祖先，使得当前子树在它的左边。

以下是当算法需要找到后继节点并且右子树存在时搜索的样子：当前节点显示为红色，其后继节点显示为绿色。算法向右走一步，然后一直向左走。

右子树

以下是当算法需要找到后继但没有右子树时的搜索结果：当前节点显示为红色，其后继显示为绿色。算法上升，检查我们是否来自左子树。对于当前节点的父节点，答案是“否”，因为当前节点在右子树中。对于父节点的父节点，答案是“是”，因此它作为当前节点的后继节点返回。

左子树

于 2013-08-05T16:56:18.683 回答
0

TreeMap 内部使用红黑树数据结构，任何红黑树都必须是二叉搜索树。

寻找后继者的概念就像寻找下一个合适的元素/对象/节点。

如果我们仔细查看 Amit 的示例并对它的节点进行排序，那么它们将是：

1,2,4,5,6,7

现在，如果我们打算找到 4 的后继者，那就是 5，而且更容易理解。现在，请注意Amit 提到的右子树的“最左叶”点。

同样，在 2 的情况下，它将是 4。使用 Amit 的第一个条件映射它，因为 2 没有右子树，它是 2 在左子树中的第一个父级

参考：
红黑树| 红黑树简介| 数据结构 https://www.youtube.com/channel/UCM-yUTYGmrNvKOCcAl21g3w

一些非常好的参考资料，可以首先了解实际的底层数据结构！

于 2021-02-02T05:08:10.087 回答