[이것이 취업을 위한 코딩 테스트] 트리 자료구조

트리 자료구조

트리 자료 구조

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

 

트리 자료구조란 무엇인가?

트리 자료구조는 노드와 노드의 연결료 표현하며 여기에서 노드는 정보의 단위로서 어떠한 정보를 가지고 있는 개체로 이해할 수 있다. 그래프를 다룰 때 나온 노드와 동일하다. 최단 경로에서는 노드가 '도시'와 같은 정점의 의미를 가진다.ㅏ 트리 자료구조는 그래프 자료구조의 일종으로 데이터 베이스 시스템이나 파일 시스템과 같은 곳에서 많은 양의 데이터를 관리하기 위한 목적으로 사용한다. 트리 자료구조는 몇가지 주요한 특징이 있다. 

트리 자료구조

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

정리하자면 큰 데이터를 처리하는 소프트웨어는 대부분 데이터를 트리 자료구조로 저장하여 이진 탐색과 같은 탐색 기법을 이용해 빠르게 탐색이 가능하다. 

 

이러한 트리 구조를 이용하여 정확히 어떠한 방식으로 항상 이진 탐색이 가능 한 것인지 알아보자

이진 탐색 트리

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

이진 탐색 트리

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

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

이진 탐색 트리에 데이터를 넣고 빼는 방법은 알고리즘보다는 자료구조에 가깝다.