Tree

Tree란?

그래프의 여러 구조 중 단방향 그래프의 한 구조로,

하나의 뿌리로부터 가지가 사방으로 뻗은 형태가 나무와 닮아 있다고 해서 트리 구조라고 부릅니다.

용어정리

• 노드(Node) : 트리 구조를 이루는 모든 개별 데이터
• 루트(Root) : 트리 구조의 시작점이 되는 노드
• 부모 노드(Parent node) : 노드가 상하관계로 연결되어 있을 때 상대적으로 루트에서 가까운 노드
• 자식 노드(Child node) : 두 노드가 상하관계로 연결되어 있을 때 상대적으로 루트에서 먼 노드
• 리프(Leaf) : 트리 구조의 끝 지점이고, 자식 노드가 없는 노드

데이터가 바로 아래에 있는 하나 이상의 데이터에 무방향으로 연결된 계층적 자료 구조입니다.

데이터를 순차적으로 나열시킨 선형 구조가 아니라, 하나의 데이터 아래에 여러 개의 데이터가 존재할 수 있는 비선형 구조입니다.

트리 구조는 계층적으로 표현이 되고, 아래로만 뻗어나가기 때문에 사이클이 없습니다.

루트(Root)라는 하나의 꼭짓점 데이터를 시작으로 여러 개의 데이터를 간선(edge)으로 연결합니다

각 데이터를 노드(Node)라고 하며, 두 개의 노드가 상하 계층으로 연결되면 부모/자식 관계를 가집니다.

위 그림에서 A는 B와 C의 부모 노드(Parent Node)이고, B와 C는 A의 자식 노드(Child Node)입니다. 자식이 없는 노드는 나무의 잎과 같다고 하여 리프 노드(Leaf Node)라고 부릅니다.

깊이 (depth)

트리 구조에서는 루트로부터 하위 계층의 특정 노드까지의 깊이(depth)를 표현할 수 있음

루트 노드는 지면에 있는 것처럼 깊이가 0임

위 그림에서 루트 A의 depth는 0이고, B와 C의 깊이는 1입니다. D, E, F, G의 깊이는 2입니다.

레벨(Level)

트리 구조에서 같은 깊이를 가지고 있는 노드를 묶어서 레벨(level)로 표현할 수 있음

depth가 0인 루트 A의 level은 1임 depth가 1인 B와 C의 level은 2임 D, E, F, G의 레벨은 3임

같은 레벨에 나란히 있는 노드를 형제 노드(Sibling Node)라고 함

높이(Height)

트리 구조에서 리프 노드를 기준으로 루트까지의 높이(height)를 표현할 수 있음

리프 노드와 직간접적으로 연결된 노드의 높이를 표현하며,

부모 노드는 자식 노드의 가장 높은 height 값에 +1한 값을 높이로 가짐

트리 구조의 높이를 표현할 때에는 각 리프 노드의 높이를 0으로 놓음

위 그림에서 H, I, E, F, J의 높이는 0입니다. D와 G의 높이는 1입니다. B와 C의 높이는 2입니다.

이때 B는 D의 height + 1을, C는 G의 height + 1을 높이로 가집니다.

따라서, 루트 A의 높이는 3입니다.

서브 트리(Sub tree)

트리 구조의 root에서 뻗어 나오는 큰 트리의 내부에, 트리 구조를 갖춘 작은 트리를 서브 트리라고함

(D, H, I)로 이루어진 작은 트리도 서브 트리이고, (B, D, E)나 (C, F, G, J)도 서브 트리입니다.

Tree의 장점

효과적인 계층 구조 표현

Tree 자료 구조는 계층 구조를 나타내는 데에 효과적입니다.

예를 들어, 회사에서 조직도를 작성할 때 Tree 자료 구조를 활용하여 부서와 직원들 간의 계층 구조를 표현할 수 있습니다.

정렬과 탐색에 활용

Tree 자료 구조는 이진 탐색 트리, 힙(Heap) 등과 같은 다양한 형태로 사용될 수 있으며,

정렬과 탐색을 위한 알고리즘을 구현하는 데에도 사용됩니다.

삽입과 삭제가 쉬움

Tree 자료 구조는 노드의 삽입과 삭제가 쉽습니다.

이는 삽입 및 삭제 시에 해당 노드의 부모와 자식 노드만 수정하면 되기 때문입니다.

구조 파악이 용이

Tree 자료 구조는 시각화가 쉬우므로, 트리를 시각적으로 표현하여 이해하기 쉽습니다.

다양한 분야에서 활용

Tree 자료 구조는 데이터베이스, 알고리즘 등 다양한 분야에서 활용됩니다.

이는 Tree 자료 구조가 다양한 문제를 해결하기 위한 다양한 알고리즘의 기초가 되기 때문입니다.

관련 메서드

1. addChildNode(value): 주어진 값(value)을 가진 자식 노드를 현재 노드에 추가합니다.
2. removeChildNode(childNode): 주어진 자식 노드(childNode)를 현재 노드에서 제거합니다.
3. getParent(): 현재 노드의 부모 노드를 반환합니다.
4. getChildren(): 현재 노드의 모든 자식 노드를 반환합니다.
5. getValue(): 현재 노드의 값을 반환합니다.

6. isLeaf(): 현재 노드가 리프(leaf) 노드인지 여부를 확인합니다.

   리프 노드는 자식 노드를 갖지 않습니다.

7. traverse(): 트리를 순회하면서 노드를 방문하는 작업을 수행합니다.

   이 메서드는 전위(pre-order), 중위(in-order), 후위(post-order) 등 다양한 순회 방식을 구현가능