4
\$\begingroup\$

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 <iostream>

#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 (p_left != nullptr)
                p_left->setParent(this);
        }
        Node* getLeft() {
            return left;
        }
        void setRight(Node *p_right) {
            right = p_right;
            // Secures the connection. //
            if (p_right != nullptr)
                p_right->setParent(this);
        }
        Node* getRight() {
            return right;
        }
        void setParent(Node *p_parent) {
            parent = p_parent;
        }
        Node* getParent() {
            return parent;
        }
        void setColour(bool p_colour) {
            colour = p_colour;
        }
        bool getColour() {
            return colour;
        }
    };

    // The root of the Red-Black Tree.
    Node *root;

public:

    RBTree() : root(nullptr) {
        // Basic constructor.
    }

    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*);

private:

    /*********************************************************************
      Tree deletion: node queue and level-order traversal implementation.
     *********************************************************************/

    // Node Queue, required for level-order traversal.
    class NodeQueue {
        class QueueMember {                                             // Node Queue structural class.
            Node *node;                                                 // Information.
            QueueMember *next;                                          // Pointer.
        public:
            QueueMember(Node* p_node) : node(p_node), next(nullptr) {
                // Conversion constructor.
            }
            Node* getNode() {
                return node;
            }
            void setNext(QueueMember *p_next) {
                next = p_next;
            }
            QueueMember* getNext() {
                return next;
            }
            ~QueueMember() {                                            // Queue member destructor..
                next = nullptr;                                         // ..ensures that when the member is deleted from dynamic memory..
                delete node;                                            // ..the associated node is also deleted from dynamic memory.
            }
        };
        // Required pointers. //
        QueueMember *front, *back;
    public:
        NodeQueue(Node *p_root) {                                       // The Queue is initialized with the root.
            front = back = new QueueMember(p_root);
        }
        QueueMember* getFront() {
            return front;
        }
        QueueMember* getBack() {
            return back;
        }
        void insert(Node *p_node) {                                     // Queue member insertion:
            QueueMember *temporary = new QueueMember(p_node);           // Create a member...
            front->setNext(temporary);                                  // ..link it to the front...
            front = temporary;                                          // ..and assign it as the front member.
        }
        void remove() {                                                 // Queue member removal:
            QueueMember *temporary = back;                              // Record the last member..
            back = back->getNext();                                     // ..move past him..
            delete temporary;                                           // ..and delete him.
        }
        bool isEmpty() {                                                // Empty queue check..
            return back == nullptr ? true : false;                      // ..relies on 'remove()'.
        }
    };

    void clear() {                                                      // Clearing the tree.
        NodeQueue queue(root);                                          // Starting from the root..
        do {                                                            // ..we process the nodes in level-order:
            Node                                                        // First, we prepare associated nodes of the LAST MEMBER: ...
                *left = queue.getBack()->getNode()->getLeft(),          // ...it's left child..
                *right = queue.getBack()->getNode()->getRight();        //  ..and it's right child.
            if (left != nullptr)                                        // Then, if it has a left child..
                queue.insert(left);                                     // ..we add it to the queue.
            if (right != nullptr)                                       // Then, if it has a right child..
                queue.insert(right);                                    // ..we add it to the queue.
            queue.remove();                                             // Finally, we remove it.
        } while (!queue.isEmpty());                                     // We continue until there are no more members to process.
    }

public:

    ~RBTree() {                                                         // Tree destructor..
        if (root) {                                                     // ..ensures that if there is an actual tree..
            clear();                                                    // ..it will be deleted from dynamic memory.
        }
    }

};

/************************************************************
  Main functionalities: value insertion and value retrieval.
 ************************************************************/

// Inserts the given value.
bool RBTree::insertValue(int p_value) {
    Node *node = new Node(p_value);     // New node for insertion.  
    // Node attachment attempt. //
    if (attachNode(node) == false) {    // If the node attachment fails..
        return false;                   // ..report the failure.
    }
    // Node processing. //
    processNode(node);
    return true;
}

// Simple binary search.
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 < node->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.
}

/****************************************************************
  Utility methods: parent, grandparent and uncle node retrieval,
  node attachment, node processing, left and right rotation.
 ****************************************************************/

RBTree::Node* RBTree::getParent(Node *p_node) {
    if (p_node != nullptr)
        return p_node->getParent();
    else
        return nullptr;
}

RBTree::Node* RBTree::getGrandparent(Node *p_node) {
    if (p_node && p_node->getParent())
        return p_node->getParent()->getParent();        // Gets parent's parent.
    else {
        return nullptr;
    }
}

RBTree::Node* RBTree::getUncle(Node *p_node) {
    Node *grandparent = getGrandparent(p_node);
    if (!grandparent)
        return nullptr;
    if (p_node->getParent() == grandparent->getLeft())  // Get's grandparent's other child (other than the parent).
        return grandparent->getRight();
    else
        return grandparent->getLeft();
}

