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
a local clone.
std.container.rbtree
This module implements a red-black tree container.
This module is a submodule of std.container.
Source std/container/rbtree.d
License:
Distributed under the Boost Software License, Version 1.0.
(See accompanying file LICENSE_1_0.txt or copy at boost.org/LICENSE_1_0.txt).
Authors:
Steven Schveighoffer, Andrei Alexandrescu
Examples:
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]));
- class
RedBlackTree
(T, alias less = "a < b", bool allowDuplicates = false) if (is(typeof(binaryFun!less(T.init, T.init)))); - Implementation of a red-black tree container.All inserts, removes, searches, and any function in general has complexity of Ο(lg(n)). To use a different comparison than "a < b", pass a different operator string that can be used by std.functional.binaryFun, or pass in a function, delegate, functor, or any type where less(a, b) results in a bool value. Note that less should produce a strict ordering. That is, for two unequal elements a and b, less(a, b) == !less(b, a). less(a, a) should always equal false. If allowDuplicates is set to true, then inserting the same element more than once continues to add more elements. If it is false, duplicate elements are ignored on insertion. If duplicates are allowed, then new elements are inserted after all existing duplicate elements.
- alias
Elem
= T; - Element type for the tree
- alias
Range
= RBRange!(RBNode*);
aliasConstRange
= RBRange!(const(RBNode)*);
aliasImmutableRange
= RBRange!(immutable(RBNode)*); - The range types for RedBlackTree
- const @property bool
empty
(); - Check if any elements exist in the container. Returns false if at least one element exists.
- const @property size_t
length
(); - Returns the number of elements in the container.
Complexity Ο(1).
- @property RedBlackTree
dup
(); - Duplicate this container. The resulting container contains a shallow copy of the elements.
Complexity Ο(n)
- Range
opSlice
();
const ConstRangeopSlice
();
immutable ImmutableRangeopSlice
(); - Fetch a range that spans all the elements in the container.
Complexity Ο(1)
- inout inout(Elem)
front
(); - The front element in the container
Complexity Ο(1)
- inout inout(Elem)
back
(); - The last element in the container
Complexity Ο(log(n))
- const bool
opBinaryRight
(string op)(Eleme
)
if (op == "in"); - in operator. Check to see if the given element exists in the container.
Complexity Ο(log(n))
- bool
opEquals
(Objectrhs
); - Compares two trees for equality.
Complexity Ο(n)
- nothrow @safe size_t
toHash
(); - Generates a hash for the tree. Note that with a custom comparison function it may not hold that if two rbtrees are equal, the hashes of the trees will be equal.
- void
clear
(); - Removes all elements from the container.
Complexity Ο(1)
- size_t
stableInsert
(Stuff)(Stuffstuff
)
if (isImplicitlyConvertible!(Stuff, Elem)); - Insert a single element in the container. Note that this does not invalidate any ranges currently iterating the container.Returns:The number of elements inserted.
Complexity Ο(log(n))
- size_t
stableInsert
(Stuff)(scope Stuffstuff
)
if (isInputRange!Stuff && isImplicitlyConvertible!(ElementType!Stuff, Elem));
aliasinsert
= stableInsert; - Insert a range of elements in the container. Note that this does not invalidate any ranges currently iterating the container.Returns:The number of elements inserted.
Complexity Ο(m * log(n))
- Elem
removeAny
(); - Remove an element from the container and return its value.
Complexity Ο(log(n))
- void
removeFront
(); - Remove the front element from the container.
Complexity Ο(log(n))
- void
removeBack
(); - Remove the back element from the container.
Complexity Ο(log(n))
- Range
remove
(Ranger
); - Removes the given range from the container.Returns:A range containing all of the elements that were after the given range.
Complexity Ο(m * log(n)) (where m is the number of elements in the range)
- Range
remove
(Take!Ranger
); - Removes the given Take!Range from the containerReturns:A range containing all of the elements that were after the given range.
Complexity Ο(m * log(n)) (where m is the number of elements in the range)
- size_t
removeKey
(U...)(Uelems
)
if (allSatisfy!(isImplicitlyConvertibleToElem, U));
size_tremoveKey
(U)(scope U[]elems
)
if (isImplicitlyConvertible!(U, Elem));
size_tremoveKey
(Stuff)(Stuffstuff
)
if (isInputRange!Stuff && isImplicitlyConvertible!(ElementType!Stuff, Elem) && !isDynamicArray!Stuff); - Removes elements from the container that are equal to the given values according to the less comparator. One element is removed for each value given which is in the container. If allowDuplicates is true, duplicates are removed only if duplicate values are given.Returns:The number of elements removed.
Complexity Ο(m log(n)) (where m is the number of elements to remove)
Example
auto rbt = redBlackTree!true(0, 1, 1, 1, 4, 5, 7); rbt.removeKey(1, 4, 7); assert(equal(rbt[], [0, 1, 1, 5])); rbt.removeKey(1, 1, 0); assert(equal(rbt[], [5]));
- Range
upperBound
(Eleme
);
const ConstRangeupperBound
(Eleme
);
immutable ImmutableRangeupperBound
(Eleme
); - Get a range from the container with all elements that are > e according to the less comparator
Complexity Ο(log(n))
- Range
lowerBound
(Eleme
);
const ConstRangelowerBound
(Eleme
);
immutable ImmutableRangelowerBound
(Eleme
); - Get a range from the container with all elements that are < e according to the less comparator
Complexity Ο(log(n))
- auto
equalRange
(this This)(Eleme
); - Get a range from the container with all elements that are == e according to the less comparator
Complexity Ο(log(n))
- const void
toString
(scope void delegate(const(char)[])sink
, ref scope const FormatSpec!charfmt
); - Formats the RedBlackTree into a sink function. For more info see std.format.formatValue. Note that this only is available when the element type can be formatted. Otherwise, the default toString from Object is used.
- this(Elem[]
elems
...); - Constructor. Pass in an array of elements, or individual elements to initialize the tree with.
- this(Stuff)(Stuff
stuff
)
if (isInputRange!Stuff && isImplicitlyConvertible!(ElementType!Stuff, Elem)); - Constructor. Pass in a range of elements to initialize the tree with.
- this();
- auto
redBlackTree
(E)(E[]elems
...);
autoredBlackTree
(bool allowDuplicates, E)(E[]elems
...);
autoredBlackTree
(alias less, E)(E[]elems
...)
if (is(typeof(binaryFun!less(E.init, E.init))));
autoredBlackTree
(alias less, bool allowDuplicates, E)(E[]elems
...)
if (is(typeof(binaryFun!less(E.init, E.init))));
autoredBlackTree
(Stuff)(Stuffrange
)
if (isInputRange!Stuff && !isArray!Stuff);
autoredBlackTree
(bool allowDuplicates, Stuff)(Stuffrange
)
if (isInputRange!Stuff && !isArray!Stuff);
autoredBlackTree
(alias less, Stuff)(Stuffrange
)
if (is(typeof(binaryFun!less((ElementType!Stuff).init, (ElementType!Stuff).init))) && isInputRange!Stuff && !isArray!Stuff);
autoredBlackTree
(alias less, bool allowDuplicates, Stuff)(Stuffrange
)
if (is(typeof(binaryFun!less((ElementType!Stuff).init, (ElementType!Stuff).init))) && isInputRange!Stuff && !isArray!Stuff); - Convenience function for creating a RedBlackTree!E from a list of values.Parameters:
allowDuplicates Whether duplicates should be allowed (optional, default: false) less predicate to sort by (optional) E[] elems
elements to insert into the rbtree (variadic arguments) Stuff range
range elements to insert into the rbtree (alternative to elems) Examples:import std.range : iota; auto rbt1 = redBlackTree(0, 1, 5, 7); auto rbt2 = redBlackTree!string("hello", "world"); auto rbt3 = redBlackTree!true(0, 1, 5, 7, 5); auto rbt4 = redBlackTree!"a > b"(0, 1, 5, 7); auto rbt5 = redBlackTree!("a > b", true)(0.1, 1.3, 5.9, 7.2, 5.9); // also works with ranges auto rbt6 = redBlackTree(iota(3)); auto rbt7 = redBlackTree!true(iota(3)); auto rbt8 = redBlackTree!"a > b"(iota(3)); auto rbt9 = redBlackTree!("a > b", true)(iota(3));
Copyright © 1999-2022 by the D Language Foundation | Page generated by
Ddoc on (no date time)