4
\$\begingroup\$

I've completely reworked the previous code, posted here, so that it is a bit more correct regarding dynamic memory management, and also a bit more true to the object-oriented paradigm.

/** A program for Red-Black Tree manipulation: insertion and value retrieval.
  * All position relations (first, last, previous, next) are in-order.
  */

class RBTree {
    struct Node {
        enum class Colour : bool { RED, BLACK };
        int value;
        Node *left, *right, *parent;
        Colour colour;
    public:
        Node* getGrandparent() const;
        Node* getUncle() const;
        void setLeft(Node*);
        void setRight(Node*);
    };
    class Iterator {
        class Stack {
            Node **buffer;
            int size, top;
        private:
            void resize();
        public: // Member 'buffer' is initialized like this because the program doesn't catch/handle exceptions.
            Stack() : size(16), buffer(new Node*[size]), top(0) {}
            void push(Node*);
            Node* pop();
            Node* peek();
            void clear();
            bool isEmpty() const;
            ~Stack() { delete[] buffer; } // ?
        public:
            Stack(const Stack&);
            Stack(Stack&&);
            Stack& operator = (const Stack&);
            Stack& operator = (Stack&&);
        };
        Stack stack;
        const RBTree* const tree; // Once set, neither the reference nor the referenced object's attributes can be modified.
        Node* pointer;
    public:
        Iterator(const RBTree*);
        void first();
        void next();
        void last();
        void reset();
        void to(Node*);
        Node* getNode() const;
        bool operator != (const Iterator&) const;
    };
    Node *root;
    Iterator iterator;
private:
    void attachValue(int);
    void resolve();
    void rotateLeft(Node*);
    void rotateRight(Node*);
    void setRoot(Node*);
    void deleteTree();
public:
    RBTree() : root(nullptr), iterator(this) {}
    bool insertValue(int);
    Node* findValue(int);
    bool printTree() const;
    ~RBTree() { deleteTree(); }
public: // This section ensures that tree can neither be copied nor initialized with another tree, only built with insertion.
    RBTree(const RBTree&) = delete;
    RBTree(RBTree&&) = delete;
    RBTree& operator = (const RBTree&) = delete;
    RBTree& operator = (RBTree&&) = delete;
};

// TREE // public: //

// Retruns {false} if value already exists.
bool RBTree::insertValue(int p_value) {
if (findValue(p_value) == nullptr) {
        attachValue(p_value);
        resolve();
        return true;
    }
    else
        return false;
}

// Returns {nullptr} if value doesn't exist.
RBTree::Node* RBTree::findValue(int p_value) {
    Node *node = root, *parent = nullptr;
    while (node != nullptr) {
        if (p_value < node->value) {
            parent = node;
            node = node->left;
        }
        else if (p_value > node->value) {
            parent = node;
            node = node->right;
        }
        else
            return node;
    }
    if (parent != nullptr)
        iterator.to(parent);
    return nullptr;
}

bool RBTree::printTree() const {
    if (root != nullptr) {
        // print using in-order iteration
        return true;
    }
    else
        return false;

}

// TREE // private: //

// Attaches the given value under the current node (referenced by member 'iterator').
void RBTree::attachValue(int p_value) {
    Node *node = new Node;
    (*node) = { p_value, nullptr, nullptr, nullptr, Node::Colour::RED };
    if (root == nullptr) {
        root = node;
        return;
    }
    Node *parent = iterator.getNode();
    iterator.reset();
    if (p_value < parent->value)
        parent->setLeft(node);
    else
        parent->setRight(node);
    iterator.to(node);
}

// Resolves the invalid states.
void RBTree::resolve() {
    int case_number = 1;
    Node *node = iterator.getNode();
    iterator.reset();
    if (node == nullptr)
        node = root;
    do {
        switch (case_number) {
            case 1: {
                if (node->parent == nullptr) {
                    node->colour = Node::Colour::BLACK;
                    return;
                }
            }
            case 2: {
                if (node->parent->colour == Node::Colour::BLACK)
                    return;
            }
            case 3: {
                Node *uncle = node->getUncle();
                if (uncle != nullptr && uncle->colour == Node::Colour::RED) {
                    Node *grandparent = node->getGrandparent();
                    node->parent->colour = Node::Colour::BLACK;
                    uncle->colour = Node::Colour::BLACK;
                    grandparent->colour = Node::Colour::RED;
                    node = grandparent;
                    break;
                }
            }
            case 4: {
                Node *grandparent = node->getGrandparent(), *parent = node->parent;
                if (node == parent->right && parent == grandparent->left) {
                    rotateLeft(parent);
                    node = node->left;
                }
                else if (node == parent->left && parent == grandparent->right) {
                    rotateRight(parent);
                    node = node->right;
                }
            }
            case 5: {
                Node *grandparent = node->getGrandparent(), *parent = node->parent;
                parent->colour = Node::Colour::BLACK;
                grandparent->colour = Node::Colour::RED;
                if (node == parent->left)
                    rotateRight(grandparent);
                else
                    rotateLeft(grandparent);
                node = parent;
                break;
            }
        }
    } while (case_number);
}

