Is it possible to avoid duplicate values from being inserted in a Red Black Tree?

Question

This is currently my code for insertion in a Red Black tree. How would I make it so that duplicate values are not added in so that the tree doesn't change?

public void insert(int i) {
    Node x = this.root;
    Node y = null;
    Node z = new Node(i, Color.RED);
    
    
    while (x != null) {
        y = x;
        if(z.data < x.data)
            x = x.left;
        else
            x = x.right;
    }
    
    z.parent = y;
    
    if(y == null)
        this.root = z;
    else if(z.data < y.data)
        y.left = z;
    else
        y.right = z;
    
    z.left = z.right = null;
    z.color = Color.RED;
    insertFixup(z);
        
}

If by duplicate you mean the int value, there’s so such concept in a tree. You’ll have to track the values separately, like in a set. — Abhijit Sarkar, Oct 18 '22 at 04:14

score 0 · Accepted Answer · answered Oct 18 '22 at 11:30

Something like this

public int insert(int i) {
    Node x = this.root;
    Node y = null;
    
    while (x != null) {
        y = x;
        if(i < x.data)
            x = x.left;
        else if (i > x.data)
            x = x.right;
        else
            return -1;  // FAILURE, data already exists
    }

    Node z = new Node(i, Color.RED);
    
    z.parent = y;
    
    if(y == null)
        this.root = z;
    else if(z.data < y.data)
        y.left = z;
    else
        y.right = z;
    
    z.left = z.right = null;
    z.color = Color.RED;
    insertFixup(z);
    return 0; // SUCCESS
}

Is it possible to avoid duplicate values from being inserted in a Red Black Tree?

1 Answers1