탐색 (선형 탐색, 트리 탐색, AVL, 회전 연산)

탐색: 임의의 키 값을 대상 파일에서 찾는 것

선형탐색 O(n)

- 정렬되어 있지 않은 파일

O(n) - none-sorted

- 정렬되어 있는 파일

O(n) - sorted

none-sorted에 비해서 없는 키값을 찾을 때 유리하다.

 

트리탐색

tree -> binary tree

정의: 임의의 키 값은 왼쪽보다 크고 오른쪽보다 작다

구성: 맨 처음 들어오는 키 값은 루트, 나머지는 정의대로 삽입한다.

 

- ex) 5 4 3 6 8 2 1 7

- ex) 5 3 6 8 4 7 1 2

- ex) 1 2 3 4 5 6

 

 

AVL Tree

: Hight Balanced -k tree 일 때 k는 1이하

k : 왼쪽 자식과 오른쪽 자식의 Depth 차이

L : 왼쪽 자식 Depth

R : 오른쪽 자식 Depth

 

Even 상태 : (L = R)

Left 상태 : (L > R)

Right 상태 : (L < R)

Critical 상태 : (2 이상 차이, (2,0) or (0,2))

    Critical 상태일 때 회전 연산을 한다.

 

-ex)

 

 

- 회전 연산

LL

RR

LR (이중 연산)

RL (이중 연산)