TL;DR

• Tree : Node와 Edge로 이루어진 계층 데이터를 표현하는데 이용하는 비선형 자료구조

Tree

• Node와 Edge로 이루어진 자료구조

• 계층적 데이터를 표현하는 데 이용하는 비선형 자료구조이다.

  (싸이클이 존재하지 않는 그래프를 트리라고도 부름)

  ☝️ 여기서 잠깐!

  왜 해당 자료구조의 이름은 트리일까?

  해당 자료구조의 모양이 나무를 뒤집어 놓은 것과 비슷해서 트리로 부른다.

  ✌️ 여기서 잠깐!

  선형 자료구조란?

  자료들 간의 앞뒤 관계가 1:1인 자료구조로 배열, 링크드리스트, 스택, 큐 등이 있다.

  비선형 자료구조는 자료들 간의 앞뒤 관계가 1:n이거나 n:n인 자료구조로 트리와 그래프가 대표적이다.

• 트리 안에 또 다른 트리가 있는 재귀적 자료구조이다.

• 노드들이 부모 자식 관계를 갖는 계층적 자료구조이며 모든 자식 노드는 하나의 부모 노드을 갖는다.

• 노드가 n개인 트리는 항상 n-1개의 간선을 갖는다. (그래프와의 차이점)

관련 용어

• 노드 : 트리를 구성하는 기본 요소로 값과 하위 노드에 대한 포인터를 가지고 있다.

• 간선 : 노드와 노드 간의 연결 선이다.

• 레벨 : 위에서부터 각 층별로 매기는 숫자 (Level 0~)

• 루트 노드 : 트리 구조에서 부모가 없는 최상위 노드이다.

• 부모 노드 : 자식 노드를 가진 노드로 상대적인 개념이다.

• 자식 노드 : 부모 노드의 하위 개념으로 상대적인 개념이다.

• 형제 노드 : 같은 부모를 가지는 노드이다.

• 리프 노드 : 자식 노드가 없는 노드이다.

• 깊이 : 루트에서 해당 노드까지의 간선의 수

• 높이 : 어떤 노드에서 리프노드까지 가장 긴 간선의 수 (트리의 최고 레벨)

트리의 활용

1. 컴퓨터의 폴더구조	2. DOM 트리	3. 인덱스 (B+트리)
	HTML 문서를 트리구조로 표현한 것	데이터 베이스 테이블의 검색 속도를 향상시켜주는 자료구조

트리의 종류

균형 트리

• O(logN) 시간에 탐색이 가능한 균형 잡힌 트리
• 레드 블랙 트리, AVL 트리

편향 트리

• 노드가 한쪽으로 편향되어 있어 생성된 이진 트리
• 연결 리스트와 다를바가 없게 되어 O(N)의 탐색 시간을 가지게 됨

1) 이진 트리 Binary Tree

• 노드들의 최대 차수가 2인 노드들로 구성되는 트리
• 레벨 $i$에서 가질 수 있는 최대 노드 수는 $2^i$

구현방법

• 배열

  • 자식 노드는 부모 노드 인덱스와 *2 와 *2+1 에 해당
  • 빈 노드를 사용하지 않아 공간이 낭비된다.

• 포인터

  struct Node {
  		int data;
  		Node *left;
  		Node *right;
  }
  

전 이진 트리 vs 완전 이진 트리 vs 포화 이진 트리

전 이진 트리 Full Binary Tree

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

완전 이진 트리 Complete Binary Tree

• 트리가 모든 레벨에서 마지막 레벨을 제외하고 꽉 차있는 트리
• 마지막 레벨은 왼쪽부터 채워져야 함

포화 이진 트리 Perfect Binary Tree

• 전 이진 트리 && 완전 이진 트리
• 모든 레벨이 꽉 차있고, 모든 말단 노드가 동일한 레벨을 갖는다.

2) 이진 탐색 트리 Binary Search Tree

• 특정한 조건을 만족하는 이진트리
  1. 각 노드들의 키는 중복되지 않아야 한다.
  2. 루트 노드의 왼쪽 서브트리는 루트 노드의 키보다 작은 키값를 갖는 노드들로 구성되어 있다.
  3. 루트 노드의 오른쪽 서브트리는 루트 노드의 키보다 큰 키값를 갖는 노드들로 구성되어 있다.
  4. 루트 노드의 서브 트리도 이진 탐색 트리여야 한다.
• 효율적인 탐색 및 삽입, 삭제가 가능하다. (균형이 잡혀있을 경우 O(logn))
  • 균형 잡히지 않고 Skewed Tree 가 된다면 Worst case 가 되고 O(N)이 됨.

이진 트리의 순회

• 중위 순회(in-order traversal) : 왼쪽 서브트리 -> 루트 -> 오른쪽 서브트리
• 전위 순회(pre-order traversal) : 루트 -> 왼쪽 서브트리 -> 오른쪽 서브트리
• 후위 순회(post-order traversal) : 왼쪽 서브트리 -> 오른쪽 서브트리 -> 루트

