최대값
or 최소값
을 빠르게 찾기 위한 이진트리
삽입
, 삭제
시, 힙 재정렬 (Re-Heapification) 수행
=> O(log_2 n)
Question) "힙에 대해 설명해 주세요."
힙
은최대값
혹은최소값
을 빠르게 찾기 위한 이진트리 입니다.
최소힙
의 경우 부모는 자식보다 작고,최대힙
의 경우 부모는 자식보다 큽니다.
힙
은삽입
,삭제
시, 힙 재정렬이 수행되어O(log_2 n)
만큼의 시간 복잡도를 갖습니다.
왼쪽 자식은 부모보다 작고, 오른쪽 자식은 부모보다 큰 이진 트리
Node
클래스 정의
필드로 Node leftChild
, Node rightChild
새 노드를 추가하는 insert()
메소드는 추가하려는 새 노드를
leftChild
, rightChild
와 각각 비교하는 과정을 재귀적으로 수행
검색
, 삽입
, 삭제
가 모두 트리의 높이인 O(log_2 n)
~ O(n)
=> 이진 탐색 트리가 한쪽으로 편향될 경우, O(n)
Question) "이진 탐색 트리 (Binary Search Tree)에 대해 설명해 주세요."
이진 탐색 트리
는 왼쪽 자식은 부모보다 작고, 오른쪽 자식은 부모보다 큰 이진 트리 입니다.
검색
,삽입
,삭제
가 모두 트리의 높이인O(log_2 n)
~O(n)
만큼의 시간 복잡도를 갖습니다.
이진 탐색 트리의 구현은Node
클래스를 정의하여 구현 합니다.
Node
클래스는 속성으로Node leftChild
,Node rightChild
를 갖습니다.
새 노드를 추가하는insert()
메소드는 추가하려는 새 노드를
leftChild
,rightChild
와 각각 비교하는 과정을 재귀적으로 수행하여 구현 합니다.
추가적으로,이진 탐색 트리
가 편향되지 않도록 하기 위해서,자가 균형 이진 탐색 트리
를 사용 합니다.
편향되지 않게 삽입
, 삭제
를 개선한 이진 탐색 트리
종류로는 AVL Tree
, Red-Black Tree
존재
Question) "자가 균형 이진 탐색 트리에 대해 설명해 주세요."
이진 탐색 트리
는검색
,삽입
,삭제
시간 복잡도가
트리의 높이에 따라 결정되므로, 트리가 편향될 경우 그 효율이 떨어집니다.
따라서, 트리가 편향되지 않게삽입
,삭제
를 개선한
이진 탐색 트리
를자가 균형 이진 탐색 트리
라고 합니다.
자가 균형 이진 탐색 트리
의 종류로는AVL 트리
와Red-Black
트리가 있습니다.
해시
에 맵핑하여 데이터를 저장하는 자료구조
검색
, 삽입
, 삭제
시간 복잡도가 모두 O(1)
Question) "해시에 대해 설명해주세요."
해시
에 맵핑하여 데이터를 저장하는 자료구조 입니다.
key
는Hash Function
을 통해hash
로 변경된 후,
value
와 맵핑되어Bucket
에 저장되게 됩니다.
시간 복잡도는검색
,삽입
,삭제
모두O(1)
입니다.
Open Addressing
: 다른 해시 값에 저장
ex) 0번 Bucket에 이미 원소가 저장되어 있으면, 다른 빈 Bucket에 저장
Chaining
: Hash Table
에 1개의 원소만 저장하는게 아닌, Linked List
를 저장
Question) "해시 충돌 회피 방법에 대해 설명해 주세요."
해시 충돌 회피 방법은 해시에서 하나의Bucket
에 여러 개의 원소가 들어갈 때,
그 충돌을 회피하는 방법으로Open Addressing
과Chaining
이 있습니다.
Open Addressing
은 충돌 발생 시, 다른 해시 값에 저장하는 방법 입니다.Chaining
은Hash Table
에 1개의 원소만 저장하는게 아닌,Linked List
를 저장 합니다.