javared-black-treered-black-tree-insertion

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

Solution

  • 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
    }