✅ 이진 탐색 트리
탐색 작업을 효율적으로 하기 위한 자료 구조
- 모든 노드의 데이터가 서로 다른 이진 트리
- 어느 노드에게 자식이 있는 경우
- 왼쪽 자식의 데이터는 부모보다 작다
- 오른쪽 자식의 데이터는 부모보다 크다
루드 노드 기준으로
- 왼쪽 서브 트리의 모든 데이터는 루트 노드보다 작다.
- 오른쪽 서브 트리의 모든 데이터는 루트 노드보다 크다.
- 중위 순회 할 경우, 오름차순 정렬된 데이터를 얻을 수 있다.
✅ 탐색
- 루트 노드와 탐색데이터를 비교
- 데이터가 더 작을 경우 왼쪽 서브트리로 (6과 12를 비교)O(h) ~ O(logn)
- 데이터가 더 클 경우 오른 쪽 서브트리로
- 편향 이진트리의 경우 O(n)
✅ 삽입
- 탐색 과정을 따라간다.
- 탐색에 성공할 경우 삽입 불가
- 탐색에 실패하는 시점에 새로운 노드로 데이터 추가
✅ 삭제
- 삭제할 데이터를 가진 노드를 탐색
- 삭제할 노드가 단말 노드면 삭제 (링크 해제)
- 삭제할 노드에 자식이 하나일 경우 부모와 대신 연결
- 자식이 두개일 경우, 왼쪽 서브 트리의 값 중 제일 큰 노드
- 오른쪽 서브트리의 값 중 제일 작은 노드 중 하나와 교체
✅ 노드로 이진 탐색 트리 구현하기
- insert()데이터를 BST에 추가(삽입)
- serch() 어떤 데이터가 BST에 존재하는지 판단(탐색)
- delete()데이터를 BST에서 제거(삭제)
구현 코드
- insert()
- serch()
- delete()
'Algorithm' 카테고리의 다른 글
그래프 Graph 알고리즘 (0) | 2023.07.09 |
---|---|
브루트 포스 Brute Force 알고리즘 (0) | 2023.07.09 |
버블정렬, 선택정렬, 계수정렬 알고리즘 (0) | 2023.07.09 |
Tree 트리 구조 알고리즘 (0) | 2023.06.21 |
깊이우선탐색(DFS), 너비우선탐색(BFS) 알고리즘 (0) | 2023.06.13 |