这个算法中变量 val 的目的是什么

Question

这是一个来自互联网的关于红黑 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

在此实现中，此数据结构的作用类似于 Map，这意味着它将键映射到值。那val是value的常用缩写，相当self-explainatory。它可以是 Java 中存在的任何类型，无论是原始类型还是参考类型。

Answer 2

是的，你没看错，它就像一个标记。我们确实可以只用一个变量来实现这个算法，即 key。在这个算法中，val 是作为一种数据类型存储的东西，我们需要对其进行跟踪。

例如考虑这个

You have several numbered boxes like 34, 23, 65, 73 and you want to implement RB Tree operations on them. So these number on boxes resembles the key in your algorithm.

Now consider each box contains a number of balls in it. These balls can be seen as a data which is stored inside the box and you need to keep a track of it. So this can be considered as val.

您甚至可以更进一步，通过将 val 的 data-type 更改为 List 或 Map 来跟踪盒子内的几样东西甚至 user-defined 个对象。它仍然会以同样的方式工作。

这个算法中变量 val 的目的是什么

what's the purpose of variable val in this algo

java

algorithm

red-black-tree

binary-search-tree