RBTree::Node* RBTree::Node::getGrandparent() const {
    if (parent != nullptr)
        return parent->parent;
    else
        return nullptr;
}

RBTree::Node* RBTree::Node::getUncle() const {
    Node *grandparent = getGrandparent();
    if (this == grandparent->left)
        return grandparent->right;
    else
        return grandparent->left;
}

void RBTree::rotateLeft(Node *p_node) {
    Node *node = p_node;
    Node *right_left = p_node->right->left;
    if (p_node == root) // If root is the pivot, update the root info.
        setRoot(p_node->right);
    p_node = p_node->right;
    if (node->parent != nullptr)
        node->parent->setRight(node->right);
    node->right->setLeft(node);
    node->setRight(right_left);

}

void RBTree::rotateRight(Node *p_node) {
    Node *node = p_node;
    Node *left_right = p_node->left->right;
    if (p_node == root) // If root is the pivot, update the root info.
        setRoot(p_node->right);
    p_node = p_node->left;
    if (node->parent != nullptr)
        node->parent->setLeft(node->left);
    node->left->setRight(node);
    node->setLeft(left_right);
}

void RBTree::setRoot(Node *p_root) {
    root = p_root;
    root->parent = nullptr;
}

void RBTree::deleteTree() {
    Node *node;
    for (Iterator i(this); (node = i.getNode()) != root; i.next())
        delete node;
    delete root;
}

// NODE: Ensures the proper connection. //

void RBTree::Node::setLeft(Node *p_left) {
    left = p_left;
    if (p_left != nullptr)
        p_left->parent = this;
}

void RBTree::Node::setRight(Node *p_right) {
    right = p_right;
    if (p_right != nullptr)
        p_right->parent = this;
}

// ITERATOR //

RBTree::Iterator::Iterator(const RBTree* p_tree) : tree(p_tree), pointer(p_tree->root) {}

// Traverses to the first node (leftmost).
void RBTree::Iterator::first() {
    if (pointer != nullptr) {
        while (true) {
            if (pointer != nullptr) {
                stack.push(pointer);
                pointer = pointer->left;
            }
            else {
                pointer = stack.peek();
                break;
            }
        }
    }
}

// Traverses to next node in-order.
void RBTree::Iterator::next() {
    if (pointer != nullptr) {
        if (!stack.isEmpty()) {
            pointer = stack.pop();
            if (pointer->right != nullptr) {
                pointer = pointer->right;
                first();
            }
        }
    }
}

// Traverses to the last node (rightmost).
void RBTree::Iterator::last() {
    pointer = tree->root;
    if (pointer != nullptr)
        while (pointer->right != nullptr)
            pointer = pointer->right;
    stack.clear();
}

// Returns to the first node.
void RBTree::Iterator::reset() {
    pointer = tree->root;
    stack.clear();
    first();
}

// Traverses to the given node. Stores {nullptr} if the node cannot be found. // ??
void RBTree::Iterator::to(Node *p_node) {
    if (p_node == tree->root) {
        pointer = p_node;
        return;
    }
    reset();
    while (pointer != p_node)
        next();
}

RBTree::Node* RBTree::Iterator::getNode() const {
    return pointer;
}

bool RBTree::Iterator::operator != (const Iterator& p_iterator) const {
    return pointer != p_iterator.pointer ? true : false;
}

// STACK //

// Doubles the stack size.
void RBTree::Iterator::Stack::resize() {
    Node **temporary = new Node*[size <<= 1];
    for (int i = 0; i < top; i++)
        temporary[i] = buffer[i];
    delete[] buffer;
    buffer = temporary;
}

// Copy constructor.
RBTree::Iterator::Stack::Stack(const Stack& p_stack) : size(p_stack.size), top(p_stack.top), buffer(new Node*[p_stack.size]) {
    for (int i = 0; i < top; i++)
        buffer[i] = p_stack.buffer[i];
}

// Move constructor.
RBTree::Iterator::Stack::Stack(Stack&& p_stack) : size(p_stack.size), top(p_stack.top), buffer(p_stack.buffer) {
    p_stack.buffer = nullptr;
}

// Copy assignment operator.
RBTree::Iterator::Stack& RBTree::Iterator::Stack::operator = (const Stack& p_stack) {
    if (p_stack.buffer == this->buffer)
        return *this;
    size = p_stack.size;
    top = p_stack.top;
    Node** temporary = new Node*[size];
    for (int i = 0; i < top; i++)
        temporary[i] = p_stack.buffer[i];
    delete[] buffer;
    buffer = temporary;
    return *this;
}

