9. 트리(Tree)
'계층'적인 구조를 가지는 비선형 자료구조로, 노드(Node)들의 집합으로 이루어짐.
트리는 하나의 루트(Root) 노드를 가지며, 루트 노드로부터 다른 노드들을 연결하는 가지(Edge)로 구성된다.
또한, 회로(Cycle)를 만들지 않는 것이 특징이다.
9-1. 용어
트리(Tree):
비선형의 자료구조로, '나무'와 같은 생김새라서 Tree라는 이름이 붙여짐.
노드(Node):
트리의 구성 요소. 각 노드는 데이터를 저장하고 있는 단위로서, 계층 구조에서 트리의 구성원으로 존재함.
루트(Root):
트리의 맨 위에 있는 노드.
전체 트리구조에 접근하기 위해 기억할 첫 번째 노드.
부모 노드가 없는 유일한 노드.
리프(Leaf):
트리의 가장 아래에 있는 노드
자식 노드가 하나도 없는 노드
내부 노드(Internal Node):
루트와 리프가 아닌 나머지 노드.
부모와 자식이 있는 중간 노드.
부모 노드(Parent Node):
어떤 노드의 상위 레벨(계층)에 연결된 노드.
자식 노드(Child Node):
어떤 노드의 하위 레벨(계층)에 연결된 노드.
형제,자매 노드(Sibling, Brother Node):
동일한 부모 노드를 가진 노드
자손 노드(Descendent Node):
특정 노드에서 계층적으로 연결되어 하위에 존재하는 모든 노드.
조상 노드(Ancestor Node):
특정 노드에서 루트 노드까지의 경로 상에 있는 모든 부모들.
레벨(Level):
최상위 노드를 Level 0으로 했을 때, 하위 가지(Branch)로 연결된 경로의 길이.
루트 노드(level 0)부터 특정 노드까지 연결된 링크(Link, =엣지) 수의 합.
깊이(Depth):
루트에서 특정 노드까지 도달하기 위한 경로의 수.
링크 수를 기준으로 함.
높이(Height):
루트에서 가장 깊은 리프 노드까지의 깊이 + 1
차수(Degree):
각 노드가 가진 자식 노드의 갯수.
계수(Order):
자식 노드의 차수 중 최대 차수.
사이즈(Size):
특정 노드 자신을 포함한 모든 자손 노드의 갯수.
트리의 사이즈 = 루트 노드의 사이즈
서브 트리(Sub Tree):
트리 내에서 특정노드를 루트노드로 하는 개념적인 트리 구조
재귀적인 구조.
'마트료시카'를 연상.
9-2. 성질
노드가 N개일 경우, 링크(엣지)는 N-1개이다.
특정 노드와 특정 노드 사이의 경로는 항상 1개이다.
9-3. 종류
형태(목적)
1) 탐색 : 이진탐색트리, B-트리, AVL트리, 레드블랙트리 등
2) 힙(최대최소연산) : 이진힙, 이항힙 등
3) 트라이(문자열) : C-트라이, 해시트리, 기수트리 등
구조
1) 이진 트리 (Binary Tree):
각 노드가 최대 두 개의 자식 노드를 가지는 트리 구조.
각 노드는 왼쪽 자식과 오른쪽 자식을 가리키며 자식이 없는 경우, 해당 자식 위치는 NULL로 표시됨.
이진 트리는 데이터를 계층적으로 구조화하고, 탐색, 삽입, 삭제 등의 연산을 수행하는 데 사용됨.
주로 검색 알고리즘, 트리 기반 알고리즘, 트리 자료구조 등에서 활용됨.
2) 완전 이진 트리 (Complete Binary Tree):
마지막 레벨을 제외한 모든 레벨에서 노드들이 완전히 채워진 이진 트리.
마지막 레벨에서는 노드가 왼쪽부터 순서대로 채워져야 함.
완전 이진 트리는 배열 등의 선형 자료구조로 효율적으로 변환할 수 있으며, 힙 구조를 구현하는 데 주로 사용됨.
또한 이진 트리에서 연산의 효율성을 높일 수 있음.
3)다진 트리 (Multinary Tree / K-ary Tree):
각 노드가 최대 K개의 자식 노드를 가지는 트리 구조로, K는 임의의 양수. (이진 트리는 K=2인 특수한 경우의 다진 트리임.)
다진 트리는 이진 트리 이외의 자식 노드를 가지는 경우에 사용됨.
계층 구조를 표현하거나 분류 알고리즘 등에서 활용될 수 있음.
4) 다항 트리 (Polynomial Tree):
각 노드가 여러 개의 자식 노드를 가지는 트리 구조이며, 각 자식 노드는 동일한 부모 노드로부터 파생됨.
다항 트리는 다항식을 계산하고 표현하는 데 사용됨.
다항식의 항들을 계수와 지수로 나타내며, 이를 트리 형태로 구성하여 계산하거나 다항식 연산을 수행할 수 있음.
