힙 (Heap)
-
최대값or최소값을 빠르게 찾기 위한 이진트리 -
삽입,삭제시, 힙 재정렬 (Re-Heapification) 수행
=>O(log_2 n)
Question) "힙에 대해 설명해 주세요."
힙은최대값혹은최소값을 빠르게 찾기 위한 이진트리 입니다.
최소힙의 경우 부모는 자식보다 작고,최대힙의 경우 부모는 자식보다 큽니다.
힙은삽입,삭제시, 힙 재정렬이 수행되어O(log_2 n)만큼의 시간 복잡도를 갖습니다.
이진 탐색 트리 (BST, Binary Search Tree)
-
왼쪽 자식은 부모보다 작고, 오른쪽 자식은 부모보다 큰 이진 트리
-
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트리가 있습니다.
해시 (Hash)
-
해시에 맵핑하여 데이터를 저장하는 자료구조 -
검색,삽입,삭제시간 복잡도가 모두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를 저장 합니다.
