힙과 이진탐색트리

1. 트리

특징

루프가 없는 무방향 그래프 구조

루트, 부모, 자식, 형제 노드로 구성되는 계층형 자료구조

하나의 루트가 존재하며, 자식 노드는 하나의 부모 노드만 가진다.

2. 힙

특징

최대값이나 최소값을 빠르게 찾기 위한 자료구조

왼쪽 자식 노드부터 채워지는 완전이진트리 구조

중복을 허용한다.

우선순위 큐를 구현하는 데 사용된다.

 

시간복잡도

원소 삽입: O(logN)

원소 삭제: O(logN)

 

*원소 삽입

1. 최하단에 노드를 삽입한다.

2. 부모 노드와 값을 비교해서 힙 종류에 맞게 스왑한다.

3. 스왑되지 않을 때까지 반복한다.

 

*원소 삭제

1. 루트 노드를 삭제한다.

2. 최하단 노드를 루트 노드로 옮긴다.

3. 자식 노드와 값을 비교해서 힙 종류에 맞게 스왑한다.

4. 스왑되지 않을 때까지 반복한다.

3. 이진탐색트리

특징

이진탐색의 빠른 속도를 유지하면서 삽입과 삭제도 원활하게 하는 자료구조

각 노드의 왼쪽 서브트리는 더 작은 값들로 구성된다.

각 노드의 오른쪽 서브트리는 더 큰 값들로 구성된다.

중복된 노드는 없다.

중위순회를 사용하면 오름차순으로 값을 읽을 수 있다.

 

시간복잡도

균등 트리: O(logN)

편향 트리: O(N)

편향 트리에서의 비효율을 해결하기 위해 B-Tree 등의 자료구조가 고안됐다.

 

*원소 삭제

1. 자식이 없는 노드 -> 바로 삭제

2. 자식이 하나인 노드 -> 자신의 자리에 자식 노드 올리기

3. 자식이 둘인 노드 -> 왼쪽 서브트리에서 가장 큰 값 혹은 오른쪽 서브트리에서 가장 작은 값 올리기