이진 검색 트리 회전 (AVL 트리에서)으로 밸런싱

Question

궁극적 인 것은 최종 밸런스 이진 검색 트리에 대해 가능한 결과가 하나 뿐인 것입니까? 때로는 내가 회전을 할 때마다 다른 최종 균형 트리를 얻습니다.

Answer 1

아니요. 몇 가지 자체 균형 유형의 나무가 있으며, 가장 널리 사용되는 것은 AVL 및 Red-Black입니다. 이 나무에 같은 데이터를 넣으면 결과 나무는 다르지만 균형을 이룹니다. AVL 트리에 대해 말하기 경우

은, 그냥 간단한 예제를 제공합니다 :

2  |  4  |  3  
1 4 | 2 5 | 2 4 
    3 5 | 1 3  | 1  5 

그들 모두가 균형 AVL 나무, 즉이 작업의 다른 순서에 의해 생성 될 수있다. 그러나 정확히 동일한 데이터로 동일한 작업 순서를 반복하면 결과 트리가 동일해야합니다. AVL 트리 알고리즘에서는 확률적일 수 없기 때문입니다.