이진탐색 Binary searching, AVL 트리 - 알고리즘
by 효기’s장점 : 고속 탐색 가능
단점 : 정렬 데이터에만 적용 가능
time complexity(시간복잡도) : O(log n)
이진탐색트리 (Binary sarch tree)
정의 : 탐색작업을 효율적으로 하기 위한 자료구조
왼쪽 서브트리 노드의 키값 < 루트 노드의 값 < 오른쪽 서브트리 노드의 키값
AVL 트리
최악의 경우 = O(n)
트리 균형이 나쁘면 = O(log n)
트리구조가 complete binary tree인 경우 바람직.
정의 : 모든 노드에 있어 왼쪽 서브트리와 오른쪽 서브트리 높이 차가 1이내인 binary search tree
★ 왼쪽 높이 - 오른쪽 높이 = 1이내
AVL 트리 삽입
Binary Search Tree 삽입과 동일
균형 조정
leaf에서 root를 향해 차례로 진행
필요한 경우 회전(rotation) 진행
'Algoritum' 카테고리의 다른 글
| Day10 자료구조 정렬의 시간복잡도 (20) | 2023.07.17 |
|---|---|
| Day09 자료구조 정렬 알고리즘 (16) | 2023.07.15 |
| B 트리(B-tree) - 알고리즘 (0) | 2022.12.06 |
| 버블정렬(bubble sort) - 알고리즘 (1) | 2022.12.05 |
| 해싱(hashing) - 알고리즘 (2) | 2022.12.02 |
블로그의 정보
감성 개발자 효기
효기’s