트리(Tree)란?

트리는 계층적인 구조를 가진 자료 구조입니다. 각 노드가 자식 노드를 가리키는 방식으로 구성됩니다.

트리는 데이터의 계층적 구조를 표현하는 데 사용되며, 파일 시스템, 조직도, DOM(Documenet Object Model) 등 다양한 상황에 사용됩니다.

1. 노드(Node):

   • 트리의 기본 단위로, 데이터와 다른 노드를 가리키는 참조(주로 자식 노드)를 포함합니다.

   • 예: 파일 시스템에서의 파일이나 폴더, 조직도에서의 직원

2. 루트 노드(Root Node):

   • 트리 구조의 최상단에 위치하는 노드입니다.

   • 이 노드는 부모가 없으며, 트리의 출발점입니다.

3. 자식 노드(Child Node):

   • 다른 노드(부모 노드)로부터 파생된 노드입니다.

   • 하나의 부모 노드는 여러 자식 노드를 가질 수 있습니다.

4. 부모 노드(Parent Node):

   • 하나 이상의 자식 노드를 가지고 있는 노드입니다.

5. 형제 노드(Sibling Node):

   • 동일한 부모 노드를 공유하는 노드들입니다.

6. 잎 노드(Leaf Node) / 단말 노드(Terminal Node):

   • 자식 노드가 없는 노드입니다.

   • 트리의 가장 아래쪽에 위치합니다.

7. 서브트리(Subtree):

   • 트리 내의 노드와 그 자손 노드들로 구성된 트리입니다.

8. 깊이(Depth):

   • 루트 노드로부터 특정 노드까지의 거리입니다.

9. 높이(Height):

   • 트리에서 가장 깊은 노드의 깊이입니다.

트리를 구현하는 기본적인 방법은 클래스와 객체를 사용하는 것입니다. 각 노드는 객체로 표현되며, 각 객체는 자식 노드에 대한 참조를 포함합니다.

1. 노드 클래스(Node Class):

   • 데이터와 자식 노드에 대한 참조를 저장합니다.

2. 트리 생성과 순회:

   • 루트 노드에서 시작하여 필요에 따라 노드를 추가하고, 순회 방법에 따라 트리를 탐색합니다.

트리의 구현은 트리의 종류와 사용 목적에 따라 다양하게 변형될 수 있습니다. 예를 들어, 이진 탐색 트리는 데이터의 삽입, 삭제, 검색에 특화되어 있으며, 균형 트리는 탐색 시간을 최적화하기 위해 사용됩니다.