💿자료구조 - 이진 탐색 트리의 구현 & AVL 트리

이진 탐색 트리의 한계

- 노드가 N개인 이진 탐색 트리에서 삽입/삭제/탐색에 드는 시간복잡도 : 최악의 경우 O(N)

 

>> 아래와 같은 최악의 불균형 모양일 때,

>> 80을 삽입하고자 하면 6개 노드를 모두 다 돌아야함.. >> O(N)

BUT!!

>> 균형 잡힌 트리의 경우

>> 최악의 상황이더라도 연산에 드는 시간복잡도 : O(logN)

>>> 높이 h만큼의 노드를 탐색해야하므로 시간복잡도는 O(hN)

>>> O(hN) = O(logN)

 

트리에서 균형이란?

임의 노드의 Balance Factor= 좌측 서브트리의 높이 - 우측 서브트리의 높이

 >> 아무것도 없는 부분은 -1로 간주함

---

 

AVL 트리

= 균형잡힌 이진탐색트리

(조건)

1. 이진탐색트리 이자

2. 모든 노드의 Balance Factor의 절대값이 1 이하인 경우 '

 

>> 눈을 믿지 말고 직접 Balance Factor의 값을 구해서 확인하기!!

 

 

 

 

 

AVL 트리에서 데이터 삽입/삭제를 하면 불균형이 생김 >> 어떻게 바꿔야 할까?!

 

[ Case1 ]

빨강이 높이, 초록이 balance factor

 

 

[ Case 2 ]

 

 

 

[ Case 3 ]

 

 

 

[ Case 4 ]

 

 

 

 

 

 

 

[ AVL 트리에서 원소 삽입 ]

1. 이진 탐색 트리의 성질에 만족하도록 우선 삽입

2. 삽입된 노드에서 시작하여 루트 노드까지 Balance Factor의 절대값이 1을 넘는 노드가 있는지 확인

3. AVL 트리의 조건(성질)을 불만족하는 노드 발견시 트리의 균형화 과정 수행 

그리구 여기서 45의 Balance Factor가 2임 / 따라서 조건 2, 3 불만족

 

 

 

[ AVL 트리에서 원소 삭제 ]

1. 이진 탐색 기준으로 삭제

2. 삭제된 노드에서 시작하여 루트노드까지 Balance Factor의 절대값이 1을 넘는 노드가 있는지 확인

3. AVL 트리의 조건(성질)을 불만족하는 노드 발견 시 트리의 균형화 과정 수행

둘다 상관 없으나, 쉬운 왼쪽으로 pick

>> 41, 28, 82 ,21, 30, 45, 89, 음?? 29 뭐야

 >>> 이거 아무튼 제거하면 균형은 깨짐 ㅇㅇ