자료구조 & 알고리즘
[JAVA/자료구조] 트리(Tree), 이진트리(Binary Tree) 란?
HSRyuuu
2023. 6. 8. 20:57
트리(Tree)
트리는 Node와 Edge로 이루어진 자료구조이다.
각 노드들이 나무가지처럼 브랜치( = 엣지, 링크)로 연결된 비선형적, 계층적 자료구조이다.
트리의 구조 (용어)
노드와 에지
- 노드(Node) : 트리 구조에서 자료 값을 담고있는 단위
- 에지(Edge) : 각 노드 간의 연결 선
- 루트 노드(Root) : 가장 위의 노드 (1)
- 잎새 노드(Leaf) : 자식이 없는 노드 (8), (9), (10) ...
- 내부 노드(Internal) : 잎새 노드를 제외한 모든 노드
노드 간의 관계
- 부모(Parent) : 연결된 두 노드 중 상위 노드 (2번 노드는 4번 노드의 부모 노드)
- 자식(Child) : 연결된 두 노드 중 하위 노드 (4번 노드는 2번 노드의 자식 노드)
- 형제(Sibling) : 같은 부모를 가지는 노드 ( 4번과 5번 노드는 형제 노드)
트리 구조 관련
- 깊이(Depth) : 루트에서 해당 노드까지의 간선 수 (4번노드의 깊이는 2) , (12번 노드의 깊이는 3)
- 레벨(Level) : 트리의 특정 깊이를 가지는 노드의 집합( 4, 5, 6, 7번 노드는 level 2), (2, 3번 노드는 level 1)
- 높이(Height) : 트리에서 가장 큰 레벨 값 (위의 트리의 높이는 3)
- 크기(Size) : 자신을 포함한 자식노드의 개수 (1번노드에서의 크기는 15) , (5번노드에서의 크기는 3)
- 차수(Degree) : 각 노드가 가진 가지의 수 (1번 노드의 차수는 2 ) , ( 이 트리에서 모든 노드의 차수는 2이다.)
- 트리의 차수 : 트리의 노드들이 가진 차수 중 가장 큰 차수
트리의 특징
트리는 하나의 루트 노드를 갖는다.
- 루트 노드를 포함한 모든 노드는 0개 이상의 자식노드를 갖고 있다.
두 노드간의 이동 방법은 유일하다.
- 그래프의 경우 다른 노드로 이동하는 방법이 여러개 일 수 있지만, 트리는 그렇지 않다.
- 계층적 구조이기 때문에, 두 노드 사이에 이동경로는 한가지이다.
- 따라서 트리에는 사이클(cycle)이 존재할 수 없다.
비선형 자료구조로 계층적 관계를 표현한다.
- 디렉터리 구조, 조직도 등
하나의 Edge를 끊으면 2개의 Sub-Tree로 분리된다.
- Edge가 끊어지면, 끊어진 Edge를 기준으로 서로 다른 Tree가 된다.
- 즉, 하나의 Tree에서 모든 Node는 Edge로 연결되어있다.
이진트리(Binary Tree)
모든 노드들이 둘 이하의 자식을 가진 트리이다.
각 노드는 좌, 우를 구분한다.
이진트리의 종류
1. 포화 이진 트리 (Perfect Binary Tree)
모든 레벨에서 노드들이 가득 차있는 트리
- 포화 이진트리의 높이가 h 일때, 노드의 수는 2^(h+1) -1 개
- 포화 이진트리의 노드가 N개 일때, 높이는 logN개
- 이진 트리의 노드가 N개 일때, 최대 가능한 높이는 N (편향트리 일때)
2. 완전 이진 트리 (Complete Binary Tree)
마지막 레벨을 제외하고 노드들이 가득 차 있는 트리
(자식 노드가 하나만 있을 경우, 왼쪽부터 채워져야 한다.)
3. 정 이진 트리 (Full Binary Tree)
모든 노드가 0개 또는 2개의 자식 노드를 갖는 트리
4. 편향 트리(Skewed Binary Tree) = 사향 트리
한쪽으로 기울어진 트리
모든 노드가 왼쪽에만 있거나, 모든 노드가 오른쪽에만 있는 트리
5. 균형 이진 트리 (Balanced Binary Tree)
높이 균형이 맞는 트리
모든 노드의 좌우 서브 트리 높이가 1 이상 차이나지 않는 트리
이진 트리의 순회(Traversal)
순회 : 모든 노드를 빠뜨리거나, 중복하지 않고 모두 방문하는 연산
1. 전위 순회 (Preorder Traversal )
방문 순서 : 현재노드 > 왼쪽노드 > 오른쪽 노드
- 현재 노드 먼저 방문 한다.
- 왼쪽 노드가 있으면 왼쪽노드가 없는 노드가 나올때까지 계속 왼쪽노드를 방문한다.
- 더이상 왼쪽노드를 찾을 수 없으면, 부모노드의 오른쪽 노드를 탐색한다.
2. 중위 순회 (Inorder Traversal)
방문 순서 : 왼쪽노드 > 현재노드 > 오른쪽 노드
- 왼쪽 끝의 노드를 찾아서 왼쪽으로 이동한다.
- 왼쪽 노드를 방문 후 부모노드(현재)를 방문한다.
- 부모노드의 오른쪽노드를 방문한다.
- 만약 해당 노드의 왼쪽노드가 존재한다면 그 왼쪽노드 먼저 방문한다. (4번째 -> 6번째 노드의 경우)
3. 후위 순회 (Postorder Traversal)
방문 순서 : 왼쪽노드 > 오른쪽 노드 > 현재 노드
- 왼쪽 끝의 노드를 찾아서 왼쪽으로 이동한다.
- 왼쪽노드를 방문 후 형제노드(오른쪽) 노드를 방문한다.
- 왼쪽, 오른쪽 노드를 모두 방문했으면 부모노드(현재)를 방문한다.
- 만약 오른쪽노드를 방문했는데, 그 노드의 왼쪽 노드가 존재한다면 그 왼쪽 노드 먼저 방문한다. (3 -> 5 -> 4의 경우)
4. 레벨 순회(LevelorderTraversal)
방문 순서 : 위쪽 레벨부터 왼쪽노드 -> 오른쪽 노드 순으로 방문
BFS(Breadth-first search)와 같다.
반응형