_03.algorithm_tree

트리(Tree) 자료구조

• 트리는 가계도와 같은 계층적인(hierarchy) 구조를 표현할 때 사용할 수 있는 자료구조
• 나무를 뒤집어 놓은 모양을 생각하면 됨

1. 트리 관련 용어

• root node: 부모가 없는 최상위 노드
  • 뒤집은 나무의 최상위는 나무의 뿌리. ROOT!!
• leaf node: 자식이 없는 노드
  • 뒤집은 나무의 최하위는 나뭇잎. LEAF!!
• size: 트리에 포함된 모든 node의 개수
• depth: root node부터의 거리
  • 친척들 촌수 셀 때 생각하면 됨
  • depth of root node = 0
• height: depth 중 최대값
• degree: 각 노드의 (자식 방향) 간선 개수
  • 몇개 자식이랑 연결 되어 있는지
  • 자식 두개랑 연결되어 있으면 2
• 트리의 크기가 N일 떄, 전체 간선의 개수는 N-1
  • 포크 생각하면 됨
  • 포크는 4개가 튀어 나와있지만 그 틈 사이는 3개

2. 이진 탐색 트리 (Binary Search Tree)

• 이진 탐색이 동작할 수 있도록 고안된 효율적인 탐삭이 가능한 자료구조 일종
• 이진 탐색트리 특징: 자식을 둘 때 나보다 작으면 왼쪽, 나보다 크면 오른쪽

탐색 과정

1. 루트 노드부터 탐색
2. 현재 노드와 찾는 원소를 비교
3. 찾는 원소가 루트보다 작으면 왼쪽 크면 오른쪽
4. 반복

3. 트리의 순회 (Tree Traversal)

• 트리 자료구조에 포함된 노드를 특정 방법으로 한번 씩 방문 하는 방법
  • 트리 정보를 시각적으로 확인 가능
• 대표적은 트리 순회 방법
  • 전위 순회 (pre-order traverse): 루트 먼저 방문
  • 중위 순회(in-order traverse): 왼쪽 자식을 방문한 뒤에 루트 방문
  • 후위 순회(post-order traverse): 오른쪽 자식을 방문한 뒤에 루트 방문