트리 균형

트리 균형은 트리에서 값을 찾을 때 내려가는 단계 수를 적게 묶어 둡니다. 값이 왼쪽과 오른쪽에 고르게 퍼져 트리가 아래로 길게 늘어지지 않은 상태입니다. 균형이 깨진 트리는 한 줄로 늘어섭니다. 그러면 찾는 시간이 데이터 수만큼 늘어납니다.

쉽고 빠른 이해

트리 균형은 트리가 한쪽으로 기울지 않은 상태입니다. 균형을 지킨 트리는 값 백만 개를 담아도 스무 번 남짓 내려가면 어느 값에든 닿습니다.

균형을 안 지키면 값을 넣는 순서가 트리의 모양을 정합니다. 작은 값부터 차례로 넣으면 트리가 한 줄로 늘어섭니다. 그러면 찾을 때 처음부터 하나씩 훑는 것과 같아집니다.

1. 노드마다 그 아래 왼쪽 가지와 오른쪽 가지가 몇 층까지 뻗었는지 견줍니다
2. 값을 넣거나 지운 뒤 그 차이가 정해 둔 한도를 넘었는지 봅니다
3. 넘었으면 노드 몇 개의 연결을 바꿔 다시 고르게 세웁니다

대가는 넣고 지울 때마다 이 확인과 손질이 붙는다는 것입니다. 노드마다 아래로 몇 층인지 같은 정보를 적어 둘 칸도 더 듭니다.

값을 자주 넣고 지우는 데이터를 크기 순서대로 훑거나 범위로 찾아야 할 때 균형을 지키는 트리를 고릅니다. 값이 똑같은지로만 찾는다면 해시 테이블이 더 낫습니다.

상세

이 절은 트리의 높이가 왜 비용을 정하는지부터 봅니다. 1 부터 7 까지 일곱 값을 두 가지 모양으로 담아 견줍니다.

그다음 균형이 무엇을 뜻하는지, 왜 깨지는지, 트리마다 균형을 어떤 기준으로 재는지 봅니다. 마지막으로 깨진 균형을 되찾는 방법과 그 대가를 짚습니다.

회사의 결재 줄을 떠올려 봅시다. 직원 백 명이 한 줄로 늘어선 회사라면 맨 끝 직원의 서류는 아흔아홉 명을 거쳐야 사장에게 닿습니다. 사장 아래 팀장 몇, 팀장 아래 팀원 몇으로 고르게 나눈 회사라면 두세 단계면 닿습니다. 사람 수는 같은데 줄을 어떻게 세웠느냐가 거치는 단계를 정합니다.

높이가 정하는 비용

트리는 값을 위아래로 이어 담는 구조입니다. 값을 담은 상자 하나하나를 노드라고 부릅니다.

한 노드 바로 아래 달린 노드를 그 노드의 자식이라고 부릅니다. 거꾸로 바로 위 노드는 부모입니다. 결재 줄로 치면 팀장이 부모, 그 아래 팀원이 자식입니다.

맨 위에서 부모가 없는 노드를 루트라고 부릅니다. 자식이 하나도 없는 노드는 잎입니다.

노드마다 자식을 둘까지 두는 트리를 이진 트리라고 부릅니다. 두 자식은 왼쪽 자식과 오른쪽 자식으로 갈립니다.

이진 탐색 트리는 이진 트리에 크기 규칙을 하나 더합니다. 어느 노드에서 봐도 왼쪽 아래에는 더 작은 값을, 오른쪽 아래에는 더 큰 값을 둡니다. 이 규칙 덕분에 값을 찾을 때 한쪽 길만 따라 내려가면 됩니다.

찾기는 루트에서 출발합니다. 찾는 값이 지금 노드보다 작으면 왼쪽으로, 크면 오른쪽으로 한 층 내려갑니다. 한 층마다 비교가 한 번 듭니다. 그래서 비교 횟수는 내려간 층 수와 같습니다.

