전공/자료구조
AVL 트리 vs Red Black 트리
NI__JY
2021. 6. 5. 20:00
SMALL
- AVL트리는 더욱 엄격한 균형을 이루고 있기 때문에 Red-Black 트리보다 더 빠른 조회를 제공
- Red-Black 트리는 상대적으로 느슨한 균형으로 인해 회전이 거의 이루어지지 않기 때문에 AVL트리보다 빠르게 삽입 및 제거 작업을 수행
- AVL트리는 각 노드에 대해 BF를 저장하므로 노드 당 int 저장이 필요
Red-Black 트리는 노드당 1비트의 정보만 필요합니다. (플래그 반전만 시키면 됨) - Red-Black 트리는 맵, C++의 멀티캐스트, Java treeMap 등 대부분의 언어 라이브러리에서 사용, AVL트리는 더 빠른 검색이 필요한 데이터베이스에서 사용
LIST