java - 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。

---

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