Proving the namesake property in one of these data structures relies on the Dynamic Finger Conjecture, and data structures without their characteristic property can obtain it by running an algorithm named for Day, Stout and Warren.  In one of these data structures, their characteristic property is m
Proving the namesake property in one of these data structures relies on the Dynamic Finger Conjecture, and data structures without their characteristic property can obtain it by running an algorithm named for Day, Stout and Warren.  In one of these data structures, their characteristic property is maintained through operations like a zig-zag during searches.  Because they are often difficult to implement, skip lists are sometimes used instead.  Data structures without this property are called degenerate and approximate linked lists.  Some of these data structures impose requirements that all nodes and leaves be the same color.  Exemplified by AVL and Red-Black Trees, for 10 points, name these special types of binary search trees that often perform tree rotations to guarantee tree heights of at most log n.
Proving the namesake property in one of these data structures relies on the Dynamic Finger Conjecture, and data structures without their characteristic property can obtain it by running an algorithm named for Day, Stout and Warren.  
Self-Balanced Binary Search Tree (or Self-Balancing Binary Search Tree or Height-Balanced Binary Search Tree; prompt on "Tree", "Binary Tree" or "Binary Search Tree")