Levá rotace

Technology

12 hours ago

Author

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

vpravo V binárním vyhledávacím stromě je levá rotace pohyb uzlu (P) dolů vlevo. +more 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. +more Rotace se provádějí proto, aby byla udržena optimální (minimální) hloubka stromu a k udržení vlastností stromu.