TreeMap 如何搜索给定条目的后继？

Question

我对以下方法有点困惑 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 的条目。但我不太明白它是如何运作的，它如何寻找继任者？

谢谢！

Answer 1

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

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)不满足。