힙/이진탐색

최소 힙: 가장 작은 값을 먼저 찾는 힙

n개의 노드를 가지고 있는 힙의 높이는 O(log n)이다.

힙은 완전 이진트리이므로 마지막 레벨 h을 제외하고는 각 레벨 i에 2^i-1개의 노드가 존재한다.

힙은 완전 이진트리이므로 배열로 구현할 수 있다.

레벨 순회로 방문하는 순서를 각 노드의 번호로 할당하고 그 번호를 배열의 인덱스로 활용 가능하다.

배열을 이용한 힙의 구현이 가장 보편적이다.

배열로 구현하면 부모 노드와 자식 노드를 쉽게 찾을 수 있다.

왼쪽 자식의 인덱스는 부모의 인덱스 * 2이다.

오른쪽 자식의 인덱스는 부모의 인덱스 * 2 + 1이다.

부모의 인덱스는 자식의 인덱스 / 2이다.

힙의 삽입 연산을 구현하는 방법으로 새로운 요소가 들어오면, 새로운 요소를 힙의 마지막 노드에 있다고 가정한 후 힙의 성질을 만족하도록 부모 노드들과 교환하여 상승시킨다.

힙의 삭제 연산을 구현하는 방법으로 루트 노드를 삭제하고 마지막 노드를 루트 노드로 이동한 후 루트에서 단말 노드로 이동하면서 경로에 있는 노드들을 교환하여 힙의 성질을 만족시킨다.

힙의 삽입/삭제 연산 복잡도 분석

삽입 연산의 시간 복잡도: O(log n)

삽입 연산의 최악의 경우: 루트 노드까지 올라가야 하므로 최대 트리의 높이에 해당하는 비교 연산 및 이동 연산이 필요하다.

삭제 연산의 시간 복잡도: O(log n)

삭제 연산의 최악의 경우: 가장 아래 레벨까지 내려가야 하므로 최대 트리의 높이 만큼의 시간이 걸린다.

힙 정렬(sorting)은 힙을 이용한 정렬이다.

오름차순으로 정렬한 경우, 정렬해야 하는 요소들의 최소 힙에 모두 삽입한 후 하나씩 꺼내 오면서 저장한다.

내림차순으로 정렬한 경우, 요소들을 최대 힙에 모두 삽입한 후 하나씩 꺼내 오면서 저장

힙 정렬의 시간 복잡도는 O(n * log n)로 빠른 편이다.

이진 탐색 알고리즘은 트리와 리스트로 구현할 수 있다.

이진 탐색 트리의 모든 노드의 키는 유일하다(중복된 값이 없어야 한다.)

왼쪽 서브 트리 키들은 노드 키보다 작아야 한다.

오른쪽 서브 트리 키들은 노드 키보다 커야 한다.

왼쪽과 오른쪽 서브 트리 모두 이진 탐색 트리이다.(순환적 정의)

이진 탐색 트리에서 순환적 탐색을 하기 위해서는

트리에서 찾고자 하는 값 s와 현재 노드 키 값이 같으면 반환한다.

s가 노드 키 값보다 작으면 왼쪽 서브 트리를 탐색한다.

s가 노드 키 값보다 크면 오른쪽 서브 트리를 탐색한다.

이진 탐색 트리에서 삽입 연산을 수행하려면 삽입하고자 하는 값과 같은 값을 가지는 노드가 있는지 탐색이 필요하다.

이진 탐색 트리는 같은 값을 가지는 노드가 두 개 이상 존재할 수 없기 떄문이다.

탐색에 실패한 위치가 새로운 노드를 삽입하는 위치가 된다.

이진 탐색 트리에서 삭제 연산을 수행하는 데 3가지 경우가 존재한다.

첫 번째는 삭제하려는 노드가 단말 노드일 경우

두 번째는 삭제하려는 노드가 하나의 서브 트리만 가지고 있는 경우

세 번째는 삭제하려는 노드가 두 개의 서브 트리 모두 가지고 있는 경우

첫 번째 경우인 삭제하려는 노드가 단말 노드일 경우에는

단말 노드의 부모 노드를 찾아서 연결을 끊는다.

두 번째 경우인 삭제하려는 논드가 하나의 서브 트리만 가지고 있는 경우에는

해당 노드를 삭제하고 서브 트리를 부모 노드에 붙인다.

세 번째 경우인 삭제하려는 노드가 두 개의 서브 트리 모두 가지고 있는 경우에는

삭제 노드의 왼쪽 서브 트리 중 가장 큰 값, 또는 오른쪽 서브 트리 중 가장 작은 값 중에 하나를 삭제 위치로 이동시킨다.

이진 탐색 트리에서의 탐색/삽입/삭제 연산의 시간 복잡도는 트리의 높이 h에 비례한다.

이진 탐색 트리에서 트리가 균형적으로 생성된 경우를 최선의 경우라고 한다.

h : O(log2n)

이진 탐색 트리에서 트리가 한 쪽으로 치우쳐 생성된 경우를 최악의 경우라고 한다.

h = O(n)