1. 그림으로 배우는 알고리즘 제 3장: 자료구조 (6)

33. 부모 노드의 값이 자식 노드의 값보다 항상 적은 이진 트리는 힙(Heap)

• 힙(Heap): 각 노드의 값이 다음 조건을 충족하도록 관리되는 이진트리
  • 부모 노드의 값은 항상 하위 노드 값보다 작다(또는 부모 노드의 값은 항상 하위 노드 값보다 크다)
  • 첫번째 경우 자식 노드의 값은 둘 중 어느쪽이 크더라도 상관 없음.
  • 위 조건에 따라 관리되는 힙은 뿌리 부분에 모든 값 중 가장 작은 값(또는 가장 큰 값)이 배치됨.
  • 최소 값(또는 최대 값)을 효율적으로 구하는 용도에 적합.
• 힙을 구현할 때 일반적으로 배열을 사용.
  • 배열 요소 번호 1번 = 힙의 뿌리요소.
  • 깊이가 작은 쪽 → 큰 쪽
  • 노드의 왼쪽 → 오른쪽

34. 해시 테이블은 배열과 리스트를 조합한 자료 구조

• 해시 테이블(Hash Table): 아래 2개 자료구조가 조합된 것

  • N개의 요소를 가진 루트 배열이라는 이름의 배열
  • 루트 배열의 각 요소가 가리키는 리스트

• 먼저 루트 배열의 요소 번호를 구해야 한다

  • 해시함수를 이용
  • 해시 함수: 관리할 데이터를 입력받아 해당 데이터를 ‘0~(N-1)’ (N: 루트 배열의 요소 개수) 사이의 값으로 바꾸어 주는 함수.
  • 해시 값: 해시 함수에 의해 구해진 값. 루트 배열의 요소 번호로 삼으면 데이터를 루트 배열의 몇 번째 요소가 가리키는 리스트에 저장해야할 지 결정할 수 있다.

• 해시 테이블의 경우 같은 배열 요소에 그룹화 된 데이터가 여러개 나오는 상황이 발생 ⇒ 충돌

• 충돌을 피하려면 각 그룹이 여러 개의 데이터를 관리할 수 있도록 만들어야 하기 때문에 루트 배열의 각 요소가 리스트를 가리키도록 만들어 해시 값이 동일한 데이터를 여러 개 관리할 수 있다.

• 해시 테이블이 관리하는 데이터 중 특정 데이터 찾는 방법

  • 해시값을 구해 데이터가 속한 그룹(리스트)을 찾는다.
  • 리스트 데이터를 순서대로 검색한다.