In 2008, Sedgewick proposed the left-leaning red–black tree, leveraging Andersson's idea that simplified algorithms. Sedgewick originally allowed nodes whose two children are red, making his trees more like 2-3-4 trees, but later this restriction was added, making new trees more like 2-3 trees. Sedgewick implemented the insert algorithm in just 33 lines, significantly shortening his original 46 lines of code. A red–black tree is a special type of binary tree, used in computer science to organize pieces of comparable data, such as text fragments or numbers. The leaf nodes of red–black trees do not contain data. These leaves need not be explicit in computer memory—a null child pointer (like NIL in the figure "An example of a red–black tree" below) can encode the fact that this child is a leaf. However, in the description of this figure, the leaves are considered to be explicit nodes—a view which may simplify the description and the understanding of some algorithms for operating on red–black trees. Now, in order to save a marginal amount of execution time (see there), these NIL-leaves may be implemented as sentinel nodes (instead of null pointers). On the other hand, in order to save (main) memory, a single sentinel node (instead of many individuals) may perform the role of all leaf nodes: all references (pointers) from internal nodes to leaf nodes then point to this unique sentinel node. Red–black trees, like all binary search trees, allow efficient in-order traversal (that is: in the order Left–Root–Right) of their elements. The search-time results from the traversal from root to leaf, and therefore a balanced tree of "n" nodes, having the least possible tree height, results in search time. In addition to the requirements imposed on a binary search tree the following must be satisfied by a    The only constraint on the children of black nodes is (5). In particular, a black node (like a leaf node) can have a black parent; for example, every perfect binary tree that consists only of black nodes is a red-black tree. The black depth of a node is defined as the number of black nodes from the root to that node (i.e. the number of black ancestors). The black height of a red–black tree is the number of black nodes in any path from the root to the leaves, which, by property 5, is constant (alternatively, it could be defined as the black depth of any leaf node).