なぜSedgwickはBSTで毎回ルートに新しいノードを割り当てるのですか？

Question

新しいノードが置かれるたびにrootが新しい値を取得するのはなぜですか？私は、ルート変数は、バイナリツリーの最初の要素への参照になるはずです。

public class BST<Key extends Comparable<Key>, Value> { 
     private Node root;    // root of BST 

     private class Node { 
      private Key key;   // sorted by key 
      private Value val;   // associated data 
      private Node left, right; // left and right subtrees 
      private int size;   // number of nodes in subtree 

      public Node(Key key, Value val, int size) { 
       this.key = key; 
       this.val = val; 
       this.size = size; 
      } 
     } 

     public void put(Key key, Value val) { 
      root = put(root, key, val); //?!! 
     } 

     private Node put(Node x, Key key, Value val) { 
      if (x == null) return new Node(key, val, 1); 
      int cmp = key.compareTo(x.key); 
      if (cmp < 0) x.left = put(x.left, key, val); 
      else if (cmp > 0) x.right = put(x.right, key, val); 
      else x.val = val; 
      x.size = 1 + size(x.left) + size(x.right); 
      return x; 
     } 
} 

Answer 1

rootは、実際に新しい値を毎回取ることはありません。それは、新しいノードを作成し、最後に訪れたノードにそれを返す場合には行き止まりに、当たるまで再帰的ヘルパー関数put()は、ツリーの下になり、それがleftまたはrightいずれかとして割り当てられている

if (x == null) return new Node(key, val, 1); 

：

if (cmp < 0) x.left = put(x.left, key, val); 
    else if (cmp > 0) x.right = put(x.right, key, val); 

このノードは、再び最終的に古い/既存のルートが返されるまで、それは、親ノードのleftまたはrightですので、バックツリーまでのすべての方法でとして返されます。

root = put(root, key, val); 

（rootがnull場合）ツリーが完全に空である場合、ヘルパー関数は、ちょうどすぐに新しいノードを作成し、それを返します。

---

一つの重要な観測：それはnullであれば、最初の引数としてヘルパー関数putに渡されたものは何でも

が、その場合には、新しいノードが作成され、除き、をそのまま返され、戻ってきた。