이진 탐색 트리(Binary Search Tree)
- 루트노드를 기준으로 왼쪽 노드이 값이 오른쪽 노드의 값보다 작은 트리
- 특정 값을 찾기가 쉬울 수 있다. 따라서 O(logn)의 복잡도를 대부분 가진다. 단, 이진 탐색 트리가 비효율적인 경우가 있다
- 예시(그림)
이진 탐색 트리의 추상적 자료구조
- 데이터 표현 : 각 노드는 (key, value)의 쌍으로 되어있다
- 키를 이용해 검색 가능하고 보다 복잡한 레코드로 확장 가능
연산의 정의
inser(key, data) : 트리에 주어진 데이터 원소 추가
remove(key) : 특정 원소를 트리로부터 삭제
lookup(key) : 특정 원소를 검색
inorder() : key의 순서대로 원소를 나열
min(), max() : 최소 key, 최대 key를 가지는 원소를 탐색
이진 탐색 트리에 원소 삽입
이진 탐색 트리에서 원소 삭제
1) 키(key)를 이용해 노드를 찾는다
- 해당 키의 노드가 없으면 삭제할 것도 없음
- 찾은 노드의 부모 노드도 알고있어야 함
2) 찾은 노드를 제거하고도 이진 탐색 트리의 성질을 만족하도록 트리의 구조를 정리
이진 탐색 트리에서 원소를 삭제하는 경우는 세가지이다
case1) 말단 leaf를 삭제
- 말단 leaf를 삭제하고 그 부모 node에게 삭제된 node가 left/right 인지에 따라 링크를 None으로 만들어 준다
- 삭제되는 node가 root node인 경우 빈 트리로 만들어준다
case2) 자식이 하나인 node 삭제 - 해당 node를 삭제하고 부모 node에게 삭제된 node가 left/right인지에 따라 삭제된 node의 자식 node를 연결해준다
- 삭제되는 node가 root node인 경우 자식 node를 root node로 만들어준다
case3) 자식이 둘인 node 삭제 - 해당 node를 삭제하면 자식이 둘이므로 문제가된다. 따라서 삭제 node 다음으로 큰 node(x라 하면)를 찾아서 삭제된 자리에 놓는다. 그리고 그 부모 node의 링크를 x가 부모의 left/right인지에 따라 x의 오른쪽에 있던 자식 node로 연결해준다.
힙(Heap)
- 이진 트리의 한 종류(이진 힙 binary heap)
- 루트 node가 언제나 최대 또는 최소값을 가진다
- 완전 이진트리(마지막 node제외한 모든 node가 채워져있고 마지막 leaf들은 왼쪽부터 채워져있는 트리) 이어야 한다.
- 재귀적으로 정의됨
최대 힙에 원소 삽입
- 트리의 마지막 자리에 새로운 원소를 임시로 저장
- 부모 노드와 키값을 비교하여 위로, 위로 이동
- 부모 노드와의 대소 비교 최대 회수 : O(logn)
최대 힙의 경우 root node가 최대값을 가지고 마찬가지로 각 서브 트리의 root node가 최대값이다. 다만, 각 node의 값들의 순서는 정렬이 되어있지않다.
최대 힙에서 원소 삭제
- 루트 노드(최대값) 제거
- 제거 후 완전 이진트리를 만족해야하므로 트리 마지막 노드를 임시로 루트 노드의 자리에 배치
- 임시 루트 노드를 자식 노드들과 값을 비교하면서 아래로 아래로 이동
. 자식이 둘인 경우 큰 값과 바꿈 - 자식 노드들과 대소 비교 최대 회수 : O(logn)
최대/최소 힙의 응용
- 우선순위 큐
- enqueue할 때 느슨한 정렬을 이루도록 함
- dequeue할 때 최대값을 순서로 추출함으로 시간적으로 효율성이 높다
- 힙 정렬
1) 정렬되지 않은 원소를 아무순서로 최대힙에 삽입 : O(logn)
2) 삽입 끈타면 최대/최소 원소 삭제로 최대값 또는 최소값 순서로 빼낼 수 있다 : O(logn)
3) 원소들이 삭제된 순서가 결국 정렬순서
4) 전체 정렬의 복잡도 : O(nlogn)
원하는 대로 살자