將元素插入左傾斜的黑色紅色樹C++

Question

我一直盯着這一整天，稍微有些地方，但它仍然不能正常工作！只是試圖'插入'（真的插入，或找到它是否存在）一個元素k到一個LL紅黑樹。這是我的方法：

Node * RPut(Node* p, const K& k, Node*& location) 
{ 
    // if you are at the bottom of the tree, 
    // add new node at bottom of the tree 
    if (p == 0) 
    { 
    // new red note with new data 
    location = NewNode(k, Data(), RED); 
    return location; 
    } 

    if(greater_(k,p->key_)) 
    { 
    // if it's greater than the root, move down to the left child 
    p->left_ = Rput(p->left_, k, location); 
    } 
    // right subtree 
    else if (greater_(p->key_,k)) 
    { 
    // but if the key is less than root, move down to right child 
    p->right_ = Rput(p->right_, k, location); 
    } 
    // if they are equal 
    else 
    { 
    location = p; 
    } 
    // code for rotating 
    // this sort of worked. 
    if(p->right_ && p->right_->IsRed()) 
    { 
    p = RotateLeft(p); 
    if (p->left_->IsBlack()) 
    { 
     p->SetBlack(); 
     p->left_->SetRed(); 
    } 
    } 
    if (p->left_ && p->left_->IsRed()) 
    {  if (p->left_->left_ && p->left_->left_->IsRed()) 
    { 
     p = RotateRight(p); 
     p->left_->SetBlack(); 
     p->right_->SetBlack(); 
    } 
    } 
    return p; 
} 

我知道我的旋轉方法工作完美。此正確地插入，直到第五元件（I沒有嘗試每種組合，但通常。）例如，ABCDE正確插入將是

d 
    b e 
a c -- 

[用b爲紅色節點]

礦山工作，但停止這裏，給我：

沒有紅色節點。

任何人都看到任何明顯的我忽略或爲什麼它不能正常工作？任何幫助都非常感謝。 謝謝！

Answer 1

這並不是直接回答這個問題，而是你讀了Sedgewick的paper在左傾的紅黑樹上嗎？其中的代碼格外清晰，有精美的圖解釋事物如何工作，並且，我想，將所有內容重新實現爲C++將是直接的。

編輯

我試過了，爲了好玩實施塞奇威克的代碼。事實證明，這篇論文中有一些方法/子程序被忽略了，這些方法/子程序對於包含這些內容非常有幫助。無論如何，我的C++ 11實現以及一些測試如下。

由於Java做自動內存管理，Sedgewick沒有明確地注意到在他的代碼中應該釋放哪些內存。我沒有選擇使用std::shared_ptr，它提供了一個類似的無憂行爲，而不是試圖找出一個快速的項目，並可能留下內存泄漏。

#include <iostream> 
#include <vector> 
#include <cstdlib> 
#include <memory> 

template<class keyt, class valuet> 
class LLRB { 
private: 
    static const bool COLOR_RED = true; 
    static const bool COLOR_BLACK = false; 

    class Node { 
    public: 
    keyt key; 
    valuet val; 
    std::shared_ptr<Node> right; 
    std::shared_ptr<Node> left; 
    bool color; 
    Node(keyt key, valuet val){ 
     this->key = key; 
     this->val = val; 
     this->color = COLOR_RED; 
     this->right = nullptr; 
     this->left = nullptr; 
    } 
    }; 

    typedef std::shared_ptr<Node> nptr; 

    nptr root; 

    nptr rotateLeft(nptr h){ 
    nptr x = h->right; 
    h->right = x->left; 
    x->left = h; 
    x->color = h->color; 
    h->color = COLOR_RED; 
    return x; 
    } 

    nptr rotateRight(nptr h){ 
    nptr x = h->left; 
    h->left = x->right; 
    x->right = h; 
    x->color = h->color; 
    h->color = COLOR_RED; 
    return x; 
    } 

    nptr moveRedLeft(nptr h){ 
    flipColors(h); 
    if(isRed(h->right->left)){ 
     h->right = rotateRight(h->right); 
     h  = rotateLeft(h); 
     flipColors(h); 
    } 
    return h; 
    } 

