1. 이진 탐색 트리(Binary Search Tree)
- 이진 탐색 : 탐색에 소요되는 시간복잡도는 O(logN), 그러나 삽입 삭제 불가능
- 연결리스트 : 삽입 삭제의 시간 복잡도는 O(1), 그러나 탐색하는 시간 복잡도가 O(N)
이 두가지를 합하여 장점을 모두 얻는 것이 이진탐색트리 - 즉 효율적인 탐색 능력을 가지고, 자료의 삽입 삭제도 가능하게!
2. 특징
- 각 노드의 자식이 2개 이하
- 각 노드의 왼쪽 자식은 부모보다 작고, 오른쪽 자식은 부모보다 큼.
- 이진 탐색트리의 순회는 중위순회
- 중복 노드가 없어야 함.
검색이 목적인데, 중복이 많은 경우 트리 사용 안함.
트리에 삽입하는 것보다, 노드에 count 값을 가지게 하여 처리
3. 이진탐색트리 핵심 연산
- 검색
- 삽입
- 삭제
- 트리 생성
- 트리 삭제
4. 시간 복잡도
- 균등 트리 : 노드 개수가 N개 -> O(logN)
- 편향 트리 : 노드 개수가 N개 -> O(N)
삽입, 삭제, 검색 시간 복잡도는 트리의 Depth 비례
5. 삭제의 3가지 case
- 자식이 없는 leaf노드 -> 그냥 삭제
- 자식이 1개 -> 지워진 노드에 자식 올리기
- 자식이 2개 -> 오른쪽 자식 노드에서 가장 작은 값 or 왼쪽 자식 노드에서 가장 큰 값 올리기
smilegate