AVL 트리 회전 및 빨강 - 검정 트리 색상 뒤집기

Question

모두 알다시피, 삽입 및 삭제에는 모두 O (log n)가 필요합니다. AVL 트리는 O (로그 n)을 삽입해야하고 O (로그 n)을 사용하여 균형을 유지해야하므로 O (로그 n)이 필요합니다.

RB 트리는 삽입하기 위해 O (log n)가 필요하기 때문에 O (log n)가 필요합니다. RB-INSERT-FIXUP은 케이스 1 (색상 뒤집기)에 O (log n) 회전시 최대 2 배. AVL은 2O (log n)을 필요로하지만 RB 트리는 2O (log n) + C를 필요로합니다.

왜 우리는 RB 트리가 삽입시 AVL보다 더 빠르다고 생각합니까? 회전이 컬러 뒤집기보다 더 많은 시간을 필요로하기 때문에? 회전 및 색상 뒤집기 둘 다 O (1)가 필요합니다. 왜 회전이 색상 뒤집기보다 시간이 오래 걸리나요? 고마워요 :)

Answer 1

질문을 올바르게 이해했다면 예, RB-Trees 및 AVL-trees 둘 다 O(logn) 시간에 조회, 삽입, 삭제를 제공한다는 것은 사실입니다.

AVL- 나무는 RB- 나무보다 더 엄격하게 균형을 이룹니다. 이를 달성하기 위해서는 많은 시간이 소요되는 많은 회전이 필요합니다. RB-Tree는 밸런싱에 대한 규칙이 약하기 때문에 약간 불균형합니다. 따라서 삽입 및 삭제 작업이 덜 필요합니다. 결과적으로 AVL-Trees에서의 검색은 RB-Tree보다 빠르지 만 삽입 및 삭제는 RB-Tree에서 더 빠릅니다.

편집

this blog post을 읽어 보시기 바랍니다. 핵심은 삽입 후 AVL 트리보다 RB 트리가 더 빨리 균형을 유지한다는 것입니다. 예, 회전에는 AVL 트리에서 O(1) 시간이 걸립니다. 최대 두 번 회전해야하지만 회전 지점을 여전히 찾아야하며 회전 시간은 O(logn)이됩니다. RB 트리에서 삽입 후 재조정은 상각 된 일정 시간으로 실행됩니다. 따라서 O(1)은 색상 변환을위한 시간을 상각합니다 (O(logn)이 아님).