[자료구조] 트리(Tree)

 

 

트리 ( Tree )

기본적으로 트리의 크기가 N개일 때, 전체 간선의 개수는 N-1개입니다.

 

 

트리는 계층적인 구조를 표한할 때 유용하게 사용할 수 있는 자료구조입니다.

 

 

 

[ 트리 관련 용어 설명 ]

 

루트 노드 (root node)	부모가 없는 최상위 노드입니다.
단말 노드 (leaf node)	자식이 없는 노드를 말합니다.
크기 (size)	트리에 포함된 모든 노드의 개수입니다.
깊이 (depth)	루트노드부터의 거리를 말합니다.
높이 (height)	깊이 중 최댓값을 의미합니다.
차수 (degree)	자식 방향의 간선갯수를 의미합니다.

 

 

 

 

 

이진 탐색 트리 ( Binary Search Tree )

 

 

왼쪽 자식 노드 < 부모 노드 < 오른쪽 자식 노드

 

 

이진 탐색이 동작할 수 있도록 고안된 효율적인 탐색이 가능한 자료구조입니다.

 

 

 

 

이진 탐색 트리의 탐색

 

 

탐색 테스트 케이스 : 37

 

37은 30보다 크기 때문에 오른쪽 간선을 탑니다. 
37은 48보다 작기 때문에 왼쪽 간선을 탑니다.

37을 만나서 탐색이 종료됩니다.


"이진 탐색 트리의 탐색은 이상적인 경우 O(log n)의 시간복잡도를 가집니다." ( 좌 우 밸런스가 잘 잡힌 경우 )

 

 

 

 

 

트리의 순회 ( Tree Traversal )

 

트리 자료구조에 포함된 노드를 한 번씩 장문하는 방법을 의미합니다.

1. 전위 순회 (pre-order traverse): 루트를 먼저 방문합니다.
2. 중위 순회 (in-order traverse): 왼쪽 자식을 방문한 뒤에 루트를 방문합니다.
3. 후위 순회 (post-order traverse): 오른쪽 자식을 방문한 뒤에 루트를 방문합니다.

 

 

 

A는 ROOT 노드 입니다.

 

 

 

 

전위 순회 pre-order	A B D E C F G
중위 순회 in-order	D B E A F C G
후위 순회 post-order	D E B G G C A