Memory management for Red-Black Tree

I've written this program yesterday, and I was reminded why I dreaded C++ before turning to Java: pointers and associated terms (like destructors, initializations and copy/move constructors) are making me rather anxious about possible logical oversights every time I need to write a C++ program, however simple or complex it might be.

So, are there any rules-of-thumb (like: there must be a delete operator for every new operator) which can help me systematize the checking for such oversights in this (and future) code? Topology changes give me the most trouble.

My other concern is if Node and QueueMember should be structures with public attributes instead of classes? Also, I'm worried that my commenting clutters the code, instead of making it more readable...

```
/*
A program for Red-Black Tree manipulation: insertion and value retrieval.
*/

#include

#define BLACK true
#define RED false

/***
The main class: Red-Black Tree.
***/

class RBTree {

/
Structural class: Red-Black Tree Node.
/

class Node {
int value; // Information.
Node left, right, *parent; // Pointers.
bool colour; // Red or black.
public:
Node(int p_value) :
// Initialization. //
value(p_value),
left(nullptr), right(nullptr), parent(nullptr),
colour(RED) {
// Conversion constructor.
}
int getValue() {
return value;
}
void setLeft(Node *p_left) {
left = p_left;
// Secures the connection. //
if

So, are there any rules-of-thumb (like: there must be a delete operator for every new operator) which can help me systematize the checking for such oversights in this (and future) code? Topology changes give me the most trouble.

Pairing delete with new is an important rule. Another one is the Rule of Three/Five/Zero. Every time you write a destructor, you have to write the copy/move constructors/assignment operators. You failed to write those, so instead you are using the ones provided by the compiler, which just do shallow copy:

RBTree r1;
// do a bunch of inserts
RBTree r2 = r1; // this just copies the pointer root, not a deep copy
// now r2 gets destroyed, which deletes all the nodes
// now r1 gets destroyed, which tries to delete all the same nodes again, BOOM

You have to write all those other functions!


My other concern is if Node and QueueMember should be structures with public attributes instead of classes

Node should definitely be a struct with public attributes, yes. It's a private, internal struct to RBTree, nothing in the outside world needs to know about it. It'll make your life much easier. Plus, adding getters and setters for every attribute is questionable design.

This is fine:

struct Node {
    int value;
    Node *left, *right, *parent;
    bool colour; 
};

No comments are necessary there. Clearly left, right, *parent are pointers. One thing about color. You have:

#define BLACK true
#define RED false

This is quite poor. You're polluting the world with these names. Macros fundamentally do not play well with others. There's also no indication that these are closely related. Strongly prefer an enumeration:

enum class Colour : uint8_t { BLACK, RED };

And have a member of class Colour instead of a bool. This will give you all the benefits (checking if colour is Colour::BLACK) without any of the downsides (wait, what's the bool mean? What's true? Why does my completely unrelated program break when I try to use BLACK?)

But there's a lot more to say than just that.

Interface

Your public interface for RBTree is:

RBTree();
void rotateRight(Node* );
void rotateLeft(Node* );
void processNode(Node* );
bool attachNode(Node* );
bool insertValue(int );
Node* findValue(int );
Node* getParent(Node* );
Node* getGrandparent(Node* );
Node* getUncle(Node* );

Node is a [correctly] private class to RBTree. All the rotation functions are super important to the internal handling of the class, but should absolutely not be visible to the user! You're basically letting me rotate your tree as I see fit. That breaks encapsulation.

You want to reduce your interface down to just:

bool insertValue(int );
iterator findValue(int );

// and these!
bool erase(int );
bool erase(iterator );

Where iterator is something you should provide to meet the expected interface of C++ containers. What if I wanted to do something like... print all the elements of your tree? Can't do it.

NodeQueue

I don't understand why this class exists. You just use it to clear(), but it's a super complicated way of doing that. You could just iterate through the nodes directly.

Repetition

Consider findValue() and attachNode(). They have to start with the same thing: finding where value would go. Try to factor out the common logic so that attachNode() calls something similar to findValue() to determine where the node would need to be attached, and then return false if such a node already exists.

Furthermore, your insert news a Node, only to potentially delete it. If you rewrite the code in the manner I suggest, you can defer the allocation to those spots where you need to allocate. This avoids a source of error, and makes the logic easier to follow.

void main()

main() must return int.

Comment Style

The purpose of comments is to explain issues that the code itself cannot. Consider this function:

RBTree::Node* RBTree::findValue(int p_value) {
    Node *node = root;                          // Required traversal pointer.
    while (node != nullptr) {                   // While there's somewhere to descend to...
        if (p_value getValue())         // ...if the value is lower..
            node = node->getLeft();             //  ..descend left.
        else if (p_value > node->getValue())    // ...if the value is greater..
            node = node->getRight();            //  ..descend right.
        else                                    // ...if the value is equal..
            return node;                        //  ..return the node.
    }                                           // Otherwise..
    return nullptr;                             // ..report failure.
}

What value do any of the comments there add? None. You have a comment to "return the node" next to the line return node; The code itself is already written in a very readable way. I have no issue with the code for findValue. If

StackExchange Code Review Q#110461, answer score: 2