1. 트리(Tree)의 개념과 용어
-
트리는 노드와 링크를 이용한 자료구조
-
연결 리스트와 사뭇 다름
1. 트리 구조
-
트리 구조는 우리 주변의 일상에서 쉽게 볼 수 있는 구조
-
한 가족의 계보를 나타내는 족보나 회사의 조직도 등을 보면 트리 구조 형태로 되어 있음
-
트리 구조는 노드와 노드를 연결하는 링크로 구성되어 있음
-
가장 상위에 있는 노드를 루트(root)라고 함
-
자신의 노드보다 상위에 있는 노드를 부모 노드(Parent Node)라고 함
-
자신의 노드보다 아래에 있는 노드를 자식 노드(Child Node)라고 함
-
최 하위 노드를 리프 노드(Leaf Node)라고 함
-
같은 부모 노드를 갖는 노드들의 사이를 형제 노드(Sibling Node)라고 함
-
트리 구조는 레벨(Level)과 높이(Height)가 존재
-
레벨은 루트 노드부터 해당 노드까지 경로를 찾아 오는데 방문한 총 노드의 수가 됨
-
트리 구조 내에서 가장 큰 레베을 그 트리 구조의 높이라고 함
-
트리 구조에서 부모 노드는 반드시 하나만 존재해야 함
-
부모 노드가 2개 이상 존재하면 그 구조는 트리 구조가 될 수 없음
트리를 재귀적인 표현으로 정의하면 다음과 같은 성질을 갖음
- 트리에는 루트 노드(Root Node)가 반드시 존재
- 루트 노드를 제외한 나머지 노드들은 여러 개의 노드들의 그룹으로 나뉠 수 있으며,
그 노드 그룹 역시 하나의 트리가 됨
2. 트리의 용어
차수
- 한 노드에 연결된 서브 트리의 개수를 차수라고 함
- 노드 A의 차수는 노드 A에 연결된 서브 트리가 모두 3개 이므로 3이 되며
노드 D의 차수는노드 D에 연결된 노드가 3개 이므로 3이 됨 - 이 중에서 차수가 2개 이하의 트리 구조를 특별히 이진트리(Binary Tree)라고 하며
일반적으로 많이 사용하는 트리 구조
단말 노드 == 터미널 노드 == 리프노드
- 트리의 가장 끝에 있는 노드를 말함
- 리프 노드는 E, J, K, L, H, I 가 됨
부모노드
- 현재의 노드에 연결되어 있는 바로 상위 노드를 부모 노드라고 함
- 트리 구조에서 루트 노드를 제외하고 모든 노드가 하나의 부모 노드를 가져야 함
- J의 부모노드는 F가 됨
자식노드
- 부모 노드의 반대의 개념
- 이진 트리의 경우 반드시 자식 노드의 수는 2개 이하가 되어야 함
- F의 자식노드는 J가 됨
형제노드
- 같은 부모 노드를 갖는 노드를 형제 노드라고 함
- G, H, I는 D를 부모로 둔 형제 노드
레벨
- 루트 노드를 레벨0으로하여 한 단계씩 내려올 떄마다 레벨이 1씩 증가
높이
- 트리의 최대 레벨 수를 트리의 높이(Height)라고 함
깊이
- 특정 노드까지의 경로의 길이를 깊이(Depth)라고 함
2. 이진 트리(Binary Tree)
- 자식 노드를 2개 이하만 갖는 트리
- 트리의 차수(Degree)가 2 이하인 트리
- 최대 2개 자식 노드를 갖는 트리구조이기 때문에 이 트리 구조의 이름은 이진 트리
1.이진 트리의 구조와 특성
- 이진 트리는 자식 노드가 2개만 존재하기 떄문에 구현이 간단하다는 장점이 있음
- 이진 트리는 형성된 형태에 따라 몇 가지 종류가 있음
2. 이진 트리의 종류
- 이진 트리는 생긴 모양으로 몇 가지 특이한 이진 트리가 존재
1. 정 이진 트리(full binary tree)
- 단말 노드 제외 모든 노드가 2개의 자식을 가진 트리
2. 포화 이진 트리(perfect binary tree)
- 모든 단말 노드의 깊이가 같은 정 이진 트리
3. 완전 이진 트리(complete binary tree)
- 마지막 레벨을 제외하고 모든 노드가 채워진 이진 트리
- 마지막 레벨의 노드들은 왼쪽으로 채워져 있고 마지막 레벨이 다 채워질 수도 있음
4. 균형 이진 트리(balanced binary tree)
- 모든 단말 노드의 깊이 차이가 많아야 1인 트리
- 균형 이진 트리는 예측 가능한 깊이를 가짐
5. 변질 트리(degenerate tree)
- 각각의 부모 노드가 하나의 자식 노드만을 갖는 트리
- 성능 측정에서 트리가 연결 리스트와 같이 움직인다는 것을 의미
learn !