AVL 트리 회전 계산기

균형이 무너진 노드의 균형인수와 그 자식의 균형인수 부호로 가릅니다. 무너진 노드가 +2(왼쪽이 무거움)이고 왼자식도 왼쪽으로 기울었으면 LL이라 오른쪽 회전 한 번, 왼자식이 오른쪽으로 기울었으면 LR이라 왼쪽·오른쪽 두 번입니다. −2일 때는 대칭으로 RR과 RL이 됩니다. 이름의 두 글자는 새 노드가 어느 쪽 손자 자리로 들어갔는지를 읽은 것입니다.

넣은 자리에서 위로 올라가며 처음 만나는, 균형인수가 ±2가 된 노드에서 합니다. 가장 아래에 있는 무너진 조상이라고도 합니다. 그보다 위쪽은 아직 확인하지 않아도 되는데, 여기서 고치면 그 부분나무의 높이가 넣기 전과 같아져 위로 번지지 않기 때문입니다. 그래서 삽입 한 번에 회전은 많아야 한 번입니다.

한 번으로는 지그재그 모양이 펴지지 않기 때문입니다. LR은 왼쪽으로 갔다가 오른쪽으로 꺾인 모양이라, 먼저 왼자식을 왼쪽으로 돌려 LL 모양으로 바꾼 뒤 오른쪽 회전을 합니다. 결과적으로 가운데 있던 손자가 그 자리의 뿌리로 올라옵니다.

달라집니다. 1 2 3 4 5를 차례로 넣은 트리와 3 1 4 2 5를 넣은 트리는 담긴 값이 같아도 모양이 다릅니다. 다만 어느 순서로 넣든 균형 조건은 지켜지므로 높이는 언제나 1.44·log₂n 안쪽에 머뭅니다. 중위 순회는 어느 쪽이든 오름차순입니다.

정의가 두 가지라서 그렇습니다. 이 계산기는 「왼쪽 높이 − 오른쪽 높이」로 두어 왼쪽이 무거우면 양수입니다. 반대로 「오른쪽 − 왼쪽」으로 두는 자료도 흔하며, 그때는 부호가 뒤집힐 뿐 어느 쪽이 무거운지는 같습니다. 높이는 간선 수로 세어 잎이 0, 빈 나무가 −1입니다.

아닙니다. 삭제는 회전이 뿌리까지 이어질 수 있습니다. 지운 자리의 부분나무 높이가 줄어들면 그 위 조상도 무너질 수 있어, 올라가며 여러 번 고쳐야 합니다. 이 계산기는 삽입만 다룹니다.

전송되지 않습니다. 모든 계산은 브라우저 안에서 이뤄지고, 입력값은 이 기기에만 남습니다.