with {| |- | ||colspan=2| |- |rowspan=2| ||rowspan=2;style="vertical-align:bot"| ||style="vertical-align:top"| || ||style="vertical-align:bot"| if even |- |style="vertical-align:top"| || ||style="vertical-align:bot"| if odd |} nodes ( is the floor function) and there is no red–black tree of this tree height with fewer nodes—therefore it is minimal.Its black height is (with black root) or for odd (then with a red root) also Proof For a red–black tree of a certain height to have minimal number of nodes, it must have exactly one longest path with maximal number of red nodes, to achieve a maximal tree height with a minimal black height. Besides this path all other nodes have to be black. If a node is taken off this tree it either loses height or some RB property. The RB tree of height with red root is minimal. This is in agreement with A minimal RB tree (RBh in figure 4) of height has a root whose two child subtrees are of different height. The higher child subtree is also a minimal RB tree, containing also a longest path that defines its height it has nodes and the black height The other subtree is a perfect binary tree of (black) height having black nodes—and no red node. Then the number of nodes is by induction The graph of the function is convex and piecewise linear with breakpoints at where The function has been tabulated as A027383(h–1) for Solving the function for The inequality leads to , which for odd leads to . So in both, the even and the odd case, is in the interval with being the number of nodes. Conclusion A red–black tree with nodes (keys) has tree height Set operations and bulk operations In addition to the single-element insert, delete and lookup operations, several set operations have been defined on union, intersection and set difference. Then fast bulk operations on insertions or deletions can be implemented based on these set functions. These set operations rely on two helper operations, Split and Join. With the new operations, the implementation of red–black trees can be more efficient and highly-parallelizable. In order to achieve its time complexities this implementation requires that the root is allowed to be either red or black, and that every node stores its own black height. Join: The function Join is on two red–black trees and and a key , where , i.e. all keys in are less than , and all