左に傾いている黒い赤い木に要素を挿入する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; 
} 

：ここに私の方法です。 5番目の要素（私はすべての組み合わせを試みたが、通常はしていない。）例えば、正しく挿入ABCDEが

d 
    b e 
a c -- 

[赤ノードとしてB付き]

鉱山作品が、停止することになるまで、これが正しく挿入されここに、私を与えて：

ノーレッドノード。

誰でも明白な何かを見ている私は見落としているか、それとも正常に動作していないのですか？どのような助けも非常に感謝しています。 ありがとう！

Answer 1

これは質問に直接答えるものではありませんが、左利きの赤い黒い木にセジウィックのpaperを読まれましたか？そのコードは非常に明確で、どのように動作するかを説明する美しい図があり、すべてをC++に再実装するのは簡単でしょう。

編集

私はSedgewickのコードを実装するための楽しみのために、試してみました。紙にはいくつかの方法/サブルーチンが残っていたことが分かりました。とにかく、私の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; 
}