Iterative Red-Black Tree (dynamic stack)

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(thi

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.

StackExchange Code Review Q#111060, answer score: 3