[자료구조] Tree & Binary Search Tree(BST) 기초

- Tree

 

자료구조 Tree는 이름 그대로 나무의 형태를 가지고 있다. 정확히는 나무를 거꾸로 뒤집어 놓은 듯한 모습을 가지고 있다. 그래프의 여러 구조 중 무방향 그래프의 한 구조로, 하나의 뿌리로부터 가지가 사방으로 뻗은 형태가 나무와 닮아 있다고 해서 트리 구조라고 부른다.

 

출처: CODESTATES

마치 가계도와 흡사해 보이는 이 트리 구조는 데이터가 바로 아래에 있는 하나 이상의 데이터에 무방향으로 연결된 계층적 자료구조이다. 데이터를 순차적으로 나열시킨 선형 구조가 아니라, 하나의 데이터 뒤에 여러 개의 데이터가 존재할 수 있는 비선형 구조이다. 트리 구조는 계층적으로 표현이 되고, 아래로만 뻗어나가기 때문에 사이클이 없다.

 

용어 정리

• 노드(Node) : 트리 구조를 이루는 모든 개별 데이터
• 루트(Root) : 트리 구조의 시작점이 되는 노드
• 부모 노드(Parent Node) : 두 노드가 상하관계로 연결되어 있을 때 상대적으로 루트에 가까운 노드
• 자식 노드(Child Node) : 두 노드가 상하관계로 연결되어 있을 때 상대적으로 루트에서 먼 노드
• 리프 노드(Leaf Node) : 트리 구조의 끝 지점이고, 자식 노드가 없는 노드
• 깊이(Depth) : 트리 구조에서는 루트로 부터 하위 계층의 특정 노드까지의 깊이(depth)를 표현할 수 있다. 루트 노드는 지면에 있는 것처럼 깊이가 0이다. 위 그림에서 루트 A의 depth는 0이고, B, C는 1, D, E, F, G의 깊이는 2이다.
• 레벨(Level) : 트리 구조에서 같은 깊이를 가지고 있는 노드를 묶어서 레벨(Level)이라고 표현한다. depth가 0인 루트 A의 레벨은 1이다. depth가 1인 B, C의 레벨은 2이다. 같은 레벨에 나란히 있는 노드를 형제 노드(sibling Node)라고 한다.
• 높이(Height) : 트리 구조에서 리프 노드를 기준으로 루트까지의 높이(height)를 표현할 수 있다. 리프 노드와 직간접적으로 연결된 노드의 높이를 표현하며, 부모 노드는 자식 노드의 가장 높은 height 값에 +1 한 값을 높이로 가진다. 트리 구조의 높이를 표현할 때에는 각 리프 노드의 높이를 0으로 놓는다.
• 서브 트리(Sub tree) : 트리 구조에서 root로 부터 뻗어 나오는 큰 트리의 내부에, 트리 구조를 갖춘 작은 트리를 서브 트리라고 부른다. 위 그림에서 (D, H, I) 도 서브 트리라고 부를 수 있다.

트리의 실사용 예제

가장 대표적인 예제는 컴퓨터 디렉토리 구조이다. 어떤 프로그램이나 파일을 찾을 때 바탕화면 폴더나 다운로드 폴더 등에서 다른 폴더에 진입하고, 또 그 안에서 다른 폴더에 진입하면서 원하는 프로그램이나 파일을 찾는다. 모든 폴더는 하나의 폴더(루트 폴더, /)에서 시작되어, 가지를 뻗어 나가는 모양새를 띤다.

 

하나의 폴더 안에 여러 개의 폴더가 있고, 또 그 여러 개의 폴더 안에 또 다른 폴더나 파일이 있다. 사용자들이 편하게 사용하기 위한 파일 시스템 등은 트리 구조를 이용해 만들어져 있다.

 

Binary Search Tree(BST)

트리 구조는 편리한 구조를 전시하는 것 외에 효율적인 탐색을 위해 사용하기도 한다. 많은 트리의 모습 중, 가장 간단하고 많이 사용하는 이진트리(binary tree)와 이진 탐색 트리(binary search tree)에 대해 알아보자.

 

먼저, 이진 트리(binary tree)는 자식 노드가 최대 두 개인 노드들로 구성된 트리이다. 이 두 개의 자식 노드는 왼쪽 자식 노드와 오른쪽 자식 노드로 나뉜다

 

이진트리는 자료 삽입, 삭제 방법에 따라 정 이진트리(Full binary tree), 완전 이진트리(Complete binary tree), 포화 이진트리(Perfect binary tree)로 나뉜다.

 

이진 트리 종류	영어 표기	설명
정 이진 트리	Full binary tree	각 노드가 0개 혹은 2개의 자식 노드를 갖는다.
완전 이진 트리	Complete binary tree	마지막 레벨을 제외한 모든 노드가 가득 차 있어야 하고, 마지막 레벨의 노드는 전부 차있지 않아도 되지만 왼쪽이 채워져 있어야 한다.
포화 이진 트리	Perfect binary tree	정 이진 트리이면서 완전 이진 트리인 경우에 해당한다. 모든 리프 노드의 레벨이 동일하고, 모든 레벨이 가득 채워져 있는 트리이다.

이진 탐색 트리(Binary Search Tree)는 모든 왼쪽 자식의 값이 루트나 부모보다 작고, 모든 오른쪽 자식의 값이 루트나 부모보다 큰 값을 가지는 특징이 있다.

 

이진 탐색 트리는 균형 잡힌 트리가 아닐 때, 입력되는 값의 순서에 따라 한 쪽으로 노드들이 몰리게 될 수 있다. 균형이 잡히지 않은 트리는 탐색하는데 시간이 더 걸리는 경우도 있기 때문에 해결해야 할 문제이다. 이 문제를 해결하기 위해 삽입과 삭제마다 트리의 구조를 재조정하는 과정을 거치는 알고리즘을 추가할 수 있다.