값을 넣거나 지울 때도 먼저 그 값이 들어갈 위치를 찾아 내려갑니다. 그래서 넣기와 지우기도 찾기와 같은 길을 밟습니다.

루트에서 가장 먼 잎까지 거치는 노드 수를 트리 높이라고 부릅니다. 높이가 3 이면 어느 값을 찾든 세 번 안에 비교가 끝납니다. 트리에서 찾기·넣기·지우기에 드는 시간은 이 높이가 정합니다.

같은 값을 담은 두 모양

1 부터 7 까지 일곱 값을 이진 탐색 트리에 넣어 봅니다. 넣는 순서만 바꿔도 모양이 크게 달라집니다.

먼저 1, 2, 3 처럼 작은 값부터 차례로 넣습니다. 새 값은 늘 지금까지 들어온 가장 큰 값보다 큽니다. 그래서 매번 맨 아래 노드의 오른쪽에 매달립니다.

flowchart TD
    subgraph 한줄["작은 값부터 넣은 트리 · 높이 7"]
        S1["1"] -->|오른쪽| S2["2"] -->|오른쪽| S3["3"] -->|오른쪽| S4["4"]
        S4 -->|오른쪽| S5["5"] -->|오른쪽| S6["6"] -->|오른쪽| S7["7"]
    end

이 트리에서 7 을 찾으려면 일곱 노드를 모두 거칩니다. 값이 n 개면 n 번 비교합니다. 값을 줄지어 이어 놓고 처음부터 훑는 연결 리스트와 다를 것이 없습니다.

이번에는 4, 2, 6, 1, 3, 5, 7 순서로 넣습니다. 가운데 값 4 가 먼저 들어가 맨 위에 섭니다. 그보다 작은 값은 왼쪽으로, 큰 값은 오른쪽으로 갈립니다.

flowchart TD
    subgraph 고름["가운데 값부터 넣은 트리 · 높이 3"]
        B4["4"] --> B2["2"]
        B4 --> B6["6"]
        B2 --> B1["1"]
        B2 --> B3["3"]
        B6 --> B5["5"]
        B6 --> B7["7"]
    end

이 트리에서는 어느 값이든 세 번 안에 찾습니다. 담은 값은 똑같이 일곱 개입니다. 두 트리를 가르는 것은 노드가 양쪽으로 고르게 퍼졌느냐 하나입니다. 이렇게 고르게 퍼져 높이가 낮게 묶인 상태를 트리 균형이라고 부릅니다.

층마다 두 배로 느는 노드

고르게 퍼진 트리가 왜 이렇게 낮은지는 층마다 노드 수를 세어 보면 보입니다. 앞 그림에서 맨 위 층에는 노드가 하나, 둘째 층에는 둘, 셋째 층에는 넷입니다. 노드마다 자식을 둘까지 두니 한 층 내려갈 때마다 두 배씩 늡니다.

아래 표는 층을 꽉 채운 트리가 높이별로 노드를 몇 개 담는지 보입니다. 오른쪽 칸은 같은 수의 노드를 한 줄로 늘어놓았을 때의 높이입니다.

높이가 열 층 늘 때마다 담는 노드는 천 배쯤 늡니다. 백만 개 남짓을 담아도 스무 층이면 됩니다. 한 줄로 세우면 같은 백만 개가 백만 층이 됩니다.

거꾸로 말하면 값 n 개를 고르게 담은 트리의 높이는 「2 를 몇 번 곱하면 n 이 되나」 정도입니다. 이 횟수를 밑이 2 인 로그라고 부릅니다. 적을 때는 log₂ n 으로 씁니다. 값이 두 배로 늘어도 높이는 한 층만 늡니다.

데이터 양 n 이 늘 때 걸리는 시간이 얼마나 빨리 느는지를 적는 방법이 빅오 표기법입니다. 한 줄로 늘어선 트리에서 찾기는 O(n), 고르게 퍼진 트리에서는 O(log n) 으로 적습니다. 앞은 데이터가 두 배면 시간도 두 배입니다. 뒤는 한 단계만 늡니다.

균형의 뜻

