Hash table & BST

BST에 대해 설명해 주세요

각 노드의 key는 왼쪽 부분 트리의 key보다 크고 오른쪽 부분 트리의 key보다 작다는 규칙을 가진 트리

 

• 그래프와 트리의 차이가 무엇인가요?

트리는 그래프의 한 종류로 그래프 중에서 방향성이 없고 사이클이 없는 그래프를 뜻한다.

• 이진탐색트리에서 중위 탐색을 하게 되면, 그 결과는 어떤 의미를 가지나요?

중위 탐색은 1. 왼쪽 자식 노드 2. 부모 노드 3. 오른쪽 자식 노드 순으로 트리를 순회한다.

위 예시를 1 - 3 - 4 - 6 - 7 - 8 - 10 - 13 - 14 순으로 방문하며 오름차순 정렬이 된다.

• 이진탐색트리의 주요 연산에 대한 시간복잡도를 설명하고, 왜 그런 시간복잡도가 도출되는지 설명해 주세요.

이진탐색트리의 탐색 연산 시간복잡도는 O(h)입니다. BST 특성상 자신보다 작을 경우 왼쪽 트리, 자신보다 클 경우 오른쪽 트리만 탐색하면 되기 때문입니다.

• 이진탐색트리의 한계점에 대해 설명해주세요.

이진탐색트리 자식 노드 높이가 균등하면 O(log n)이라는 빠른 시간에 데이터를 탐색할 수 있지만 트리가 한쪽으로 쏠린 경우 최대 O(n)이라는 한계가 있습니다.

• 이진탐색트리의 값 삽입, 삭제 방법에 대해 설명해주세요.

삽입

1. 루트의 키보다 작다면 왼쪽 서브 트리를 탐색하고 비어 있다면 삽입 아니면 다시 값비교

2. 루트의 키보다 크다면 오른쪽 서브 트리를 탐색하고 비어 있다면 삽입 아니면 다시 값비교

 

삭제

1. 삭제할려는 노드가 leaf node인 경우, 그냥 삭제

2. 삭제할려는 노드의 자식 노드가 1개인 경우, 부모와 자식을 연결하고 자기 자신 삭제

3. 삭제할려는 노드의 자식 노드가 2개인 경우

삭제할 노드 왼쪽 서브 트리의 가장 큰 자손을 해당 노드의 자리에 올린다.

삭제할 노드 오른쪽 서브 트리의 가장 작은 자손을 해당 노드의 자리에 올린다.

 

Hash table은 어떤 자료구조인가요?

해시함수를 통해 변환한 값을 index로 사용하여 데이터를 빠르게 탐색할 수 있는 자료구조

 

• Hash table에서 collision이 발생하면 어떻게 되나요? 해결방법엔 뭐가 있을까요?

Collision이란 서로 다른 key를 해시함수에 넣었는데 동일한 결과가 나오는 현상이다.

 

해결 방법으로는 크게 분리 연결법(separate chaining), 개방 주소법(open addressing)이 있다.

 

분리 연결법

collision이 일어난 데이터에 대해 추가 메모리를 사용하여 다음 데이터를 연결해 주는 방식이다. 테이블 확장이 필요없어 구현이 간단하다는 장점이 있지만, chaining이 많아지면 성능이 떨어진다는 단점이 있다. 

개방 주소법

추가적인 메모리를 사용하는 chaining과 다르게 비어있는 해시테이블 공간을 찾아 데이터를 저장하는 방식이다.

• 본인이 사용하는 언어에서는, 어떤 방식으로 해시 충돌을 처리하나요?

자바에서는 Separate Chaining기법을 통해 해시 충돌을 해결한다.

• Double Hashing 의 장점과 단점에 대해서 설명하고, 단점을 어떻게 해결할 수 있을지 설명해 주세요.

Double Hashing의 장점은 2개의 해시 함수를 사용하기 때문에 첫번째 함수값이 같더라도 두번째에 또 같을 확률이 낮아 군집 문제가 덜 발생한다. 그러나 해시 함수를 2개 사용하기 때문에 어떤 해시함수를 쓰느냐에 따라 성능차이가 더 크게 나타난다.