Dictionary using Red-Black tree - deletion error

Question

I'm trying to implement a Dictionary using a Red-Black tree.
I've tested the insert method and it seems to work good, the RBtree seems to keep the correct shape and colors. The method that performs the binary tree node deletion seems to be correct, but I'm having huge problems on the deleteFixUp method called at the end of the deletion.

Would you like to help me figure out what I'm doing wrong? And, of course, if you have any suggestion to improve my code it would be very appreciated.

RBTreeWParentDictionary.java (Here I implemented the RedBlackTree)

package dictionary;

import java.util.Comparator;

public class RBTreeWParentDictionary<K, V> implements IDictionary<K, V> {
  /**
   * The root node of the RBTreeWParentDictionary
   */
  public RBTreeWParentNode<K, V> root;

  /**
   * Object used to compare two T objects.
   */
  private Comparator<K>          comparator;

  private int                    length;

  /**
   * Creates the dictionary based on red/black tree with null root
   * 
   * @param comparator
   *          The comparator for keys
   */
  public RBTreeWParentDictionary(Comparator<K> comparator) {
    this.root = null;
    this.comparator = comparator;
    this.length = 0;
  }

  /**
   * Checks if the tree is empty
   * 
   * @return True if the tree is empty
   */
  public boolean isEmpty() {
    return this.root == null;
  }

  /**
   * Returns the number of elements in the tree
   * 
   * @return The number of elements in the tree
   */
  public int length() {
    return this.length;
  }

  /**
   * Performs a left rotation on the tree node
   * 
   * @param node
   *          The node on which rotate
   */
  private void rotateLeft(RBTreeWParentNode<K, V> node) {
    RBTreeWParentNode<K, V> y = node.getRight();
    node.setRight(y.getLeft());
    if (y.hasLeft()) {
      y.getLeft().setParent(node);
    }
    y.setParent(node.getParent());
    if (!node.hasParent()) { // = this.isEmpty()
      this.root = y;
    }
    else {
      if (node.equals(node.getParent().getLeft())) {
        node.getParent().setLeft(y);
      }
      else {
        node.getParent().setRight(y);
      }
    }
    y.setLeft(node);
  }

  /**
   * Performs a right rotation on the tree node
   * 
   * @param node
   *          The node on which rotate
   */
  private void rotateRight(RBTreeWParentNode<K, V> node) {
    RBTreeWParentNode<K, V> y = node.getLeft();
    node.setLeft(y.getRight());
    if (y.hasRight()) {
      y.getRight().setParent(node);
    }
    y.setParent(node.getParent());
    if (!node.hasParent()) {
      this.root = y;
    }
    else {
      if (node.equals(node.getParent().getRight())) {
        node.getParent().setRight(y);
      }
      else {
        node.getParent().setLeft(y);
      }
    }
    y.setRight(node);
  }

  /*
   * Uses for first tests, now removed
   * 
   * public void testRotateLeft() { this.rotateLeft(this.root); }
   * 
   * public void testRotateRight() { this.rotateRight(this.root); }
   */

  /**
   * Performs all the needed work to the tree under the 3 main rules of R/BTree
   * 
   * @param node
   *          The current node that needs to be checked
   */
  private void treeFixUp(RBTreeWParentNode<K, V> node) {
    RBTreeWParentNode<K, V> u;
    if (!node.hasParent()) {
      return;
    }
    while (node.getParent().isRed()) {
      if (node.getParent().equals(node.getParent().getParent().getLeft())) {
        u = node.getParent().getParent().getRight();
        if (u != null && u.isRed()) {
          node.getParent().setBlack();
          u.setBlack();
          node.getParent().getParent().setRed();
          node = node.getParent().getParent();
        }
        else {
          if (node.equals(node.getParent().getRight())) {
            node = node.getParent();
            rotateLeft(node);
          }
          node.getParent().setBlack();
          node.getParent().getParent().setRed();
          rotateRight(node.getParent().getParent());
        }
      }
      else {
        u = node.getParent().getParent().getLeft();
        if (u != null && u.isRed()) {
          node.getParent().setBlack();
          u.setBlack();
          node.getParent().getParent().setRed();
          node = node.getParent().getParent();
        }
        else {
          if (node.equals(node.getParent().getLeft())) {
            node = node.getParent();
            rotateRight(node);
          }
          node.getParent().setBlack();
          node.getParent().getParent().setRed();
          rotateLeft(node.getParent().getParent());
        }
      }
      if (!node.hasParent()) {
        node.setBlack();
        break;
      }
    }
  }

