Какова цель переменной val в этом algo

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

Да, вы правы, это точно так же, как знак. Мы действительно можем реализовать этот алгоритм только с одной переменной, т. Е. key. В этом algo val - это то, что хранится как тип данных, для которого нам нужно отслеживать.

Для примера рассмотрим этот

У вас есть несколько пронумерованных ящиков, как 34, 23, 65, 73, и вы хотите осуществлять операции RB Tree на них. Значит, это число на ящиках похоже на key в вашем алгоритме.

Теперь рассмотрим, что каждая коробка содержит в себе несколько шаров. Эти шары можно рассматривать как данные, которые хранятся внутри коробки, и вам необходимо, чтобы сохранил ее. Таким образом, это можно рассматривать как val.

Вы можете даже пойти на шаг дальше и постоянно отслеживать несколько вещей, которые находятся внутри коробки, изменяя тип данных из val в List или Map или даже определенных пользователем объектов. Он по-прежнему будет работать одинаково.

Answer 2

В этой реализации эта структура данных действует как Map, что означает, что она сопоставляет ключи со значениями. То, что val является общей аббревиатурой value, что вполне самоочевидно. Он может быть любого типа, существующего на Java, будь он примитивным или справочным.