Template Class SearchTree

Nested Relationships

Nested Types

Class Documentation

template<std::totally_ordered K, class V, bool RB>
class SearchTree

a binary search tree, balanced as a Red-Black tree if RB

Public Types

using Key = K

the type of the keys

using Value = V

the type of the values

using value_type = std::pair<const K&, const V&>
using size_type = std::size_t
using difference_type = std::ptrdiff_t
using reference = value_type
using const_reference = value_type
using iterator = const_iterator

Public Functions

SearchTree(void)

an empty tree

SearchTree(const SearchTree &o)

a copy, node by node with the same shape, in O( n ) time

SearchTree(SearchTree &&o) noexcept
SearchTree &operator=(SearchTree o) noexcept
~SearchTree()
void swap(SearchTree &o) noexcept
std::optional<V> lookup(const K &k) const

the value of the key k, or nothing

void insert(const K &k, const V &v)

associates the value v to the key k

void remove(const K &k)

removes the key k, if present

bool contains(const K &k) const

true if the key k is present

std::size_t size(void) const
bool empty(void) const
void clear(void)

removes all the nodes

Link *root(void) const

The nodes can be walked as in the book: from root(), along the fields parent, left and right of a Link, until the leaf, isNil().

They must not be changed.

bool isNil(const Link *u) const

true if u is the sentinel leaf (or the parent of the root)

Link *lookupNode(const K &x) const

the node of the key x, nil if absent

Link *min(void) const

the node of the smallest key, nil if the tree is empty

Link *max(void) const

the node of the largest key, nil if the tree is empty

Link *successorNode(Link *t) const

successorNode(): the node of the next key, nil after the largest one and from nil

Pre:

t is not a null pointer

template<class F>
void forEach(F &&f) const

the foreach of the book: f( k , v ) on the pairs in increasing order of the keys, O( n ) time

Link *predecessorNode(Link *t) const

predecessorNode(): the node of the previous key, nil before the first one and from nil

Pre:

t is not a null pointer

inline const_iterator begin(void) const
inline const_iterator end(void) const
inline const_iterator cbegin(void) const
inline const_iterator cend(void) const

Public Static Functions

static const K &key(const Link *u)

the key of the node u

Pre:

u is a node, not the sentinel leaf, which has no key (only nil is checked, as a static function cannot know the sentinel)

static const V &value(const Link *u)

the value of the node u

Pre:

u is a node, not the sentinel leaf

class const_iterator

Public Types

using reference = std::pair<const K&, const V&>
using value_type = reference
using difference_type = std::ptrdiff_t
using iterator_concept = std::bidirectional_iterator_tag
using iterator_category = std::input_iterator_tag

Public Functions

const_iterator(void) = default
inline const_iterator(const SearchTree *t, Link *x)
inline reference operator*(void) const
inline const_iterator &operator++(void)
inline const_iterator &operator--(void)
inline const_iterator operator++(int)
inline const_iterator operator--(int)
inline bool operator==(const const_iterator &o) const
inline Link *node(void) const

the node, the sentinel at the end

struct Link

the links of a node; the sentinel leaf is a Link and nothing more

Subclassed by ADS::SearchTree< K, V, RB >::Node

Public Members

Link *parent

the parent

Link *left

the left child

Link *right

the right child

Color color = Color::BLACK

the color, read only if RB

struct Node : public ADS::SearchTree<K, V, RB>::Link

a node of the tree, with its key and its value

Public Members

K key

the key

V value

the value