Red-Blackツリー削除エラーを使用している辞書

Question

Red-Blackツリーを使用して辞書を実装しようとしています。
私は挿入メソッドをテストしましたが、うまくいくようですが、RBtreeは正しい形状と色を保っているようです。バイナリツリーノードの削除を実行するメソッドは正しいようですが、削除の最後に呼び出されるdeleteFixUpメソッドに大きな問題があります。

私が間違っていることを理解するのを手助けしますか？そして、もちろん、私のコードを改善するための提案があれば、非常に感謝しています。

RBTreeWParentDictionary.java（ここで私は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（ここ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

更新9月7日/ 2016 私はコードを更新しました。なぜなら、私はupdatではないことが分かったからです修正後にノードカーソルをrootに移して、削除されたノードが黒である場合にのみ修正を呼び出すことができませんでした。
私のテストケースを考慮するtestDeleteDoubles私は、兄がいるときに削除する項目に切り替えるために間違った候補を選択していることを理解しました。
this simulatorを参照すると、候補は削除されたアイテムの左の枝にある最大ノードである必要がありますが、それは後続ではないはずです。

Answer 1

delete()には、削除後に赤黒のプロパティが侵害される可能性があるため、削除されたノードの子ノードを覚えておく必要があります。我々は左の子の場合のために、あなたは両方の子供たちのためにchildOfDeletedNode = node.getRight();

を更新右の子の場合にはchildOfDeletedNode = node.getLeft();

を更新し、その後

RBTreeWParentNode<K, V> childOfDeletedNode;を宣言しましょう、あなたは後、次のを追加する必要がありますmin()呼び出し：葉については

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

、すべての子を取るchildOfDeletedNode = node.getRight();

その後、あなたはループ条件にnode != nullのチェックを追加し、IF-を追加することにより、childOfDeletedNodeはnullすることができるので、あなたがdeleteFixUpにそのケースを処理する必要がある今deleteFixUp(childOfDeletedNode);

と子ノードの色を修正します最後の行で黒に色を設定する前に、ステートメントを実行します。

とにかく、あなたが参照するシミュレータは、左側のサブツリーの最大ノードを見つけます。あなたの解は正しいサブツリーの最小ノードを見つける。どちらも正しいが、異なる結果が生じる。テストケースを修正する必要があります。

を削除する前に、説明するために：8の削除後

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

を、あなたはそれ9、右のサブツリーの最小ノード交換してください。色が赤に変わります。

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