AVL 트리 vs Red-Black 트리

BST(Binary Search Tree, 이진탐색트리)는 key 삽입 순서에 따라서 트리의 모양 및 균형이 많이 달라진다.

BST에서 검색 시간복잡도는 보통 O(logN), 즉 트리의 높이 값이다.

하지만 트리의 모양이 한 쪽으로 치우친 최악의 상황이라면 BST의 이점을 하나도 살리지 못하고 시간 복잡도가 O(N)이 된다.

AVL 트리, Red-Black 트리 모두 BST의 단점을 보완하기 위한 자료구조이다.

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

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

자바에서 TreeSet과 TreeMap은 내부적으로 R-B 트리를 구현해서 제공하고, AVL 트리는 빠른 탐색이 필요한 데이터베이스에서 쓰인다.