  /**
   * Inserts a node with give key/value
   * 
   * @param key
   *          The key of the node to be inserted
   * @param value
   *          The value of the node to be inserted
   */
  @Override
  public void insert(K key, V value) {
    int res;
    RBTreeWParentNode<K, V> insertedNode = new RBTreeWParentNode<K, V>(key,
        value);
    if (this.isEmpty()) {
      this.root = insertedNode;
      this.root.setBlack();
    }
    else {
      RBTreeWParentNode<K, V> node = this.root;
      while (node != null) {
        res = comparator.compare(key, node.getKey());
        if (res < 0) {
          if (node.hasLeft()) {
            node = node.getLeft();
          }
          else break;
        }
        else if (res > 0) {
          if (node.hasRight()) {
            node = node.getRight();
          }
          else break;
        }
        else { // duplicate key, overwriting
          node.setValue(value);
          return;
        }
      }
      res = comparator.compare(key, node.getKey());
      if (res < 0) {
        node.setLeft(insertedNode);
      }
      else {
        node.setRight(insertedNode);
      }
      treeFixUp(insertedNode);
      this.length++;
    }
  }

  @Override
  public V get(K key) {
    // TODO Auto-generated method stub
    return null;
  }

  @Override
  public void delete(K key) {
    RBTreeWParentNode<K, V> node = root;
    boolean oldColor;
    int res;

    while (node != null
        && (res = comparator.compare(key, node.getKey())) != 0) {
      if (res < 0) node = node.getLeft();
      else node = node.getRight();
    }    
    if (node == null)
      return;
    oldColor = node.getColor();
    // key found, work with children
    if (!node.hasParent()) {//In root
      root = null;
      return;
    }
    else if(node.hasLeft() && !node.hasRight()) {//left child
      node.getLeft().setParent(node.getParent());
      node.getParent().setLeft(node.getLeft());
    }
    else if (!node.hasLeft() && node.hasRight()) {//right child
      node.getRight().setParent(node.getParent());
      node.getParent().setRight(node.getRight());
    }
    else if (node.hasLeft() && node.hasRight()) {//both children
      RBTreeWParentNode<K, V> tmp = node;
      node = min(tmp.getRight());
      //fix parent node of node
      node.setParent(tmp.getParent());
      if (tmp.getParent().getLeft().equals(tmp)) {
        node.getParent().setLeft(node);
      }
      else node.getParent().setRight(node);

      node.setRight(deleteMin(tmp.getRight()));
      node.setLeft(tmp.getLeft());
      tmp = null;
    }
    else { // is a leaf
      if (node.equals(node.getParent().getLeft()) ) {
        node.getParent().setLeft(null);
      }
      else node.getParent().setRight(null);
    }
    if (oldColor == false) {
      deleteFixUp(node);
    }
  }

  private RBTreeWParentNode<K, V> deleteMin(
      RBTreeWParentNode<K, V> node) {
    if (node.getLeft() == null) {
      return node.getRight();
    }
    node.setLeft(deleteMin(node.getLeft()));
    return node;
  }

  private RBTreeWParentNode<K, V> min(RBTreeWParentNode<K, V> node) {
    if (node.getLeft() == null) {
      return node;
    }
    else return min(node.getLeft());
  }


