When this structure has n nodes, it has a maximum height of 2 times log of quantity n plus one, and these objects are balanced by either changing a flag bit or by rotating them.
The generating function for the number of these structures is recursively given by "x plus x-squared plus the same function of x-squared times quantity one plus x-squared." These structures are required to observe their four namesake rules, with the result that the longest path from the root to a (*) leaf is never more than twice as long as the shortest such path. When this structure has n nodes, it has a maximum height of 2 times log of quantity n plus one, and these objects are balanced by either changing a flag bit or by rotating them. Having a lookup time of order log of the number of nodes, like the B-tree and the AVL tree, for 10 points identify this data structure which takes its name from the fact that it uses an extra bit to "color" the nodes.
The generating function for the number of these structures is recursively given by "x plus x-squared plus the same function of x-squared times quantity one plus x-squared.
red-black tree [prompt on "(self-balancing) binary search tree"]