자료구조

우선순위 큐와 힙

 

우선순위 큐와 큐이면서 데이터의 저장방식이 우선순위대로 저장되어 데이터를 꺼낼 때 우선순위가 높은 데이터를 먼저 꺼낼 수 있도록 합니다.

 

힙은 우선 완전 이진트리의 형태를 띄고 있습니다. 

완전 이진트리는 노드의 값이 자식의 값보다 항상 크거나 같은 이진 트리를 말합니다 ( Max Heap )

 

 

 

균형 잡힌 이진 탐색 트리

 

균형 잡힌 이진 탐색 트리를 만들기 전에 트리에 균형 인수를 도입하여 트리가 얼마나 균형 잡혔는지 확인할 수 있습니다.

균형 인수 = 왼쪽 서브 트리의 높이 - 오른쪽 서브 트리의 높이

균형을 맞추는 방법에는 4가지가 있습니다.

 

- LL회전

- RR회전

- LR회전

- RL회전

 

 

해쉬 테이블

 

데이터의 탐색이 주로 필요한 환경에서 자주 사용되는 해쉬 테이블은 키 값으로 바로 데이터를 찾을 수 있다는 장점이 있습니다.

 

그리고 그 키 값을 실제로 참조할 수 있는 해쉬 값으로 바꾸는 것이 해쉬 함수입니다.

 

좋은 해쉬 함수라는 것은 해쉬 값이 고르게 나오는 함수입니다.

그런데 해쉬 값이 고르게 나오기 위해서는 키 값을 일부만 사용하도록 하기도 합니다.

 

예를 들어 데이터들의 키 값들이 Alpha-1523, Alpha-5261, Alpha-9281 ... 식이라고 한다면 

중복되는 Alpha- 영역을 제외한 나머지를 이용하는 것이 효율적일 수 있습니다.

 

이러한 방법은 자릿수 선택 방법이라고 합니다.

 

다른 방법으로는 자릿수 폴딩 방법이 있는데

예를 들어 데이터의 키 값이 596214 이라고 하면

두자리씩 겹치게 하여 59 + 62 + 14 = 135 를 해쉬 값으로 쓰는 방법이 있습니다.

 

그래프

 

그래프는 정점과 간선이 있는 형태의 데이터를 표현하기 좋다.

 

그래프는 인접행렬이나 인접 리스트로 표현할 수 있다.

각각 정방 행렬과 연결 리스트를 활용한다.