-
(7) 이진탐색트리자료구조/Tree 2021. 5. 2. 13:23
■ 이진 탐색트리
1) 정의 :
> Linked list
- O(1) 삽입 / 삭제
- O(N) 탐색 복잡도
> Binary Search
- 자료구조가 sorting되어있는 상태에서 시행
- O(logN) 탐색 복잡도
※ 위 두개의 장점을 합친 방식으로 자료구조를 짠 것이
'이진 탐색 트리'
2) 이진탐색 트리 특징
(a) 각 노드의 자식이 2개 이하
(b) 완전이진트리 구조는 아님!!
- 각 노드의 왼쪽 자식은 부모보다 작고, 오른쪽 자식은 부모보다 같거나 큼
(c) 중복노드 많은 경우 - 다른 자료구조 사용하는 것이 효율적
(d) 평균시간복잡도 O(log(N))
편향 트리인 경우 O(N)에 가까워 짐 → 트리가 왼쪽 / 오른쪽으로 쏠려있는 경우
3) 트리 변경의 3가지 case
- 자식이 없는 leaf 노드일 때 → 그냥 삭제
- 자식이 1개인 노드일 때 → 지워진 노드에 자식을 올리기
- 자식이 2개인 노드일 때 → 오른쪽 자식 노드에서 가장 작은 값 or 왼쪽 자식 노드에서 가장 큰 값 올리기
참조 :
gyoogle.dev/blog/computer-science/data-structure/Binary%20Search%20Tree.html
반응형'자료구조 > Tree' 카테고리의 다른 글
(6) Tree - Heap (0) 2021.04.28