Binary Search Tree -> AVL Tree -> B Tree (-> B+ Tree)
BST의 검색/삽입/삭제 평균 시간복잡도는 O(logN)이다.
데이터 삽입 순서에 따라 tree의 균형이 달라진다.
최악의 경우는 한쪽으로만 쏠려 선형 구조처럼 된 경우이다.
이 때 시간복잡도는 O(logN)이 아닌 O(N)이다.
AVL Tree는 BST에서 이러한 상황이 안나오게 삽입, 삭제 시 트리의 균형을 맞춰주는 알고리즘을 추가했다.
이 때문에 검색/삽입/삭제 시간 복잡도는 최악의 상황에도 O(logN)이 되었다.
트리의 성능은 트리의 높이가 낮을수록 높다.
이를 위해서는 하나의 레벨에 더 많은 key를 저장하고, 더 많은 자식노드를 가지면 된다.
이것이 B Tree이다.
하나의 노드는 하나 이상의 key 값을 저장하고, 2개 이상의 자식노드를 가질 수 있다.
루트노드에서부터 모든 리프노드까지의 높이가 같은 균형트리이다.
포인터로 자식노드에 접근하는 횟수가 적어 검색 속도가 좋기 때문에 데이터베이스의 인덱스를 구현하는데 많이 사용된다.
참고
'자료구조 & 알고리즘 > 자료구조' 카테고리의 다른 글
| AVL 트리 vs Red-Black 트리 (0) | 2022.03.19 |
|---|
댓글