[Data Structure] 트리

트리(Tree)는 데이터의 계층적인 관계를 표현하는 비선형 자료구조로 그래프(Graph)의 특별한 형태이다. 이진 트리, 이진 검색 트리, AVL 트리, 레드-블랙 트리, 힙 등 다양한 특수화된 형태의 트리가 존재하며  검색 알고리즘, 파일 시스템, 데이터베이스 등 다양한 분야에서 유용하게 활용된다.

 

 

트리의 표현

---

트리(Tree)의 표현

 

트리는 그래프의 특별한 형태로 다음과 같은 조건 만족해야 한다.

• 사이클(Cycle)이 없는 비순환 구조 (한 노드에서 출발하여 다시 자신으로 돌아오는 경로가 존재하지 않는다.)
• 하나의 루트(Root) 노드와 N개의 서브 트리(Sub Tree)로 구성
• 모든 노드는 하나의 부모(Parent) 노드만 가진다.
• 트리의 모든 노드를 순회하기 위해서는 반드시 루트(Root) 노드를 거쳐야한다.
• 노드가 N개인 트리는 반드시 N-1개의 간선을 갖는다. (추가적인 간선은 사이클을 형성하기 때문에 안된다.)

노드(Node)	트리를 구성하는 기본 요소로, 데이터와 하위 노드에 대한 참조로 구성
간선(Edge)	노드와 노드 사이를 연결하는 선으로, 노드에서 '하위 노드에 대한 참조'는 다른 노드로의 연결, 즉 간선을 의미
루트 노드(Root Node)	트리의 최상위에 위치한 노드로, 트리의 시작 지점 루트 노드는 상위 노드(부모 노드)를 가질 수 없다.
리프 노드(Leaf Node)	자식 노드를 가지지 않는 노드로, 말단 노드(Terminal Node)라고도 부른다.
부모 노드(Parent Node)	한 노드에  대하여 상위에 위치하는 노드
자식 노드(Child Node)	한 노드에 대하여 하위에 위치하는 노드
형제 노드(Sibling Node)	같은 부모 노드를 공유하는 노드들의 집합
깊이(Depth)	루트 노드에서 특정 노드까지 도달하기 위해 거쳐야 하는 간선의 개수
높이(Height)	루트 노드에서 가장 깊은 리프 노드까지의 깊이
레밸(Level)	루트 노드로부터의 깊이가 같은 노드들의 집합
차수(Degree)	노드의 자식 노드의 개수 트리의 차수는 자식 노드가 가장 많은 노드의 차수로 정의된다.
너비(Width)	같은 레벨에 있는 노드들의 수
크기(Size)	해당 노드를 포함한 모든 자식 노드의 개수
경로(Path)	한 노드에서 다른 노드로 이동할 때 거치는 노드들의 순서
거리(Distance)	한 노드에서 다른 노드까지의 최단 경로를 구성하는 간선의 개수

 

 

트리의 종류

---

[이진 트리 (Binary Tree)]

내용을 적어주세요.

 

[이진 탐색 트리 (Binary Search Tree)]

내용을 적어주세요.

 

[레드-블랙 트리 (Red-Balck Tree)]

내용을 적어주세요.

 

[AVL 트리 (Adelson-Velky and Landis Tree)]

내용을 적어주세요.

 

[힙 (Heap)]

내용을 적어주세요.

 

 

트리의 구현

---

트리를 구현하는 방법에는 N-Link 방식과 LCRS(Left Child-Right Sibling) 방식이 있다. 트리는 일반적으로 노드를 사용하여 구현되지만, 배열을 사용하는 경우도 있다. 하지만 각 노드가 임의의 수의 자식을 가질 수 있도록 하는 구현은 복잡할 수 있으며, 이러한 이유로 배열을 사용한 구현은 완전 이진 트리와 같은 특정 형태의 트리에서 주로 사용된다.

 

[N-Link 방식]

N-Link 방식의 표현

N-Link 방식은 각 노드가 자신의 자식 노드들을 직접 가리키는 포인터의 목록(배열 또는 리스트)을 가진다. 노드의 자식들을 직접적으로 관리하기 때문에 트리구조를 쉽게 이해하고 관리할 수 있다. 하지만 동적으로 노드를 추하거나 삭제할 때 포인터 목록의 관리가 복잡해 질 수 있다.

 

- 코드 삽입

 

 

[ LCRS(Left Child-Right Sibling) 방식]

LCRS 방식의 표현

LCRS 방식은 각 노드가 자신의 왼쪽 자식과 오른쪽 형제를 가리키는 두 개의 포인터만을 가진다. 모든 자식을 개별적으로 가리키는 대신 2개의 포인터만 가지기 때문에 구조가 단순하고, N-Link 방식에 비해 메모리 사용이 감소한다. 하지만 트리를 순회할 때 자식과 형제 관계를 따라가야 하기 때문에 N-Link 방식보다 복잡할 수 있다.

 

- 코드 삽입