알고리즘3-2 자료구조 리뷰2

AVL Tree

BST가 보통의 경우에 성능이 좋지만, 특수한 경우에 안 좋다. = > Balanced Tree 최악의 경우에도 O(logN)

 

 

왼쪽, 오른쪽 subtree의 높이 차이가 1이하

L-R = 0, 1, -1 중에 하나

 

따라서 위의 오른쪽 그림은 안됨

 

루트에서 갈 수 있는 제일 짧은 길과 제일 긴 길 차이가 2배 이하다.

중간까지는 tree높이에 비해서 노드 수가 많기 떄문에

=> 노드 갯수에 비해서 tree 높이가 작다. => O(log n)

 

 

 

2-3 Tree

key가 1개 있고 child가 2개 있는 노드

key가 2개 있고 child가 3개 있는 노드를 섞어서 만든다.

 

AVL tree와 결국 비슷한 얘기지만 이게 더 직관적이다.

 

 

삽입할땐 key와 key사이 가운데로 삽입되어서 위로 올라갈 수 있으면 올라간다. (내가 이해한 방식)

 

5와 10을 삽입

8삽입

 

15삽입

 

12 삽입

 

2 삽입

 

3은 들어갈 자리가 없다.

 

 

 

<Heap을 쓰는 이유>

AVL, 2-3 , Red-Black 트리는 Heap과 같이 O(log N)으로 search, insert, delete 모두 가능했다.

하지만 Heap의 차이점은 특정한 값이 아닌 가장 작은 값을 delete한다.

다른 트리도 왼쪽으로 쭉 내려가면 할 수 있는 일이지만, annotation상으로는 같지만

실제로 돌려보면 heap이 10배 빠르다. (+따라가는 동작없이 배열의 인덱스를 이용하기 떄문에)

 

 

 

Binary Trie (Radix Idea)

다른 구조는 "숫자를 비교할 수 있다" 를 사용하지만 내부 구조를 사용한다.

ex) 2진수, 문자열

 

네트워크 라우터에도 사용된다.

ex) IP 83.236.19.27 

 

왼쪽 = 0 , 오른쪽 = 1

숫자 하나를 저장하기 위해 노드 여러개를 사용하는 것이 비효율적일 수 있다.

 

직관적이다.

 

8을 지우려했지만 없다.

 

7을 지우기 - child가 없어졌으므로 위쪽 주소도 없앤다.

 

 

항상 좋지는 않다. 내부 구조를 사용하기 때문에 내부구조가 다른 것에는 적용안된다.

즉, 특수 구조에만 가능하며 일부에만 빠르다.

 

 

 

Graph

 

우리가 생각하는 모든 것을 표현할 수 있는 자료구조, 종류가 많다.

굉장히 느리기 때문에 성능을 높이기 위해 특이한 기술 많이 사용

 

G = (V,E)

V : 노드 set - any set(finite)

E : 엣지 set 

 

가능한 edge는 nC2개 = n(n-1)/2

 

그래프를 컴퓨터 안에 어떻게 표현할 것인가?

 

1. 인접그래프 - edge많을 때

메모리 많이 쓰지만 빨리 찾을 수 있음 (노드^2)

(무방향 그래프이므로 대칭)

 

2. 인접 리스트 - edge적을 때 (보통 이거 씀)