[면접준비] 자료구조 면접준비 2탄

AVL 트리 란 무엇인가?

 

AVL 트리( Adelson-Velsky and Landis tree) 는 앞서 설명한 최악의 경우 선형적인 트리가 되는 것을 방지하고 스스로 균형을 잡는 이진트리 입니다 두 자식 서브 트리의 높이는 항상 최대 1만큼 차이 난다는 특징이 있습니다

AVL 트리는 탐색,삽입,삭제 모두 시간 복잡도가 O(logn)이며 삽입, 삭제를 할 때마다 균형이 안맞는 것을 맞추기 위해 트리 일부를 왼쪽 혹은 오른쪽으로 회전 시키며 균형을 잡습니다

 

레드 블랙 트리란 무엇인가?

레드 블랙 트리는 균형 이진 탐색 트리로 탐색 , 삽입 , 삭제 모두 시간 복잡도가 O(logn)입니다

각 노드는 빨간색 또는 검은색의 색상을 나타내는 추가 비트를 저장하며 , 삽입 및 삭제 중에 트리가 균형을 유지하도록 하는 데 사용됩니다

 

모든 리프 노드와 루트 노드는 블랙이고 어떤 노드가 레드이면 그 노드의 자식은 반드시 블랙이다 란 규칙을 기반으로 균형을 잡는 트리입니다!

 

힙(Heap)

 

힙은 완전 이진 트리 기반의 자료구조이며 최소힙과 최대 힙 두가지가 있고 해당 힙에 따라 특정한 특징을 지킨 트리를 말합니다

 

최대힙 : 루트 노드에 있는 키는 모든 자식에 있는 키 중에서 가장 커야 합니다 도한 각 노드의 자식 노드와의 관계도 이와 같은 특징이 재귀적으로 이루어져야합니다

 

최소힙 : 최소힙에서 루트노드에 있는 키는 모든 자식에 있는 키 중에서 최솟값이어야합니다 또한 각 노드의 자식 노드와의 관계도 이와 같은 특징이 재귀적으로 이루어져야합니다

 

최대힙의 삽입

힙에 새로운 요소가 들어오면 일단 새로운 노드를 힙의 마지막 노드에 이어서 삽입합니다 이 새로운 노드를 부모 노드들과의 크기를 비교하며 교환해서 힙의 성질을 만족시킵니다 

 

최대힙의 삭제

최대 힙에서 최댓값을 루트 노드 이므로 루트 노드가 삭제되고 그 이후 마지막 노드와 루트 노드를 스왑하여 또다시 스왑 등의 과정을 거쳐 재구성됩니다

 

우선순위 큐

 

우선순위 큐는 우선순위 대기열이라고도 하며 대기열에서 우선순위가 높은 요소가 우선 순위가 낮은 요소보다 먼저 제공되는 자료구조입니다

우선순위 큐는 힙을 기반으로 구현됩니다

 

 

맵(map)

맵(Map) 은 특정 순서에 따라 키와 매핑된 값의 조합으로 형성된 자료구조 입니다.

맵은 보통 레드 블랙 트리 자료구조를 기반으로 형성됩니다 

 

셋(set)

 

셋(set)은 특정 순서에 따라 고유한 요소를 저장하는 컨테이너 이며 중복되는 요소는 없고 오로지 희소한(unique) 값만 저장하는 자료구조입니다 즉 중복을 허용하지 않습니다

 

해시테이블

해시 테이블은 무한에 가까운 데이터들을 유한한 개수의 해시 값으로 매핑한 테이블입니다

삽입 , 삭제 , 탐색 시 평균적으로 O(1)의 시간 복잡도를 가지며 정렬을 보장하지 않습니다