[자료구조] 트리 (Tree)

트리(Tree)의 개념

트리(Tree)는 비선형 자료구조, 계층적 그래프의 한 종류이다.
트리는 노드들의 집합으로, 노드들은 Edge로 이어져 있다.

트리는 하나의 루트 노드를 갖는다.
루트 노드는 0개 이상의 자식 노드를 갖는다.
자식 노드는 0개 이상의 자식노드를 갖으며, 이는 하위 자식노드들에도 똑같다.

트리의 특징

여러 노드가 한 노드를 가리킬 수 없다.
노드 사이에 Cycle이 존재하지 않는다.
서로 다른 두 노드의 연결이 오직 한 개(Edge)뿐이다.

트리와 관련된 용어

Tree

노드 (Node) : 트리의 구성 요소로, 값(value/key)과 자식노드를 가지고 있다.
엣지 (Edge) : 부모 노드와 자식 노드를 연결하는 연결선. 하나의 노드는 하나의 부모 노드를 갖고 있다.
루트 노드 (Root Node) : 가장 상위에 있는 노드로, 부모 노드를 갖지 않으며, 하나의 트리에 오직 하나의 루트 노드를 갖는다.
단말 노드 (Leaf Node) : 가장 하위에 있는 노드로, 자식 노드를 갖지 않는다.
내부 노드 (Internal) : 단말 노드가 아닌 모든 노드
부모 (Parent) : 부속 트리(Sub-tree)를 가지는 노드, 자식 노드를 갖고 있는 노드
자식 (Child) : 부속 트리에서 부모에 속하는 노드
형제 (Sibling) : 같은 부모 노드를 갖는 노드
조상 (Ancestor) : 노드의 모든 부모 노드의 집합 (현재 노드의 부모 노드, 부모의 부모 노드….)
자손 (Descendent) : 노드의 부속 트리에 있는 모든 하위 노드들 (현재 노드의 자식 노드, 자식 노드의 자식 노드, …)
깊이 (Depth) : 루트 노드에서 현재 노드 사이의 Edge의 개수
레벨 (Level) : 루트 노드로부터의 깊이 (루트 노드 = 1), level = depth + 1
트리에서 특정 깊이를 가지는 노드의 집합
높이 (Height) : 트리의 최대 레벨
노드의 차수 (Degree) : 하위 트리 개수, 노드가 가진 가지(자식)의 수
트리의 차수 (Degree of Tree) : 트리의 최대 차수

트리의 종류

트리의 종류는 굉장히 많다. 따라서 오늘은 간략하게 트리 종류의 이름만 간략하게 다룰 것이다.
각각의 트리는 다른 포스트들에서 자세히 알아보도록 하자 o,<

트리는 가장 크게 이진 트리(Binary Tree)와 Non-Binary Tree로 나눌 수 있다.
이진 트리는 자식 노드를 최대 2개 가질 수 있으며, Non-Binary Tree는 자식의 개수에 제한이 없는 트리를 말한다.
Non-Binary Tree의 대표적인 예로는 Trie가 있다.

이진 트리의 탐색 방법

오늘은 간략하게 설명하고, 른 포스트에서 더 자세히 다룰 예정이다.

전위 (preorder)

위 → 왼 → 오

중위 (inorder)

왼 → 위 → 오

후위 (postorder)

왼 → 오 → 위

해당 순서로 트리의 단말 노드까지 간 후 다음 순서로 이동한다.

이진 트리의 종류

이진 트리 (Binary Tree) vs. 이진 탐색 트리 (Binary Search Tree)
이진 탐색 트리는 특정한 규칙/순서를 가지고 노드가 구성된다.
균형 이진 트리 (Balanced Binary Tree) vs. 비균형 이진 트리 (Unbalanced Binary Tree)
균형 트리는 각각의 모든 노드가 가지는 자식 노드의 깊이가 1이상 차이나지 않는 이진 트리를 말한다.
완전 이진 트리 (Complete Binary Tree) vs. 전 이진 트리 (Full Binary Tree) vs. 포화 이진 트리 (Perfect Binary Tree)
- 완전 이진 트리 (Complete Binary Tree) : 마지막 레벨을 제외하고 모든 레벨이 자식이 2개이며, 마지막 레벨에서 자식 노드가 채워질 때 왼쪽 노드부터 채워진다.
- 전 이진 트리 (Full Binary Tree / Strictly Binary Tree) : 모든 노드가 자식이 0개이거나 2개인 트리
- 포화 이진 트리 (Perfect Binary Tree) : 모든 내부 노드가 2개의 자식 노드를 가지며, 깊이가 동일한 트리

자료구조