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을 배치해 다양한 규칙을 이용해 트리의 균형을 맞춘다.

두 트리 모두 검색 시간복잡도는 항상 O(logN)이다.

 

AVL 트리는 R-B 트리보다 균형을 엄격하게 맞추고 있다.

그래서 AVL 트리가 R-B 트리보다 조회 성능이 좋고, R-B 트리는 AVL 트리보다 상대적으로 노드 재배치가 덜 일어나기 때문에 삽입/삭제 성능이 평균적으로 더 좋다.

 

AVL 트리는 노드 당 BF를 저장할 int 저장공간이 필요하고, R-B 트리는 노드 당 1비트(색 반전)의 저장공간만 추가로 필요하다.

 

자바에서 TreeSet과 TreeMap은 내부적으로 R-B 트리를 구현해서 제공하고,

AVL 트리는 빠른 탐색이 필요한 데이터베이스에서 쓰인다.