    nptr moveRedRight(nptr h){ 
    flipColors(h); 
    if(isRed(h->left->left)){ 
     h = rotateRight(h); 
     flipColors(h); 
    } 
    return h; 
    } 

    void flipColors(nptr h){ 
    h->color  = !h->color; 
    h->left->color = !h->left->color; 
    h->right->color = !h->right->color; 
    } 

    bool isRed(const nptr h) const { 
    if(h==nullptr) return false; 
    return h->color == COLOR_RED; 
    } 

    nptr fixUp(nptr h){ 
    if(isRed(h->right) && !isRed(h->left))  h = rotateLeft (h); 
    if(isRed(h->left) && isRed(h->left->left)) h = rotateRight(h); 
    if(isRed(h->left) && isRed(h->right))   flipColors (h); 

    return h; 
    } 

    nptr insert(nptr h, keyt key, valuet val){ 
    if(h==nullptr) 
     return std::make_shared<Node>(key,val); 

    if  (key == h->key) h->val = val; 
    else if(key < h->key) h->left = insert(h->left, key,val); 
    else     h->right = insert(h->right,key,val); 

    h = fixUp(h); 

    return h; 
    } 

    //This routine probably likes memory 
    nptr deleteMin(nptr h){ 
    if(h->left==nullptr) return nullptr; 
    if(!isRed(h->left) && !isRed(h->left->left)) 
     h = moveRedLeft(h); 
    h->left = deleteMin(h->left); 
    return fixUp(h); 
    } 

    nptr minNode(nptr h){ 
    return (h->left == nullptr) ? h : minNode(h->left); 
    } 

    //This routine leaks memory like no other!! I've added a few cleanups 
    nptr remove(nptr h, keyt key){ 
    if(key<h->key){ 
     if(!isRed(h->left) && !isRed(h->left->left)) 
     h = moveRedLeft(h); 
     h->left = remove(h->left, key); 
    } else { 
     if(isRed(h->left)) 
     h = rotateRight(h); 
     if(key==h->key && h->right==nullptr) 
     return nullptr; 
     if(!isRed(h->right) && !isRed(h->right->left)) 
     h = moveRedRight(h); 
     if(key==h->key){ 
     std::shared_ptr<Node> mn = minNode(h->right); 
     h->val = mn->val; 
     h->key = mn->key; 
     h->right = deleteMin(h->right); 
     } else { 
     h->right = remove(h->right, key); 
     } 
    } 

    return fixUp(h); 
    } 

    void traverse(const nptr h) const { 
    if(h==nullptr) 
     return; 
    traverse(h->left); 
    std::cout<< h->key << "=" << h->val <<std::endl; 
    traverse(h->right); 
    } 

public: 
    LLRB(){ 
    root = nullptr; 
    } 

    void traverse() const { 
    traverse(root); 
    } 

    valuet search(keyt key){ 
    nptr x = root; 
    while(x!=nullptr){ 
     if  (key == x->key) return x->val; 
     else if (key < x->key) x=x->left; 
     else     x=x->right; 
    } 

    return keyt(); 
    } 

    void insert(keyt key, valuet val){ 
    root  = insert(root,key,val); 
    root->color = COLOR_BLACK; 
    } 

    void remove(keyt key){ 
    root  = remove(root,key); 
    root->color = COLOR_BLACK; 
    } 
}; 

int main(){ 
    for(int test=0;test<500;test++){ 
    LLRB<int,int> llrb; 
    std::vector<int> keys; 
    std::vector<int> vals; 

    for(int i=0;i<1000;i++){ 
     //Ensure each key is unique 
     int newkey = rand(); 
     while(llrb.search(newkey)!=int()) 
     newkey = rand(); 

     keys.push_back(newkey); 
     vals.push_back(rand()+1); 
     llrb.insert(keys.back(),vals.back()); 
    } 

    //llrb.traverse(); 

    for(int i=0;i<1000;i++){ 
     if(llrb.search(keys[i])!=vals[i]){ 
     return -1; 
     } 
    } 

    for(int i=0;i<500;i++) 
     llrb.remove(keys[i]); 

    for(int i=500;i<1000;i++){ 
     if(llrb.search(keys[i])!=vals[i]){ 
     return -1; 
     } 
    } 
    } 

    std::cout<<"Good"<<std::endl; 
}