알고리즘 개념[실전] - 트리

트리(Tree) 는 노드와 에지로 연결된 그래프의 특수한 형태입니다.

트리의 특징

• 순환 구조를 지니고 있지 않고, 1개의 루트 노드가 존재.
• 루트 노드를 제외한 노드는 단 1개의 부모 노드를 갖음.
• 트리의 부분 트리 역시 트리의 특징과 동일함.
• 트리 내에 또 다른 트리가 재귀적으로 존재하는 자료구조.
• 노드가 n개인 트리는 항상 n-1개의 간선을 가짐.

트리의 구성요소

• 노드(Node) : 데이터의 index와 value를 표현하는 요소
• 에지(Edge) : 노드와 노드의 연결 관계를 나타내는 선
• 루트 노드(Root) : 트리에서 가장 상위에 존재하는 노드
• 부모 노드(Parent Node) : 두 노드 사이의 관계에서 상위 노드에 해당하는 노드
• 자식 노드(Child Node) : 두 노드 사이의 관계에서 하위 노드에 해당하는 노드
• 리프 노드(Leaf Node) : 트리에서 가장 하위에 존재하는 노드(자식 노드가 없는 노드)
• 서브 트리(Sub-tree) : 진짜 트리에 속한 작은 트리
• 형제 노드(Sibling Node) : 같은 부모를 가지는 노드
• 깊이(Depth) : 루트에서 해당 노드까지의 간선(에지)의 수
• 높이(Height) : 어떤 노드에서 리프 노드까지의 가장 긴 경로의 간선의 수.