[SW정글] 4/29 TIL - 메모리 누수, 균형이진트리, RB TREE(feat, C)

메모리누수

메모리 누수란 ? 컴퓨터가 필요하지 않은 메모리를 계속 점유하고 있는 현상이다.

 

c는 파이썬이나 자바스크립트처럼 가비지 컬렉터가 없다.

사용자가 메모리를 할당해주고 해제?(free)를 해주지 않으면 메모리  누수 현상이 발생한다.

 

malloc 등과 같은 메모리를 동적할당 했다면, 꼭! 꼮! free를 해주는 습관을 들이도록 하쟈!

 

 

균형 이진 트리

균형 이진 트리란? 말 그대로 균형이 잡힌 이진 트리이다. (높이는 O(logN)을 만족)

균형이 잡히지 않았다면 search까지 최대 O(N)이 걸릴 수 있기 때문에 나온 개념이다.

 

균형 이진트리의 종류로 AVL Tree, Red-Black Tree가 있는데 Red-Black 트리가 많이 쓰인다.

 

이유는 밑에서 설명하겠다.

 

AVL Tree

Avarage ~~일 줄알았는데  AVL은 사람이름이라고 한다. 

AVL 트리의 조건은 자식 트리의 높이차가 1이하인 트리이다.

균형이 깨지면. 즉, 자식 트리의 높이차가 2이상이면 회전을 하며 균형을 맞춘다.

 

 

Red - Black Tree

RB Tree는 조건 5개를 만족해야 한다.

 

1. 모든 노드는 색을 가진다. Red or Black

2. root 노드는 black

3. leaf node는 black

4. red node의 child node는 black(black node의 child node는 상관없다.)

5. 각 노드에서 leaf node로 가는 경로 중 black node의 수는 항상 같아야 한다. (-> 이 조건 때문에 균형이 유지된다.)

 

fact 1, v의 서브트리의 내부노드 개수 >= 2^(bh(v)-1)

 

fact 2, black의 노드 개수 >= h/2 

      =>    black(root) >= h/2

 

fact 3, h = O(log2N)

 

h(v) : v의 높이

bh(v) : v에서 leaf node까지 존재하는 black node의 개수(v는 제외한다.)

 

R B 트리 많이 쓰는 이유

	AVL	Red-Black Tree
SEARCH	-	-
INSERT	2	2
DELETE	O(logN)	3

위는 operation별 회전 수 이다.

AVL, RB트리의 search, insert의 회전수는 같지만 DELETE에서 많은 차이가 난다. 이 이유 때문에 RB Tree를 많이 사용한다고 한다.

(시간 복잡도는 둘 다 O(logN)이다.

 

 

2-3-4 tree

균형 이진트리는 아니지만 RB트리와 비슷하다.

조건 1, 자식 노드 개수가 2,3,4 중 하나다

조건 2, leaf node가 모두 같은 level에 존재한다.

 

log4N <= h <= log2N을 만족한다.

 

 

---

너 ~ 무 어렵다. 내일은 포인터를 부숴보쟈

 

모두 열코~