Skip to content
Advertisement

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

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

Advertisement

Answer

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
}
User contributions licensed under: CC BY-SA
4 People found this is helpful
Advertisement