초안아직 검토하지 않은 글이라 틀린 곳이 있을 수 있습니다.
회원 번호나 가입 시각처럼 커지는 순서로 들어오는 값은 흔합니다. 이런 값을 이진 탐색 트리에 차례로 넣으면 한 줄로 늘어서 찾기가 O(n)이 됩니다. 넣는 순서를 고를 수 없다면, 넣은 뒤에 모양을 고쳐 층 수를 낮출 수는 없을까요?
1, 2, 3이 한 줄로 늘어선 트리에서 2를 루트로 올리면 1은 왼쪽, 3은 오른쪽 자식이 됩니다. 왼쪽부터 읽은 순서는 그대로 1, 2, 3이라 이진 탐색 트리 규칙이 지켜지고, 층 수는 3에서 2로 줄었습니다.
이처럼 노드 하나를 부모 자리로 올리고 부모를 그 아래로 내리는 일을 회전(rotation)이라 합니다. 왼쪽 자식 x를 부모 p 자리로 올리면 p는 x의 오른쪽 자식이 되고, 원래 x의 오른쪽 서브트리는 p의 왼쪽으로 옮겨 갑니다. 그 값들은 x보다 크고 p보다 작으니 자리가 맞습니다. 오른쪽 자식을 올릴 때는 좌우를 바꿉니다. 포인터는 세 개만 고칩니다.
층 수 7
노드를 누르면 그 노드를 부모 자리로 올립니다. 회전만으로 층 수를 3까지 낮춰 봅시다.
몇 번을 회전해도 왼쪽부터 읽은 순서는 바뀌지 않습니다.
그럼 언제 회전할까요? 1962년 아델슨벨스키(Adelson-Velsky)와 란디스(Landis)가 내놓은 AVL 트리는 규칙 하나를 지킵니다. 모든 노드에서 왼쪽과 오른쪽 서브트리의 층 수 차이가 1 이하입니다. 빈 서브트리는 0층으로 칩니다.
넣는 방법은 이진 탐색 트리와 같습니다. 넣은 뒤 새 노드에서 루트 쪽으로 올라가며 층 수 차이가 2가 된 노드를 찾으면, 그 노드의 높은 쪽 자식을 올립니다. 새 노드가 그 자식의 안쪽으로 꺾여 들어갔다면 대신 그 안쪽 손자를 두 번 올립니다. 3, 1, 2 순서로 넣으면 3에서 차이가 2가 되는데, 1을 올리면 이번엔 1에서 반대로 치우칩니다. 1의 안쪽에 있는 2를 두 번 올려야 2가 루트가 됩니다.
아직 넣은 값이 없습니다.
1부터 15까지 차례로 넣습니다. 하이라이트된 노드가 방금 넣은 값, 굵은 테두리가 회전으로 올라간 값입니다.
그냥 이진 탐색 트리는 15층이 되지만 AVL 트리는 4층입니다. 이 규칙만 지키면
노드가 100만 개여도 28층을 넘지 않아, 찾기와 넣기가 모두 O(log n)입니다. 실제
라이브러리는 비슷한 생각의 레드-블랙 트리를 많이 씁니다. 자바의 TreeMap이
그렇습니다.
AVL 트리의 규칙을 지키면서 층 수가 7인 트리를 만들려고 합니다. 노드는 적어도 몇 개 있어야 할까요? 숫자로 답하세요.