रेड-ब्लैक पेड़ का उपयोग करके शब्दकोश - हटाने की त्रुटि

Question

मैं एक लाल-काले पेड़ का उपयोग करके एक शब्दकोश को लागू करने की कोशिश कर रहा हूं।
मैंने सम्मिलित विधि का परीक्षण किया है और ऐसा लगता है कि यह अच्छा काम करता है, आरबीटीरी सही आकार और रंग रखने लगता है। बाइनरी पेड़ नोड हटाना करने वाली विधि सही प्रतीत होती है, लेकिन मुझे हटाए जाने के अंत में हटाए गए हटाए गए फ़िक्सअप विधि पर बड़ी समस्याएं आ रही हैं।

क्या आप मुझे यह जानने में मदद करना चाहते हैं कि मैं क्या गलत कर रहा हूं? और, ज़ाहिर है, अगर आपके पास मेरे कोड को बेहतर बनाने के लिए कोई सुझाव है तो इसकी बहुत सराहना की जाएगी।

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

अद्यतन 09/07/2016 मैंने अपना कोड अपडेट कर दिया है क्योंकि मुझे पता चला कि मैं अपडेट नहीं कर रहा था फिक्स-अप के बाद नोड कर्सर को रूट करने के लिए और मैं केवल फिक्स-अप को कॉल नहीं कर रहा था जब हटाया गया नोड काला था।
मेरे टेस्ट केस टेस्ट को ध्यान में रखते हुए डिलीट डबल्स मैंने यह पता लगाया है कि मैं एक भाई होने पर आइटम के साथ स्विच करने के लिए गलत उम्मीदवार चुन रहा हूं।
this simulator देखकर उम्मीदवार हटाए गए आइटम की बाएं शाखा पर अधिकतम नोड होना चाहिए, लेकिन यह उत्तराधिकारी नहीं होना चाहिए, तो सही शाखा पर न्यूनतम आइटम?

Answer 1

delete() में, आपको हटाए गए नोड के बच्चे नोड को याद रखना होगा क्योंकि हटाए जाने के बाद लाल-काले गुणों का उल्लंघन किया जा सकता है। मान लीजिए कि हम RBTreeWParentNode<K, V> childOfDeletedNode;

घोषित फिर, बाईं बच्चों को मजबूरन के लिए आप अद्यतन childOfDeletedNode = node.getLeft();

सही बच्चे के मामले के लिए आप अद्यतन childOfDeletedNode = node.getRight();

दोनों बच्चों के लिए करते हैं, तो आप के बाद निम्नलिखित जोड़ने की जरूरत min() बुला:

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

पत्ती के लिए, किसी भी बच्चे को लेने के childOfDeletedNode = node.getRight();

उसके बाद, आप deleteFixUp(childOfDeletedNode);

अब

childOfDeletedNode के बाद से साथ चाइल्ड नोड के रंग को ठीक null हो सकता है, आप पाश हालत में node != null का एक चेक को जोड़ने और एक अगर- जोड़कर deleteFixUp में उस मामले को संभालने की ज़रूरत आखिरी पंक्ति में काले रंग को रंग देने से पहले बयान।

वैसे भी, सिम्युलेटर जिसे आप संदर्भित करते हैं, बाएं उप-पेड़ का अधिकतम नोड पाता है। आपका समाधान सही उप-पेड़ का न्यूनतम नोड पाता है। दोनों सही हैं, लेकिन परिणामस्वरूप अलग-अलग परिणाम होंगे। आपको अपने टेस्ट केस को ठीक करने की आवश्यकता होगी।

हटाने से पहले इसे समझने के लिए,:

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

8 के हटाने के बाद, आप इसे 9, सही उप पेड़ की न्यूनतम नोड की जगह। रंग लाल हो गया है।

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