TIL ( 해시테이블과 이진검색트리 )

📑 해시 테이블 (Hash Table)

 

의의

 

해시 테이블은 키-값 쌍을 저장하는 데이터 구조로, 해시 함수를 사용하여 키를 해시 값으로 변환하고, 이를 기반으로 데이터를 저장한다.

 

장점

 

- 빠른 검색 속도:평균적으로 O(1) 시간 복잡도로 데이터를 검색할 수 있어 매우 빠르다
- 직관적인 키-값 쌍 저장: 데이터 삽입 및 검색이 키를 통해 직관적으로 이루어져 사용하기 쉽다.
- 유연한 크기 조정: 데이터 수가 증가하면 해시 테이블의 크기를 동적으로 조정할 수 있다.

 

( 💡  O(1)은 "상수 시간"이라고 하며, O(1) 시간 복잡도는 어떤 작업을 하는 데 걸리는 시간이 항상 일정하다는 의미한다. 입력 데이터의 크기와는 상관없이 같은 시간에 작업이 끝남을 의미한다. )

단점

 

- 충돌 처리: 두 개 이상의 키가 동일한 해시 값을 가질 경우 충돌이 발생하며, 이를 해결하기 위한 추가 작업이 필요하다.

- 메모리 사용: 해시 테이블이 비어 있을 때도 일정량의 메모리를 차지하며, 최악의 경우 O(n) 시간 복잡도를 가질 수 있다.

- 정렬 불가능: 해시 테이블은 데이터를 정렬된 상태로 유지하지 않기 때문에, 순서가 필요한 경우 불편하다.

 

📑이진 검색 트리 (Binary Search Tree, BST)

 

의의

 

이진 검색 트리는 각 노드가 최대 두 개의 자식을 가지며, 각 노드의 왼쪽 서브트리에는 해당 노드보다 작은 값, 오른쪽 서브트리에는 해당 노드보다 큰 값을 가지는 특성을 갖는 트리 구조이다.

 

장점

- 정렬된 데이터 유지: 이진 검색 트리는 데이터를 정렬된 형태로 유지하므로, 중위 순회를 통해 오름차순으로 데이터를 쉽게 출력할 수 있다.

- 효율적인 검색: 평균적으로 O(log n)의 시간 복잡도로 데이터를 검색할 수 있습니다. 적절히 균형 잡힌 트리인 경우 성능이 좋다.

- 동적 크기 조정: 노드를 추가하거나 삭제할 때 트리가 자동으로 조정된다.

 

단점

 

- 최악의 경우 성능 저하: 데이터가 정렬된 상태로 추가될 경우, 트리가 편향되어 O(n)의 성능을 보일 수 있다.

- 균형 유지 필요: 성능을 최적화하기 위해서는 트리를 균형 상태로 유지해야 하며, 이를 위해 추가적인 알고리즘이 필요할 수 있다.

- 복잡한 구현: 해시 테이블에 비해 구현이 복잡할 수 있다. (ex. 균형 잡힌 트리의 경우)