Java 자료구조(Data Structure) - 트리(Tree)

자료구조 Tree 란?

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

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

Tree의 구조와 특징

트리 구조는 루트(Root)라는 하나의 꼭지점 데이터를 시작으로 여러 개의 데이터를 간선(edge)로 연결한다. 각 데이터를 노드(Node)라고 하며, 두 개의 노드가 상하 계층으로 연결되면 부모/자식 관계를 가진다. 위 그림에서 A는 B와 C의 부모 노드(Parent Node)이고, B와 C는 A의 자식 노드(Child Node)이다. 자식이 없는 노드는 나무의 잎과 같다고 하여 리프 노드(Leaf Node)라고 부른다. 자료 구조 Tree는 깊이와 높이, 레벨 등을 측정할 수 있다.

• 깊이(depth)
  트리 구조에서는 루트로부터 하위 계층의 특정 노드까지의 깊이 (depth)를 표현할 수 있다. 루트 노드는 지면에 있는 것처럼 깊이가 0 이다. 위 그림에서 A의 depth는 0이고 B와 C는 1, D, E, F, G의 깊이는 2이다.
• 레벨(Level)
  같은 깊이를 가지고 있는 노드를 묶어 레벨(level)로 표현한다. depth가 0인 루트는 level1, depth가 1인 루트는 level2 이다. 같은 레벨에 나란히 있는 노드를 형제노드(Sibling Node)라고 한다.
• 높이(Height)
  트리구조에서 리프노드를 기준으로 루트까지 높이(height)를 표현할 수 있다. 리프 노드와 직간접적으로 연결된 노드의 높이를 표현하며, 부모 노드는 자식 노드의 가장 높은 height 값에 +1한 값을 높이로 가진다. 트리 구조의 높이를 표현할 때에는 각 리프 노드의 높이를 0으로 놓는다. 위 그림에서 H, I, E, F, J의 높이는 0이다. D와 G의 높이는 1이다. B와 C의 높이는 2이다. 루트 A의 높이는 3이다.
• 서브 트리(Sub tree)
  트리 구조의 root에서 뻗어 나오는 큰 트리의 내부에 트리 구조를 갖춘 작은 트리를 서브 트리라고 부른다. 위의 그림에서 (D, H, I), (B, D, E), (C, F, G, J) 를 서브 트리라고 볼 수 있다.
  
  

반응형

Tree의 장점

• 효과적인 계층 구조 표현
  Tree 자료 구조는 계층 구조를 나타내는데에 효과적이다.예를 들어 회사 조직도 트리 구조에서 직원들 간 계층 구조를 표현하는 방법이다.
  
  
• 정렬과 탐색에 활용
  Tree 자료 구조는 이진 탐색 트리, 힙(Heap) 등과 같은 다양한 형태로 사용될 수 있으며 정렬과 탐색을 위한 알고리즘을 구현하는 데에도 사용된다.
  
  
•  삽입과 삭제가 쉬움
  Tree 자료 구조는 노드의 삽입과 삭제가 쉽다. 이는 삽입 및 삭제 시에 해당 노드의 부모와 자식 노드만 수정하면 되기 때문이다.
  
  
• 구조 파악이 용이
  Tree 자료 구조는 시각화가 쉬워 트리를 시각적으로 표현하여 이해하기 쉽다.
  
  
• 다양한 분야에서 활용
  Tree 자료 구조는 데이터 베이스 알고리즘 등 다양한 분야에서 활용된다. 이는 Tree 자료 구조가 다양한 문제를 해결하기 위한 다양한 알고리즘의 기초가 되기 때문이다.

Tree의 실사용 예제

가장 대표적인 예제로 컴퓨터의 디렉토리 구조이다. 어떤 프로그램이나 파일을 찾을 때, 바탕화면 폴더나 다운로드 폴더 등에서 다른 폴더에 진입하고, 또 그 안에서 다른 폴더에 진입하면서 원하는 프로그램이나 파일을 찾는다.
하나의 폴더 안에는 여러개의 폴더가 있고, 또 그 여러개의 폴더 안에는 또 다른 폴더나 파일이 있다. 위 그림처럼 제일 첫 번째 폴더에서  출발하여 도착하려는 폴더로 가는 경로는 유일하다. 사용자들이 편하게 사용하기 위한 파일 시스템 등에서는 트리 구조를 이용해 만들어져 있다.