java - 这个算法中变量 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));
    }
}

这只是我们在树中放置的数字的标记吗？那我们不是已经有 key 作为标记了吗？为什么我们还需要变量 val？

Answer 1

是的，你没看错，它就像一个标记。我们确实可以只用一个变量来实现这个算法，即 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 的数据类型更改为 List 或 来跟踪盒子中的几样东西映射 甚至用户定义的对象。它仍将以相同的方式工作。