211026TIL_트리,힙 / SQL

트리와 힙

큐, 스택 -> 선형 구조(데이터 순차적 나열)

트리 -> 비선형 구조(데이터 계층적)

 

선형 구조와 비선형 구조는 용도에서 차이점이 나는데,

선형 구조 : 자료 저장, 꺼내기

비선형 구조 : 표현에 초점 (EX : 폴더 구조)

 

트리

- 트리 용어

Node: 트리에서 데이터를 저장하는 기본 요소 Root Node: 트리 맨 위에 있는 노드

Level: 최상위 노드를 Level 0으로 하였을 때, 하위 Branch로 연결된 노드의 깊이를 나타냄

Parent Node: 어떤 노드의 상위 레벨에 연결된 노드 Child Node: 어떤 노드의 하위 레벨에 연결된 노드

Leaf Node(Terminal Node): Child Node가 하나도 없는 노드

Sibling: 동일한 Parent Node를 가진 노드

Depth: 트리에서 Node가 가질 수 있는 최대 Level

 

- 트리 종류

1. 이진 트리 : 각 노드가 최대 두개 자식

2. 완전 이진 트리 : 노드 삽입시 최하단 왼쪽 노드부터!!

 

- 트리 구조를 코드로 표현 

완전 이진 트리는 왼쪽부터 노드가 쌓이니까 이를 이용해 배열로~

 

- 트리 연산

1. 현재 인덱스 * 2 -> 왼쪽 자식의 인덱스

2. 현재 인덱스 * 2 + 1 -> 오른쪽 자식의 인덱스

3. 현재 인덱스 // 2 -> 부모의 인덱스

 

-트리 노드 개수

1 Level 0 -> 1개

2 3 Level 1 -> 2개

4 5 6 7 Level 2 -> 4개

8 9....... 14 15 Level 3 -> 8개

Level k -> 2^k 개

 

높이가 h일 때 노드가 최대인 이진 트리의 노드 개수 :

1 + 2^1 + 2^2 + 2^3 + 2^4 ..... 2^h = 2^(h+1) - 1

 

이때 h를 표현하자면..... 2^(h+1) -1 = N → h = log_2(N+1)-1

 

즉 완전 이진 트리 노드 개수가 N일 때, 최대 높이는  log_2(N+1)-1

그래서 높이는 최대로 O(log(N))

 

힙(완전 이진 트리)

데이터에서 최대값과 최소값을 빠르게 찾기 위해 고안된 완전 이진 트리

 

-힙 용도

항상 최대의 값들이 필요한 연산이 있을 때 힙을 사용!

 

힙은 항상 큰 값이 상위 레벨에 있고 작은 값이 하위 레벨에 있도록 하는 자료구조

부모 노드의 값이 자식 노드의 값보다 항상 커야 함

그러므로 최대값이 가장 맨 위에 있게 됨

 

- 힙 종류

최댓값이 맨 위인 힙을 Max 힙, 최솟값이 맨 위인 힙을 Min 힙

 

-MAX 힙 순서

<원소 추가>

1. 원소를 맨 마지막에 넣습니다.

2. 그리고 부모 노드와 비교합니다. 만약 더 크다면 자리를 바꿉니다.

3. 부모 노드보다 작거나 가장 위에 도달하지 않을 때까지 2. 과정을 반복합니다.

 

<원소 제거>

1. 루트 노드와 맨 끝에 있는 원소를 교체한다.

2. 맨 뒤에 있는 원소를 (원래 루트 노드)를 삭제한다.

3. 변경된 노드와 자식 노드들을 비교합니다. 두 자식 중 더 큰 자식과 비교해서 자신보다 자식이 더 크다면 자리를 바꿉니다.

4. 자식 노드 둘 보다 부모 노드가 크거나 가장 바닥에 도달하지 않을 때까지 3. 과정을 반복합니다.

5. 2에서 제거한 원래 루트 노드를 반환합니다.

(코드 참고)

 

-시간 복잡도 

완전 이진 트리이니, 완전 이진트리를 전부 순회하는 시간 O(log(N)) 이겠쥬?

 

---

SQL

이미 설계된 DB에서 데이터를 꺼내오는 요청만 함. 그러므로 우리는 "꺼내오는 연습" 반복할 예정~

 

SQL : DB에서 내가 원하는 형태로 Data를 가져오기 위해 DB와 약속한 규칙/언어

DB : 데이터 담는 책장. 데이터 저장/사용 위해 CRUD 기능 제공

 

SQL은 여러번 반복하면 외워질 것 같다!

에러 메세지를 유심히 살펴보기 약속~