Red Black Tree¶

1

import "std/data/red-black-tree";

RedBlackTree<K, V> struct¶

Implements: IIterable<Pair<K, V>>

A Red-Black Tree is a self-balancing search tree, which is used e.g. in the implementation of maps.

Time complexity:
Insert: O(log n)
Delete: O(log n)
Lookup: O(log n)

Methods¶

insert¶

1

public p RedBlackTree.insert(const K& key, const V& value)

Insert a new key-value pair into the tree.

Parameters

upsert¶

1

public p RedBlackTree.upsert(const K& key, const V& value)

Upsert a key-value pair into the tree. If the key already exists, update its value. Otherwise, insert a new key-value pair.

Parameters

remove¶

1

public p RedBlackTree.remove(const K& key)

Remove an element from the tree. If the key is not found, this method is a noop.

Parameters

find¶

1

public f<V&> RedBlackTree.find(const K& key)

Find the value for a given key. Note: If the key is not found in the tree, this function will panic. To avoid this, use findSafe instead.

Parameters

Returns: V& — The value for the given key

findSafe¶

1

public f<Result<V>> RedBlackTree.findSafe(const K& key)

Find the value for a given key.

Parameters

Returns: Result<V> — The value for the given key, or an error if the key was not found

contains¶

1

public f<bool> RedBlackTree.contains(const K& key)

Check if the tree contains a given key.

Parameters

Returns: bool — True if the key was found, false otherwise

getSize¶

1

public f<unsigned long> RedBlackTree.getSize()

Get the number of elements in the tree.

Returns: unsigned long — The number of elements in the tree

isEmpty¶

1

public f<bool> RedBlackTree.isEmpty()

Check if the tree is empty.

Returns: bool — True if the tree is empty, false otherwise

clear¶

1

public p RedBlackTree.clear()

Clear all elements from the tree.

getIterator¶

1

public f<RedBlackTreeIterator<K, V>> RedBlackTree.getIterator()

Retrieve a forward iterator for the red black tree

Returns: RedBlackTreeIterator<K, V>

RedBlackTreeIterator<K, V> struct¶

Implements: IIterator<Pair<const K&, V&>>

Iterator to iterate over a red black tree data structure

Constructors¶

ctor¶

1

public p RedBlackTreeIterator.ctor<K, V>(RedBlackTree<K, V>& tree)

Construct a red-black tree iterator over the given tree, starting at its minimum key

Parameters

Methods¶

get¶

1

public inline f<Pair<const K&, V&>&> RedBlackTreeIterator.get()

Returns the current key-value pair of the red black tree

Returns: Pair<const K&, V&>& — Current key/value pair

getIdx¶

1

public inline f<Pair<unsigned long, Pair<const K&, V&>&>> RedBlackTreeIterator.getIdx()

Returns the current index and the current item of the red black tree

Returns: Pair<unsigned long, Pair<const K&, V&>&> — Pair of current index and current key/value pair

isValid¶

1

public inline f<bool> RedBlackTreeIterator.isValid()

Check if the iterator is valid

Returns: bool — true or false

next¶

1

public inline p RedBlackTreeIterator.next()

Moves the cursor to the next key/value pair