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

트리 자료구조

이진 탐색은 전제 조건이 데이터 정렬이다. 예를 들어 동작하는 프로그램에서 데이터를 정렬해두는 경우가 많으므로 이진 탐색을 효과적으로 사용할 수 있다. 데이터베이스는 내부적으로 대용량 데이터 처리에 적합한 트리 자료구조를 이용하여 항상 데이터가 정렬되어 있다. 따라서 데이터베이스에서의 탐색은 이진 탐색과는 조금 다르지만, 이전 탐색과 유사한 방법을 이용해 탐색을 항상 빠르게 수행하도록 설계되어 있어서 데이터가 많아도 탐색하는 속도가 빠르다.

 

그렇다면 트리 자료구조가 무엇인지 간단하게 알아보자. 트리 자료구조는 노드와 노드의 연결로 표현하며 여기에서 노드는 정보의 단위로서 어떠한 정보를 가지고 있는 개체로 이해할 수 있다. 트리 자료구조는 그래프 자료구조의 일종으로 데이터베이스 시스템이나 파일 시스템과 같은 곳에서 많은 양의 데이터를 관리하기 위한 목적으로 사용한다. 트리 자료구조는 몇 가지 주요한 특징이 있다. 

• 트리는 부모 노드와 자식 노드의 관계로 표현된다.
• 트리의 최상단 노드를 루트 노드라고 한다.
• 트리의 최하단 노드를 단말 노드라고 한다.
• 트리에서 일부를 떼어내도 트리 구조이며 이를 서브 트리라 한다.
• 트리는 파일 시스템과 같이 계층적이고 정렬된 데이터를 다루기에 적합하다.

 

 

 

이진 탐색 트리

트리 자료구조 중에서 가장 간단한 형태가 이진 탐색 트리이다. 이진 탐색 트리란 이진 탐색이 동작할 수 있도록 고안된, 효율적인 탐색이 가능한 자료구조이다. 다음 그림을 보자. 이진 탐색 트리에 데이터를 넣고 빼는 방법은 알고리즘보다는 자료구조에 가까우며, 이진 탐색 트리 자료구조를 구현하도록 요구하는 문제는 출제 빈도가 낮다. 따라서 이진 탐색 트리가 미리 구현되어 있다고 가정했다. 

 

이진 탐색 트리에서 데이터 조회는 동작 원리만 보면 간단하게 느껴진다. 루트 노드부터 왼쪽 자식 노드 혹은 오른쪽 자식 노드로 이동하며 반복적으로 방문한다. 자식 노드가 없을때까지 원소를 찾지 못했다면, 이진 탐색 트리에 원소가 없는 것이다.