AVL 트리 로테이션. 다른 가능성

Question

AVL 트리에 삽입에 관한 질문이 있습니다. 예를 들어 요소를 삽입 한 후 부모와 자식 모두 AVL 조건을 위반하는 경우가 있습니다. 예를 들어 여기에서 https://www.youtube.com/watch?v=EsgAUiXbOBo, 분. 12시 50 분, 1을 삽입 한 후 4와 3 모두 AVL 상태를 깨고 있습니다. 내 질문은 우리가 어떤 노드에서 회전해야하는지에 있습니다. 이 경우 루트에 가장 가까운 것 (이 경우 루트 자체) 또는 루트에서 가장 먼 것입니다. 그러면 두 개의 다른 트리를 얻을 수 있습니까? 아니면 어느 쪽이라도 맞습니까?

Answer 1

회전은 맨 아래부터 시작됩니다 (삽입 된 노드).

모든 노드의 균형을 P (포함) 한 것으로 간주해 봅시다. 따라서 P의 하위 트리가 완벽하게 균형을 이룹니다. 우리는 P의 부모 (Q)에게갑니다. Q의 서브 트리가 검사되고 (결국) 회전됩니다. 결과 트리 (회전이 수행 된 경우 루트가 변경되었을 수 있음)는 완벽하게 균형을 유지합니다. 다시 시작하십시오.