AVL 트리 & Red-Black 트리 비교

RB 트리는 노드에 색깔을 부여하며 일정한 규칙 안에서 재구조화를 한다. 반대로 AVL 트리는 각 노드의 좌우 자식의 높이 차이를 비교하여 1이 초과할 때 재구조화를 한다. ★이때 알아야 할 것은 AVL 트리가 더 엄격하게 트리의 균형을 유지한다는 것이다.

 

따라서 삽입, 삭제 연산에서 RB 트리보다 AVL 트리가 더 많은 회전 작업을 수행하게 될 가능성이 있다. 하지만 이는 AVL 트리가 더 낮은 높이를 가질 수 있다는 뜻이기에 서로 장단점이 있다.

 

AVL 트리 - 성질/삽입방법/활용

 

RB(Red-Black) 트리 - 성질/삽입방법/활용

 

 

 

연산 비교

• 삽입 :
  • (데이터 적은 경우)  RB 트리의 평균 회전수가 AVL 트리에 비해 적어 RB 트리가 유리하다. 
  • (데이터 많은 경우) 삽입하기 전 어디에 데이터를 삽입할지 탐색이 필요하므로 높이가 낮은 AVL 트리가 유리하다. 
• 탐색 : AVL 트리의 높이가 더 낮아 AVL 트리가 유리하다.
• 삭제 : 최악의 경우 AVL 트리의 회전수가 더 많아 RB 트리가 유리하다.

 

 

저장공간 비교

 

Red-Black 트리 : 각 노드 당 색깔을 표현하는 데 단 1bit의 저장공간만 필요하다. (장점)

AVL 트리 : 각 노드 당 Balance Factor(BF)나 Height를 노드에 저장해야한다. (단점)

 

 

 

 

 

 

★

삽입, 삭제 작업 시 균형을 맞추기 위한 작업 횟수가 적은 트리는 Red-Black 트리이다.

AVL트리는 트리의 모든 내부 노드(internal node) v에 대해 v의 자식 노드들의 높이 차이가 최대 1이라는 조건을 삽입, 삭제를 할 때에도 맞춰줘야 해서 RB트리보다 더 많은 작업이 필요하기 때문에 효율이 떨어지는 편이다. 그렇지만, 엄격하게 균형을 맞춰주는 작업이 있기에 조회 시에는 높이가 낮춰져있기 때문에 유리하다. 

 

또한, 저장공간에 있어서는 RB트리가 AVL트리보다 유리하다.