앞에서 AVL Tree와 RedBlackTree에 대해 알아보았는데요. 이번에는 두 트리를 비교해보겠습니다.
AVL Tree
AVL트리는 발명자의 이름인 Geory Adelson-Velsky and Evgeii LanDis을 따서 지어졌습니다. 스스로 균형을 맞추는 이진 탐색 트리여서 self-balancing binary search tree 라고 부르기도 합니다. 이진 트리에서, 데
sol248.tistory.com
RedBlackTree (레드-블랙 트리)
레드블랙 트리는 스스로 균형을 잡는 이진트리 라는 점에서 앞에서 살펴본 AVL과 비슷합니다.https://sol248.tistory.com/61 AVL TreeAVL트리는 발명자의 이름인 Geory Adelson-Velsky and Evgeii LanDis을 따서 지어
sol248.tistory.com
두 트리 모두 스스로 균형을 잡는 이진 탐색 트리라고 할 수 있습니다.
다른 점이라면 레드블랙트리는 노드에 색을 사용함으로써 균형을 잡는 조건이 약해졌다는 것이겠죠.
조건이 약해졌다는 것은 트리가 AVL트리보다 덜 변형된다는 것을 의미합니다.
여기서 변형이란 Rotate 즉, 회전을 의미합니다.
데이터를 삽입하거나 삭제할 떄 회전이 덜 발생하므로 삽입이나 삭제가 많은 경우 유용하겠죠.
하지만, 만약 검정 노드, 빨간 노드가 부모 자식간에 번갈아가면서 추가된다면,
트리의 높이가 거의 2배 가까이 높아질 수 있습니다.
빨간 균형잡는데 영향을 안준다고 해도 결국 이진 트리로 구현했으니까요.
그래도 시간 복잡도는 O(log N) 으로 표현할 수 있습니다.
시간 복잡도에서 상수는 무시할 수 있기 때문이죠.
정리하자면,
삽입/삭제가 많은 경우 레드 블랙트리가 더 효율적이고,
탐색이 많은 경우 높이가 더 낮은 AVL트리가 더 효율적이라고 할 수 있습니다.
'DataStructure' 카테고리의 다른 글
| std::map , std::unordered_map (0) | 2024.09.26 |
|---|---|
| RedBlackTree (레드-블랙 트리) (0) | 2024.09.25 |
| 2-3Tree (2-3트리) (0) | 2024.09.25 |
| AVL트리를 이용한 영어사전 만들기 (2) | 2024.09.25 |
| AVL Tree (0) | 2024.09.24 |