Display the source code in std/container/rbtree.d from which this page was generated on github.

If you spot a problem with this page, click here to create a Bugzilla issue.

Quickly fork, edit online, and submit a pull request for this page. Requires a signed-in GitHub account. This works well for small changes. If you'd like to make larger changes you may want to consider using local clone.

Module `std.container.rbtree`

This module implements a red-black tree container.

This module is a submodule of std.container.

Example

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

auto rbt = redBlackTree(3, 1, 4, 2, 5);
writeln(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);
writeln(rbt2.insert(1)); // 0
assert(equal(rbt2[], [1, 3]));
writeln(rbt2.insert(2)); // 1

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

Functions

Name	Description
`redBlackTree()`	Convenience function for creating a `RedBlackTree!E` from a list of values.

Classes

Name	Description
`RedBlackTree`	Implementation of a red-black tree container.

Authors

Steven Schveighoffer, Andrei Alexandrescu

License

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