AVL 트리 (AVL tree)# AVL 트리는 Adelson-Velsky와 Landis가 1962년에 발명한 자체 균형 이진 검색 트리(self-balancing binary search tree)이다.
https://en.wikipedia.org/wiki/AVL_tree
모든 노드의 왼쪽과 오른쪽 서브트리의 높이 차이(균형 인수)가 -1, 0, 1 중 하나이다. 트리의 높이는 항상 O(log N)을 유지한다 (N은 노드의 수). 자체 균형 기능으로 삽입, 삭제, 검색 연산의 시간 복잡도가 O(log N)으로 보장된다. 검색, 삽입, 삭제 연산의 시간 복잡도가 O(log N)으로 보장된다. 트리의 균형을 유지하여 최악의 경우에도 효율적인 성능을 제공한다. 레드-블랙 트리에 비해 더 엄격한 균형을 유지하여 검색 작업에 더 효율적이다. 데이터베이스 인덱싱 메모리 관리 시스템 파일 시스템 구현 맵(Map)과 셋(Set) 자료구조 구현 동작 원리# 삽입: 새 노드를 일반 이진 검색 트리처럼 삽입한 후, 균형 인수를 확인하고 필요시 회전을 수행하여 균형을 유지한다.일반적인 이진 탐색 트리처럼 새로운 노드를 삽입한다. 삽입 경로를 따라 올라가면서 각 노드의 높이를 갱신한다. 불균형이 발생한 경우(균형 인수의 절댓값이 2가 된 경우) 회전 연산을 수행한다.LL Case: 오른쪽 회전 RR Case: 왼쪽 회전 LR Case: 왼쪽-오른쪽 회전 RL Case: 오른쪽-왼쪽 회전 삭제: 노드를 제거한 후, 트리의 균형을 유지하기 위해 필요한 회전을 수행한다. 검색: 일반적인 이진 검색 트리와 동일한 방식으로 수행된다. 구성 요소# 노드: 키 값, 왼쪽 자식 포인터, 오른쪽 자식 포인터, 높이 정보를 포함한다.키(key): 데이터 값 높이(height): 해당 노드를 루트로 하는 서브트리의 높이 왼쪽 자식 포인터 오른쪽 자식 포인터 (선택적으로) 부모 노드 포인터 균형 인수(Balance Factor): 각 노드의 왼쪽과 오른쪽 서브트리의 높이 차이를 나타낸다.각 노드의 왼쪽 서브트리와 오른쪽 서브트리의 높이 차이 수식으로는 BF = height(left) - height(right) 이 값은 항상 -1, 0, 1 중 하나여야 합니다 회전 연산: 트리의 균형을 유지하기 위한 왼쪽 회전, 오른쪽 회전, 왼쪽-오른쪽 회전, 오른쪽-왼쪽 회전이 있다. 구현 방식# AVL 트리는 일반적으로 다음과 같은 구조로 구현된다:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
class Node :
def __init__ ( self , key ):
self . key = key
self . left = None
self . right = None
self . height = 1
class AVLTree :
def __init__ ( self ):
self . root = None
# 노드의 높이를 가져오는 메서드
def getHeight ( self , node ):
if not node :
return 0
return node . height
# 균형 인수를 계산하는 메서드
def getBalance ( self , node ):
if not node :
return 0
return self . getHeight ( node . left ) - self . getHeight ( node . right )
# 오른쪽 회전
def rightRotate ( self , y ):
x = y . left
T2 = x . right
x . right = y
y . left = T2
y . height = max ( self . getHeight ( y . left ), self . getHeight ( y . right )) + 1
x . height = max ( self . getHeight ( x . left ), self . getHeight ( x . right )) + 1
return x
# 왼쪽 회전
def leftRotate ( self , x ):
y = x . right
T2 = y . left
y . left = x
x . right = T2
x . height = max ( self . getHeight ( x . left ), self . getHeight ( x . right )) + 1
y . height = max ( self . getHeight ( y . left ), self . getHeight ( y . right )) + 1
return y
# 노드 삽입
def insert ( self , root , key ):
if not root :
return Node ( key )
elif key < root . key :
root . left = self . insert ( root . left , key )
else :
root . right = self . insert ( root . right , key )
root . height = 1 + max ( self . getHeight ( root . left ), self . getHeight ( root . right ))
balance = self . getBalance ( root )
# 왼쪽-왼쪽 케이스
if balance > 1 and key < root . left . key :
return self . rightRotate ( root )
# 오른쪽-오른쪽 케이스
if balance < - 1 and key > root . right . key :
return self . leftRotate ( root )
# 왼쪽-오른쪽 케이스
if balance > 1 and key > root . left . key :
root . left = self . leftRotate ( root . left )
return self . rightRotate ( root )
# 오른쪽-왼쪽 케이스
if balance < - 1 and key < root . right . key :
root . right = self . rightRotate ( root . right )
return self . leftRotate ( root )
return root
참고 및 출처# 