Implementation of a red-black tree container.
Convenience function for creating a RedBlackTree!E from a list of values.
Undocumented in source.
1 import std.algorithm.comparison : equal; 2 import std.container.rbtree; 3 4 auto rbt = redBlackTree(3, 1, 4, 2, 5); 5 assert(rbt.front == 1); 6 assert(equal(rbt[], [1, 2, 3, 4, 5])); 7 8 rbt.removeKey(1, 4); 9 assert(equal(rbt[], [2, 3, 5])); 10 11 rbt.removeFront(); 12 assert(equal(rbt[], [3, 5])); 13 14 rbt.insert([1, 2, 4]); 15 assert(equal(rbt[], [1, 2, 3, 4, 5])); 16 17 // Query bounds in O(log(n)) 18 assert(rbt.lowerBound(3).equal([1, 2])); 19 assert(rbt.equalRange(3).equal([3])); 20 assert(rbt.upperBound(3).equal([4, 5])); 21 22 // A Red Black tree with the highest element at front: 23 import std.range : iota; 24 auto maxTree = redBlackTree!"a > b"(iota(5)); 25 assert(equal(maxTree[], [4, 3, 2, 1, 0])); 26 27 // adding duplicates will not add them, but return 0 28 auto rbt2 = redBlackTree(1, 3); 29 assert(rbt2.insert(1) == 0); 30 assert(equal(rbt2[], [1, 3])); 31 assert(rbt2.insert(2) == 1); 32 33 // however you can allow duplicates 34 auto ubt = redBlackTree!true([0, 1, 0, 1]); 35 assert(equal(ubt[], [0, 0, 1, 1]));
Red-black tree code copyright (C) 2008- by Steven Schveighoffer. Other code copyright 2010- Andrei Alexandrescu. All rights reserved by the respective holders.
This module implements a red-black tree container.
This module is a submodule of std.container.