  private void deleteFixUp(RBTreeWParentNode<K, V> node) {
    while (!node.equals(this.root) && node.isBlack()) {
      if (node.equals(node.getParent().getLeft())) {
        if (node.getParent().hasRight()) {
          RBTreeWParentNode<K, V> w = node.getParent().getRight();
          if (w.isRed()) {
            w.setBlack();
            node.getParent().setRed();
            rotateLeft(node.getParent());
            w=node.getParent().getRight();
          }
          if (w.hasLeft() && w.hasRight() && w.getLeft().isBlack() && w.getRight().isBlack()) {
            w.setRed();
            node = node.getParent();
          }
          else {
            if (w.hasRight() && w.getRight().isBlack()) {
              w.getLeft().setBlack();
              w.setRed();
              rotateRight(w);
              w = node.getParent().getRight();
            }
            w.setColor(node.getParent().getColor());
            node.getParent().setBlack();
            w.getRight().setBlack();
            rotateLeft(node.getParent());
            node = this.root;
          }          
        }
      }
      else {
        //Repeat up changing left with right
        if (node.getParent().hasLeft()) {
          RBTreeWParentNode<K, V> w = node.getParent().getLeft();
          if (w.isRed()) {
            w.setBlack();
            node.getParent().setRed();
            rotateRight(node.getParent());
            w=node.getParent().getLeft();
          }
          if (w.hasLeft() && w.hasRight() && w.getLeft().isBlack() && w.getRight().isBlack()) {
            w.setRed();
            node = node.getParent();
          }
          else {
            if (w.hasLeft() && w.getLeft().isBlack()) {
              w.getRight().setBlack();
              w.setRed();
              rotateLeft(w);
              w = node.getParent().getLeft();
            }
            w.setColor(node.getParent().getColor());
            node.getParent().setBlack();
            w.getLeft().setBlack();
            rotateRight(node.getParent());
            node = this.root;
          }          
        }
      }
    }
    node.setBlack();
  }

  @SuppressWarnings("unused")
  @Override
  public boolean equals(Object other) {
    if (!(other instanceof RBTreeWParentDictionary)) {
      return false;
    }
    if ((this == null && other != null) || (this != null && other == null)) {
      return false;
    }
    if (this == null && other == null) {
      return true;
    }
    else {
      @SuppressWarnings("unchecked")
      RBTreeWParentDictionary<K, V> oth = (RBTreeWParentDictionary<K, V>) other;
      return equalsNodes(this.root, oth.root);
    }
  }

  private boolean equalsNodes(RBTreeWParentNode<K, V> node1,
      RBTreeWParentNode<K, V> node2) {
    if ((node1 == null && node2 != null) || (node1 != null && node2 == null)) {
      return false;
    }
    else if (node1 == null && node2 == null) {
      return true;
    }
    else return node1.equals(node2)
        && equalsNodes(node1.getLeft(), node2.getLeft())
        && equalsNodes(node1.getRight(), node2.getRight());
  }

}

RBTreeWParentNode.java (Here is the node of RedBlackTree)

package dictionary;

public class RBTreeWParentNode<K, V> {
  private K                    key;
  private V                    value;
  private boolean              color;
  private RBTreeWParentNode<K, V>  left, right, parent;

  private static final boolean RED   = true;
  private static final boolean BLACK = false;

  public RBTreeWParentNode(K key, V value, RBTreeWParentNode<K, V> left,
      RBTreeWParentNode<K, V> right, RBTreeWParentNode<K, V> parent) {
    this.key = key;
    this.value = value;
    this.color = RED;
    this.left = left;
    if (this.hasLeft())
      this.getLeft().setParent(this);
    this.right = right;
    if (this.hasRight())
      this.getRight().setParent(this);
    this.parent = parent;
  }

  public RBTreeWParentNode(K key, V value) {
    this.key = key;
    this.value = value;
    this.color = RED;
  }

  public RBTreeWParentNode() {
  }

  public K getKey() {
    return key;
  }

  public V getValue() {
    return value;
  }

  public boolean getColor() {
    return color;
  }

  public RBTreeWParentNode<K, V> getLeft() {
    return left;
  }

  public RBTreeWParentNode<K, V> getRight() {
    return right;
  }

  public RBTreeWParentNode<K, V> getParent() {
    return parent;
  }

  public RBTreeWParentNode<K, V> getBrother() {
    if (this.hasParent()) {
      if (this.getParent().getLeft().equals(this)) {
        return this.getParent().getRight();
      }
      else return this.getParent().getLeft();
    }
    else return null;
  }

  public boolean isRed() {
    return this.color == RED;
  }

  public boolean isBlack() {
    return this.color == BLACK;
  }

  public boolean hasLeft() {
    return this.getLeft() != null;
  }

  public boolean hasRight() {
    return this.getRight() != null;
  }