// Fails if the value isn't unique.
bool RBTree::attachNode(Node *p_node) {
    Node *temporary = root;
    if (temporary == nullptr)                                   // If the tree is empty..
        root = p_node;                                          // ..attach the root.
    while (temporary != nullptr) {                              // If the state is valid....
        if (p_node->getValue() < temporary->getValue())         // ....and if the value is lower...
            if (temporary->getLeft() != nullptr)                //  ...and if there is a left child..
                temporary = temporary->getLeft();               //   ..go left.
            else {                                              //  ...and if there is no left child..
                temporary->setLeft(p_node);                     //   ..attach the node to the left.
                break;
            }
        else if (p_node->getValue() > temporary->getValue())    // ....and if the value is greater...
            if (temporary->getRight() != nullptr)               //  ...and if there is a right child..
                temporary = temporary->getRight();              //   ..go right.
            else {                                              //  ...and if there is no right child..
                temporary->setRight(p_node);                    //   ..attach the node to the right.
                break;
            }
        else {                                                  // ....and if the value is equal...
            delete p_node;                                      //  ...delete the node..
            return false;                                       //   ..and report the failure.
        }
    }
    return true;                                                // Otherwise, report success.
}

// Node recolouring and tree balancing.
void RBTree::processNode(Node* p_node) {
    do {
        // Required pointers. //
        Node
            *uncle = getUncle(p_node),
            *grandparent = getGrandparent(p_node),
            *parent = getParent(p_node);
        // Root case. //
        if (parent == nullptr) {                                // If the node has no parent..
            p_node->setColour(BLACK);                           //  ..set it to black.
            return;
        }
        // Valid case. //
        if (parent->getColour() == BLACK)                       // If the node's parent is black.
            return;
        // RPRU colour case. //
        if (uncle != nullptr && uncle->getColour() == RED) {    // If both parent and uncle are red.....
            parent->setColour(BLACK);                           // .....set the parent to black....
            uncle->setColour(BLACK);                            //  ....and set the uncle to black....
            grandparent->setColour(RED);                        //   ...and set the granparent to red..
            p_node = grandparent;                               //    ..and process the grandparent.
            break;
        }
        // LR/RL leaning case. //
        if (p_node == parent->getRight()                        // If the node is a right child.....
            &&                                                  // .....and....
            parent == grandparent->getLeft()) {                 //  ....if the parent is a left child....
            rotateLeft(parent);                                 //   ...rotate left around the parent..
            p_node = p_node->getLeft();                         //    ..and process the parent (which became node's left child).
            break;
        }
        else if (p_node == parent->getLeft()                    // If the node is a left child.....
            &&                                                  // .....and....
            parent == grandparent->getRight()) {                //  ....if the parent is a right child...
            rotateRight(parent);                                //   ...rotate left around the parent..
            p_node = p_node->getRight();                        //    ..and process the parent (which became node's right child).
            break;
        }
        // LL/RR leaning case. //
        parent->setColour(BLACK);                               // Otherwise, set parent to black....
        grandparent->setColour(RED);                            // ....and set grandparent to red...
        if (p_node == parent->getLeft())                        //  ...and if node is a left child..
            rotateRight(grandparent);                           //   ..rotate right around grandparent.
        else                                                    //  ...and if node is a right child..
            rotateLeft(grandparent);                            //   ..rotate left around grandparent.
    } while (true);
}

// Simple pointer reconnecting.
void RBTree::rotateLeft(Node *p_node) {
    // Required pointers. //
    Node
        *saved_node = p_node,                                           // Keeps the node.
        *saved_right_child_left_sub = p_node->getRight()->getLeft();    // Keeps its RL grandchild.
    p_node = p_node->getRight();                                        // Node takes the place of its right child.
    saved_node->getRight()->setLeft(saved_node);                        // Node becomes its right child's left child.
    saved_node->setRight(saved_right_child_left_sub);                   // Node's RL grandchild becomes its right child.
}

// Simple pointer reconnecting.
void RBTree::rotateRight(Node *p_node) {
    // Required pointers. //
    Node
        *saved_node = p_node,                                           // Keeps the node.
        *saved_left_child_right_sub = p_node->getLeft()->getRight();    // Keeps its LR grandchild.
    p_node = p_node->getLeft();                                         // Node takes the place of its left child.
    saved_node->getLeft()->setRight(saved_node);                        // Node becomes its left child's right child.
    saved_node->setLeft(saved_left_child_right_sub);                    // Node's LR grandchild becomes its left child.
}

/***************
  Main program.
 ***************/

using std::cin;
using std::cout;

