Pravá rotace - Right rotation

Pravá rotace odkazuje na následující

• V pole, přesunutí všech položek na nejbližší vyšší umístění. Poslední položka je přesunuta na první místo, které bylo uvolněno.
• V seznam, odstranění ocas a vložením do hlava.
• v strojový kód (a montážní jazyk ) přesunutí všech bitů v registru doprava, zcela doprava (nejméně významný bit ) stát se úplně vlevo.

Střídání stromů

V binární vyhledávací strom, pravá rotace je pohyb uzlu, X, dolů doprava. Tato rotace předpokládá, že X má levé dítě (nebo podstrom). Levé dítě X, R, se stane rodičovským uzlem X a pravé dítě R se stane novým levým dítětem X. Tato rotace se provádí za účelem vyvážení stromu; konkrétně když má levý podstrom uzlu X výrazně (v závislosti na typu stromu) větší výšku než pravý podstrom.

Pravé otáčení (a levé) jsou zachování objednávky v binární vyhledávací strom; zachovává vlastnost binárního vyhledávacího stromu (an in-order traversal stromu získá klíče uzlů ve správném pořadí). AVL stromy a červeno-černé stromy jsou dva příklady binárních vyhledávacích stromů, které používají pravou rotaci.

Jedna pravá rotace se provádí v čase O (1), ale je často integrována do vkládání a mazání uzlů binární vyhledávací stromy. Otáčení se provádí, aby se minimalizovaly náklady na další metody a výška stromu.

Reference

• Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, a Clifford Stein, 16. července 2001, Úvod do algoritmů, druhé vydání. McGraw-Hill, ISBN  0-07-013151-1. Kapitola 13.