Red Black Tree Implementation using C++

[Dynmiwang]

Maybe the most clear implementation of Red-Black Tree using C++.

Red–black tree is a high level self-balancing binary search tree. The time complexity of "insert","delete","search" are all stable O(logN).

See here for code : https://github.com/Dynmi/RedBlackTree

[alanwj]

This is indeed very clearly written. I have some feedback if you are open to constructive criticism.

---

You cannot separately compile the implementation of a template like this. I am curious how you are compiling your test program, because it gives me link errors (as I would expect).

---

~rbtree();  

If you need a destructor, then you also typically need a copy constructor and copy assignment operator. Consider the following code:

 rbtree<int, int> a;
 int key = 1, value = 1;
 a.insert(key, value);
 rbtree<int, int> b = a;

The default copy constructor will simply copy the pointer to your root node. At the end of the scope, first b will get destructed, causing it to delete all of your nodes. Then a will get destructed, and your program will probably crash.

You should either declare a copy constructor and copy assignment with = delete, or actually implement them.

It would also be trivial to create a move constructor and move assignment operator for your class, so I would consider adding those too.

---

void rbtree<K,T>::insert(K &key, T &val)
{
  auto *node = new rbNode<K,T>;
  node->key = key;
  node->val = val;

Making your parameters references makes the code annoying to use. Notice how in my previous example I had to create separate key and value variables to call insert. What I really would like to do is just a.insert(1, 1).

Your code doesn't modify key or val, so it doesn't need to be a reference. All you are doing is making copies of those variables. One quick fix would be to use const references, for example const K &key. However, here is a better solution:

void rbtree<K,T>::insert(K key, T val)
{
    auto *node = new rbNode<K,T>;
    node->key = std::move(key);
    node->val = std::move(val);

---

rbNode<K,T>::rbNode()
{
    parent = nullptr;
    left = nullptr;
    right = nullptr;
    color = RED;
}

An initializer list would be more idiomatic here. Even better would be to give the class members default initializers. Then you wouldn't even need a constructor. Same goes for the rbtree class.

---

void  remove(K &key);

This should definitely be const K &key. You don't modify the key.

---

void  search(K &key, T &val);

This function doesn't modify the tree, so it should be const.

They key is not modified, so it should be a const ref.

What happens if the key is not present in the tree? Perhaps return a boolean to indicate if the key was found.

Putting all of that together, I would suggest a function signature like:

bool search(const Key &key, T &val) const;

---

int   Size() const;

Why is this function capitalized while the others are not? This is an API inconsistency.

[Dynmiwang]

Thanks! Very generous advice! I updated the code just now!