[자료구조] 비선형 자료구조 - 트리(Tree)

✅ 비선형 자료구조 : i 번째 값을 탐색한 뒤의 i+1이 정해지지 않은 구조

트리(Tree)?

계층적인 자료를 표현하는 데 이용되는 자료구조. 그래프의 한 종류이다.

예) 컴퓨터 directory

출처 : 도서 - 파이썬 알고리즘 인터뷰

• 노드(Node) : 그래프의 정점

  • 루트 노드 : 트리의 기준이 되는 노드. 나무의 뿌리를 생각하면 된다. 루트 노드에서 가지가 뻗어나가는 이미지.

  • 부모 노드 : 자신과 인접한 노드들 중 루트 노드로 향하는 노드

  • 자식 노드 : 자신과 인접한 노드들 중 루트 노드의 반대 방향으로 향하는 노드

  • 단말 노드 : 자식 노드가 존재하지 않는 노드. 가지의 끝

  • 형제 노드 : 부모 노드가 같은 노드

• 가지(Branch) : 그래프의 간선. 트리에서는 양방향 간선만 사용한다.

• 부트리(Sub Tree) : 부분 그래프와 비슷하게 정의한다.

• 차수(Degree) : 자식 노드의 개수.

• 길이(Length) : 임의의 두 노드를 시작 노드, 도착 노드로 하는 경로에서 거치게 되는 노드의 수.

  • 깊이(Depth) : 루트 노드에서 해당 노드까지의 길이.

    • 레벨(Level) : 깊이가 같은 노드의 집합.

    • 높이(Height) : 가장 깊이가 깊은 단말 노드까지의 길이. 깊이 중 최댓값

트리의 종류

1. 이진 트리(Binary Tree)

각 노드가 최대 두 개의 자식을 갖는 트리. 즉, 모든 노드의 차수가 2 이하이다.

•  전 이진 트리(Full Binary Tree)

  • 모든 노드가 0개 또는 2개의 자식 노드를 갖는 트리

• 포화 이진 트리(Perfect Binary Tree)

  • 모든 단말 노드의 깊이가 같은 이진트리

• 완전 이진 트리(Complete Binary Tree)

  • 모든 단말 노드의 깊이의 최댓값과 최솟값의 차이가 0 또는 1인 이진트리. 즉, 트리의 원소를 왼쪽에서 오른쪽으로 하나씩 빠짐없이 채워나간 형태이다.

이진 트리 순회 알고리즘

• 전위 순회(preorder traverse): 루트를 먼저 방문. 그래프의 깊이 우선 탐색과 같다.
• 중위 순회(inorder traverse): 왼쪽 하위 트리를 방문 후 루트를 방문
• 후위 순회(postorder traverse): 하위 트리 모두 방문 후 루트를 방문
• 레벨 순서 순회(level-order traversal) : 노드를 레벨 순서대로 방문. 그래프의 너비 우선 탐색과 같다.

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

모든 노드가 [ 모든 왼쪽 자식들 < n < 모든 오른쪽 자식들 ]의 특징을 가지는 이진 트리. 같은 값을 가지는 노드는 없다.

이진 탐색 알고리즘

• 이진 검색 트리의 루트 노드부터 방문한다.
• 찾는 값이 방문한 노드의 값보다 작으면 왼쪽, 크면 오른쪽 자식을 방문한다.
• 두 번째 과정을 값을 찾을 때까지 반복한다.

트리의 구현

그래프의 한 종류이므로 그래프 구현 방법으로 구현할 수 있다.

인접 배열(행렬) 방식

• 1차원 배열에 자신의 부모 노드만 저장 : 트리는 부모 노드를 0개(루트노드) 또는 1개만 가짐
• 2차원 배열에 자식 노드를 저장 : 이진 트리일 경우만 가능. 각 노드가 최대 두 개의 자식을 갖기 때문

인접 리스트 방식

• 가중치가 없는 트리인 경우 : ArrayList< ArrayList > list = new ArrayList<>();
• 가중치가 있는 트리의 경우 : 노드 번호와 거리를 변수로 정의한 후, ArrayList[] list = new ArrayList[정점의 수 + 1];

그래프와 트리의 차이

이미지 출처

참고

• https://gmlwjd9405.github.io/2018/08/12/data-structure-tree.html
• https://namu.wiki/w/%ED%8A%B8%EB%A6%AC(%EA%B7%B8%EB%9E%98%ED%94%84)
• https://jud00.tistory.com/entry/%EC%9E%90%EB%A3%8C%EA%B5%AC%EC%A1%B0-%ED%8A%B8%EB%A6%ACTree%EB%9E%80#%ED%-A%B-%EB%A-%AC%--%EC%--%-C%ED%-A%-C
• https://hongcoding.tistory.com/173
• https://librewiki.net/wiki/%EC%8B%9C%EB%A6%AC%EC%A6%88:%EC%88%98%ED%95%99%EC%9D%B8%EB%93%AF_%EA%B3%BC%ED%95%99%EC%95%84%EB%8B%8C_%EA%B3%B5%ED%95%99%EA%B0%99%EC%9D%80_%EC%BB%B4%ED%93%A8%ED%84%B0%EA%B3%BC%ED%95%99/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98_%EA%B8%B0%EC%B4%88