c++ - C++ 构建 RB 树，nilNode 不是黑色的

Question

我正在构建一个红黑树作为一个学校项目，我已经完成了代码，但由于某种原因，当我运行程序测试用例时，我在 nilNode 为黑色时得到了错误，我无法弄清楚为什么会这样。

程序代码

#ifndef RBTREE_HPP
#define RBTREE_HPP

#include <string>
#include <vector>

#define FMT_HEADER_ONLY
#include <fmt/format.h>
#include <stack>

enum class Colour { RED, BLACK };

namespace std {
std::string to_string(const std::string& str) { return str; }
std::string to_string(const Colour& colour) {
  return (colour == Colour::RED) ? "RED" : "BLACK";
}
}  // namespace std

// Remember to always do a make clean / refresh build when using templates
template <typename V>
class RBReader;

template <typename T>
class RBTree {
  friend RBReader<T>;

private:
  struct Node {
    Node* parent = nullptr;
    Node* leftChild = nullptr;
    Node* rightChild = nullptr;
    Colour colour = Colour::RED;
    T element = T();
  };

  Node* root = nullptr;
  Node* nilNode = nullptr;

  int GzAddNode(std::string& nodes, std::string& connections, const Node* curr,
                size_t to);
  int GzAddChild(std::string& nodes, std::string& connections,
                const Node* child, size_t from, size_t to,
                const std::string& color);
  template <typename V>
  std::string GzNode(size_t to, const V& what, const std::string& style,
                    const std::string& fillColor,
                    const std::string& fontColor);
  std::string GzConnection(size_t from, size_t to, const std::string& color,
                          const std::string& style);

public:
  RBTree();
  ~RBTree();

  RBTree(const RBTree& other) = delete;
  RBTree& operator=(const RBTree& other) = delete;
  RBTree(RBTree&& other) = delete;
  RBTree& operator=(RBTree&& other) = delete;

  bool addNode(const T& element);
  void rightRotate(Node* node);
  void leftRotate(Node* node);
  bool deleteNode(const T &element);
  bool find(const T& element);

  const T& min();
  const T& max();

  std::vector<T> inOrder();
  int height();
  std::vector<T> pathFromRoot(const T& element);

  std::string ToGraphviz();
};

template <typename T>
RBTree<T>::RBTree() {}

template <typename T>
RBTree<T>::~RBTree() {}

template <typename T>
bool RBTree<T>::addNode(const T& element) {
  
  // if tree is empty, return true
  if (root == nilNode) {
    root = new Node();
    root->element = element;  
    return true;
  }

  // if element is already in tree, return false
  if (find(element)) {
    return false;
  }

  // otherwise, insert element
  Node* curr = root;
  Node* parent = nullptr;
  Node* child = nullptr;
  while (curr != nilNode) {
    parent = curr;
    if (element < curr->element) {
      child = curr->leftChild;
    } else {
      child = curr->rightChild;
    }
    if (child == nilNode) {
      break;
    }
    curr = child;
  }
  Node* newNode = new Node();
  newNode->element = element;
  newNode->parent = parent;
  if (child == nilNode) {
    child = newNode;
  } else {
    child->parent = newNode;
  }
  if (element < parent->element) {
    parent->leftChild = child;
  } else {
    parent->rightChild = child;
  }
  return true;

}

template <typename T>
bool RBTree<T>::deleteNode(const T& element) {
  // delete node from rb tree and return true if node exists, else return false
  Node* curr = root;
  while (curr != nullptr) {
    if (element < curr->element) {
      curr = curr->leftChild;
    } else if (element > curr->element) {
      curr = curr->rightChild;
    } else {
      break;
    }
}
  if (curr == nullptr) {
    return false;
  }
  if (curr->leftChild == nullptr || curr->rightChild == nullptr) {
    Node* child = curr->leftChild == nullptr ? curr->rightChild : curr->leftChild;
    if (child != nullptr) {
      child->parent = curr->parent;
    }
    if (curr->parent == nullptr) {
      root = child;
      nilNode = child;
    } else {
      if (curr->parent->leftChild == curr) {
        curr->parent->leftChild = child;
      } else {
        curr->parent->rightChild = child;
      }
    }
    delete curr;
  } else {
    Node* successor = curr->rightChild;
    while (successor->leftChild != nullptr) {
      successor = successor->leftChild;
    }
    curr->element = successor->element;
    delete successor;
  }
  return true;

}



template <typename T>
bool RBTree<T>::find(const T& element) {
  // find node in rb tree and return true if node exists, else return false
  Node* curr = root;
  while (curr != nullptr) {
    if (element < curr->element) {
      curr = curr->leftChild;
    } else if (element > curr->element) {
      curr = curr->rightChild;
    } else {
      return true;
    }
  }
  return false;
}

template <typename T>
const T& RBTree<T>::min() {
  static T tmp;
  // return minimum element in rb tree
  if (root == nullptr) {
    tmp = T();
    return tmp;
  }
  Node* curr = root;
  while (curr->leftChild != nullptr) {
    curr = curr->leftChild;
  }
  tmp = curr->element;
  return tmp;
}

