有人可以驗證RedBlack Tree後繼是否被正確寫入？

Question

pair<K,V> *RedBlackTree<K,V,Compare>::successor(K key) { 

    Node *found = findNode(key, root); 

    Node *p; 
    Node *ch; 
    Node *x; 

    Node *y; 
    if(found->right != sentinel) 
     return new pair<K,V>(found->right->key, found->right->value); 

    y = found->parent; 
    /* if it does not have a left child, 
    predecessor is its first left ancestor */ 
    while(y != NULL && found == y->right) { 
      found = y; 
      y = y->parent; 
    } 
    return new pair<K,V>(y->key, y->value); 



} 

Answer 1

此錯誤代碼不正確。考慮下面的樹：

b 
/\ 
a f 
    /\ 
    d g 
/\ 
c e 

的b的有序繼任者是c。你的功能認爲有序的繼任者是f。要找到有序的後繼者，你必須處理幾個案例;這個例子樹有一個需要處理的每個案例的實例。從每個節點開始，寫下你需要找到每個節點的有序後繼的步驟。

如果您有興趣，您可以在an answer I gave to another question中找到該算法的實施方案並提供完整的說明。

---

在一個不相關的音符，你的函數應該幾乎肯定會返回一個std::pair按值和你不應該動態分配std::pair。