[자료구조(Data Structure)] Tree / Hashing

09 Oct 2021 - Less than 1 minute read

트리 (Tree)

---

• 부모 노드와 자식 노드간의 연결로 이루어진 자료 구조

이진 트리 (binary tree)

• 부모노드에 자식노드가 두 개 이하인 트리 (각 노드가 최대 두개의 자식을 가짐)

이진 검색 트리 (binary search tree)

• 자료(key)의 중복 허용하지 않음

• 왼쪽 자식 노드는 부모 노드보다 작은 값 / 오른쪽 자식 노드는 부모 노드보다 큰 값을 가짐

• 자료 검색에 걸리는 시간 = 평균 log(n)

힙 (heap)

• 최댓값 및 최솟값을 찾아내는 연산을 빠르게 하기 위해 고안된 완전이진트리(complete binary tree)를 기본으로 한 자료구조(tree-based structure)

• • Max heap (최대 힙): 부모 노드는 자식 노드보다 항상 크거나 같은 값을 가짐

  • Min heap (최소 힙) : 부모 노드는 자식 노드보다 항상 작거나 같은 값을 가짐

  • 키값의 대소관계는 부모-자식노드간에만 성립, 형제 사이에는 대소관계 정해지지 않음

• 가장 높(낮)은 우선순위를 가지는 노드가 항상 뿌리노드에 위치 > 우선순위 큐(Priority queue)와 같은 추상적 자료형 구현 가능

해싱 (Hashing)

---

• 키(key)에 대한 자료를 검색하기 위한 사전(dictionary) 개념의 자료 구조

• key - value 한 쌍, key는 유일

• index = h(key)

  • 해시함수를 사용하여 키를 해시값으로 매핑, 인덱스 반환
  • 해당 인덱스 위치에 자료 저장, 검색

• 이렇게 저장되는 메모리 구조를 ‘해시테이블(Hash table)’이라고 함