red black tree implementation in cpp

Question

I am learning algorithms and trying to implement them in c++, I have chosen to try to implement a red-black tree due to its self-balancing properties and its ability to stop the worst case of O(n) when searching for a value. I also needed to allow duplicates to have a vector to hold duplicates in node objects, and a key to hold the main value the node holds. Can someone please review my code and suggest and improvements? if I have even implemented a red-black tree correctly (I have no need for deletion operations). I have also been thinking if I should change my Node* to std::shared_ptr, would this be a good idea? or should I keep them as raw pointers.

#define _CRT_SECURE_NO_WARNINGS #include <algorithm> #include <cctype> #include <iostream> #include <memory> #include <string> #include <vector> #include <ctime> using namespace std; // CHANGE THIS // Complex type used for the BST class Transaction { private: std::string desc; time_t timestamp; std::string value; bool isWithdrawal; public: explicit Transaction(std::string value, std::string reason = "None.") : desc(reason), timestamp(time(nullptr)), value(std::move(value)) { // timestamp is current date/time based on current // system // Lambda to convert reason to lower to we can identify elements easier std::transform(reason.begin(), reason.end(), reason.begin(), [](const unsigned char c) { return std::tolower(c); }); // Check if reason is a withdrawal if so update the member function this->isWithdrawal = reason.find("withdrawal") != std::string::npos; } std::string toString() const { // convert timestamp to string form const char* string_timestamp = ctime(&timestamp); if (this->isWithdrawal) { return "-- " + desc + ": -\x9C" + value + " on " + string_timestamp; } return "-- " + desc + ": \x9C" + value + " on " + string_timestamp; } // Getters std::string getValue() const { return this->value; } double getValueNum() const { return std::stod(this->value); } std::string getDesc() const { return this->desc; } time_t getTimestamp() const { return this->timestamp; } bool getIsWithdrawal() const { return this->isWithdrawal; } friend std::ostream& operator<<(std::ostream& os, const Transaction& transaction); }; std::ostream& operator<<(std::ostream& os, const Transaction& transaction) { os << transaction.toString(); return os; } // class RBTree implements the operations in Red Black Tree class RBTree { private: // data structure that represents a node in the tree struct Node { double key = 0.0; std::vector<std::shared_ptr<Transaction>> data; // holds the key Node* parent = nullptr; // pointer to the parent Node* left = nullptr; // pointer to left child Node* right = nullptr; // pointer to right child int color = -1; // 1 -> Red, 0 -> Black std::string toString() const { std::string result; for (const auto& item : data) { result += item->toString() + "\n"; } return result; } }; Node* root; Node* TNULL; // initializes the nodes with appropriate values // all the pointers are set to point to the null pointer void initializeNULLNode(Node* node, Node* parent) { node->key = 0.0; node->parent = parent; node->left = nullptr; node->right = nullptr; node->color = 0; } Node* searchTreeHelper(Node* node, const double key) { if (node == TNULL || key == node->key) { return node; } if (key < node->key) { return searchTreeHelper(node->left, key); } return searchTreeHelper(node->right, key); } // Traverse through tree and print all data in order void inOrderTraversal(Node* node) const { if (node != TNULL) { inOrderTraversal(node->left); for(const auto& item : node->data){ std::cout << *item; } inOrderTraversal(node->right); } } void rbTransplant(Node* u, Node* v) { if (u->parent == nullptr) { root = v; } else if (u == u->parent->left) { u->parent->left = v; } else { u->parent->right = v; } v->parent = u->parent; } // fix the red-black tree void fixInsert(Node* k) { Node* u; while (k->parent->color == 1) { if (k->parent == k->parent->parent->right) { u = k->parent->parent->left; // uncle if (u->color == 1) { // case 3.1 u->color = 0; k->parent->color = 0; k->parent->parent->color = 1; k = k->parent->parent; } else { if (k == k->parent->left) { // case 3.2.2 k = k->parent; rightRotate(k); } // case 3.2.1 k->parent->color = 0; k->parent->parent->color = 1; leftRotate(k->parent->parent); } } else { u = k->parent->parent->right; // uncle if (u->color == 1) { // mirror case 3.1 u->color = 0; k->parent->color = 0; k->parent->parent->color = 1; k = k->parent->parent; } else { if (k == k->parent->right) { // mirror case 3.2.2 k = k->parent; leftRotate(k); } // mirror case 3.2.1 k->parent->color = 0; k->parent->parent->color = 1; rightRotate(k->parent->parent); } } if (k == root) { break; } } root->color = 0; } public: RBTree() : TNULL(new Node) { TNULL->color = 0; TNULL->left = nullptr; TNULL->right = nullptr; root = TNULL; } // search the tree for the key k // and return the corresponding node Node* searchTree(const double k) { return searchTreeHelper(this->root, k); } // find the node with the minimum key Node* minimum(Node* node) const { while (node->left != TNULL) { node = node->left; } return node; } // find the node with the maximum key Node* maximum(Node* node) const { while (node->right != TNULL) { node = node->right; } return node; } // find the successor of a given node Node* successor(Node* x) const { // if the right subtree is not null, // the successor is the leftmost node in the // right subtree if (x->right != TNULL) { return minimum(x->right); } // else it is the lowest ancestor of x whose // left child is also an ancestor of x. Node* y = x->parent; while (y != TNULL && x == y->right) { x = y; y = y->parent; } return y; } // find the predecessor of a given node Node* predecessor(Node* x) const { // if the left subtree is not null, // the predecessor is the rightmost node in the // left subtree if (x->left != TNULL) { return maximum(x->left); } Node* y = x->parent; while (y != TNULL && x == y->left) { x = y; y = y->parent; } return y; } // rotate left at node x void leftRotate(Node* x) { Node* y = x->right; x->right = y->left; if (y->left != TNULL) { y->left->parent = x; } y->parent = x->parent; if (x->parent == nullptr) { this->root = y; } else if (x == x->parent->left) { x->parent->left = y; } else { x->parent->right = y; } y->left = x; x->parent = y; } // rotate right at node x void rightRotate(Node* x) { Node* y = x->left; x->left = y->right; if (y->right != TNULL) { y->right->parent = x; } y->parent = x->parent; if (x->parent == nullptr) { this->root = y; } else if (x == x->parent->right) { x->parent->right = y; } else { x->parent->left = y; } y->right = x; x->parent = y; } // insert the key to the tree in its appropriate position // and fix the tree void insert(const std::shared_ptr<Transaction>& key) { // Ordinary Binary Search Insertion Node* node = new Node; node->key = key->getValueNum(); node->parent = nullptr; node->data.push_back(key); node->left = TNULL; node->right = TNULL; node->color = 1; // new node must be red Node* y = nullptr; Node* x = this->root; while (x != TNULL) { y = x; if (node->key == x->key) { // Duplicate insert x->data.emplace_back(key); delete node; // Delete node as we don't need it, due to duplicate data return; } if (node->key < x->key) { x = x->left; } else { x = x->right; } } // y is parent of x node->parent = y; if (y == nullptr) { root = node; } else if (node->key < y->key) { y->left = node; } else { y->right = node; } // if new node is a root node, simply return if (node->parent == nullptr) { node->color = 0; return; } // if the grandparent is null, simply return if (node->parent->parent == nullptr) { return; } // Fix the tree fixInsert(node); } Node* getRoot() const { return this->root; } void printAllNodesInOrder() const { inOrderTraversal(getRoot()); } }; // TO DO: // Try convert Node* to shared ptr // cleanup int main() { RBTree bst; bst.insert(std::make_shared<Transaction>("1500", "Deposit")); bst.insert(std::make_shared<Transaction>("1500", "Deposit 2")); bst.insert(std::make_shared<Transaction>("500.50", "Deposit")); bst.insert(std::make_shared<Transaction>("2000.69", "Deposit")); std::cout << bst.searchTree(1500)->toString(); bst.printAllNodesInOrder(); return 0; } ```

