BST：キーを指定した後継キーの検索方法

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. あなたはまた、あなたの「Vのget（Kキー）」メソッドを更新する必要があり、あなたは、そのノードの後継を取得し、その値
2. を返すキー
3. のgetNodeにプライベートメソッドが必要になりますコードの重複

を避けるためにgetNode（Kキー）メソッドを使用するように私はすべての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; 
    }  

の下に書きました