[자료구조 공부기록] 5. Tree

 특징

• 비선형 자료구조입니다.
• 계층적인 구조를 가지고 있습니다.

 

장점 및 단점

 

1) 장점

• (특정 트리의 경우) 선형 자료구조에 비해서 탐색 및 검색이 빨라집니다. 

2) 단점

• (대부분의 경우) 트리가 편향된 경우 삽입, 삭제가 늦어질 수 있습니다.

 

---

트리의 구조 및 용어

관련 용어

• 노드(node): 트리를 구성하는 기본 원소
• 루트 노드(root node/root): 트리에서 부모가 없는 최상위 노드, 트리의 시작점
• 부모 노드(parent node): 루트 노드 방향으로 직접 연결된 노드
• 자식 노드(child node): 루트 노드 반대방향으로 직접 연결된 노드
• 형제 노드(siblings node): 같은 부모 노드를 갖는 노드들
• 리프 노드(leaf (node))/단말 노드(terminal node): 자식이 없는 노드
• 경로(path): 한 노드에서 다른 한 노드에 이르는 길 사이에 있는 노드들의 순서
• 길이(length): 출발 노드에서 도착 노드까지 거치는 노드의 개수
• 깊이(depth): 루트 경로의 길이
• 레벨(level): 루트 노드(level=1)부터 노드까지 연결된 링크 수의 합
• 높이(height): 가장 긴 루트 경로의 길이
• 차수(degree): 각 노드의 자식의 개수
• 트리의 차수(degree of tree): 트리의 최대 차수 = max [deg1, deg2,..., degn]
• 크기(size): 노드의 개수
• 너비(width): 가장 많은 노드를 갖고 있는 레벨의 크기

 

트리는 또한 여러 가지 종류를 가지고 있습니다. 

 

보통 저장 방법으로 나뉘는데 유명한 2개만 살펴보자면

 

• 이진트리(Binary Tree) : 각 노드의 차수가 2개씩 밖에 안 되는 트리입니다. 
  • 이진 탐색 트리(Binary Search Tree) : 부모 노드보다 큰 값을 가진 데이터는 오른쪽에 저장하고 작은 값은 왼쪽에 저장하는 가장 흔한 형태의 트리입니다. 

 

B-Tree

• B-트리(B-Tree) : 위 사진과 같이 차수가 2개로 정해진 트리가 아니라 여러 개를 가지고 있는 트리입니다. 다만 노드 안에 있는 데이터들은 정렬된 상태로 있습니다.

B-Tree 및 B+Tree에 대해 더 자세히 알고 싶으시다면 아래 링크를 참조해주세요.

https://zorba91.tistory.com/293

[MySQL] B-tree, B+tree란? (인덱스와 연관지어서)

 

---

트리는 비선형 자료구조다 보니 전체를 탐색하기 위한 방법도 선형 자료구조들과 달리 몇 가지가 더 있습니다.

 

 

중위 순회(In-order traversal)

1. 중위 순회 : 왼쪽 자식노드  -> 부모노드 -> 오른쪽 자식노드 순으로 탐색하는 방법입니다. 이진 탐색 트리처럼 왼쪽에 작은 값, 오른쪽에 큰 값을 저장했다면 전체 데이터가 오름차순으로 정렬되어 나옵니다.

 

 

전위 순회(Pre-order traversal)

2. 전위 순회 : 부모노드 -> 왼쪽 자식노드 -> 오른쪽 자식노드 순으로 탐색하는 방법입니다. 

 

 

 

후위 순회(Post-order traversal)

3. 후위 순회 : 왼쪽 자식노드 - > 오른쪽 자식노드 -> 부모노드 순으로 탐색하는 방법입니다.

 

 

레벨 순회(Level-order traversal)

4. 레벨 순회 : 위 그림과 같이 각 레벨 별 노드를 모두 탐색하고 다음 레벨로 탐색하는 방식입니다. 알고리즘 문제에서 흔히 보이는 BFS와 같은 방식입니다.

 

https://towardsdatascience.com/4-types-of-tree-traversal-algorithms-d56328450846

4 Types of Tree Traversal Algorithms

애니메이션 그림들 출처는 위 링크에 있습니다. 

 

각 순회들에 대하여 파이썬은 아니지만 코드로도 작성되있으니 한번 보셔도 좋을 듯 합니다.

 

---

파이썬 구현코드는 아래 링크를 참조하시면 좋습니다.

 

http://ejklike.github.io/2018/01/09/traversing-a-binary-tree-1.html

Eunji Kim @ CAU - 파이썬을 사용한 이진 트리와 순회 알고리즘 구현 (1)

 

언젠간 제 짧은 머리로도 구현을 다시..