[이코테 with Java] 트리 자료구조

트리 자료구조

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

 

그렇다면 트리 자료구조란 무엇일까?

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

 

트리 자료구조의 특징에는 아래와 같은 것들이 있다.

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

이진 탐색 트리

트리 자료구조 중에서 가장 간단한 형태가 이진 탐색 트리이다. 이진 탐색 트리란 이진 탐색이 동작할 수 있도록 고안된, 효율적인 탐색이 가능한 자료구조이다. 

 

 

보통 이진 탐색 트리는 위의 그림과 같은데, 모든 트리가 다 이진 탐색 트리는 아니며, 이진 탐색 트리는 다음과 같은 특징을 가진다. 

 

• 부모 노드보다 왼쪽 자식 노드가 작다.
• 부모 노드보다 오른쪽 자식 노드가 크다.

좀 더 간단하게 표현하면 왼쪽 자식 노드 < 부모 노드 < 오른쪽 자식 노드가 성립해야지 이진 탐색 트리라 할 수 있다.

 

이진 탐색 트리가 미리 구현되어 있다고 가정하고, 이진 탐색 트리에서 데이터를 조회하는 과정을 살펴보겠다.

다음은 찾는 원소가 37일 때 동작하는 과정이다. 

step 1

이진 탐색은 루트 노드부터 방문한다. 루트 노드는 '30'이고 찾는 원소값은 '37'이다. 

공식에 따라 부모 노드의 왼쪽 자식 노드는 '30' 이하이므로 왼쪽에 있는 모든 노드는 확인할 필요가 없다. 

따라서 오른쪽 노드를 방문한다. 

step 2

오른쪽 자식 노드인 '48'이 이번에는 부모 노드이다. '48'은 찾는 원소값인 '37'보다 크다. 

공식에 따라 부모 노드(48)의 오른쪽 자식 노드는 모두 '48' 이상이므로 확인할 필요가 없다.

따라서 왼쪽 노드를 방문한다. 

step 3

현재 방문한 노드의 값인 '37'과 찾는 원소값인 '37'이 동일하다. 따라서 탐색을 마친다. 

 

이진 탐색 문제는 입력 데이터가 많거나, 탐색 범위가 매우 넓은 편이다. 예를 들어 데이터의 개수가 1000만 개를 넘어가거나 탐색 범위의 크기가 1,000억 이상이라면 이진 탐색 알고리즘을 의심해보자.