I have been working on a custom Tree class that enforces certain rules upon insertion and deletion.
The implemented tree is a Red-Black-Tree but since the implementation is far too long, I will not post the complete code but only the relevant parts. I have also reduced the code and removed the Red-Black-Tree specific parts such as the colour that each node usually has to store.
This question is not about the tree itself, but about its iterator.
Note that I can not use any elements from the STL such as shared_ptr or unique_ptr on my target platform.
Tree Nodes
This struct represents the nodes of the tree and since I implemented a Red-Black-Tree, each node already has a pointer to its parent. This will be used later for iterating the tree without recursion and without an extra stack.
Member-Declarations
template <typename T>
struct Node {
Node(T content);
virtual ~Node() = default;
/** Get the object stored in the node */
T& getContent();
/** Pointers to construct the tree */
Node<T> *leftChild, *rightChild, *parent;
/** Content stored in the node */
T content;
};
Member-Definitions
template <typename T>
RBNode<T, K>::RBNode(T content)
: leftChild(nullptr)
, rightChild(nullptr)
, parent(nullptr)
, content(content) {
}
template <typename T>
T& RBNode<T, K>::getContent() {
return content;
}
Tree-Iterator
The interesting part of the Implementation is the iterator I use to traverse the tree. It is important that it iterates in post-order, so that during the destruction of the tree I can use this iterator to delete all nodes by simply iterating over them.
Member-Declarations
template <typename T>
class Tree;
template <typename T>
struct Node;
template <typename T>
class TreeIterator {
friend class Tree<T>;
public:
TreeIterator(const Tree<T>* instance, Node<T>* initialNode);
TreeIterator(const TreeIterator&);
TreeIterator(TreeIterator&&);
~TreeIterator() = default;
TreeIterator<T>& operator=(const TreeIterator<T>&);
TreeIterator<T>& operator=(TreeIterator<T>&&);
TreeIterator<T>& operator++();
TreeIterator<T> operator++(int);
T& operator*();
T* operator->();
const T* operator->() const;
Node<T>* node();
bool operator==(const TreeIterator<T>&) const;
bool operator!=(const TreeIterator<T>&) const;
/** Used by the tree to generate begin() iterator */
static TreeIterator<T> begin(Tree<T>* instance, Node<T>* rootNode);
private:
const Tree<T>* instance;
Node<T>* currentNode;
};
Constructors and Assignment
template <typename T>
TreeIterator<T>::TreeIterator(const Tree<T>* instance, Node<T>* initialNode)
: instance(instance)
, currentNode(initialNode) {
}
template <typename T>
TreeIterator<T>::TreeIterator(const TreeIterator& other)
: instance(other.instance)
, currentNode(other.currentNode) {
}
template <typename T>
TreeIterator<T>::TreeIterator(TreeIterator&& other)
: instance(other.instance)
, currentNode(other.currentNode) {
other.instance = nullptr;
other.currentNode = nullptr;
}
template <typename T>
TreeIterator<T>& TreeIterator<T>::operator=(const TreeIterator<T>& other) {
this->instance = other.instance;
this->currentNode = other.currentNode;
return *this;
}
template <typename T>
TreeIterator<T>& TreeIterator<T>::operator=(TreeIterator<T>&& other) {
this->instance = other.instance;
this->currentNode = other.currentNode;
other.instance = nullptr;
other.currentNode = nullptr;
return *this;
}
-> ITERATING <-
The iterator uses the parent and the leftChild and rightChild pointers to traverse the tree. Since the relation between two connected nodes is always evident and since there are no loops, it is possible to iterate over the nodes without requiring additional memory.
/*
* iterate over a Tree in postorder
*/
template <typename T>
TreeIterator<T>& TreeIterator<T>::operator++() {
Node<T>* parent;
if(this->currentNode == nullptr) {
/* '-> end iterator does not increment */
return *this;
}
parent = this->currentNode->parent;
/*
* reaches root -> next is end()
*/
if(parent == nullptr) {
this->currentNode = nullptr;
return *this;
}
/*
* left child -> go to right child
* right child -> go to parent
*/
if((this->currentNode == parent->leftChild) && (parent->rightChild != nullptr)) {
this->currentNode = parent->rightChild;
} else {
this->currentNode = this->currentNode->parent;
return *this;
}
while(true) {
if(this->currentNode->leftChild != nullptr) {
/* '-> has left child node */
this->currentNode = this->currentNode->leftChild;
} else if(this->currentNode->rightChild != nullptr) {
/* '-> only right child node */
this->currentNode = this->currentNode->rightChild;
} else {
/* '-> has no children -> stop here */
return *this;
}
}
}
template <typename T>
TreeIterator<T> TreeIterator<T>::operator++(int) {
TreeIterator<T> old = *this;
++(*this);
return old;
}
Other Member-Definitions
template <typename T>
T& TreeIterator<T>::operator*() {
return this->currentNode->getContent();
}
template <typename T>
T* TreeIterator<T>::operator->() {
return &(this->currentNode->getContent());
}
template <typename T>
const T* TreeIterator<T>::operator->() const {
return &(this->currentNode->getContent());
}
template <typename T>
Node<T>* TreeIterator<T>::node() {
return this->currentNode;
}
template <typename T>
bool TreeIterator<T>::operator==(const TreeIterator<T>& other) const {
return (this->instance == other.instance && this->currentNode == other.currentNode);
}
template <typename T>
bool TreeIterator<T>::operator!=(const TreeIterator<T>& other) const {
return !((*this) == other);
}
template <typename T>
TreeIterator<T> TreeIterator<T>::begin(Tree<T>* instance, Node<T>* rootNode) {
if(rootNode == nullptr) {
return TreeIterator(instance, rootNode);
}
/*
* iterate to the node in the bottom-left
*/
while(true) {
if(rootNode->leftChild != nullptr) {
rootNode = rootNode->leftChild;
} else if(rootNode->rightChild != nullptr) {
rootNode = rootNode->rightChild;
} else {
return TreeIterator(instance, rootNode);
}
}
}
Questions
- Have I missed anything important about implementing iterators? Are there style flaws?
- Since large parts of the tree can change during an
add()orremove()operation, these operations may not be performed while iterating over the tree, because the active iterator might skip elements or visit them multiple times. Is this also the case for STL iterators of standard containers?- If not, is there a way to make my iterator more robust against changes in the tree structure?
You can also have a look at the complete implementation including the Red-Black-Tree at this GitHub repository.
