트리(tree)와 이진트리(binary tree)
concepts
1. TREE
- 모양이 뒤집어 놓은 나무와 같다고 해서 이름 붙혀짐
- 계층적인 구조를 표현할 때 사용할 수 있는 자료구조
- "루트노드를 제외한 모든 노드는 단 하나의 부모노드만을 가진다"
● 임의의 노드에서 다른 노드로 가는 경로(path)는 유일하다.
● 회로(cycle)가 존재하지 않는다.
● 모든 노드는 서로 연결되어 있다.
● 엣지(edge)를 하나 자르면 트리가 두 개로 분리된다.
● 엣지(edge)의 수 |E| 는 노드의 수 |V|에서 1을 뺀 것과 같다.
- 노드(node) = 검정색 동그라미(데이터가 담김)
- 엣지(edge) = 노드와 노드 사이를 이어주는 선
- 경로(path) = 인접한 노드들로 이뤄진 시퀀스, 경로의 길이는 경로에 속한 엣지의 수
- 트리의 높이(height) = 루트노드에서 말단 노드에 이르는 가장 긴 경로의 엣지 수(최댓값)
- 레벨(level) = 트리의 특정 깊이를 가지는 노드의 집합
- 잎새노드(leaf node) = 자식노드가 없는 노드
- internal node = 잎새노드를 제외한 노드
- 루트노드(root node) = 부모노드가 없는 노드(최상위 노드)
- 깊이(depth) = 루트 노드부터의 거리
- 크기(size) = 트리에 포함된 모든 노드의 개수
- 차수(degree) = 각 노드의 (자식 방향) 간선 개수
2. Binary Search Tree(이진 탐색 트리)
- 자식노드가 최대 두개인 노드들로 구성된 트리
- 왼쪽 자식 노드 < 부모 노드 < 오른쪽 자식 노드
- 정이진트리, 완전이진트리, 균형이진트리가 있다.
정이진트리
-모든 레벨에서 노드들이 꽉 채워진 이진트리
-노드수 (n) = 2^n+1 - 1 ex) n = 5 = 2^5 -1 = 31
-잎새노드 = 노드/2를 반올림 한값 ex) 31/2 반올림 = 16
완전이진트리
- 마지막 레벨을 제외한 모든 레벨에서 노드들이 꽉 채워진 이진트리
균형이진트리
- 모든 잎새노드의 깊이 차이가 많아야 1인 트리
- 예측 가능한 깊이 (predictable depth)를 가진다
- 노드가 n개인 균형이진트리의 깊이는 log n을 내림한 값이 된다.
3. 트리의 순회 (Tree Treversal)
- 트리 자료구조에 포함된 노드를 특정한 방법으로 한 번씩 방문하는 방법
- 트리의 정보를 시각적으로 확인 할 수 있다
트리 순회 방법
● 전위 순회(pre-order traverse) : 루트를 먼저 방문 : a → b → d → e → c → f
● 중위 순회(in-oreder traverse) : 왼쪽 자식을 방문한 뒤에 루트를 방문 : d → b → e → a → f → c
● 후위 순회(post-order traverse) : 오른쪽 자식까지 방문한 뒤에 루트를 방문 : d → e → b → f → c → a