[Data Strucutre] 면접 질문 대비

• 힙
  • 최대값 혹은 최소값을 빠르게 찾기 위한 이진 트리
  • 최소 힙인 경우, 부모는 자식보다 값이 작고
  • 최대 힙인 경우, 부모가 자식보다 값이 크다
  • 힙의 삽입과 삭제는 O(log n) 만큼의 시간 복잡도를 가진다
• 이진탐색트리
  • 왼쪽 자식은 부모 보다 작고, 오른쪽 자식은 부모보다 큰 이진트리가 이진 탐색 트리
  • 삽입,검색,삭제가 모두 트리의 높이인 O(log n ~ N) 만큼의 시간복잡도를 가짐
  • 시간 복잡도가 O(N)이 되는 상황인 편향된 트리를 방지하기 위해 자가 균형 트리를 사용함
• 자가 균형 트리
  • 이진 탐색 트리는 시간 복잡도가 트리의 높이에 따라 결정되므로 편향 될경우 효율이 떨어짐
  • 이를 방지하기위해 삽입과 삭제를 개선한 이진탐색트리를 자가균형트리라고 함
  • AVL 트리 , Red Black 트리가 있음
• 해시
  • 해시에 매핑하여 데이터를 저장하는 자료 구조
  • key는 hash function을 통해 hash로 변경된 다음, value와 매핑되어 bucket에 저장됨
  • 시간 복잡도는 삽입,삭제,조회 모두 O(1)임
• 충돌 회피 방법
  • 해시에서 하나의 버킷에 여러개의 데이터가 들어갈때 충돌을 회피하는 기법으로
  • Open Addressing과 Chaining이 있다
    • Open Addressing
      • 다른 해시값에 저장함
    • Chaining
      • 해시 테이블이 원소를 Linked list에 저장함