Tree란 무엇인가

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

계층적 자료구조

마치 가계도와 흡사해보이는 이 트리구조는, 데이터가 바로 아래에 있는 하나 이상의 데이터가 무방향으로 연결되어 있는 계층적 자료구조이다.

비선형 구조

데이터를 순차적으로 나열 시킨 선형 구조가 아니라, 하나의 데이터 뒤에 여러 개의 데이터가 존재할 수 있는 비선형 구조이다. 트리 구조는 계층적으로 표현이 되고, 아래로만 뻗어 나가기 때문에 , 사이클이 없다

그러면 self loop 인가?

트리구조

트리구조는 루트라는 하나의 꼭짓점 데이터를 시작으로 여러 개의 데이터를 간선으로 연결한다. 각 데이터를 노드라고 하며, 두 개의 노드가 상하계층으로 연결되면, 부모/자식 관계를 가지게 된다. 하지만 만약에 자식이 없는 노드는 나무의 잎과 같다고해서 리프 노드라고 한다.

용어정리

• 노드 : 트리구조를 이루는 모든 개별 데이터

• 루트 : 트리 구조의 시작점이 되는 노드

• 부모 노드 : 두 노드가 상하관계로 연결되어 있을 때 상대적으로 루트에서 가까운 노드

• 자식 노드 : 두 노드가 상하관계로 연결되어 있을 때 상대적으로 루트에서 먼 노드

• 리프 노드 : 트리 구조의 끝 지점이고, 자식 노드가 없는 노드

Tree는 깊이,높이,레벨 등을 측정할 수 있다.

• 깊이 : 트리 구조에서 루트로부터 하위 계층의 특정 노드까지의 깊이를 표현할 수 있다. 루트 노드는 지면에 있는 것처럼 깊이가 0이다.

• 레벨 : 트리 구조에서 같은 깊이를 가지고 있는 노드를 묶어서 레벨로 표현할 수 있다. 같은 레벨에 있는 노드를 형제노드라고 한다.

• 높이 : 트리 구조에서 리프 노드를 기준으로 루트까지의 높이를 표현할 수 있다. 리프 노드와 직간접적으로 연결된 노드의 높이를 표현하며, 부모 노드는 자식 노드의 가장 높은 height값에 + 1한 값을 높이로 가진다. 트리 구조의 높이를 표현할 때는 각 리프 노드(자식이없으면)의 높이를 0으로 놓는다.

• 서브트리 : 트리 구조에서 루트에서 뻗어나오는 큰 트리 내부에 , 트리구조를 갖춘 작은 트리를 서브 트리라고 한다.

트리의 실사용 예제

• 컴퓨터의 디렉토리 구조
  • 모든 폴더는 하나의 폴더(루트폴더,/)에서 시작되어 가지를 뻗어나간다.

트리의 다른 예시

• 월드컵 토너먼트 대진표, 가계도, 조직도 등