  public boolean hasParent() {
    return this.getParent() != null;
  }

  public boolean hasBrother() {
    if (this.hasParent()) {
      if (this.getParent().getLeft().equals(this)) {
        return this.getParent().getRight() != null;
      }
      else return this.getParent().getLeft() != null;
    }
    else return false;
  }

  public void setKey(K key) {
    this.key = key;
  }

  public void setValue(V value) {
    this.value = value;
  }

  public void setRed() {
    this.color = RED;
  }

  public void setBlack() {
    this.color = BLACK;
  }

  public void setParent(RBTreeWParentNode<K, V> node) {
    this.parent = node;
  }

  public void setLeft(RBTreeWParentNode<K, V> node) {
    this.left = node;
    if (this.hasLeft())
      this.left.setParent(this);
  }

  public void setRight(RBTreeWParentNode<K, V> node) {
    this.right = node;
    if (this.hasRight())
      this.right.setParent(this);
  }

  public void setColor(boolean color) {
    this.color = color;
  }

  @Override
  public boolean equals(Object other) {
    if (!(other instanceof RBTreeWParentNode)) {
      return false;
    }
    if ((this == null && other != null) || (this != null && other == null)) {
      return false;
    }
    @SuppressWarnings("unchecked")
    RBTreeWParentNode<K, V> oth = (RBTreeWParentNode<K, V>) other;
    return checkFieldsEquals(oth);
  }

  private boolean checkFieldsEquals(RBTreeWParentNode<K, V> oth) {
    //Check keys
    if ((this.getKey() == null && oth.getKey() != null)
        || (this.getKey() != null && oth.getKey() == null)) {
      return false;
    }
    else {
      if ((this.getKey() == null && oth.getKey() == null)
          || this.getKey().equals(oth.getKey())) {
        if ((this.getValue() == null && oth.getValue() != null)
            || (this.getValue() != null && oth.getValue() == null)) {
          return false;
        }
        else {
          if ((this.getValue() == null && oth.getValue() == null)
              || (this.getValue().equals(oth.getValue()))) {
            if (this.getColor() != oth.getColor()) {
              return false;
            }
            else {
              return (this.getKey() == null && oth.getKey() == null)
                  || this.getKey().equals(oth.getKey());
            }
          }
          else return false;
        }
      }
      else {
        return false;
      }
    }
  }

}

RBTreeWParentDictionaryTest.java -> My test class

Update 09/07/2016 I've updated my code because i found out that I wasn't updating the node cursor to root after the fix-up and I wasn't calling the fix-up only when the deleted node is black.
Considering my test case testDeleteDoubles I've figured out that I'm choosing a wrong candidate to switch with the item to delete when it has a brother.
Seeing this simulator the candidate should be the max node on the left branch of the deleted item, but shouldn't it be the successor, so the min item on the right branch?

Answer 1

In delete(), you need to remember the child node of the deleted node because the red-black properties might be violated after the delete. Let's say we declare RBTreeWParentNode<K, V> childOfDeletedNode;

Then, for the case of left child you update childOfDeletedNode = node.getLeft();

For the case of right child you update childOfDeletedNode = node.getRight();

For both children, you need to add the following after calling min():

oldColor = node.getColor();
childOfDeletedNode = node.getLeft();
node.setColor(tmp.getColor());

For leaf, take any child childOfDeletedNode = node.getRight();

Then, you fix the color of the child node with deleteFixUp(childOfDeletedNode);

Now since childOfDeletedNode can be null, you need to handle that case in deleteFixUp by adding a check for node != null in the loop condition and adding an if-statement before setting the color to black in the last line.

Anyway, the simulator you refer to finds the maximum node of the left sub-tree. Your solution finds the minimum node of the right sub-tree. Both are correct, but will result in different results. You'll need fix your test case.

To illustrate, before the delete:

      10(B)
     /    \
    8(R)  100(B)
   /   \
  5(B) 9(B)
 /   \
2(R) 6(R)

After the delete of 8, you replace it 9, the minimum node of the right sub-tree. The color is changed to red.

      10(B)
     /    \
    9(R)  100(B)
   /
  5(B)
 /   \
2(R) 6(R)