Answer 1

This ia a great follow-up and deserves a closer look than I can give it right now, but a handful of things jumped out at me.

Write the Class as a Template

You’ve got a nice tree class, but it’d be a shame to re-write the whole thing whenever you want to hold a different data type. You’re better off writing this as a class template and instantiating RBTree<Transaction>.

Duck-Type to Standard Interfaces

For example, if you name your begin and end iterators .begin() and .end(), a lot of the standard library will work with them, and if you call them anything else, it won’t. And I like camelCase too, but the C++ standard library uses snake_case.

A minor instance of this is that your serialization function is named toString, in camelCase, but the C++ standard library uses to_string(s), s.to_string(), or both, and you might well find a template duck-typed to expect your type to, as well.

On a larger scale:

Follow the STL Interface as Closely as Possible

Or as closely as you feel like. I’d honestly suggest you just leave out everything relating to allocators and comparators at first, and if you’re still interested in them when you have something you like, you can go back and add them.

This is a good practice for two reasons. First, it gives you a data structure you can use as a drop-in replacement for std::multimap (if you’re storing and comparing values) or the more complicated std::map (if you have different keys and values). This will be much more useful to anyone considering actually using your code, and not only that, it lets you benchmark your implementation against the one in your compiler’s library.

Second, it’s a great way to learn your way around the STL.

So, you can start with a STL reference, pick a place to start, and copy and paste those declarations from the public interface into your class declaration. Then implement them beneath, until you’ve filled in enough of the interface to be able to write a test driver.

Use Separate Files

Maybe you’re just flattening it to make your post shorter, but it looks like you’ve got everything in a blob right now.

You really want a "RBTree.h" and a test driver like main.cpp that calls it. Most of your code looks like it would need to go in your header, but you might have some non-template definitions that belong in a RBTree.cpp as well. A "Transaction.h" and Transaction.cpp would also be good.

