비선형 자료구조

데이터가 특정한 형태를 띄고 있는 자료구조

1. 트리 (Tree)

특징

값을 가진 노드 (Node) 와 노드들을 연결해주는 간선 (Edge) 로 이루어짐

자료들 사이의 계층적 관계를 나타내는데 사용하는 자료구조

부모(Parent) - 자식(Child) 관계로 표현됨

루트 노드(Root Node) 가 존재함 => 트리는 반드시 1개 이상의 노드를 가짐

사이클(Cycle) 이 존재 할 수 없음 (그래프와의 차이점)

트리의 부분 트리 (Sub Tree) 또한 트리 구조를 따름

모든 노드는 자료형으로 표현이 가능

루트 노트에서 특정 노드로 가는 경로는 유일함

노드의 개수가 N 개 인 경우 간선의 개수는 N - 1 개 존재함

용어

루트 노트(Root Node) : 트리의 최상위 노드, Unique

부모 노드(Parent Node) : 부모 - 자식 관계에서 상위 계층의 노드

자식 노드(Child Node) : 부모 - 자식 관계에서 하위 계층의 노드

형제 노드 : 부모가 동일한 노드

조상 노드 : 해당 노드의 부모 노드에서 루트 노드까지 가는 경로에 존재하는 모든 노드

후손 노드 : 해당 노드를 루트로 하는 부분 트리에 있는 모든 노드

내부 노드(Internal/Nonterminal Node) : 자식이 있는 노드

외부 노드(잎새 노드, 단말 노드, Leaf / External / Terminal Node) : 자식이 없는 노드

깊이(Depth) : 루트 노드에서 해당 노드까지 도달하는데 사용하는 간선의 개수 (루트 노드의 깊이는 0)

레벨(Level) : 노드의 깊이 + 1

높이(Height) : 루트 노드에서 해당 노드까지 도달하기 위해 지나는 정점의 개수

• 트리의 높이 : 해당 트리 내 모든 노드의 높이 중 최댓값
• 트리의 높이 = 1 + Max(왼쪽 하위트리의 높이, 오른쪽 하위 트리의 높이)

노드의 차수(Degree) : 노드의 자식 수

• 트리의 차수 : 해당 트리 내 모든 노드의 차수 중 최댓값

균형(Balance) : 루트 노드를 기준으로 왼쪽 하위트리와 오른쪽 하위트리 사이의 높이 차이

• 균형 트리(Height Balanced Tree) : 균형의 차이가 1 이하인 트리
• 완전 균형 트리(Completely Height Balanced Tree) : 왼쪽, 오른쪽 하위 트리의 높이가 일치하는 트리

순회 방식

1. 전위 순회 (Pre Order)

각 루트를 순차적으로 먼저 방문하는 순회 방식 : 루트 -> 왼쪽 자식 -> 오른쪽 자식

위 예시에서의 전위 순회 : 1 → 2 → 4 → 8 → 9 → 5 → 10 → 11 → 3 → 6 → 13 → 7 → 14

2. 중위 순회 (In Order)

왼쪽 하위 트리 방문 후 루트를 방문하는 방식 : 왼쪽 자식 -> 루트 -> 오른쪽 자식

위 예시에서의 중위 순회 : 8 → 4 → 9 → 2 → 10 → 5 → 11 → 1 → 6 → 13 → 3 →14 → 7

3. 후위 순회 (Post Order)

왼쪽 하위 트리부터 모든 하위노드 방문 후 루트를 방문하는 방식 : 왼쪽 자식 -> 오른쪽 자식 -> 루트)

위 예시에서의 후위 순회 : 8 → 9 → 4 → 10 → 11 → 5 → 2 → 13 → 6 → 14 → 7 → 3 → 1

4. 레벨 순회 (Level Order)

루트부터 계층(Level) 별로 방문하는 방식

위 예시에서의 레벨 순회 : 1 → 2 → 3 → 4 → 5 → 6 → 7 → 8 → 9 → 10 → 11 → 13 → 14

시간 복잡도

노드 삽입 : $O(1)$
노드 삭제 : $O(1)$ (언어와 구현에 따라 시간 복잡도가 상이할 수 있음)
노드 검색 : $O(N)$

활용

• HTML DOM 트리
• 파일 시스템
• DBMS
• 검색 엔진

---

이진 트리 (Binary Tree)

특징

트리의 차수(Degree) 가 2 이하인 트리

• 아무런 노드가 없거나
• 가운데 노드를 중심으로 좌우로 나누어지면서 하위 트리 모두 이진 트리여야함

높이가 N 인 이진 트리의 최대 노드 개수는 $2^N-1$ 개

종류

1. 정 이진 트리 (Fully Binary Tree)

모든 노드의 차수가 0 또는 2인 이진트리

2. 포화 이진 트리 (Perfect Binary Tree)

정 이진트리에서 모든 말단 노드 (Leaf Node) 의 깊이가 같은 이진 트리

• 높이가 H 인 포화 이진 트리의 노드 개수는 $2^H-1$ 개
• 노드의 개수가 N 개인 포화 이진트리의 높이는 $log_2(N+1)$ 개
• 깊이가 D 인 포화 이진 트리의 외부 노드 개수는 $2^D$ 개

3. 편향 이진 트리 (Skewed Binary Tree)

연결 리스트처럼 한줄로 연결되어 있는 형태의 이진트리

이진 탐색 트리 (BST, Binary Search Tree)

이진 트리 중에서 탐색을 위해 고안된 트리
이진 탐색이 동작할 수 있도록 고안된, 효율적인 탐색이 가능한 자료구조

특징

• 왼쪽 자식 노드 < 부모 노드 < 오른쪽 자식 노드 의 관계 성립
  • 부모 노드보다 왼쪽 자식 노드가 작음
  • 부모 노드보다 오른쪽 자식 노드가 큼
  • “약하게 정렬되어 있다” 고 함
• 중복된 노드가 없어야함
  • 중복이 없어야 하는 이유?
    • 검색 목적 자료구조 → 중복 값이 있을 경우에 트리를 사용하여 굳이 속도를 느리게 할 필요가 없음
• 노드 N 에 대하여 왼쪽 하위트리와 오른쪽 하위트리 모두 이진 탐색트리임
• 중위순회(inorder) 방식을 통해 순회를 하여 정렬된 순서를 읽을 수 있음
  • 왼쪽 자식 노드 → 루트 노드 → 오른쪽 자식 노드

시간 복잡도

• 균형 트리 : $O(logN)$
• 편향 트리 : $O(N)$

삽입, 검색, 삭제 시간복잡도는 트리의 Depth 에 비례함

삭제의 3가지 경우

1. 자식이 없는 단말 노드일 경우 → 그냥 삭제
2. 자식이 1개인 노드일 경우 → 지워진 노드에 자식을 올림
3. 자식이 2개인 노드일 때 → 오른쪽 자식 노드에서 가장 작은 값 / 왼쪽 자식 노드에서 가장 큰 값 올림

---