힙(Heap)과 이진탐색트리(Binary Search Tree)

힙(Heap)

- 트리구조 중 하나로 우선순위 큐를 구현할 때 사용됩니다. (다익스트라에서도 사용됨.)

- 우선순위 큐의 특징 : 데이터를 자유롭게 추가 가능, 꺼낼 때는 가장 작은 데이터를 꺼냅니다.

 

- 힙은 노드들로 구성되어 있습니다.

각각의 노드들은 부모와 자식으로 이루어져 있고, 부모는 최대 2개의 자식 노드를 가질 수 있습니다.

- 부모 노드의 데이터가 자식 노드의 데이터보다 항상 작아야합니다.

 

ex) 새로운 수를 힙에 추가하는 예시.

1) 새로운 숫자를 힙의 가장 끝에 추가합니다.

2) 만약 부모 노드가 존재한다면, 부모 노드와 데이터를 비교 후 숫자가 더 작다면 그 둘의 위치를 바꿔줍니다.

3) 계속 그렇게 해서, 더 이상 부모보다 작지 않을 경우, 정렬은 종료됩니다.

 

ex) 숫자를 하나 꺼낼때의 예시.

1) 가장 맨 위의 부모 노드를 꺼냅니다.

2) 맨 위의 부모 노드 자리에 힙의 마지막에 있는 노드를 옮겨줍니다.

3) 올라온 노드를 자식노드와 비교하여, 더 작은 노드와 교체시켜줍니다.

 

힙을 꺼낼 때의 시간복잡도 : O(1)

힙에서 데이터를 꺼낸 후 재정렬 : O(log n)

데이터를 추가할 때의 시간복잡도 : O(log n)

 

---

이진 탐색 트리 (Binary Search Tree)

- 그래프의 트리 구조로 각 노드에 데이터가 저장됩니다.

- 각 노드의 값은 왼쪽 가지의 데이터들 보다 크고, 오른쪽 가지의 데이터들 보다 작습니다.

ex) 숫자를 하나 추가하는 예시.

1) 맨 위 부모노드와 비교하여 본인보다 크면 오른쪽으로, 작으면 왼쪽으로 보냅니다.

2) 더이상 노드가 없을 때 해당 위치에 노드를 추가합니다.

 

ex) 숫자 하나를 삭제하는 예시. (자식 노드가 없는 경우)

1) 바로 삭제하면 끝이다.

 

ex) 숫자 하나를 삭제하는 예시. (자식 노드가 1개 있는 경우)

1) 숫자를 삭제하고, 자식노드를 해당 위치에 배치하면 됩니다.

 

ex) 숫자 하나를 삭제하는 예시. (자식 노드가 2개 있는 경우)

1) 숫자를 삭제한다.

2) 삭제한 노드의 왼쪽 가지에서 가장 큰 값을 꺼내서 삭제한 위치로 이동시킨다.

 

- 값을 찾을 때 (Search)

원하는 값을 맨 위 부모 노드와 비교 후 작으면 왼쪽 자식 노드와 비교하고,

크면 오른쪽 자식 노드와 비교하면 됩니다.

 

시간복잡도

- 비교 연산 : 균형 있게 배치되어 있을 경우 O(log n), 한쪽으로 치우쳐져 있을 경우 O(n)

 

발전된 알고리즘

- 균형 이진 탐색 트리 : 매 연산뒤에 트리의 형태를 수정하여 항상 균형을 유지하는 트리.

- B 트리 : 최대 자식 노드를 m개로 확장한 트리.