このアルゴールの変数valの目的は何ですか

Question

Red-Black BST Javaの実装についてインターネットからの仲間です。このプログラムではvalという変数について混乱しています。コードは次のとおりです。

package tools; 
public class redBlack2 { 
    private static final boolean RED = true; 
    private static final boolean BLACK = false; 
    private Node root; 
    public redBlack2() {} 
    private class Node { 
     private int key; 
     private int val; 
     private Node left, right; 
     private boolean color; 
     public Node(int key, int val, boolean color) { 
      this.key = key; 
      this.val = val; 
      this.color = color; 
     } 
    } 
    private boolean isRed(Node x) { 
     if (x == null) return false; 
     return x.color == RED; 
    } 
    public int get(int key) { 
     return get(root, key); 
    } 
    private int get(Node x, int key) { 
     while (x != null) { 
      if  (key < x.key) x = x.left; 
      else if (key > x.key) x = x.right; 
      else    return x.val; 
     } 
     System.out.println("There is no such key."); 
     return 0; 
    } 
    public boolean contains(int key) { 
     return get(key) != 0; 
    } 
    public void put(int key, int val) { 
     root = put(root, key, val); 
     root.color = BLACK; 
    } 
    private Node put(Node h, int key, int val) { 
     if (h == null) return new Node(key, val, RED); 
     if  (key<h.key) h.left = put(h.left, key, val); 
     else if (key>h.key) h.right = put(h.right, key, val); 
     else if (key == h.key) h.val = val; 
     if (isRed(h.right) && !isRed(h.left))  h = rotateLeft(h); 
     if (isRed(h.left) && isRed(h.left.left)) h = rotateRight(h); 
     if (isRed(h.left) && isRed(h.right))  flipColors(h); 
     return h; 
    } 
    private Node rotateRight(Node h) { 
     Node x = h.left; 
     h.left = x.right; 
     x.right = h; 
     x.color = x.right.color; 
     x.right.color = RED; 
     return x; 
    } 
    private Node rotateLeft(Node h) { 
     Node x = h.right; 
     h.right = x.left; 
     x.left = h; 
     x.color = x.left.color; 
     x.left.color = RED; 
     return x; 
    } 
    private void flipColors(Node h) { 
     h.color = !h.color; 
     h.left.color = !h.left.color; 
     h.right.color = !h.right.color; 
    } 
    public static void main(String[] args) { 
     redBlack2 r = new redBlack2(); 
     r.put(34,1); 
     r.put(23,2); 
     r.put(65,3); 
     r.put(73, 4); 
     System.out.print(r.get(73)); 
    } 
} 

は、私たちがツリー内に入れた数字にちょうどいいマークですか？私たちはすでにマークとしてキーを持っていないのですか？なぜ変数valが必要なのでしょうか？

Answer 1

はい、そうです、これはマークのようなものです。実際には、このアルゴリズムをただ1つの変数、すなわちkeyで実装することができる。このアルゴリズムでは、valは、追跡する必要のある種類のデータとして格納されているものです。例えば

この

あなたは34、23、65、73のようないくつかの番号のボックスを持っていて、 それらにRBツリーの操作を実装することを検討してください。したがって、これらの数字は のアルゴリズムのkeyに似ています。

ここで、各ボックスに多数のボールが含まれているとします。これらのボール は、ボックスの中に格納されているデータと見ることができ、 を追跡する必要があります。したがって、これはvalと考えることができます。

あなたも、さらに一歩進み、ListへvalまたはMap、あるいはユーザー定義オブジェクトのデータ型を変更することにより、ボックス内にあるいくつかのトラックを保つことができます。同じように動作します。

Answer 2

この実装では、このデータ構造はMapのように動作します。つまり、キーを値にマップします。そのvalは、一般的な略称valueであり、それは非常に自明である。プリミティブでもリファレンスでも、Javaにはどんな型でも構いません。