층을 꽉 채운 모양만 균형이라고 부르면 쓸모가 없습니다. 그런 모양은 노드 수가 7, 15, 31 처럼 2 의 거듭제곱보다 하나 적을 때만 나옵니다. 노드 하나만 더 넣어도 바로 깨집니다.

그래서 트리 균형이 말하는 「고르게 퍼진 상태」는 꽉 찬 모양보다 느슨합니다. 노드가 n 개일 때 높이가 늘 log n 의 몇 배 안쪽에 묶여 있으면 그 트리를 균형 잡혔다고 부릅니다. 높이가 log n 의 두 배여도 찾는 시간은 여전히 O(log n) 입니다.

반대로 높이가 n 에 비례해 길어질 수 있으면 균형이 없는 트리입니다. 한쪽으로 쏠린 그런 트리를 편향 이진 트리라고 부릅니다. 앞의 한 줄짜리 트리가 그 끝입니다.

균형이 깨지는 까닭

아무 손질도 안 하는 이진 탐색 트리는 넣는 순서가 곧 모양입니다. 값이 들어오는 순서는 트리가 고를 수 없습니다.

작은 값부터 차례로 들어오는 데이터는 드물지 않습니다. 1 씩 늘어나는 회원 번호, 시간 순서로 쌓이는 주문 기록, 미리 정렬해 둔 파일이 다 그렇습니다. 손질 없는 트리에 이런 값을 넣으면 앞에서 본 한 줄 모양이 됩니다.

값이 무작위 순서로 들어오면 평균으로는 높이가 log n 쪽에 머뭅니다. 하지만 평균일 뿐 보장은 아닙니다. 들어오는 순서가 한 번 나쁘면 그 트리는 계속 느립니다.

그래서 값을 넣고 지울 때마다 스스로 모양을 손봐 균형을 지키는 트리가 따로 있습니다. 이런 트리를 자가 균형 트리라고 부릅니다. 넣는 순서가 어떻든 높이를 log n 의 몇 배 안쪽에 붙잡아 둡니다.

균형을 재는 기준

자가 균형 트리마다 「기울었다」고 보는 기준이 다릅니다. 목적은 같습니다. 높이를 log n 쪽에 붙잡는 것입니다.

기준을 보기 전에 낱말 둘을 짚습니다. 한 노드 아래에 딸린 노드를 모두 묶은 것을 서브트리라고 부릅니다. 왼쪽 자식 아래를 묶으면 왼쪽 서브트리, 오른쪽 자식 아래를 묶으면 오른쪽 서브트리입니다.

어떤 노드가 루트에서 몇 층 아래에 있는지를 그 노드의 깊이라고 부릅니다. 루트는 맨 위 층에 있고 루트의 자식은 그다음 층에 있습니다.

높이 균형을 지키는 대표가 AVL 트리입니다. AVL 은 이 트리를 처음 내놓은 두 연구자 Georgy Adelson-Velsky 와 Evgenii Landis 의 머리글자입니다. 기준이 빡빡한 만큼 찾는 길이 짧습니다. 대신 넣고 지울 때 손볼 일이 잦습니다.

경로 길이를 보는 대표는 레드-블랙 트리입니다. 노드마다 빨강이나 검정 표시를 붙입니다. 이 색의 배치 규칙 덕에 가장 긴 경로가 가장 짧은 경로의 두 배를 못 넘습니다. 기준이 느슨한 만큼 손볼 일이 적습니다.

잎 깊이를 보는 대표는 B-tree입니다. 노드 하나에 값을 여럿 담고 자식도 여럿 둡니다. 그래서 같은 수의 값을 자식이 둘뿐인 트리보다 훨씬 적은 층에 담습니다.

노드 하나에 담는 값 수는 정해 둔 범위 안에서 늘고 줄 수 있습니다. 그래서 값을 넣고 지워도 대개는 층을 안 바꾸고 노드 안에서 흡수합니다. 층이 늘 때는 맨 위에서 늘어 모든 잎이 함께 한 층 내려갑니다. 덕분에 모든 잎이 늘 같은 깊이에 있습니다.

