this far apart as soon as n is sufficiently large. Lionel Pournin showed that, in fact, such pairs exist whenever n ≥ 11. See also AVL tree, red–black tree, and splay tree, kinds of binary search tree data structures that use rotations to maintain balance. Associativity of a binary operation means that performing a tree rotation on it does not change the final result. The Day–Stout–Warren algorithm balances an unbalanced BST. Tamari lattice, a partially ordered set in which the elements can be defined as binary trees and the ordering between elements is defined by tree rotation. References External links The AVL Tree Rotations Tutorial (RTF) by John Hargrove Binary trees Search trees de:Binärbaum#Rotation