[자료 구조] - 트리 자료 구조(1)-기본 트리 용어 및 개념 정리 :: Tree Data Structure.

트리 자료구조

트리 자료구조는 우리가 일상을 살면서 모르지만 자주 마주하고 사용하는 개념이다.

 

이를테면 우리 부모와 자식의 관계 또한 트리 구조이다.

트리 하면 가장 대표적으로 표현하는 것이 바로 컴퓨터의 File System이다.

 

파일을 찾기 위해서 우리는 디렉토리 안에 또 디렉토리를 파고 들어가서 파일을 찾곤 하는데, 이것이 바로 트리의 사용이다.

더 다양한 트리의 사용을 보고 트리를 유추해보자!

• File System
• HTML Tag 구조
• 도-시군구-읍면동-의 주소 체계
• DBMS
• 라우터 통신 알고리즘
• 검색 엔진

위에서 나온 사용들이 갖는 가장 두드러지는 공통점이 있는데, 바로 계층 구조라는 것이다.

계층 구조

트리는 계층 구조의 대표적 자료구조이다.

 

계층 구조라고 함은 부모-자식 관계를 갖는 데이터의 구조를 뜻한다.

 

이와 비슷한 여러 특성이 존재하는데(사이클을 갖지 않는 비선형 자료구조, 그래프의 일종, 여러 노드가 한 노드를 가리킬 수 없음) 이는 아직 이해하기 어려우니 넘어가자.

 

그럼 이러한 계층 구조를 갖는 트리가 왜 유명하고 실생활에 많이 사용할까?

그 이유는 바로 탐색이다. 탐색을 위해 트리가 태어났다고 해도 과언이 아닐 만큼 트리에서 탐색 효율은 엄청나다.

 

우리는 이 탐색 효율을 위해서 트리를 충분히 배워볼 가치가 있는데, 그 길이 험난하므로 천천히 하나씩 정복해보자.

트리 구성 요소

출처 : https://towardsdatascience.com/

트리를 설명하는데 좋은 자료가 있어서 가져왔다.

 

위에 있는 구성 요소 하나 하나를 봐보자.

 

트리를 이해하기 위해서는 연결 리스트에 있는 노드라는 개념에 대해 알고 있어야 하므로 한 번 가볍게 읽고 오는 것도 좋은 방법이다.

Key

키, 혹은 Value라고도 불리며 해당 노드에 있는 실질적 Data가 된다.

Root

트리의 가장 윗 부분에 위치하는 노드를 루트 노드라고 한다. 하나의 트리에는 하나의 루트 노드가 존재한다.

Edge

간선이라고도 불리며 트리와 트리를 이어주는 개념적 존재이다. 간선으로 서로 연결되어 있으면 해당 트리는 부모-자식 관계로 이어진 것이다.

Leaf Nodes

트리의 가장 아래에 위치하는 노드를 리프 노드라고 한다. 주의해야할 점이 트리에 물리적으로 가장 아래에 있는 노드를 뜻하는게 아니라 노드가 더 이상 간선으로 연결할 수 없고, 더 뻗어나갈 수 없는 마지막 노드에 위치할 때 리프 노드라고 부른다.

Siblings

같은 부모를 갖고 같은 차수에 있는 노드를 형재(Siblings) 관계라고 한다. 차수는 밑에 있는 Height of the tree인데, 루트 노드가 0차수(혹은 1차수) 부터 한 세대가 지날 수록 차수가 1씩 늘어난다.

Parent

한 노드에서 위로 직접적으로 연결된 노드를 부모 노드라고 한다. 노드는 1개의 부모 노드를 가질 수 있다. 아까 위에서 말한 여러 특징중 하나가 이것이다.

Children

어떤 노드로 부터 간선으로 연결된 아래쪽 노드를 자식 노드라고 한다. 노드는 여러 개의 자식을 가질 수 있지만 자식 노드는 하나의 부모만 가질 수 있다.

SubTree

트리 안에서 다시 어떤 노드를 루트 노드로 정하고 그 자손으로 이루어진 트리를 서브 트리라고 한다.

Height of the Tree

트리의 높이, 즉 차수(Degree, Level)라고도 하며 루트 노드로부터 한 계층이 내려갈 수록 1씩 차수가 증가한다.

 

---

이제 트리에 대한 개념은 어느 정도 잡혀있을 거라고 생각한다. 다음 시간에는 트리의 탐색 방법에 대해서 개념적으로 알아보고 추후에는 코드로 구현해보자.