Rotace doleva - Left rotation

Rotace doleva odkazuje na následující

• V pole, přesunutí všech položek na další nižší umístění. První položka se přesune na poslední místo, které je nyní prázdné.
• V seznam, odstranění hlava a vložením do ocas.
• v strojový kód (a montážní jazyk ) přesunutí všech bitů v registru doleva, přičemž nejvíce vlevo (nejvýznamnější bit ) stát se úplně vpravo.

Střídání stromů

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

Levé rotace (a pravé) 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í rotaci doleva.

Jediná rotace vlevo 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.