c++ - 将元素插入左倾的黑红树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;
}

我知道我的旋转方法非常有效。这会正确插入直到第五个元素(我没有尝试过所有组合，但通常是这样。)例如，正确插入的 abcde 将是

   d
  b  e
 a c --

[以b为红色节点]

我的工作但停在这里，给我:

    b
  a   d
- -  c   e

没有红色节点。

有人看到我忽略的任何明显的东西或为什么它不能正常工作吗？非常感谢任何帮助。 谢谢!

Answer 1

这并没有直接回答问题，但是你读过 Sedgewick 的 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;
}