트리 | 트리 개념

트리

트리(tree)는 데이터를 저장하고 탐색하기에 유용한 구조를 갖고 있습니다. 트리가 데이터를 어떤방식으로 저장하고 탐색하는지 알아봅시다.

 

트리의 특성을 활용하는 분야

프로그램이 분야에서 트리는 계층 구조를 표현하는 용도로 많이 사용합니다. 예를 들어 파일 시스템이나 디렉터리 구조 등을 트리로 구성하거나 관리할 수 있습니다.

 

• 인공지능 : 인공지능의 판단 기준을 만들 때 의사 결정 트리를 사용합니다. 이를 통해 외부에서 입력된 데이터를 분류하거나 상황을 예측하는 모델을 만들 수 있습니다.
• 자동 완성 기능 : 트리는 문자열 처리에도 많이 활용됩니다. 예를 들어 검색 엔진에서 자동 검색어 추천 기능도 트라이(trie)라는 독특한 트리 구조를 활용한 것입니다. 이를 활용하면 접두사나 패턴 검색을 쉽게 할 수 있습니다.
• 데이터베이스 : 데이터를 쉽게 검색, 삽입, 삭제를 할 수 있도록 트리를 활용해서 데이터를 구조화하고 인덱싱합니다. 이때 B-트리나 B+트리를 많이 사용합니다.

 

나무를 거꾸너 뒤집어 놓은 모양의 트리

트리(tree)는 나무 기둥에서 가지가 뻗어나가는 모습을 거꾸로 뒤집어 놓은 모양입니다. 따라서 나무 밑둥(root)이 맨 위에 있습니다. 다음 그림은 트리 구조를 표현한 것입니다. 트리 구조를 표현하는 데 사용하는 새로운 용어가 많이 등장합니다. 그림과 함께 용어를 꼼꼼하게 보기 바랍니다.

 

트리를 구성하는 노드

노드는 트리를 구성하는 요소입니다. 노드 중 가장 위에 있는 노드를 루트 노드(root node)라고 합니다. 앞의 그림에서는 맨 위에 있는 값 1이 들어 있는 노드가 루트 노드입니다.

 

노드를 연결하는 엣지

노드와 노드 사이에는 이어주는 선이 있습니다. 이를 간선 또는 엣지(edge)라고 합니다. 트리는 노드와 노드가 단방향 간선으로 연결되어 있고, 루트 노드에서 각 노드까지 경로는 유일합니다. 루트 노드로부터 특정 노드까지 거쳐가는 최소한의 간선 수를 레벨로 표현합니다. 예를 들어 루트 노드는 레벨 0, 노드 19, 2, 13은 레벨 1입니다.

 

부모-자식, 형제 관계를 가지는 노드

간선으로 연결된 노드들은 서로 부모-자식 관계가 있다고 표현합니다. 간선으로 직접 연결된 노드 중 상대적으로 위에 있는 노드를 부모 노드(parent node), 아래에 있는 노드를 자식 노드(child node)라고 합니다. 그림에는 표현하지 않았지만 2, 7, 5의 관계를 보면 2가 상대적으로 7, 5의 부모 노드인 셈입니다. 그리고 7, 5처럼 같은 부모 노드를 갖는 노드를 형제 노드(sibling node)라고 합니다.

 

자식이 없는 말단 노드

자식이 없는 노드는 리프 노드(leaf node)라고 합니다.

 

아래로 향하는 간선의 개수, 차수

차수(degree)란 특정 노드에서 아래로 향하는 간선의 개수입니다. 예를 들어 노드 1은 차수가 3입니다. 왜냐하면 아래로 향하는 간선이 3개이기 때문입니다.