what's the purpose of variable val in this algo

Question

it's an algo from internet about Red-Black BST Java implementation. I am confused about the variable named val in this program. Here is the code:

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));
    }
}

is that just a mark we give to the number we put inside the Tree? then don't we already have key as a mark? why we still need variable val?

Answer 1

Yes, you're right, it's just like a mark. We can indeed implement this algorithm with just one variable, i.e., key. In this algo, val is something that is being stored as a type of data for which we need to keep track.

For example consider this

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.

You can even go a step further and keep a track of several things that are inside a box by changing the data-type of val to List or Map or even user-defined objects. It will still work the same way.