Write Portable Strings

Your Transaction::toString function currently has the string ": -\x9C" in two places. Since there’s no comment, I’m left to assume that you want the program to run in IBM code page 850, where \x9E is £.

This was the default on some versions of Windows, but not in all countries. Windows 11 changes this to UTF-8, and most other operating systems also use UTF-8 by default. Most cannot support code page 850 at all. Since there’s no comment, someone compiling this file would have no way of knowing that it needs the execution character set and current code page to be 850.

What you want to do instead is use Unicode escape codes. Since the pound sign is U+00A3, you can write ": -\u00A3". This should still work if you compile on Windows with cl /execution-charset:.850 (although I admit I haven’t actually tested that) but these days, I would just compile with /utf-8 in Visual Studio, or use the default settings for almost any other compiler.

If you save as UTF-8 with a byte-order mark, every compiler should automatically detect the source character set and understand ": -£". This will still work if you choose an execution character set different from your source character set.

You should be saving your source files as UTF-8 with a byte-order mark, as this is the only format that all major compilers using their default settings understand. If you use anything else, definitely warn maintainers in the comments!

While you’re at it, adding the line

using namespace std::literals; 

will let you write ": -£"s to make this literal a std::string rather than a const char* const. You can also use ": -£"sv for a std::string_view, which is often more efficient, but that doesn’t help you concatenate with +.

An alternative interface is std::format, which often has very low overhead.

Smart Pointers

You ask about changing your shared_ptr links to plain C-style pointers. This could work—after all, it’s how people code binary trees in C—but is a bad idea. You would need to do manual memory management again.

So starting with shared_ptr and getting that to work was a great idea. I’d recommend you next learn to write this using node_type = std::unique_ptr<Node>; for your left and right pointers. This forces you to use plain pointers for any other weak references to those nodes (such as pointers back up to the parent, or pointers stored in iterators), but that’s okay, because the memory management still is automatic, with RAII.

Not only is unique_ptr more efficient than shared_ptr and a lot less likely to corrupt your heap than a C-style *, it allows you to implement functions like extract from the STL, and see what they’re used for. Many modern C++ libraries now pass around unique_ptr as efficient, versatile object handles, so it’s well worth understanding them.

You said in a previous discussion that you got compiler errors when you tried to use std::unique_ptr. This is probably because you cannot copy a unique_ptr, at least not by writing up2 = up1 or std::unique_ptr<Node>(up).

But you can do other things with one. You can swap two of them with std::swap, which is an efficient way to rotate a subtree. You can move the pointer, usually by writing up2 = std::move<up1> or foo(std::move(up1)). That transfers the pointer to a different pointer and invalidates the original. You can dereference it to access the object it points to, or get a dumb pointer to the object, or even .release ownership of it. You can turn it into a shared_ptr, and a few other things.

It might take a little while to get used to, but it’s actually a good fit for your problem, because every node should either be the root, or the left or right child of exactly one node in the tree. So, it should have one unique node that owns it, and if the same node were ever linked two different places in the tree, it would be a serious bug. If you implement .extract(), it becomes possible to cut a node off its tree, but then it’s pruned from the tree, so there’s still only ever one pointer to it. You can also splice a unique_ptr to a node back into the tree, or a different one, but only by moving and consuming it, so there is still only one canonical unique_ptr to the node in existence at any time. In fact, the way .extract and .insert(node_type&&) are specified is a strong hint from the language standard that the STL map and set containers are supposed to use unique_ptr to store their nodes.

But this is a more advanced technique, and it’s possible to make the tree work without it.

Iterators?

I suggested above that you implement the std::multimap interface, which instead of returning pointers to a node, either returns the stored value by reference, or an iterator to the node. The implementation would probably actually be a wrapper to a RBTree::Node*.

The main things an iterator can do are dereference with *it (returning the data by reference), increment with ++it (which you already have, but spell .successor()), decrement with --it (which you already have, but spell predecessor()), and compare with == and !=.

You have the right general idea by returning Node*, but your library would be immediately be able to use all the STL algorithms, ranges, initialization and so on by turning them into iterators. And you’ve already done most of the work!

You’d also save yourself from exposing the entire definition of your node and allowing anyone who requests a value to arbitrarily tamper with your tree.

Use Const Where Appropriate

Currently, you don’t have any const functions, so if someone creates a const RBTree, they can’t do anything with it. Since your interface returns Node*, there’s nothing stopping people from seeing all your tree’s internals and even changing them. You really don’t want this.

Some Implementation Tips

In the comments, @greybeard linked to the left-leaning red-black tree data structure, which goes to some great references, including this paper.

You don’ need to use that particular algorithm. If you do, one tip is that there’s a single representation of a 2-node, a 3-node and a 4-node if you happen to use those, and those could all be created as subtrees, by constructors or factories with two, three or four rvalue-reference arguments.