이진 탐색 트리
탐색작업을 효율적으로 하기 위한 자료 구조
모든 원소는 다른 키를 가짐
key(왼쪽 서브트리) < key(루트 노드) < key(오른쪽 서브트리)
각각의 서브트리도 이진 탐색 트리
중위 순회 > 오른차순으로 정렬된 값을 얻을 수 있음
탐색 연산
루트에서 시작
키 값 x
루트노드 키 값 r
- x = r : 원하는 원소이므로 탐색연산 성공
- x < r : 루트노드의 왼쪽 서브트리에 대해 탐색연산
- x > r : 루트노드의 오른쪽 서브트리에 대해 탐색연산
서브트리에 대해 순환적으로 탐색 연산을 반복하기
삽입 연산
탐색연산을 수행하다 탐색 실패한 위치에 원소 삽입
검색 알고리즘의 시간복잡도
| 검색 알고리즘 | 시간 복잡도 |
| (정렬된) 배열에서의 순차 검색 | O(N) |
| 정렬된 배열에서의 이진탐색 (고정 배열 크기와 추가 연산 필요) |
O(logN) |
| 이진 탐색트리에서의 평균 최악의 경우 (완전 이진 트리와 균형트리로 바꾼다면 평균, 최악) |
O(logN) O(N) ( O(logN) , O(logN)) |
| 해쉬 검색 (추가 저장 공간 필요) |
O(1) |
heap
완전 이진 트리에서 키값이 가장 크거나 가장 작은 노드를 찾기 위해 만든 자료구조
max heap
키값이 가장 큰 노드를 찾기 위한 완전 이진 트리
부모노드 키값 > 자식노드 키값
루트 : 키값이 가장 큰 노드
min heap
키값이 가장 작은 노드를 찾기 위한 완전 이진 트리
부모노드 키값 < 자식노드 키값
루트 : 키값이 가장 작은 노드
힙 연산
삽입
가장 크거나 가장 작은 숫자가 아닌 경우 일반 노드에서 확장이 되어 삽입됨
숫자가 큰 경우 부모 노드와 비교하며 자리바꾸기
> max heap이 됨
삭제
힙에서는 루트 노드의 원소만 삭제할 수 있다
1. 루트 노드의 원소 삭제
2. 마지막 노드를 루트로 옮김
3. 더 큰 자식 노드와 자리 바꾸기
4. 빈 자식이 없으면 멈춤 , 부모>자식이 유지되는 채로
힙의 키를 우선순위로 하여 우선순위 큐를 구현할 수도 있음
'CS > 자료구조' 카테고리의 다른 글
| Tree - Binary Tree (1) | 2024.02.20 |
|---|---|
| Queue (1) | 2024.02.15 |
