CodeGym /자바 코스 /Python SELF KO /트리의 균형 조정: AVL 트리

트리의 균형 조정: AVL 트리

Python SELF KO

레벨 55 , 레슨 3

사용 가능

4.1 불균형 트리의 문제점

일반적인 (불균형) 트리에서는 요소를 추가할 때 불쾌한 효과가 발생할 수 있어.

1. 트리 높이 증가:

불균형 트리에서는 높이가 n (여기서 n은 노드의 수)이 될 수 있어서 성능이 저하될 수 있어.

기본 연산(검색, 삽입, 삭제)의 최악의 경우 시간 복잡도는 O(n)이 돼.

2. 불균형한 노드 분포:

불균형 트리에서는 몇몇 서브트리가 다른 것들보다 노드를 훨씬 더 많이 포함할 수 있는데, 이는 메모리의 비효율적인 사용과 처리 시간 증가로 이어져.

3. 연산 시간 증가:

불균형 트리에서는 검색, 삽입, 삭제 연산이 높이가 커진 트리 때문에 더 오래 걸려.

불균형 트리의 예:

이 예에서는 트리가 사실상 연결 리스트로 변하게 되고, 연산 시간은 선형이 돼.

AVL 트리 (Adelson-Velsky와 Landis의 이름을 따서 지음) - 이는 모든 노드에 대해 왼쪽과 오른쪽 서브트리의 높이 차이가 1을 넘지 않는 균형 잡힌 이진 검색 트리야.

AVL 트리의 속성:

1. 균형:

어느 노드의 왼쪽과 오른쪽 서브트리의 높이 차이가 1을 넘지 않아.

이는 트리 높이를 O(log n)으로 보장하는데, 여기서 n은 노드의 수야. 이로 인해 검색, 삽입, 삭제 연산이 효율적으로 수행돼.

2. 이진 검색 트리:

AVL 트리는 모든 이진 검색 트리의 속성을 가지고 있어: 어느 노드든 왼쪽 서브트리의 모든 키는 노드의 키보다 작고, 오른쪽 서브트리의 모든 키는 노드의 키보다 커.

3. 자동 균형 조정:

각 삽입이나 삭제 연산 후에는 트리의 속성을 유지하기 위해 균형 조정이 수행돼.

회전은 AVL 트리에서 노드를 삽입하거나 삭제한 후 균형을 회복하기 위해 수행하는 연산이야. 네 가지 회전 타입이 있어: 왼쪽, 오른쪽, 왼쪽-오른쪽, 오른쪽-왼쪽.

1. 왼쪽 회전 (Left Rotation):

왼쪽 회전에서는 노드 x가 위로 올라가고, 그 오른쪽 자식 노드 y가 부모 노드가 돼. y의 왼쪽 서브트리는 x의 오른쪽 서브트리가 되고.

2. 오른쪽 회전 (Right Rotation):

오른쪽 회전에서는 노드 x가 위로 올라가고, 그 왼쪽 자식 노드 y가 부모 노드가 돼. y의 오른쪽 서브트리는 x의 왼쪽 서브트리가 되고.

3. 왼쪽-오른쪽 회전 (Left-Right Rotation):

먼저 왼쪽 자식 노드에서 왼쪽 회전을 수행한 후 본 노드에서 오른쪽 회전을 수행해.

4. 오른쪽-왼쪽 회전 (Right-Left Rotation):

먼저 오른쪽 자식 노드에서 오른쪽 회전을 수행한 후 본 노드에서 왼쪽 회전을 수행해.

AVL 트리의 기본 연산에는 삽입, 삭제, 검색이 포함돼.

삽입 (Insertion)

AVL 트리에 새 노드를 삽입하고 필요 시 균형을 맞춰야 해.

단계:

노드 삽입하기:
- 트리의 루트에서 시작하여 재귀적으로 현재 노드와 값을 비교해 새 노드를 올바른 위치에 찾는 과정이야.
- 이진 검색 트리처럼 새 노드를 찾은 위치에 삽입해.
높이 업데이트:
- 삽입 후에는 새 노드부터 루트까지의 모든 노드의 높이를 업데이트해.
트리 균형 맞추기:
- 새 노드부터 루트까지의 모든 노드의 균형을 확인해.
- 만약 어떤 노드의 균형이 깨진다면 (왼쪽과 오른쪽 서브트리의 높이 차이가 1보다 큰 경우), 해당 균형을 복원하기 위해 적절한 회전을 수행해.