Prawy obrót
Obrót w prawo odnosi się do następujących
- W tablicy , przenosząc wszystkie elementy do następnej wyższej lokalizacji. Ostatni element jest przenoszony do pierwszego miejsca, które zostało zwolnione.
- W liście usunięcie ogona i wstawienie go na głowie .
- W kodzie maszynowym (i języku asemblera ) przesunięcie wszystkich bitów w rejestrze w prawo, przy czym skrajny prawy ( najmniej znaczący bit ) staje się najbardziej wysunięty na lewo.
Rotacja drzew
W drzewie wyszukiwania binarnego obrót w prawo to ruch węzła X w prawo. Ta rotacja zakłada, że X ma lewe dziecko (lub poddrzewo). Lewe dziecko X, R, staje się węzłem nadrzędnym X, a prawe dziecko R staje się nowym lewym dzieckiem X. Ten obrót ma na celu zrównoważenie drzewa; szczególnie, gdy lewe poddrzewo węzła X ma znacznie (w zależności od typu drzewa) większą wysokość niż jego prawe poddrzewo.
Obroty w prawo (i w lewo) zachowują kolejność w drzewie wyszukiwania binarnego ; zachowuje właściwość drzewa wyszukiwania binarnego ( przechodzenie po drzewie w kolejności da klucze węzłów we właściwej kolejności). Drzewa AVL i drzewa czerwono-czarne to dwa przykłady drzew wyszukiwania binarnego, które wykorzystują obrót w prawo.
Pojedynczy obrót w prawo jest wykonywany w czasie O(1), ale często jest zintegrowany z wstawianiem i usuwaniem węzłów binarnych drzew wyszukiwania . Rotacje są wykonywane w celu utrzymania kosztów innych metod i wysokości drzewa na minimalnym poziomie.
- Thomas H. Cormen , Charles E. Leiserson , Ronald L. Rivest i Clifford Stein , 16 lipca 2001, Wprowadzenie do algorytmów , wydanie drugie. McGraw-Hill, ISBN 0-07-013151-1 . Rozdział 13.