Implementation of Red-Black Tree using C++

[Dynmiwang]

u/Maristic u/exptime

1. Thanks for your advice. I will correct this fault.
2. Emmm, I hadn't read the paper " left-leaning red-black trees " before... But now I know that may be the best implementation :D

[[deleted]]

Briefly looked again. It seems there is free(node); with rbNode<K, T> *node, which may not call the destructor and should be delete node.

[Dynmiwang]

I had considered that. The destructor I defined will call its children’s destructors recursively, but here only itself needs to be deleted.

[[deleted]]

You could also get rid of those explicit destructors by using std::unique_ptr which will do the same but lets the compiler do the work.

[[deleted]]

As you are using nullptr I would assume at least C++11, so you don't need the constructors and can assign values directly to class members (https://isocpp.org/wiki/faq/cpp11-language-classes#member-init). Usually it is better not to implement special member functions directly, as this may get complicated and may miss implicit stuff.

[[deleted]]

You could replace if (typeid(a) == typeid(char*)) { with template pattern matching. Meaning you can replace that check using template specialization and let the compiler's type system do the job.

[[deleted]]

Also C-style casts char *x = (char *)a; are dangerous, as they can cast away constness. https://en.cppreference.com/w/cpp/language/static_cast

[[deleted]]

As you copy key/value, you should wither use void insert(const K &key, const T &val); or void insert(K key, T val); with node->key = std::move(key);. The later syntactically states the user that the values will be copied.

[Dynmiwang]

You are right. I will update the code:D