3) 자가 균형 이진 탐색 트리 (Red-black Tree)

• Self-balancing Binary Tree

• 트리가 한쪽으로 치우치는 Worst case 방지를 위해 트리의 균형이 유지되도록 하는 트리

  여기서 잠깐!

  균형이란? 깊이가 2이상 차이나지 않는다. (루프노드 ~ 리프 노드까지의 경로)

• 검색, 삽입, 삭제에 O(logN)

  • 삽입 : 새로운 노드는 빨간색으로 삽입하고, 만약 Double Red 발생시, 삼촌 노드가 검은색이면 Restructuring을, 빨간색이면 Recoloring 을 수행한다.

• Red-Black 트리의 규칙
  1. 각 노드의 색은 red 또는 black이다.
  2. root 노드는 black이다.
  3. 모든 말단노드(leaf node)는 black이다. (NIL이 black이 된다)
  4. red 노드의 자식노드들은 전부 black이다. (즉, red 노드는 연속되어 등장할 수 없다.)
  5. Root 노드에서 시작해서 자손인 leaf노드에 이르는 모든 경로에는 동일한 개수의 black노드가 존재한다.
• 색상이 추가되어 AVL 보다 느슨하게 균형을 유지해 삽입, 삭제가 더 빠르다.

4) AVL 트리 (높이 균형 이진 탐색 트리)

• Adelson-Velsky and Landis, AVL 트리

• 삽입, 삭제, 탐색 모두 평균이든 최악의 경우든 O(logN)

• 트리에 노드를 삽입 혹은 삭제할 때마다 자가 균형 조정 메서드를 호출하여 트리의 균형을 유지한다.
  • 높이 차이가 1보다 커지면 회전을 통해 균형을 맞춰 높이 차이를 줄인다.
  • Balance Factor (BF)를 사용해 균형이 무너짐을 판단
    • K의 왼쪽 서브 트리 높이 - K의 오른쪽 서브 트리 높이
  • LL, RR, LR, RL case 존재

5) 힙 Heap

• 완전 이진트리를 기본으로 한 자료구조

• 여러개의 값들 중에서 최댓값(최대 힙) 혹은 최솟값(최소 힙)을 빠르게 찾아내는데 사용한다.

  → 빠르게 최댓값 혹은 최솟값을 찾아내기 위해 힙은 반정렬 상태 (느슨한 정렬 상태)를 유지한다.

• 우선순위 큐 기능 -> 다익스트라 최단 경로 알고리즘에서 사용

• 삽입 및 삭제 시의 시간 복잡도가 O(log n)이다.
  • 삽입 : 마지막 노드에 x를 넣고, 정렬
  • 삭제 : 마지막 노드 값을 루트로 이동하고, 정렬
• 배열을 사용해서 구현, 인덱스 0은 사용하지 않음
  • N번째 노드의 왼쪽 자식의 인덱스 : 2*N
  • N번째 노드의 오른쪽 자식의 인덱스 : 2*N + 1
  • N번째 노드의 부모의 인덱스 : N/2

6) 트라이 자료구조

• 문자열을 저장하고 효율적으로 탐색하기 위한 트리 형태의 자료구조이다.
• 문자열 탐색 속도가 빠르다.
  • 길이가 M인 문자열 검색할 때 시간 복잡도는 O(M), 저장되어 있는 문자열 개수에 영향 안받는다.
  • 이진 검색 트리에서 원소를 찾는데 O(log N) 시간이 걸리는데, 문자열의 경우 두 문자열을 비교하기 위한 시간이 추가로 들기 때문에 O(M log N) 시간이 걸린다.
• 각 노드들이 자식 노드에 대한 포인터를 저장해야하므로 공간 복잡도가 높을 수 있다. (메모리 측면에서 비효율적일 수 있다.)

7) B-Tree

• 이진 트리를 확장해 하나의 노드가 가질 수 있는 자식의 개수가 2보다 큰 트리 구조
• 항상 정렬된 상태로 저장되고 , 내부 노드는 M/2 ~ M개의 자식을 가질 수 있음
• 검색, 삽입, 삭제 O(log N
• 방대한 데이터 양에도 빠른 메모리 접근이 가능

질문

최소 스패닝 트리란 무엇일까요?

각 트리의 검색/삽입/삭제에 대한 시간 복잡도는 어떻게 될까요?

파이썬 heapq 모듈은 최소 힙 기능만 제공한다. 최대 힙으로 쓰고 싶으면 어떻게 해야할까?

• 음수로 저장하기

트리로 문자열을 저장하게 되면 어떨까? 해결책은?

References

• https://github.com/shinhee-rebecca/2022-cs-study/blob/44209fb47d923173a2716dcfb2801d9c27749585/Algorithm/%ED%8A%B8%EB%A6%AC.md