// Move assignment operator.
RBTree::Iterator::Stack& RBTree::Iterator::Stack::operator = (Stack&& p_stack) {
    if (p_stack.buffer == this->buffer)
        return *this;
    delete[] buffer;
    buffer = p_stack.buffer;
    p_stack.buffer = nullptr;
    return *this;
}

void RBTree::Iterator::Stack::push(Node *p_node) {
    if (top == size)
        resize();
    buffer[top++] = p_node;
}

RBTree::Node* RBTree::Iterator::Stack::pop() {
    return isEmpty() ? nullptr : buffer[--top];
}

RBTree::Node* RBTree::Iterator::Stack::peek() {
    return isEmpty() ? nullptr : buffer[top - 1];
}

void RBTree::Iterator::Stack::clear() {
    top = 0;
}

bool RBTree::Iterator::Stack::isEmpty() const {
    return top == 0 ? true : false;
}

#include <iostream>

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

int 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 successful.\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 3: {
                if (tree.printTree())
                    cout << "\n > Print unsuccessful.\n";
                else
                    cout << "\n > Print failed.\n";
                break;
            }
            case 0: {
                return 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;
    }
}

The printTree() function is a stub, I'm still looking for an appropriate algorithm that utilizes the in-order traversal. That's not a part of this review, for it is discussed here, in detail.

I am looking for a confirmation that the code has sufficiently improved since the previous version, guided by the answers I was given in that post regarding encapsulation, memory management, etc... Also I would appreciate if you could point out if I've done anything wrong while applying those critiques.

\$\endgroup\$
3
\$\begingroup\$

What is an Iterator?

An iterator is a very powerful concept in the world of C++. At its core, iterator is just a set of required operations, but when every iterator-like object adheres to those concepts, you can open up the wonderful world of generic programming.

Writing a container that has iterators that adhere to the standard means that I can be completely agnostic to whatever it is you're doing under the hood. If I want to iterate over everything in your map, I just do that:

for (auto const& item : map) { ... }

I bring this up because RBTree::Iterator meets almost none of the concepts of even the lowest level of iterator, InputIterator. Those operations are: i != j, *i, i->member, ++i, (void)i++, *i++. Although a RedBlack Tree should really support a BidirectionalIterator.

In this case, Iterator (which should be spelled iterator) should really just be a thin wrapper for Node*. There is no Stack necessary (indeed, I am unsure what Iterator::Stack is for).

class iterator {
    Node* cur;

public:
    ...
};

Equality, inequality, and dereference are trivial operations. Since you have the Node*, and thus know the node's parent, left, and right children, that is enough to figure out what the next and previous nodes are to this one, which should be spelled:

iterator& operator++() { /* next */; return *this; }
iterator& operator--() { /* prev */; return *this; }

To get you started, the easy case for "next" is if our current node has a right child:

iterator& operator++() {
    if (cur->right) {
        cur = cur->right;
        while (cur->left) {
            cur = cur->left;
        }
        return *this;
    }
    else {
        ...
    }
}

It is very important to write your iterators to work the way that users expect iterators to work. I cannot stress this enough.

Lastly, you should not have a member iterator. That doesn't make sense. An iterator is for iterating. The tree should have a single member: the root.

Consistency

Once we have a working iterator, let's keep the interface consistent with other containers. To start with, we need the typical container skeleton:

iterator begin();
iterator end();

Then, find() should return an iterator

iterator find(int);

which should be compared to end() to see if we've found anything. And printTree() should really look like:

friend std::ostream& operator<<(std::ostream&, const RBTree& );

Since std::cout << tree; is natural, and easily allows you to write your tree to other kinds of streams.

Why not copyable?

Why is your class neither copyable nor moveable? At the very least, writing the move operations should be trivial:

RBTree(RBTree&& rhs)
: root(rhs.root) {
    rhs.root = nullptr;
}

No reason not to support it. Copying will involve a deep copy, but that's less complicated than any other operation for the tree. You don't need to figure out colouring! Just copy.

Principle of Least Surprise

I think most people would be surprised that findValue() mutates your RBTree! When I said in your previous post to factor out the common logic so they call a common function, I meant just that - not to create a new member to store the intermediate data!

This isn't just a questionable solution because it's surprising. This also means you can't write find() as a const member function, which means that a const RBTree is useless.

Furthermore, we have resolve(), which is only called here:

bool RBTree::insertValue(int p_value) {
    if (findValue(p_value) == nullptr) {
        attachValue(p_value);
        resolve();  // <===
        return true;
    }
    else
        return false;
}

It should be up to attachValue()'s job to keep the map in a consistent state. Otherwise, you could simply forget to call resolve() and now your tree is broken.

\$\endgroup\$
  • 1
    \$\begingroup\$ @StefanStanković There's no need for "redeeming" yourself. Nobody here is think less of you as a human being for writing non-perfect code. And nobody left the womb with perfect knowledge of C++ either. That's what we're here for. \$\endgroup\$ – Barry Nov 18 '15 at 15:05

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.