JavaBST：如何在给定密钥的情况下找到后续密钥？

Question

我正在使用BST。给定一个密钥，如何找到后续密钥？这是我目前掌握的代码。我已经成功地插入了一个新的键，并在给定键的情况下检索了一个值。现在，我需要完成下一个方法。我将如何处理这个问题

class BST<K extends Comparable<K>, V> implements RangeMap<K,V> {
class Node {
    Node left;
    Node right;
    Node parent;
    KVPair<K,V> kv;
    K key;
    V value;
    public Node(K key, V value) {
        this.key = key;
        this.value = value;
        parent = left = right = sentinel;
    }
}

private Node root;


public void add(K key, V value) {
    // TODO: Implement me(basic score)
    root = add (root, key, value);
}

private Node add(Node x, K key, V value){
    if (x == null){
        return new Node(key, value); }
        int cmp = key.compareTo(x.key);
        if (cmp < 0){
            x.left = add(x.left, key, value);}
            else if (cmp > 0 ){
                x.right = add(x.right, key, value);}
                else if (cmp == 0){
                    x.value = value;} 
    return x;
}


public V get(K key) {
    Node x = root;
    while (x != null){
        int cmp = key.compareTo(x.key);
        if (cmp < 0){
            x = x.left;}
            else if (cmp > 0 ){
                x = x.right;}
               else if (cmp == 0){
                   return x.value;}
      }
    return null;
}


public K next(K key) {

Answer 1

1. 您需要一个私有方法来获取密钥的节点
2. 然后获取该节点的后续节点并返回其值
3. 您还应该更新“V get（K key）”方法，以使用getNode（K key）方法来避免代码重复

我已经写了下面所有3种方法

    private Node getNode(K key) {
        Node x = root;
        while (x != null){
            int cmp = key.compareTo(x.key);
            if (cmp < 0){
                x = x.left;
            } else if (cmp > 0 ) {
                x = x.right;
            } else if (cmp == 0){
                return x;
            }
          }
        return null;
    }

    public K next(K key) {
        Node x = getNode(key);
        if (x.right != null) {
            x = x.right;
            while (x.left != null) {
                x = x.left;
            }
            return x.key;
        }
        Node p = x.parent;
        while (p != null && p.right == x) {
            p = p.parent;
            x = x.parent;
        }
        return p.key;
    }

    public V get(K key) {
        Node x = getNode(key);
        return x==null?null:x.value;
    }