좌회전

좌측 회전은 다음을 가리킨다.

• 배열에서 모든 항목을 다음 낮은 위치로 이동.첫 번째 항목은 현재 비어 있는 마지막 위치로 이동한다.
• 리스트에서, 머리를 제거하고 꼬리에 삽입한다.
• 기계 코드(및 어셈블리 언어)에서 레지스터의 모든 비트를 왼쪽으로 이동시키고, 가장 왼쪽(가장 중요한 비트)이 가장 오른쪽이 된다.

나무 회전

이진 검색 트리에서 왼쪽 회전은 노드 X가 왼쪽으로 이동하는 것이다.이 회전은 X가 올바른 아이(또는 하위 트리)를 가지고 있다고 가정한다.X의 오른쪽 아이 R은 X의 부모 노드가 되고, R의 왼쪽 아이는 X의 새로운 오른쪽 아이가 된다.이 회전은 나무의 균형을 맞추기 위해 이루어진다. 특히 노드 X의 오른쪽 하위 트리가 왼쪽 하위 트리보다 상당히 큰 (나무 유형에 따라 다름) 높이를 갖는 경우.

왼쪽 회전(및 오른쪽)은 이진 검색 트리에 보존하는 순서로서, 이진 검색 트리 속성을 보존한다(트리의 순서 내 통과는 노드의 키를 적절한 순서로 산출한다).AVL 트리와 빨간색-검은색 트리는 왼쪽 회전을 사용하는 바이너리 검색 트리의 두 가지 예다.

단일 좌측 회전은 O(1) 시간에 이루어지지만 종종 이진 검색 트리의 삽입 및 삭제 노드에 통합된다.회전은 다른 방법의 비용과 나무 높이를 최소한으로 유지하기 위해 이루어진다.

참조

• 토마스 H. 코멘, 찰스 E. Leiserson, Ronald L. Rivest, 그리고 Clifford Stein, 2001년 7월 16일, 알고리즘 소개, 제2판.맥그로힐 ISBN0-07-013151-1.13장.