Chapter 12. 탐색(Search) 2
#12-1. 균형 잡힌 이진 탐색 트리: AVL 트리의 이해 1
트리
이진트리 > 표현
이진 탐색 트리
AVL TREE : 균형이 잡힌 트리
하나를 선택해서 구현을 하는거야! 이것이 도움이 될 것이야!!
실무에서는 사용할 일이 없다..
구현 경험이 중요한거야!! 실제 사용 않더라도
이진 탐색 트리의 문제점과 AVL 트리
O(log 2 n)의 시간 복잡도를 가진다!!
균형이 맞지 않을 경우 O(n)에 가까운 시간 복잡도를 보인다.
#12-1. 균형 잡힌 이진 탐색 트리: AVL 트리의 이해 2
자동으로 균형 잡힌 AVL 트리와 균형 인수
균형 인수=왼쪽 서브 트리의 높이 - 오른쪽 서브 트리의 높이
#12-1. 균형 잡힌 이진 탐색 트리: AVL 트리의 이해 3
리밸런싱이 필요한 첫 번째 상태와 LL회전
LL 왼쪽 또 왼쪽 >> 어떻게 균형 잡혀줘?? > 맨 위 꺼 오른쪽으로 내려..
*
RR 오른쪽으로 한 번 또 한번 오른쪽으로 또 한 번
---------------
LR
*
RL
#12-1. 균형 잡힌 이진 탐색 트리: AVL 트리의 이해 4
#12-1. 균형 잡힌 이진 탐색 트리: AVL 트리의 이해 5
LR, RL 상태..
그 차제로 균형을 잡을 수 없다.
LL상태, RR상태는 균형을 잡을 수 있다. 부담이 없이 가능하다.
LL, RR 상태로 바꾸는게 우선이다. LR, RL 상태는 바꾸는 것이 우선이다!!
LR > RR > LL 바꿔주는 것
RL상태와 RL회전
RL > LL > RR 바꿔주는 것
#12-2. 균형 잡힌 이진 탐색 트리 : AVL 트리의 구현 1
AVL 트리를 어떻게 구현할 것인가?
#12-2. 균형 잡힌 이진 탐색 트리 : AVL 트리의 구현 2
LR회전, RL회전
LR > RR > LL
RL > LL > RR
#12-2. 균형 잡힌 이진 탐색 트리 : AVL 트리의 구현 3
#12-2. 균형 잡힌 이진 탐색 트리 : AVL 트리의 구현 4