Computer Musings The Associative Law, or The Anatomy of Rotations in Binary Trees [por] Donald Knuth

Grabado en noviembre 30, 1993

Donald Knuth presenta una simple demostración del teorema de Tamari's : juego binario de árbol con n nudos que forman un entretejido en un solo sentido asociativo de ley. Es una consecuencia de la asociación de la ley (ab) c = a (bc), cualquiera de las dos opciones de la fórmula son iguales cuando la variable aparece en el mismo orden de izquierda a derecha, la única ley, asociativa (ab) - a (bc) puede ser construida con una reducción sencilla al lado derecho menos que al izquierdo. Después presenta una forma simple de código de arbol binario, Kunth determina una ordenación en los códigos. La rotación a la derecha del árbol incrementa su codificación con respecto a su ordenación, la relación de los códigos facilita la simple distribución del entretejido del árbol binario.