[MIT] 파이썬을 이용한 알고리즘의 이해 - 균형 이진 탐색 트리

 

 

BoostCourse의 "[MIT]파이썬을 이용한 알고리즘의 이해" 강의 내용을 정리한 글입니다.

 

 

✔ 복습: 이진 탐색 트리(BST)

이진 탐색 트리에서 노드의 높이와 속성

• 루트가 있는 이진 트리
• 각 노드는 다음을 가짐 : [ 키, 왼쪽 포인터, 오른쪽 포인터, 부모 포인터 ]
• 노드의 높이 = 단말 노드까지의 가장 긴 하향 경로의 길이
  ⭐ 노드의 높이는 자식 노드들 높이 중 가장 큰 값에 1을 더함
  ⭐ 자식 노드가 없는 부모 노드는 자식 노드 부분 높이를 -1로 설정
• 각 노드는 자신의 높이를 저장((높이 대신 높이의 차를 저장할 수도 있음)

 

 

 

✔ 균형을 이루는 것의 중요성

• 이진 탐색 트리는 삽입, 삭제, 최솟값, 최댓값, 다음으로 큰 값 찾기, 다음으로 작은 값 찾기 등을 O(h) 안에 실행할 수 있습니다. 이때 h=트리의 높이(=루트의 높이)
• h는 log n과 n 사이에 있습니다.
• 균형 이진 탐색 트리는 h = O(log n)로 유지됩니다.
  ⇒ 모든 작업은 O(log n) 시간 안에 실행됩니다.

 

✔ AVL 트리

⁉️ 정의

: 자가 균형 이진 탐색 트리. 모든 노드에 대해, 왼쪽과 오른쪽 자식들의 높이가 최대 ±1만큼 달라야 합니다.

 

⁉️ 성질

• 높이 균형 성질: 트리의 모든 내부 노드에 대하여 자식 노드들의 높이 차이가 최대 1입니다.
  → 높이 균형 성질로부터 n개의 원소를 갖는 AVL 트리의 높이는 log n입니다.

  

⁉️ 삽입

1. 간단한 이진 탐색 트리로 삽입
2. 트리를 따라 올라가면서 처리, AVL 속성 회복(올라가면서 높이 값도 갱신)

삽입 예시

 

⁉️ 회전

• x가 AVL을 위반하는 가장 낮은 노드라고 가정
• x가 오른쪽-무거움이라고 가정(왼쪽은 대칭임)
• if: x의 오른쪽 자식이 오른쪽-무거움이거나 균형이라면 아래의 그림 단계 수행

• else: 아래의 그림 단계 수행

• 그다음에 x의 조부모, 증조부모까지 올라가며 계속함

👀 화살표 방향은 무거운 쪽을 향한다.

 

⁉️ 정렬

• AVL 트리에 각 아이템 삽입 : Θ(n log n)
• 중위 순회 : Θ(n)/Θ(n log n)