AVL 트리 vs Red-Black 트리 BST(Binary Search Tree, 이진탐색트리)는 key 삽입 순서에 따라서 트리의 모양 및 균형이 많이 달라진다. BST에서 검색 시간복잡도는 보통 O(logN), 즉 트리의 높이 값이다. 하지만 트리의 모양이 한 쪽으로 치우친 최악의 상황이라면 BST의 이점을 하나도 살리지 못하고 시간 복잡도가 O(N)이 된다. AVL 트리, Red-Black 트리 모두 BST(Binary Search Tree, 이진탐색트리)의 단점을 보완하기 위한 자료구조이다. AVL 트리는 트리 높이를 이용한 BF(Balance Factor, 균형도)를 노드마다 계산하여 삽입/삭제 시에 균형을 맞춘다. Red-Black 트리는 각 노드에 Red 혹은 Black을 배치해 다양한 규칙을 이용해 트리의 균형을 맞춘다. 두 트.. 2022. 3. 19. 트리 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이다. 하나의 노드는 하나 이상의 k.. 2021. 12. 8. 이전 1 다음
