Tree 자료구조

Tree의 개념

트리는 노드들의 구조가 계층적 구조를 갖는 비선형 자료구조이며, 노드와 노드를 연결하는 간선으로 구성된다.

 

트리 자료구조는 나무(Tree)를 거꾸로 매단 모양과 유사하다.

 

 

트리는 하나의 루트 노드를 갖으며 루트 노드는 0개 이상의 자식 노드를 갖는다. 그 자식 노드 또한 0개 이상의 자식 노드를 갖으며 이는 반복적으로 정의된다.

 

 

트리 구조의 기본 용어

노드(Node)

트리를 구성하는 기본 요소이며, 노드에는 키 또는 값과 하위 노드에 대한 포인터를 갖고있다.

 

간선(Edge)

노드와 노드 간의 연결선

 

루트 노드(Root Node)

트리 구조에서 부모가 없는 최상위 노드

 

부모 노드(Parent Node)

자식 노드를 갖는 노드

 

자식 노드(Child Node)

부모 노드의 하위 노드

 

형제 노드(Sibling Node)

같은 부모를 갖는 노드

 

내부 노드(Inner Node), 가지 노드(Branch Node)

자식 노드 하나 이상을 갖는 노드

 

깊이(Depth)

루트에서 어떤 노드까지의 간선 수

 

높이(Height)

어떤 노드에서 리프 노드까지 가장 긴 경로의 간선 수

 

레벨(Level)

루트 노드에서 특정 노드까지의 간선 수

 

Degree

노드의 자식 수

 

Path

한 노드에서 다른 한 노드에 이르는 길 사이에 놓여있는 노드들의 순서

 

Path Length

해당 경로에 있는 총노드의 수

 

Size

자신을 포함한 자손의 노드 수

 

Width

레벨에 있는 노드 수

 

Breadth

리프 노드의 수

 

Distance

두 노드 사이의 최단 경로에 있는 간선의 수

 

Order

부모 노드가 갖을 수 있는 최대 자식의 수

 

 

Tree 자료구조의 특징

하나의 루트 노드와 0개 이상의 하위 트리로 구성되어있다.

 

그래프의 한 종류이며 최소 연결 트리 로도 불린다.

 

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

 

트리 내에 또다른 트리가 저장되는 재귀적 자료구조이다.

 

단순 순환(loop)를 갖지 않으며, 연결된 노드간의 방향성이 있는 무방향 그래프 구조이다.

 

자식 노드는 하나의 부모 노드만 갖는다.

 

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

 

 

트리의 종류

편향 트리(skew tree)

모든 노드들이 하나의 자식 노드만 갖는 트리이며, 왼쪽 혹은 오른쪽으로 한 방향으로 하나씩만 갖는다.

 

이진 트리(binary tree)

각 노드가 최대 두 개의 자식을 갖는 트리이며, 모든 트리가 이진 트리는 아니다.

 

이진 탐색 트리

순서화된 이진 트리이며, 노드의 왼쪽 자식은 부모의 값보다 작은 값을 갖으며 노드의 오른쪽 자식은 부모 값보다 큰 값을 갖는다.

 

이진 힙(최소 힙과 최대 힙)

이진 트리를 사용하는 대표적인 예시로써 최소 힙과 최대 힙 두가지가 존재한다.

최소 힙(Min Heap)

트리 마지막 단계에서 오른쪽 부분을 뺀 나머지 부분이 가득 채워져 있는 완전 이진 트리이며, 각 노드의 원소가 자식들의 원소보다 작다.

 

즉 루트 노드가 가장 작은 최소 값을 갖고있으며, 리프 노드가 가장 큰 트리 구조이다.

 

최대 힙(Max Heap)

원소가 내림차순으로 정렬되어 있다는 점으로 최소 힙과 다르다.

 

루트 노드가 모든 노드의 값들 중 최대 값을 갖고있다.

 

그래프와 트리의 차이점