[HUFS/자료구조] #9 탐색 트리

탐색 트리

탐색 트리란 탐색을 위한 트리 기반의 자료구조이다

 

이진탐색트리는 이진트리 기반의 탐색 자료구조

이진탐색트리 노드 구조 (키와 노드를 입력 받아 탐색)

이진탐색트리 키를 이용한 탐색

순환 구조와 반복 구조

최대와 최소 노드

삽입 연산: 탐색이 실패한 위치가 노드를 삽입해야 하는 위치

삽입 연산 알고리즘

삭제 연산의 3가지 경우

1. 삭제하려는 노드가 단말(가장 마지막) 노드인 경우
2. 삭제하려는 노드가 왼쪽이나 오른쪽 중 하나의 서브트리를 가지는 경우 (자식이 하나)
3. 삭제하려는 노드가 2개의 서브트리를 모두 가지고 있는 경우 (자식이 둘)

case1: 단말 노드 삭제 (부모 노드를 기반으로 삭제)

case2: 자식이 하나인 노드 삭제 (삭제 후 자식을 상위 부모와 연결)

case3: 자식이 2개인 노드 삭제

자식 노드가 2개인 경우 이진탐색트리의 조건을 고려해 후계 노드를 선택

자식의 자식 노드에서 가장 유사한 값으로 교체

삭제 연산 전체 코드

연산 시간이 트리의 높이에 비례 (트리가 균형을 이룰수록 효율적)

이진탐색트리를 활용해 맵 클래스를 구현해보자

 

맵 클래스 구현

테스트 프로그램

균형이진탐색(AVL)트리

AVL 트리는 모든 노드에서 왼쪽 서브트리와 오른쪽 서브트리의 높이 차가 1을 넘지 않는 이진탐색트리

* 평균, 최선, 최악의 경우 모두 시간 복잡도 O(logn)을 보장

 

균형 인수가 1보다 크면 AVL 트리가 아님

탐색 연산은 기존 방식과 동일하지만 삽입/삭제 연산의 경우 균형 상태가 깨진다면

불균형 상태의 조상 노드(균형 인수 +-2)의 서브 트리들이 다시 재균형 (회전)

 

회전해서 재균형 (불균형 상태 4가지 LL/LR/RL/RR)

LL 회전 방법

RR 회전 방법

RL 회전 방법

LR 회전 방법

재균형 함수

AVL 트리 삽입 함수

AVL 트리 구축 예시

AVL 트리를 이용한 맵

이진탐색트리와 AVL 트리 비교 (계속해서 균형을 맞춰서 높이 차이 ~ 효율적)

+ Red-Black Tree