76일차 TIL ( 면접 카타 9일차 )

17. 이진트리, 이진 검색트리, 힙이 각각 무엇인지 설명하고, 차이점을 설명해주세요

답:
1. 이진 트리 : 각 노드가 최대 두 개의 자식 노드를 가질 수 있는 트리 구조입니다.
- 특별한 정렬 규칙이 없으며, 단순히 트리 형태를 유지하는 것이 특징입니다.
- 대표적인 예로 이진 검색 트리, 힙, 완전 이진 트리 등이 있습니다.

예제로는 : 
- 파싱 트리 -> 수식 계산을 위한 구문 분석
- 네트워크 구조 표현 -> 네트워크 토폴로지

2. 이진 검색 트리: 이진 트리의 한 종류로, 왼쪽 자식 노드는 부모보다 작고, 오른쪽 자식 노드는 부모보다 큰 값을 갖는 트리입니다.

특징으로는:
- 평균적으로 탐색, 삽입, 삭제가 O(log n)
- 중위 순회 시 오름차순 정렬된 결과 반환
- 군형이 깨질 경우 성능 저하 가능 (최악의 경우O(n))
-> 이를 해결하기 위해 AVL 트리, Red-Black 트리 같은 Self-balancing BST 사용

예제:

- 데이터베이스 인덱스(B+ Tree 등) → 검색 최적화
- 검색 자동 완성 시스템 → 정렬된 데이터 탐색

3. 힙 : 완전 이진 트리의 형태를 가지며, 부모-자식 간의 특정한 우선순위 관계를 유지하는 트리입니다.

종류:
- 최대 힙: 부모 노드가 자식보다 항상 크거나 같음
- 최소 힙: 부모 노드가 자식보다 항상 작거나 같음

특징: 
- 탐색이 O(n), 삽입/삭제가 O(log n)
- 최댓값 또는 최솟값을 빠르게 찾는 데 유리 ( 우선순위 큐 활용 )
- 정렬된 순서로 데이터 저장은 불가능 ( 단, 힙 정렬을 활용 가능 )

예제 :
- 우선순위 큐 -> 운영체제의 작업 스케줄링
- 다익스트라 알고리즘 -> 최단 경로 탐색


18. 해시테이블과 이진 검색트리를 비교하고 장단점을 이야기해주세요


답: 해시 테이블과 이진 검색 트리는 데이터 검색을 최적화 하는 대표적인 자료구조지만, 동작 방식과 특성이 다릅니다. 각각의 특징과 차이를 비교해보겠습니다.

1. 해시 테이블 : 키-값 쌍을 저장하는 자료구조로, 해시 함수를 사용해 데이터를 배열의 특정 위치(버킷)에 저장합니다.

- 시간 복잡도 : 평균적으로 검색, 삽입, 삭제가 O(1) (단, 해시 충둘이 발생하면 O(n)생깁니다.

- 특징 :
- 빠른 데이터 조회 가능
- 정렬된 데이터 저장 불가능 ( 순차적 탐색 어려움 )
- 해시 충돌 해결을 위한 추가 비용 발생 ( 체이닝, 개방 주소법 등 )

-사용 사례:
- 데이터베이스 인덱스 (해시 기반 인덱싱)
- 캐시 시스템 (ex: 웹 브라우저 캐싱)


2. 이진 검색 트리 : 왼쪽 자식 노드는 부모보다 작고, 오른쪽 자식 노드는 부모보다 큰 값을 갖는 트리 구조 입니다.

- 시간 복잡도: 평균적으로 검색, 삽입, 삭제가 O(log n) (단, 트리가 한쪽으로 치우치면 O(n))

- 특징 :
- 데이터가 정렬된 상태로 저장됨 (중위 순회 시 오름차순 출력 가능)
- 특정 범위의 데이터 검색에 유리
- 균형이 깨지면 성능 저하 가능 (-> AVL 트리, Red-Black 트리 사용)

- 사용 사례:
- 데이터베이스 인덱스 (B-Tree, AVL Tree)
- 검색 자동 완성 시스템 


3. 장단점 비교

O 해시테이블의 장점
- 평균 O(1)으로 빠른 검색 가능
- 데이터 크기가 크더라도 일정한 성능 유지 가능
- 간단한 구현으로 빠른 조회가 필요한 경우 유리

X 단점
- 정렬된 데이터 검색 불가능
- 해시 충동 발생 시 성능 저하 가능
- 추가적인 메모리 공간( 버킷, 충동 해결용 구조) 필요

O 이진 검색 트리(BST)의 장점 
- 데이터가 정렬된 상태로 유지됨
- 범위 검색(Range Query)에 유리
- 추가적인 공간이 적게 필요

X 이진 검색 트리(BST)의 단점
- 탐색 성능이 O(log n) 으로 해시테이블보다 느림
- 균형이 깨지면 성능 저하 (-> 균형 트리 필요)
- 삽입/삭제 시 트리 균형 유지 비용 발생

1.핵심 개념을 먼저 정의하고 비교하기

- "해시테이블은 키-값 기반, 이진 검색 트리는 정렬된 트리 기반입니다."

2. 시간 복잡도 비교를 통해 차이 설명

- "해시테이블은 평균적으로 O(1) 탐색이 가능하지만, 충돌이 발생하면 성능이 저하됩니다. 반면, 이진 검색 트리는 O(log n) 성능을 유지하지만, 균형이 깨지면 O(n)까지 성능이 떨어질 수 있습니다."

3. 실무 사례와 연결하기

- "해시테이블은 캐싱 시스템, 데이터베이스 인덱스에 사용되고, 이진 검색 트리는 검색 엔진, 범위 기반 검색에 활용됩니다."