[DataStructure] 트리(Tree)

트리란

자료구조에서 트리(Tree)는 계층적인 구조를 갖는 비선형 자료구조이다. 트리는 노드(Node)들로 구성되며, 이들 간에 부모-자식 관계가 있다. 최상위 노드를 루트(Root)라고 하고, 각 노드는 0개 이상의 자식 노드를 가질수 있다. 

• 노드(node)들과 노드들을 연결하는 간선(edge)들로 구성되어 있다.
• 그래프(Graph)와 가장 큰 차이로는 트리에는 사이클(cycle)이 존재할 수 없다.
• 노드들은 특정 순서로 나열될 수도 있고 그럴 수 없을 수도 있다.
• 각 노드는 부모 노드로의 연결이 있을 수도 있고 없을 수도 있다.
• 각 노드는 어떤 자료형으로도 표현 가능하다.

이미지 출처

https://gmlwjd9405.github.io/2018/08/12/data-structure-tree.html

[자료구조] 트리(Tree)란 - Heee's Development Blog

 

트리 용어 정리

1. 루트(Root): 트리의 최상위 노드를 의미한다. 모든 다른 노드는 루트로부터 어떤 경로로든 접근할 수 있다.
2. 노드(Node): 트리의 구성 요소로, 데이터와 부모-자식 관계를 가진다. 각 노드는 데이터와 연결된 다른 노드들로 구성된 트리의 일부이다.
3. 부모(Parent): 트리에서 어떤 노드의 바로 위에 위치한 노드를 부모 노드라고 한다. 부모 노드는 자식 노드들을 가질 수 있다.
4. 자식(Children): 트리에서 어떤 노드 아래에 위치한 노드들을 자식 노드라고 한다. 노드는 0개 이상의 자식을 가질 수 있다.
5. 형제(Siblings): 같은 부모를 가지는 노드들을 형제 노드라고 한다. 부모 노드의 자식들은 서로 형제 관계에 있다.
6. 잎(Leaf) 또는 말단 노드(Leaf Node): 자식을 가지지 않는 노드를 잎 노드라고 한다. 즉, 말단에 위치하는 노드를 의미한다.
7. 가지(Branch): 자식을 가지는 노드를 가지 노드 또는 가지라고 한다. 루트와 잎 노드는 가지가 아니다.
8. 서브트리(Subtree): 트리에서 특정 노드와 해당 노드의 모든 자손 노드로 이루어진 부분 트리를 서브트리라고 한다. 트리는 서브트리들의 집합으로 구성된다.
9. 높이(Height): 트리에서 노드의 깊이(depth) 중 가장 큰 값을 해당 트리의 높이라고 한다. 루트의 깊이를 0으로 설정하는 경우가 일반적이다.
10. 깊이(Depth): 트리에서 루트로부터 특정 노드까지의 경로의 길이를 해당 노드의 깊이라고 한다. 루트의 깊이는 0으로 시작한다.

 

트리의 특징

• 계층적 구조: 트리는 계층적인 구조를 가지며, 노드 간에 부모-자식 관계가 있습니다. 각 노드는 바로 위에 있는 하나의 부모 노드와 0개 이상의 자식 노드를 가질 수 있습니다. 이러한 계층 구조로 인해 데이터의 상위 및 하위 관계를 표현할 수 있습니다.
• 단일 루트: 트리는 하나의 최상위 노드인 루트(Root)를 가집니다. 루트는 다른 모든 노드에 대한 진입점이며, 트리의 시작점입니다.
• 가지와 잎: 트리의 노드는 가지(Branch)와 잎(Leaf)으로 구분됩니다. 가지는 하나 이상의 자식 노드를 가지는 노드를 의미하며, 잎은 자식 노드가 없는 말단 노드를 의미합니다.
• 순환 구조 없음: 트리는 순환 구조가 없습니다. 즉, 어떤 경로를 따라 이동해도 같은 노드에 도달할 수 없습니다. 이는 한 노드가 자신의 조상이 될 수 없다는 의미입니다.
• 단일 부모: 각 노드는 하나의 부모 노드만을 가집니다. 부모 노드는 자식 노드를 관리하고, 자식 노드는 부모 노드에 대한 참조를 유지합니다.
• 유연한 크기: 트리의 크기는 동적으로 변할 수 있습니다. 노드를 추가하거나 삭제함으로써 트리의 구조와 크기를 조절할 수 있습니다.
• 분할 가능한 서브트리: 트리는 분할 가능한 서브트리(Subtree)로 구성됩니다. 트리의 일부인 서브트리는 독립적인 트리 구조로 간주할 수 있습니다.

 

 

참고

https://gmlwjd9405.github.io/2018/08/12/data-structure-tree.html

[자료구조] 트리(Tree)란 - Heee's Development Blog