트리 간단 정리

트리

트리는 그래프의 한 종류로 무방향, 연결 비순환 그래프이다.

계층적인 구조

사이클이 없다.

노드가 N개인 트리는 N-1개의 간선을 가진다.

임의의 두 노드 간의 경로가 유일하다.

 

https://gmlwjd9405.github.io/2018/08/12/data-structure-tree.html

 

관련 용어

- 노드

- 루트

- 서브트리

- 차수 : 각 노드의 자식의 갯수

- 리프노드 : 자식없는 노드

- 레벨 (층을 나타내는 index) : 루트노드부터 0레벨 내려갈수록 1++

- 높이 :트리의 최대 레벨, (중간노드의 높이는 해당 노드가 루트노드가 되는 서브트리의 높이)

 

 

---

 

트리의 종류

이진트리

모든 노드의 차수가 2 이하인 트리 (모든 노드가 최대 2개의 자식 노드를 가짐)

 

이진트리의 모양에 따른 분류

1. 포화 이진 트리(Full Binary Tree) : 레벨의 노드가 꽉 차 있는 트리 (높이가 h일 때 노드의 개수는 2^(h-1))
2. 완전 이진 트리(Complete Binary Tree) : 마지막 레벨 전까지는 노드가 꽉 차 있고, 마지막 레벨의 왼쪽에서 오른쪽으로 노드가 채워져 있는 트리
3. 편향 이진 트리(Skewed Binary Tree) : 왼쪽 혹은 오른쪽 서브 트리만을 가지는 트리

 

순회방식

1. 전위(PREORDER) : Me - Left - Right
2. 중위(INORDER) : Left - Me - Right
3. 후위(POSTORDER) : Left - Right - Me

발견하지 않은 노드를 찾는데 찾는 방향의 우선순위에 따른 순회이다.

※ DFS 전위탐색

※ BFS 레벨우선탐색

 

이진탐색트리 (BST : Binary Search Tree) 

모든 노드가 아래와 같은 특정 순서를 따른다.

모든 왼쪽 자식들 <= n < 모든 오른쪽 자식들 (모든 노드 n에 대해서 반드시 참)

 

 

---

 

균형트리

트리가 한 쪽 방향으로 치우쳐져 있지 않고 균형을 이루는 트리

O(logN) 시간에 insert와 find를 할 수 있을 정도로 균형이 잘 잡혀 있는 경우

레드블랙 트리, AVL 트리

 

 

이진 힙(최대 힙, 최소 힙)

여러 개의 값 중에서 가장 큰 값이나 가장 작은 값을 빠르게 찾을 수 있도록 구성된 자료구조

힙은 배열을 사용하여 구현하는 것이 일반적이다.

1. 최소 힙(Min Heap): 부모 노드의 값이 항상 하위 노드의 값보다 작은 경우
2. 최대 힙(Max Heap): 부모 노드의 값이 항상 하위 노드의 값보다 큰 경우

가장 큰/작은 값이 루트노드에 위치한다.