자료구조 - 트리[이진탐색트리]

트리 자료 구조

- 데이터 베이스는 내부적으로 대용량 데이터 처리에 적합한 트리 자료구조를 이용하여 항상 데이터가 

정렬되어있다.

- 노드와 노드의 연결로 표현하며 노드는 정보의 단위로서 어떠한 정보를 가지고 있는 개체이다.

- 그래프 자료구조의 일종이다.

 

- 트리는 부모 노드와 자식 노드의 관계로 표현된다.

- 트리의 최상단 노드를 루트 노트라고 한다.

- 트리의 최하단 노드를 단말 노드라고 한다.

- 트리에서는 일부를 떼어내도 트리 구조이며 이를 서브 트리라 한다.

- 트리는 파일 시스템과 같이 계층적이고 정렬된 데이터를 다루기에 적합하다.

 

큰 데이터 처리를 요구하는 소프트웨어는 대부분 데이터를 트리 자료구조로 저장해서

이진탐색과 같은 탐색 기법을 이용해 빠르게 탐색이 가능하다. 

 

이진 탐색 트리

 

- 이진 탐색이 동작 할 수 있도록 고안된, 효율적인 탐색이 가능한 자료구조이다.

- 모든 트리가 다 이진 탐색 트리는 아니다. 

 

 

1. 부모 노드보다 왼쪽 자식 노드가 작다.

2. 부모 노드보다 오른쪽 자식 노드가 크다.

 

 

왼쪽 자식노드 < 부모노드 < 오른쪽 자식노드

 

찾는 원소값이 14일 때 이진 탐색트리의 과정을 살펴보자.

 

1. 부모 노드와 찾는 원소값 14 를 비교하자, 원소값 14는 부모노드 보다 크다.

2. 왼쪽 자식 노드는 부모노드 보다 작다. 따라서 원소값 14보다 작다.

3. 따라서 왼쪽 자식 노드는 모두 버리고 오른쪽 자식 노드를 방문한다.

 

위 과정을 반복하여 원소값 14를 찾아보자.  

 

1) 루트 노드 10은 원소값 14보다 작다. -> 왼쪽 노드를 전부 버리고 오른쪽 노드 17을 방문하여 부모노드는 17이 된다.

2) 부모 노드 17은 원소값 14보다 크다. -> 오른쪽 노드를 전부 버리고 왼쪽 노드 14를 방문한다.

3) 방문한 노드와 원소값이 같다. 탐색 종료