Red-Black 트리(이하 RB 트리)와 AVL 트리는 평균적인 실행 속도를 개선하기 위한 이진 탐색 트리(이하 BST)이다. 따라서 특정 노드보다 값이 작은 노드를 좌측, 큰 노드를 우측에 위치시키는 구조를 가지며 중위 순회(Inorder traversal)로 트리의 원소를 정렬할 수 있다.
이 자료구조들의 특징은 노드의 삽입, 삭제 연산시 '회전'이라는 과정을 통해 BST가 일정 수준 이상의 균형을 유지하도록 재구조화를 해준다는 것이다. 이 과정을 통한 비용이 발생하지만, 트리의 높이에 따라 삽입, 삭제, 탐색의 시간 복잡도가 크게 차이날 수 있는 일반 BST의 연산을 평균적으로 로 만들어 준다.
· RB 트리와 AVL 트리 비교
RB 트리는 노드에 색깔을 부여하며 일정한 규칙 안에서 재구조화를 한다. 반대로 AVL 트리는 각 노드의 좌우 자식의 높이 차이를 비교하여 2 이상 차이날 때 재구조화를 한다. 이때 알아야 할 것은 AVL 트리가 더 엄격하게 트리의 균형을 유지한다는 것이다.
따라서 삽입, 삭제 연산에서 RB 트리보다 AVL 트리가 더 많은 회전 작업을 수행하게 될 가능성이 있다. 하지만 이는 AVL 트리가 더 낮은 높이를 가질 수 있다는 뜻이기에 서로 장단점이 있다. 트리가 다루는 데이터 양에 따라 각 연산에서 어떤 트리 구조가 유리한지 알아보자.
- 데이터가 적은 경우
삽입: RB 트리의 평균 회전수가 AVL 트리에 비해 적어RB 트리가 유리하다.탐색: AVL 트리의 높이가 더 낮아AVL 트리가 유리하다.삭제: 최악의 경우 AVL 트리의 회전수가 더 많아RB 트리가 유리하다.
- 데이터가 많은 경우
삽입: 삽입하기 전 어디에 데이터를 삽입할지 탐색이 필요하므로 높이가 낮은AVL 트리가 유리하다.탐색:AVL 트리가 유리하다.삭제: 삭제할 데이터를 찾아야 해 일반적으로AVL 트리가 유리하지만, 최악의 경우 회전수가 많아RB 트리가 유리할 수도 있다.
· 참고