// Third option will print out the ASCII tree in the console.
void main() {
    RBTree tree;
    int choice = 0;
    cout << "\nOptions: \n\n 1 Insert value.\n 2 Find value.\n\n 0 Exit.\n\nChoice: ";
    cin >> choice;
    while (choice != 0) {
        switch (choice) {
            case 1: {
                cout << "\nValue = ";
                cin >> choice;
                if (tree.insertValue(choice))
                    cout << "\n > Insertion succesful.\n";
                else
                    cout << "\n > Insertion failed.\n";
                break;
            }
            case 2: {
                cout << "\nValue = ";
                cin >> choice;
                if (tree.findValue(choice) != nullptr)
                    cout << "\n > Value found.\n";
                else
                    cout << "\n > Value not found.\n";
                break;
            }
            case 0: {
                exit(0);
            }
            default: {
                cout << "\n > Invalid option.\n";
            }
        }
        cout << "\nOptions: \n\n 1 Insert node.\n 2 Find node.\n\n 0 Exit.\n\nChoice: ";
        cin >> choice;
    }
}
\$\endgroup\$
  • \$\begingroup\$ Ah, VS. int main() is not valid C++, main must return int. \$\endgroup\$ – Mat Nov 11 '15 at 16:56
  • \$\begingroup\$ The rule you are looking for is Never use new. Consequently you don't need delete. Prefer vector when possible and use unique_ptr if not. This eliminates your concern and makes you use modern C++. \$\endgroup\$ – nwp Nov 11 '15 at 18:58
  • 2
    \$\begingroup\$ @nwp In this case, you definitely want new. You're managing a container. In this case, unique_ptr will make it much harder to implement correctly - especially the rotations. \$\endgroup\$ – Barry Nov 11 '15 at 21:02
2
\$\begingroup\$

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 < node->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 a reader can't understand what the function is doing, then it's because they don't know C++ - the comments aren't going to help anybody.

Minor comments follow

  1. Comparing against false (e.g. if (attachNode(node) == false)) is bad practice. Simply say if (!attachNode(node)). It would also be clearer if the name attachNode indicated that it could fail somehow.
  2. Since getParent() already checks for null, getGrandparent() could just be return getParent(getParent(p_node)).
  3. Avoid declaring multiple things on a single line. This is especially egregious when you declare multiple things on a single line that is split anyway:

    Node
        *left = queue.getBack()->getNode()->getLeft(),
        *right = queue.getBack()->getNode()->getRight();
    

    Just do:

    Node *left = ...;
    Node *right = ...;
    
\$\endgroup\$
  • \$\begingroup\$ What about enum class Colour : bool { BLACK, RED };? Is it also bad? \$\endgroup\$ – Stefan Stanković Nov 12 '15 at 12:03
  • \$\begingroup\$ @StefanStanković That's perfectly fine. That's actually even better since then if you try to add another color (say, GREEN), you'd get a compile error that will force you to rethink what you're doing. \$\endgroup\$ – Barry Nov 12 '15 at 13:24
  • \$\begingroup\$ Please, get a look at this if you've got the time. :) Thanks in advance. \$\endgroup\$ – Stefan Stanković Nov 17 '15 at 23:26
2
\$\begingroup\$

Yes, an important aspect of C++ is that the programmer has to somehow free memory that was allocated explicitly. If you use operator new then yes, you have to delete the memory at some point. That's one of the reasons for destructors. However, manual memory management with new/detete, malloc/free and the like is somewhat an outdated practice in current C++. That's not to say that this is never done, but certainly, manual memory management is not the kind of thing you'd be doing on your average C++ programming.

These days the C++ Standard Library has what are called "smart pointers", which are template classes that wrap a native pointer into an object to make the resource free itself in the destructor of this wrapper object. So the vast majority of objects you allocate in your program should use these library wrappers.

Then there are dynamically sized collections, like arrays and lists. Again, the Standard Library covers those with template containers like std::vector and std::list, so in the end of the day, there's little reason to do manual memory management where you don't have to. So resource management in C++ doesn't have to be as obscure as it might seem like from a GC'd language perspective ;)

Now back to your code specifically, you're writing a kind of container class, much like std::map (which is usually implemented as an RBTree, btw), so it is more difficult to make use of smart pointers in your specific case, given the nature of the tree nodes and possibility of cyclic references in the hierarchy. Since the tree structure owns every node, it's still not that hard cleaning it up. You just have to make sure the destructor deletes all the children. You seem to be doing that correctly, but you can also check to make sure no memory is being leaked with a tool like Valgrind or Clang-Sanitizer.


Your code seems quite good, @Barry has already mentioned the main points, he just missed one thing which is important:

Const correctness

Class methods that are not changing member data are marked with const at the end to emphasise this and to also allow them being called on a const declared object. Read more about it here. get*() methods are the obvious candidates for this, but you should also apply const to any non-mutating class method.

Misc

I'll have to agree that your comments are too verbose. No need to detail what each line is doing. You're not writing Assembly code, so if the names are good and clear, each statement should already be human readable.

Pointer dereference is bad for performance. If you could redesign this structure to operate on an array backing store, you'd gain a lot better data locality. This should be feasible, but you might have to replace the pointers to nodes by indexes into the underlaying array, so that the array can still be resized on demand.

And of course, next step is upgrading it to a template class (in Java parlance, a generic), so that it can operate on more types rather than just int.

\$\endgroup\$
  • \$\begingroup\$ Please, get a look at this if you've got the time. :) Thanks in advance. \$\endgroup\$ – Stefan Stanković Nov 17 '15 at 23:27

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.