균형을 되찾는 손질

가장 흔한 손질은 회전입니다. 기운 곳의 노드 둘레에서 부모와 자식의 연결을 바꿔 거는 일입니다. 값의 크기 순서는 바뀌지 않습니다. 높이만 줄어듭니다.

1, 2, 3 을 차례로 넣으면 1 의 오른쪽에 2, 2 의 오른쪽에 3 이 매달려 높이가 3 입니다. 가운데 값 2 를 위로 올립니다. 1 은 2 의 왼쪽 자식으로 내립니다. 그러면 높이가 2 가 됩니다. 왼쪽부터 1, 2, 3 으로 읽히는 순서는 바뀌지 않습니다.

flowchart TD
    subgraph 전["회전 전 · 높이 3"]
        R1["1"] -->|오른쪽| R2["2"] -->|오른쪽| R3["3"]
    end
    subgraph 후["회전 후 · 높이 2"]
        T2["2"] -->|왼쪽| T1["1"]
        T2 -->|오른쪽| T3["3"]
    end
    전 -->|2 를 위로 올린다| 후

회전 말고도 손질 방법은 몇 가지 더 있습니다. 아래 표는 방법마다 무엇을 바꾸는지 보입니다.

회전과 분할은 넣거나 지운 노드에서 루트까지 거슬러 오르는 길 위에서 끝납니다. 그 길의 길이가 곧 높이입니다. 그래서 손질을 더해도 넣기와 지우기는 O(log n) 에 머뭅니다.

균형을 지키는 대가

첫째 대가는 시간입니다. 넣고 지울 때마다 기울었는지 확인하고 손보는 일이 붙습니다. 찾기만 하는 트리라면 이 일이 필요 없습니다.

둘째 대가는 공간입니다. 노드마다 자기 아래가 몇 층인지, 무슨 색인지 같은 정보를 적어 둘 칸이 하나 더 듭니다. 노드가 많으면 이 칸도 쌓입니다.

셋째 대가는 코드입니다. 손질은 기운 모양마다 경우가 갈립니다. 그래서 손질 없는 이진 탐색 트리보다 코드가 길어지고 틀리기 쉽습니다.

이 대가 때문에 늘 자가 균형 트리를 고르지는 않습니다. 한 번 만들고 바꾸지 않는 데이터라면 정렬된 값의 가운데를 루트로 삼아 처음부터 고르게 지으면 됩니다.

값이 똑같은지로만 찾고 크기 순서는 필요 없을 때도 있습니다. 그때는 해시 테이블이 손질 없이 찾습니다. 데이터 양과 상관없이 평균으로 거의 한 번에 닿습니다. 빅오 표기법으로는 O(1) 이라고 적습니다.

자가 균형 트리는 값을 자주 넣고 지우는 데이터를 크기 순서대로 훑거나 범위로 찾아야 할 때 고릅니다.

관련 항목

트리 균형을 따지는 대상 자료구조

트리 · 이진 트리 · 이진 탐색 트리 · 완전 이진 트리 · 포화 이진 트리 · 편향 이진 트리 · 자료구조

트리 균형을 재는 지표와 표기

트리 높이 · 노드 깊이 · 서브트리 · 균형 인수 · 로그 함수 · 로그 시간 · 빅오 표기법 · 시간 복잡도 · 최악의 경우 · 평균의 경우

트리 균형을 스스로 지키는 트리

자가 균형 트리 · 균형 이진 탐색 트리 · AVL 트리 · 레드-블랙 트리 · 2-3 트리 · AA 트리 · B-tree · B+tree · 크기 균형 트리 · 희생양 트리 · 트립 · 스플레이 트리

깨진 트리 균형을 되찾는 연산

트리 회전 · 재균형 · 노드 분할 · 노드 병합 · 분할 상환 비용

트리 균형 대신 고를 수 있는 다른 수단

해시테이블 · 스킵 리스트 · 정렬된 배열 · 이진 탐색 · 연결 리스트