2
AVL 트리에서는 삽입 지점과 삭제 지점에서 루트까지의 경로 만 확인하면되므로 삽입 및 삭제시 다시 균형을 조정할 때마다 일정한 수의 단일 및 이중 회전이 필요합니다.불균형/부분 균형 BST 밸런싱의 복잡성?
불균형 트리가있는 경우 가능한 모든 노드의 균형이 맞춰 졌는지 확인해야하므로 불균형 트리를 다시 조정하려면 O(n)이 필요합니다. 이 올바른지?
A
답변
2
언밸런스 트리를 리 밸런싱하는 데 O (n) 시간이 걸리지 만 언급 한 이유는 아닙니다. AVL 트리에서 요소가 삽입되기 전에 트리가 최대로 불균형 한 경우 삽입 및 삭제에 Θ (log n) 회전이 필요할 수 있습니다. 이는 n 노드 각각에 O (log n) 작업을 수행 할 수 있으므로 트리 재 균형을 맞추기 위해 잠재적으로 O (n log n) 시간이 필요할 수 있습니다.
그러나 다른 알고리즘을 사용하면 O (n) 시간에 트리를 재조정 할 수 있습니다. 하나의 간단한 옵션은 트리의 inorder traversal을 수행하여 정렬 된 순서로 요소를 가져온 다음 트리를 상향식으로 재귀 적으로 빌드하여 해당 요소에서 최적의 BST를 재구성하는 것입니다. 또는 Day-Stout-Warren algorithm을 사용하면 O (n) 시간 및 O (1) 공간에있는 모든 트리의 균형을 유지할 수 있습니다.
희망이 도움이됩니다.
리 밸런스를 놓친 AVL 트리가 있고 다른 서브 트리에 여러 개의 불균형 노드가있는 경우 O (n) 시간에 전체 트리의 균형을 다시 조정해야합니까? 내가 할 수있는 일이 또 있니? – ask
하나의 재조정 또는 잠재적으로 많은 재조정을 놓쳤습니까? – templatetypedef
한 번의 균형 조정. 예 : 불균형의 원인이되는 삽입물 2. 재조정을 잊어라. 그런 다음 다른 불균형을 일으키는 3을 삽입하십시오. 이제 나는 그것을 고치고 그것을 균형있게 만들고 싶다. – ask