std.container.rbtree

This module implements a red-black tree container.

This module is a submodule of std.container.

Public Imports

std.container.util
public import std.container.util;
Undocumented in source.

Members

Classes

RedBlackTree
class RedBlackTree(T, alias less = "a < b", bool allowDuplicates = false)

Implementation of a red-black tree container.

Functions

redBlackTree
auto redBlackTree(E[] elems)
auto redBlackTree(Stuff range)

Convenience function for creating a RedBlackTree!E from a list of values.

Structs

RBNode
struct RBNode(V)
Undocumented in source.

Examples

import std.algorithm.comparison : equal;
import std.container.rbtree;

auto rbt = redBlackTree(3, 1, 4, 2, 5);
assert(rbt.front == 1);
assert(equal(rbt[], [1, 2, 3, 4, 5]));

rbt.removeKey(1, 4);
assert(equal(rbt[], [2, 3, 5]));

rbt.removeFront();
assert(equal(rbt[], [3, 5]));

rbt.insert([1, 2, 4]);
assert(equal(rbt[], [1, 2, 3, 4, 5]));

// Query bounds in O(log(n))
assert(rbt.lowerBound(3).equal([1, 2]));
assert(rbt.equalRange(3).equal([3]));
assert(rbt.upperBound(3).equal([4, 5]));

// A Red Black tree with the highest element at front:
import std.range : iota;
auto maxTree = redBlackTree!"a > b"(iota(5));
assert(equal(maxTree[], [4, 3, 2, 1, 0]));

// adding duplicates will not add them, but return 0
auto rbt2 = redBlackTree(1, 3);
assert(rbt2.insert(1) == 0);
assert(equal(rbt2[], [1, 3]));
assert(rbt2.insert(2) == 1);

// however you can allow duplicates
auto ubt = redBlackTree!true([0, 1, 0, 1]);
assert(equal(ubt[], [0, 0, 1, 1]));

Meta

License

Distributed under the Boost Software License, Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at ).

Authors

Steven Schveighoffer, Andrei Alexandrescu