- RBTree와 AVL-Tree
AVL-Tree는 노드를 삽입/삭제할 때마다 균형을 유지하기 위해 회전을 다수 수행함
반면 RB-Tree는 적절한 색 변경 및 회전을 통해 균형을 유지하기 때문에 더 효율적임
RB-Tree는 AVL-Tree보다 좀 더 느슨한 균형 조건을 가짐
AVL-Tree는 각 노드의 서브 트리 높이 차가 항상 1이하여야 함 [-1, 0, 1]
RB-Tree는 노드의 색을 이용해 균형 유지
기존 BST에서 탐색할 때 최선의 경우 O(logN), 최악의 경우 O(N)의 시간복잡도를 가지게 되는데, 이 격차를 좁히기 위해 Self-Balancing-Tree인 AVL-Tree와 RB-Tree가 고안됨
둘의 차이는 rebalancing 과정이 다름
- AVL-Tree: 삽입할 때 무조건 parent를 차례로 하나씩 비교해 리밸런싱 하는 과정이 포함되기 때문에 평균/최악의 경우 모두 O(logN)
- RB-Tree: color가 추가되었기 때문에 무조건 트리를 회전하는게 아니라 색깔만 바꾸는 등 좀 더 느슨하게 리밸런싱하기 때문에 트리 회전 횟수가 감소
-> RB-Tree는 삽입 한 번당 관점에서 보면, 색상 포인터만 바꿔 O(1)인 경우도 있음, AVL-Tree와 같이 재귀를 무조건 사용하는게 아니라 CPU의 오버헤드가 적기 때문에 선호됨
두 트리 모두 삽입/삭제/검색 시 O(logN)의 시간이 소요되는 건 똑같지만,
AVL-Tree는 트리의 밸런스가 좀 더 엄격하게 유지되기 때문에 탐색에 유리하고
RB-Tree는 밸런싱을 느슨하게 하기 때문에 AVL-Tree에 비해 탐색엔 불리하지만 삽입/삭제에 유리함
현실에서의 프로그램에서는 데이터의 삽입/삭제가 빈번하게 일어나니까 RB-Tree를 주로 사용하는 느낌
