Node Color Representation

Associative containers within the STL, such as maps and sets, rely heavily on the red-black tree data structure for their core operations including insertion, deletion, and lookup. The foundational element of this structure requires a distinction between red and black nodes.

enum class NodeShade { Crimson = 0, Obsidian = 1 };

Base Vertex Structure

The fundamental architecture of a red-black tree node encompasses a color indicator, a parent link, and two child links. Utility functions are also provided to traverse to the extreme ends (minimum and maximum) of the subtree rooted at a given vertex.

struct TreeVertexBase {
    using BaseLink = TreeVertexBase*;
    using ConstBaseLink = const TreeVertexBase*;

    NodeShade shade;
    BaseLink ancestor;
    BaseLink left_child;
    BaseLink right_child;

    static BaseLink find_min(BaseLink curr) noexcept {
        while (curr->left_child != nullptr) curr = curr->left_child;
        return curr;
    }

    static ConstBaseLink find_min(ConstBaseLink curr) noexcept {
        while (curr->left_child != nullptr) curr = curr->left_child;
        return curr;
    }

    static BaseLink find_max(BaseLink curr) noexcept {
        while (curr->right_child != nullptr) curr = curr->right_child;
        return curr;
    }

    static ConstBaseLink find_max(ConstBaseLink curr) noexcept {
        while (curr->right_child != nullptr) curr = curr->right_child;
        return curr;
    }
};

Data Vertex Structure

Building upon the base structure, the data vertex incorporates the actual stored value. The storage mechanism evolved between C++11 and earlier standards. Prior to C++11, the value was directly embedded as a member variable. From C++11 onwards, an aligned buffer is utilized to guarantee proper memory alignment, which is crucial for performance and hardware compatibility, particularly for types requiring specific alignment like SIMD vectors.

template<typename ValType>
struct DataVertex : public TreeVertexBase {
    using DataLink = DataVertex<ValType>*;

#if __cplusplus < 201103L
    ValType payload;

    ValType* get_ptr() { return std::__addressof(payload); }
    const ValType* get_ptr() const { return std::__addressof(payload); }
#else
    __gnu_cxx::__aligned_buffer<ValType> aligned_storage;

    ValType* get_ptr() { return aligned_storage._M_ptr(); }
    const ValType* get_ptr() const { return aligned_storage._M_ptr(); }
#endif
};

Tree Navigator (Iterator)

To traverse the tree, a bidirectional navigator is implemented, adhering to STL iterator requirements by defining essential type aliases. The core traversal logic resides in the increment and decrement operations, which navigate the tree in key order.

template<typename ValueType>
class TreeNavigator {
public:
    using value_type = ValueType;
    using reference = ValueType&;
    using pointer = ValueType*;
    using iterator_category = std::bidirectional_iterator_tag;
    using difference_type = std::ptrdiff_t;

    using Self = TreeNavigator<ValueType>;
    using BaseLink = TreeVertexBase::BaseLink;
    using DataLink = DataVertex<ValueType>*;

    TreeNavigator() noexcept = default;
    explicit TreeNavigator(DataLink x) noexcept : current(x) {}

    reference operator*() const noexcept {
        return *static_cast<DataLink>(current)->get_ptr();
    }

    pointer operator->() const noexcept {
        return static_cast<DataLink>(current)->get_ptr();
    }

    Self& operator++() noexcept {
        current = advance_forward(current);
        return *this;
    }

    Self operator++(int) noexcept {
        Self tmp = *this;
        current = advance_forward(current);
        return tmp;
    }

    Self& operator--() noexcept {
        current = advance_backward(current);
        return *this;
    }

    Self operator--(int) noexcept {
        Self tmp = *this;
        current = advance_backward(current);
        return tmp;
    }

    bool operator==(const Self& other) const noexcept { return current == other.current; }
    bool operator!=(const Self& other) const noexcept { return current != other.current; }

    BaseLink current;
};

Navigator Traversal Logic

Moving to the next logical node requires checking the right subtree first. If it exists, the next node is the leftmost child of that right subtree. Otherwise, the traversal moves upward until a node is reached that is the left child of its parent; the parent then becomes the next node. Decrementing follows inverse logic, with special handling for the header node.

TreeVertexBase* advance_forward(TreeVertexBase* node) {
    if (node->right_child != nullptr) {
        node = node->right_child;
        while (node->left_child != nullptr) node = node->left_child;
    } else {
        TreeVertexBase* ancestor = node->ancestor;
        while (node == ancestor->right_child) {
            node = ancestor;
            ancestor = ancestor->ancestor;
        }
        if (node->right_child != ancestor) node = ancestor;
    }
    return node;
}

TreeVertexBase* advance_backward(TreeVertexBase* node) {
    if (node->shade == NodeShade::Crimson && node->ancestor->ancestor == node) {
        node = node->right_child;
    } else if (node->left_child != nullptr) {
        TreeVertexBase* predecessor = node->left_child;
        while (predecessor->right_child != nullptr) predecessor = predecessor->right_child;
        node = predecessor;
    } else {
        TreeVertexBase* ancestor = node->ancestor;
        while (node == ancestor->left_child) {
            node = ancestor;
            ancestor = ancestor->ancestor;
        }
        node = ancestor;
    }
    return node;
}

Red-Black Tree Class Architecture

The main tree structure encapsulates the node management and provides the interface for insertion. The tree maintains a sentinel header node to simplify boundary conditions.

template <class KeyType, class ValueType, class KeyExtractor, class Comparator, class Allocator = std::allocator<ValueType>>
class BalancedSearchTree {
protected:
    using BaseLink = TreeVertexBase*;
    using DataNode = DataVertex<ValueType>;

public:
    using key_type = KeyType;
    using value_type = ValueType;
    using pointer = value_type*;
    using reference = value_type&;
    using size_type = size_t;
    using difference_type = ptrdiff_t;
    using navigator = TreeNavigator<value_type>;

    DataNode* sentinel_node;

    navigator begin() { return navigator(find_min(sentinel_node->left_child)); }
    navigator end() { return navigator(sentinel_node); }

    navigator insert_duplicate(const value_type& val);
    std::pair<navigator, bool> insert_distinct(const value_type& val);
};

The insert_duplicate method allows multiple nodes with identical keys. When traversing for insertion, if the key matches an existing node, the new node is placed in the right subtree of that existing node. Conversely, insert_distinct enforces key uniqueness; if the prospective parent node holds an identical key, the insertion is aborted.

The actual value stored within the tree is defined as std::pair<const KeyType, ValueType>, ensuring that the key remains immutable once the node is created.