View source code
Display the source code in std/container/rbtree.d from which this
page was generated on github.
Report a bug
If you spot a problem with this page, click here to create a
Bugzilla issue.
Improve this page
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
.
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 ).
Copyright © 1999-2022 by the D Language Foundation | Page generated by ddox.