트리(Tree) 기본 구조와 핵심 개념 정리

1. 트리(Tree)란 무엇인가?

트리는 **노드(Node)**들의 집합으로 구성된 비선형 자료구조이다.
각 노드는 하나의 값(value)과 여러 개의 자식 노드(child nodes)에 대한 **레퍼런스(참조)**를 가진다.

트리의 특징

루트(Root): 최상단에 위치한 하나의 노드
사이클 없음: 어떤 경로로도 다시 자신에게 돌아올 수 없다.
부모-자식 관계: 각 자식 노드는 오직 하나의 부모 노드만 가진다.
계층적 구조: 데이터가 순차적으로가 아닌 계층적으로 저장된다.
재귀적 성질: 각 노드 자체가 또 다른 서브트리(subtree)를 구성할 수 있다.

2. 트리 기본 용어 정리

용어	설명
간선(Edge)	노드와 노드를 연결하는 선. 구현 관점에서는 레퍼런스(포인터) 의미.
루트 노드(Root Node)	트리의 가장 최상단에 있는 노드. 오직 하나 존재.
자녀 노드(Child Node)	어떤 노드로부터 이어진 하위 노드들.
부모 노드(Parent Node)	자녀 노드를 가지는 노드. 위 사진 - 2,5,9,6,11
형제 노드(Sibling Node)	같은 부모를 공유하는 노드들. 위 사진 - {8,1,4} , {6,7} , {5,9}
조상 노드(Ancestor Node)	부모를 거슬러 올라가면서 만나는 모든 노드들. 위 사진 - 8의 조상 노드 - 11,9,2
자손 노드(Descendant Node)	어떤 노드의 자녀와 그 자녀의 자녀까지 모두 포함. 위 사진 - 9의 자손 노드 - 11,8,1,4
내부 노드(Internal Node)	자녀 노드를 가지고 있는 노드. 위 사진 - 2,5,9,6,11
외부 노드(External Node, Leaf Node)	자녀 노드가 없는 노드. (= 리프 노드) 위 사진 - 3,7,8,1,4
경로(Path)	한 노드에서 다른 노드까지 연결된 노드들의 연속. 위 사진 - 2에서 7 경로 : 2-5-7
경로 길이(Path Length)	경로를 따라 이동할 때 지나야 하는 간선(Edge) 수. 위 사진 - 2에서 7 경로 길이 :3 , 2에서 3 경로 길이 :4
노드의 높이(Node Height)	해당 노드에서 가장 먼 리프 노드까지의 경로 길이. 위 사진 - 5의 높이 :2 , 리프의 노드의 높이 : 0
트리의 높이(Tree Height)	루트 노드의 높이. 트리에서 가장 먼 리프까지의 경로 길이. 위 사진 - 트리 높이 : 3
노드의 깊이(Node Depth)	루트 노드에서 특정 노드까지 이동한 간선 수. 위 사진 - 11의 깊이 :2 , 루트 노드의 깊이 : 0
트리의 깊이(Tree Depth)	트리에서 가장 깊게 위치한 노드의 깊이. 위 사진 - 트리 깊이 :3 , 트리 높이 = 트리 깊이
노드의 차수(Node Degree)	해당 노드가 가진 자녀 노드의 수. 위 사진 - 11의 차수 :3 , 3의 차수 : 0
트리의 차수(Tree Degree)	트리 전체 노드 중 가장 높은 차수. 위 사진 - 트리의 차수 : 3
두 노드 사이 거리(Distance)	두 노드를 연결하는 최단 경로상의 간선 수. 위 사진 - Distance(9,8) : 2 , Distance(3,8) : 6)
노드의 레벨(Level)	루트에서 몇 번 간선을 거쳐 도달했는지를 나타내는 수. 위 사진 - 루트 노드의 레벨 : 0 , 5 노드의 레벨1 , 11 노드 레벨 2
트리의 폭(Tree Width)	임의의 동일 레벨에 존재하는 노드의 수 중 최대값. 위 사진 - level 2의 width : 3
노드의 크기(Node Size)	해당 노드와 모든 자손 노드 수의 합. 위 사진 - 9의 크기 : 5 , 5의 크기 :4
트리의 크기(Tree Size)	트리 전체에 존재하는 노드 수.
서브트리(Subtree)	하나의 노드와 그 노드의 모든 자손 노드로 구성된 트리.