📚 트리 구조

데이터 사이의 계층 관계를 표현하는 자료구조

관련 용어

• 루트 (Root)
  트리의 가장 위쪽에 있는 노드로, 트리 내에 1개만 존재한다.

• 리프 (Leaf)
  트리의 가장 아래쪽에 있는 노드로, 단말 노드, 외부 노드라고도 부른다.

• 비단말 노드 (Non-terminal node)
  리프를 제외한 노드(루트 포함)로, 내부 노드라고도 한다.

• 자식 (Child)
  어떤 노드와 가지가 연결되었을 때 아래쪽 노드를 자식이라고 한다.

• 부모 (Parent)
  어떤 노드와 가지가 연결되었을 때 가장 위쪽에 있는 노드를 부모라고 한다. 노드의 부모는 하나뿐이다.

• 형제 (Sibling)
  부모가 같은 노드를 형제라고 한다.

• 조상 (Ancestor)
  어떤 노드에서 위쪽으로 가지를 따라가면 만나는 모든 노드를 조상이라고 한다.

• 자손 (Descendant)
  어떤 노드에서 아래쪽으로 가지를 따라가면 만나는 모든 노드를 자손이라고 한다.

• 레벨 (Level)
  루트에서 얼마나 멀리 떨어져 있는지 나타내는 것이 레벨이다. 가장 위쪽에 있는 루트의 레벨은 0이고, 가지가 하나씩 아래로 뻗어 내려갈 때마다 레벨이 1씩 증가한다.

• 차수 (Degree)
  각 노드가 갖는 자식의 수를 차수라고 한다. 모든 노드의 차수가 n 이하인 트리를 n진 트리라고 한다.

• 높이 (Height)
  루트에서 가장 멀리 있는 리프까지의 거리, 곧 리프 레벨의 최댓값을 높이라고 한다. (= 루트를 제외한 리프 레벨 수)

• 서브트리 (Subtree)
  어떤 노드를 루트로 하고, 그 자손으로 구성된 트리를 서브트리라고 한다.

• 빈 트리 (None tree)
  노드와 가지가 전혀 없는 트리를 빈 트리 또는 널 트리라고 한다.

순서 트리와 무순서 트리

형제 노드의 순서 관계가 있는지에 따라

• 형제 노드의 순서 관계가 존재하면 순서 트리,
• 순서를 구별하지 않으면 무순서 트리
  라고 한다.

순서 트리 검색

너비 우선 탐색 (Breadth-first search)

폭 우선 검색, 가로 검색, 수평 검색이라고도 한다.
너비 우선 검색은 낮은 레벨부터 왼쪽에서 오른쪽으로 검색하고, 한 레벨에서 검색을 마치면 다음 레벨로 내려가는 방법이다.

깊이 우선 탐색 (Depth-first search)

세로 검색, 수직 검색이라고도 한다.
깊이 우선 탐색은 리프에 도달할 때까지 아래쪽으로 내려가면서 검색하는 것을 우선으로 하는 방법이다.
리프에 도달해서 더 이상 검색할 곳이 없으면 일단 부모 노드로 돌아가고 그 뒤 다시 자식 노드로 내려간다.

• 전위 순회 : 부모 > 왼쪽 자식 > 오른쪽 자식
• 중위 순회 : 왼쪽 자식 > 부모 > 오른쪽 자식
• 후위 순회 : 왼쪽 자식 > 오른쪽 자식 > 부모

📚 이진 트리와 이진 검색 트리

이진 트리

노드가 왼쪽 자식과 오른쪽 자식만을 갖는 트리를 이진 트리라고 한다. 이때 두 자식 가운데 하나 또는 둘 다 존재하지 않는 노드가 있어도 상관없다.

이진 트리 특징

• 왼쪽 자식과 오른쪽 자식을 구분한다.
• 왼쪽 자식을 루트로 하는 서브트리를 왼쪽 서브트리라 하고, 오른쪽 자식을 루트로 하는 서브트리를 오른쪽 서브트리라고 한다.

완전 이진 트리

루트부터 아래쪽 레벨로 노드가 가득 차 있고, 같은 레벨 안에서 왼쪽부터 오른쪽으로 노드가 채워져 있는 이진 트리를 완전 이진 트리라고 한다.

높이가 k인 완전 이진 트리가 가질 수 있는 노드의 수는 최대 2^(k+1) -1개 이므로, n개의 노드를 저장할 수 있는 완전 이진 트리의 높이는 log n 이다.

이진 검색 트리

이진 검색 트리는 다음과 같은 조건을 만족한다.

• 왼쪽 서브트리 노드의 키값은 자신의 노드 키값보다 작아야 한다.
• 오른쪽 서브트리 노드의 키값은 자신의 노드 키값보다 커야 한다.

이진 검색 트리 특징

• 구조가 단순하다.
• 중위 순회의 깊이 우선 검색을 통해 노드 값을 오름차순으로 얻을 수 있다.
• 이진 검색과 비슷한 방식으로 아주 빠르게 검색할 수 있다.
• 노드를 삽입하기 쉽다.