자료구조 - 트리(Tree)

트리(Tree)

---

트리

트리는 노드와 에지로 연결된 그래프의 특수한 형태로 비선형 계층적 자료구조이다.

각 노드는 여러 노드의 주소를 저장한다. 모든 노드는 자식의 주소를 저장하고 첫 번째 노드의 주소는 루트라는 별도의 포인터에 저장된다.

그래프의 특수한 형태이기 때문에 그래프의 표현으로도 트리를 표현할 수 있다.

 

트리의 구성 요소

트리의 구성요소

• 노드 - 데이터의 인덱스와 벨류를 표현하는 요소
• 에지 - 노드와 노드의 연결 관계를 나타내는 선
• 루트 노드 - 트리에서 가장 상위에 존재하는 노드
• 부모 노드 - 두 노드 사이의 관계에서 상위 노드에 해당하는 노드
• 자식 노드 - 두 노드 사이의 관계에서 하위노드에 해당하는 노드
• 리프 노드 - 트리에서 가장 하위에 존재하는 노드(자식 노드가 없는 노드)
• 서브 트리 - 전체 트리에 속한 작은 트리

 

트리의 특징

• 순환 구조(사이클)를 지니고 있지 않고, 1개의 루트 노드가 존재한다.

앞서 트리는 그래프의 특수한 형태라고 설명했었는데 그 이유는 순환 구조를 가지고 있지 않아 때문이다.

그래프 자료구조

그래프 자료구조는 루트 노드가 존재하지 않기 때문에 여러 개의 그래프가 개별적으로 생성될 수 있다.

 

트리 자료구조

하지만 트리는 루트 노드가 존재하고, 단 하나만 존재해야 한다.

 

• 루트 노드를 제외한 노드는 단 1개의 부모 노드를 갖는다.

트리 자료구조

그림을 살펴보면 최상위 노드인 루트 노드를 제외하고 나머지 노드들은 단 1개의 부모 노드만 갖고 있다.

 

• 트리의 부분 트리(서브 트리) 역시 트리의 모든 특징을 따른다.

서브트리

트리의 자식 노드를 따라가보면 부모 노드를 기준으로 서브 트리를 나눌 수 있다.

서브 트리 또한 하나의 트리로 간주하여 트리 자료구조가 지니는 모든 특징을 따르게 된다.

 

• 연결되어 있는 트리에서는 임의의 두 노드를 연결해 주는 경로는 유일하다.

노드를 이어주는 간선은 하나 이상 존재할 수 없기 때문에 임의의 두 노드를 연결해 주는 간선은 무조건 1개이다.

 

• 데이터를 순차적으로 저장하지 않기 때문에 비선형 자료구조 이다.

배열이나 리스트 등 선형 자료구조는 데이터를 저장할 때 받아온 순서대로 저장하게 되지만 비선형 자료구조에서는 순서를 보장하지 않는다.

 

• 노드가 n개인 트리는 항상 n - 1개의 간선을 가진다.

앞서 임의의 두 노드를 이어주는 간선은 무조건 하나라고 설명했었다. 식을 세우면 E = N - 1이 되는데 위의 그림을 보고 계산을 해보면 노드는 총 6개로 간선 = 6 - 1 즉, 총간선의 수는 5개가 된다.

 

• 트리에서 특정 노드로 가는 경로는 유일하다.

트리에서 자식 노드는 단 하나의 부모 노드만 가질 수 있는데 그럼 하나의 자식 노드와 부모 노드의 관계는 1대1이 된다.

그렇다면 맨 하단에 위치하는 리프 노드에서 루트 노드까지 계속 1대1 관계가 유지되기 때문에 특정 노드로 가는 경로가 유일해진다.

 

트리는 어디서 사용될까?

계층 적 데이터 저장

데이터를 계층 구조로 저장하는 데 사용된다.

우리가 흔히 사용하는 파일 및 폴더는 계층적 트리 형태로 저장되는데

그림과 같이 어떤 폴더 밑에 폴더나 파일이 있는 것이 트리 구로조 이뤄져 있다.

 

효율적인 검색 속도

트리에도 종류가 여러 가지 있는데 트리를 잘 활용하면 상당히 빠른 시간 내에 탐색이나 삽입 및 삭제 작업을 할 수 있다.

이진 탐색 트리를 예로 들면 탐색을 할 때 평균적으로 O(logn) 정도의 시간 복잡도를 가진다. 데이터의 양이 방대할수록 트리를 사용하면 훨씬 적은 작업만으로 원하는 데이터를 탐색할 수 있게 된다.

 

데이터베이스 인덱싱

앞서 설명했던 효율적인 검색 속도에서 트리는 여러 작업들을 빠른 시간 내에 수행할 수 있다고 했는데 이러한 특성을 잘 살린 곳이 데이터베이스 인덱싱이다.

데이터베이스 인덱싱을 구현하는데 트리를 사용한다. (B-Tree, B+Tree, AVL-Tree) 따라서 사용자가 원하는 데이터를 검색하거나 찾을 때는 빠른 속도로 탐색 작업을 수행할 수 있다.

 

코딩 테스트에서 트리 관련 문제가 나올 경우 크게 2가지 경우로 나올 수 있다.

1. 그래프 개념을 활용하여 해결하는 문제

트리는 그래프의 특수한 형태이기 때문에 그래프의 표현 방법을 적용할 수 있다.

DFS, BFS를 활용하여 트리 문제를 해결한다.

 

2. 그래프의 개념을 활용하지 않고 오로지 트리만을 위한 문제

트리만을 위한 문제이기 때문에 그래프의 개념을 활용하지 않는다. (인접 리스트 등으로 표현하지 않음)

이진트리, 세그먼트 트리, 최소 공통 조상 등 주로 어려운 문제로 나온다.