将元素插入左倾红黑树（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

没有红色节点。

有人看到我忽略的明显问题或为什么它不能正常工作吗？任何帮助都非常感激。 谢谢！

- Tee

Answer 1

这并不是直接回答问题，但你是否阅读过Sedgewick关于左偏红黑树的论文？其中的代码非常清晰，有美丽的图表解释了如何运作，而且我想，将所有东西重新实现到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;
}

- Richard

---

@Tracy 我尝试过类似的变化，但是一直出现段错误问题 -- 我认为问题在于，如果你想按照教科书上所读的实现数据结构，C++并不是一个好的（应该说是理想的）语言。像Java这样的语言更适合这个任务。原因是对于C++，你必须担心正确地管理动态分配的内存，而其他语言则不需要。因此，你有两座山要攀登--语言本身和你正在实现的数据结构。 - PaulMcKenzie

@PaulMcKenzie 嗯，这个我知道了，我在很多地方看到了这种简单实现的变体，似乎都能正常工作。我不知道。我刚刚再试了一次，在将第二个变量输入列表后，出现了段错误。肯定是其中一个if语句的问题，因为它可以顺利通过比较循环，然后在没有进入循环的情况下发生段错误。 - Tee

@Richard我从未使用过assert()，但我会研究一下。谢谢！ - Tee

@Tracy：我有一点空余时间，所以我按照Sedgewick的论文实现了LLRB。也许你会觉得这很有帮助。和你一样，在大约5个对象左右我也遇到了问题。这些问题是由于在插入例程中没有将“h”设置为“fixUp（）”的返回值引起的。还因为需要初始化“left”和“right”指针以及“root”而出现了问题。 - Richard

是的，您可以在空指针上运行fixUp，因为isRed可以防止滥用。 - Richard