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 }