template <typename T>
const T& RBTree<T>::max() {
  static T tmp;
  // return maximum element in rb tree
  if (root == nullptr) {
    tmp = T();
    return tmp;
  }
  Node* curr = root;
  while (curr->rightChild != nullptr) {
    curr = curr->rightChild;
  }
  tmp = curr->element;
  return tmp;
}

template <typename T>
std::vector<T> RBTree<T>::inOrder() {
  // return vector of elements in rb tree in order
  std::vector<T> result;
  if (root == nullptr) {
    return result;
  }
  std::stack<Node*> st;
  Node* curr = root;
  while (curr != nullptr || !st.empty()) {
    while (curr != nullptr) {
      st.push(curr);
      curr = curr->leftChild;
    }
    curr = st.top();
    st.pop();
    result.push_back(curr->element);
    curr = curr->rightChild;
  }
  return result;
}

template <typename T>
int RBTree<T>::height() {
  // return height of rb tree
  if (root == nullptr) {
    return 0;
  }
  std::stack<Node*> st;
  st.push(root);
  int h = 0;
  while (!st.empty()) {
    Node* curr = st.top();
    st.pop();
    if (curr->leftChild != nullptr) {
      st.push(curr->leftChild);
    }
    if (curr->rightChild != nullptr) {
      st.push(curr->rightChild);
    }
    h++;
  }
  return h;
}

template <typename T>
std::vector<T> RBTree<T>::pathFromRoot(const T& element) {
  // return vector of elements in rb tree from root to element
  std::vector<T> result;
  if (root == nullptr) {
    return result;
  }
  std::stack<Node*> st;
  Node* curr = root;
  while (curr != nullptr || !st.empty()) {
    while (curr != nullptr) {
      st.push(curr);
      curr = curr->leftChild;
    }
    curr = st.top();
    st.pop();
    result.push_back(curr->element);
    if (curr->element == element) {
      break;
    }
    curr = curr->rightChild;
  }
  return result;
}

template <typename T>
std::string RBTree<T>::ToGraphviz()  // Member function of the AVLTree class
{
  std::string toReturn = std::string("digraph {\n");
  if (root != nullptr &&
      root != nilNode)  // root is a pointer to the root node of the tree
  {
    std::string nodes;
    std::string connections = "\t\"Root\" -> 0;\n";
    GzAddNode(nodes, connections, root, 0);
    toReturn += nodes;
    toReturn += connections;
  }
  toReturn += "}";
  return toReturn;
}

template <typename T>
int RBTree<T>::GzAddNode(std::string& nodes, std::string& connections,
                        const Node* curr, size_t to) {
  size_t from = to;
  nodes += GzNode(from, curr->element, "filled",
                  curr->colour == Colour::RED ? "tomato" : "black",
                  curr->colour == Colour::RED ? "black" : "white");

  to = GzAddChild(nodes, connections, curr->leftChild, from, ++to, "blue");
  to = GzAddChild(nodes, connections, curr->rightChild, from, ++to, "gold");
  return to;
}

template <typename T>
int RBTree<T>::GzAddChild(std::string& nodes, std::string& connections,
                          const Node* child, size_t from, size_t to,
                          const std::string& color) {
  if (child != nilNode) {
    connections += GzConnection(from, to, color, "");
    to = GzAddNode(nodes, connections, child, to);
  } else if (child == nullptr) {
    nodes += GzNode(to, "null", "filled", "orange", "black");
    connections += GzConnection(from, to, "", "");
  } else {
    nodes += GzNode(to, child->element, "invis", "", "");
    connections += GzConnection(from, to, "", "invis");
  }
  return to;
}

template <typename T>
template <typename V>
std::string RBTree<T>::GzNode(size_t to, const V& what,
                              const std::string& style,
                              const std::string& fillColor,
                              const std::string& fontColor) {
  return fmt::format(
      "\t{} [label=\"{}\", fillcolor=\"{}\", fontcolor=\"{}\", style=\"{}\"]\n",
      to, what, fillColor, fontColor, style);
}

template <typename T>
std::string RBTree<T>::GzConnection(size_t from, size_t to,
                                    const std::string& color,
                                    const std::string& style) {
  return fmt::format("\t{} -> {} [color=\"{}\" style=\"{}\"]\n", from, to,
                    color, style);
}
#endif

我试图做什么 - 更改节点结构中的颜色 - 更改 nill 节点的颜色 - 更改根节点的颜色

我得到的错误

-------------------------------------------------------------------------------
Scenario: Some simple cases
    Given: An empty tree
    Then: The nil node should be black
-------------------------------------------------------------------------------
test/testsRedBlacktree.cpp:29
...............................................................................

test/testsRedBlacktree.cpp:29: FAILED:
REQUIRE( reader.nilIsBlack() )
with expansion:
false
with message:
GraphViz representation:
---
digraph {
}

===============================================================================
test cases: 1 | 1 failed
assertions: 3 | 2 passed | 1 failed

标签： c++algorithmred-black-treered-black-tree-insertion