오늘한 일
- 오늘의 코드카타
- 오후 알고리즘 세션: 그래프
- 알고리즘 문제 복습: 1,2,3 더하기
- (밍글데이)
Tree
Tree 자료구조: 나무를 아래로 엎어놓은 구조와 유사하다
- 비선형 구조로써, 노드와 간선을 가지는 자료구조를 말한다
- 포함범위: 이진탐색트리 < 이진트리 < 트리
- => 즉, 트리가 가장 포괄적인 자료구조이다. 이진탐색트리는 이진트리 중 탐색을 효율적으로 하기 위한 한 종류이며,(중위순회를 할 경우에) 가장 작은 수부터 가장 큰 수까지 차례대로 구할 수 있다. 따라서 이진탐색트리에서는 최솟값과 최댓값을 구하기 용이하다
이진탐색트리
- 이진탐색트리를 만족하지 않으면 이진트리(최대 자식 노드를 2개 가질 수 있는 트리)가 되며, 이진트리도 아니라면 그냥 트리라고 할 수 있다
- 이진트리의 종류
- 포화 이진트리: 모든 깊이가 포화상태인 이진트리
- 완전 이진트리: 노드 수가 n개 일 때, 1번부터 n개까지 노드가 있는 이진트리
- 편향 이진트: 한쪽 방향으로만(왼or오) 자식 노드를 갖는 이진트리
- 트리의 순회방법
- 전위 순회(preorder, ↓ ): (루트)/왼쪽 자식/오른쪽 자식
- 중위 순회(inorder, → ): 왼쪽 자식/(루트)/오른쪽 자식
- 후위 순회(postorder, ↑ ): 왼쪽 자식/오른쪽 자식/(루트)
- 따라서 아래 트리에서 각 순회의 결과는 다음과 같다
- 전위 순회한 결과: ABDHIEJCFG
- 중위 순회한 결과: HDIBEJAFCG
- 후위 순회한 결과: HIDJEBFGCA
- 트리 용어
- 노드(Node)
- 트리의 기본 구성 단위.
- 각 노드는 키/값을 가지며, 하위 노드에 대한 포인터를 가짐
- A,B,C,D,E,F,G,H,I,J
- 간선(Edge)
- 트리의 기본 구성 단위
- 노드와 노드 간의 연결선
- 루트 노드(Root node)
- 부모 노드(Parent node)
- 자식 노드를 가진 노드
- DHI의 서브트리에서 부모 노드는 D
- 자식 노드(Child node)
- 부모 노드의 하위 노드
- DHI의 서브트리에서 자식 노드는 H,I
- 형제 노드(Sibling node)
- 같은 부모 노드를 가지는 노드
- H와 I, F와 G는 같은 부모를 가지는 형제 노드
- 리프 노드(Leaf node)
- 자식 노드가 없는 말단 노드
- H,I,J,F,G
- 가지 노드(Branch node)
- 자식 노드를 하나 이상 가진 노드
- A,B,C,D,E
- 깊이(Depth)
- 루트 노드에서 어떤 노드까지의 간선(Edge) 수
- 루트노드의 깊이는 0이고, J노드의 깊이는 3임
- 높이(Height)
- 어떤 노드에서 리프 노드까지 가장 긴 경로의 간선(Edge)
- 리프 노드의 깊이는 0이며, A노드의 높이는 3임
- 레벨(Level)
- 루트에서 어떤 노드까지의 간선(Edge) 수
- 보통은 루트 노드가 있는 층을 level 0으로 표시함
- 레벨에 따라 각기 부모 노드와 자식 노드가 달라짐
