Levá rotace

Levá rotace označuje následující akce:

• v poli: přesun všech prvků o jednu pozici vlevo (na nižší index). První prvek, který „přeteče“ se přemístí na poslední pozici pole. Stejný postup lze aplikovat na libovolný vektor.
• v seznamu: přesunutí prvku ze začátku na konec.
• v binárním vyhledávacím stromě lokální změna struktury, viz dále

Rotace stromu

V binárním vyhledávacím stromě je levá rotace pohyb uzlu (P) dolů vlevo. Při této rotaci se očekává, že (P) má pravého potomka (či podstrom). Ten (Q) se stane rodičem uzlu (P) a jeho levý potomek (B) se stane pravým potomkem uzlu (P). Tato rotace se vykonává, aby se vyvážil strom, obzvlášť když má pravý podstrom stromu výrazněji větší hloubku (záleží na typu stromu).

Levé (i pravé) rotace zachovávají vlastnosti standardního binárního vyhledávacího stromu. AVL a Red-black stromy jsou dvěma příklady použití levých rotací.

Jedna rotace má algoritmickou složitost O(1). Většinou je vykonávána v rámci vkládání či odebírání uzlu ve stromu, kde potom záleží na jeho implementaci, kolik rotací se provede. Rotace se provádějí proto, aby byla udržena optimální (minimální) hloubka stromu a k udržení vlastností stromu.

Odkazy

Reference

V tomto článku byl použit překlad textu z článku Left rotation na anglické Wikipedii.

Literatura

• Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein, 2001, Introduction to Algorithms, druhé vydání. McGraw-Hill, ISBN 0-07-013151-1. 13. kapitola