On average, the basic operations on a randomly built example of these structures can be done in big theta of log n time.
The number of different "full" examples of these structures with n internal vertices is the nth Catalan number. An example of these structures with good amortized properties uses zig, zig-zig, and zig-zag operations. Rotation of these structures maintains their balance, a concept introduced by Evgenii Landis and Georgii Adelson-Velskii. On average, the basic operations on a randomly built example of these structures can be done in big theta of log n time. A balanced example of these structures maintains its properties using the red or black property of each node. The "search" type of these structures has le᥸ and right subnodes that, respectively, have a lesser and greater value than the parent node. For 10 points, what structure has at most two children at every node?
The number of different "full" examples of these structures with n internal vertices is the nth Catalan number.
binary tree [or self-adjusting binary search tree; or self-balancing binary search tree; or BST; or splay trees; or AVL trees; or red-black trees; accept rooted tree or ordered tree or plane tree or k-ary tree before "zig"; prompt on "tree"; do not accept or prompt on answers that do not mention "tree"]