AVL 트리에서 장애가 발생한 노드를 식별하는 방법은 무엇입니까?

Question

AVL 삽입 기능을 코딩하고 있습니다. 새 노드를 삽입 할 때 균형이 깨지는 노드를 어떻게 식별 할 수 있습니까? 어떤 노드의 균형 요소를 계산하는 방법을 알고 있습니다. 그러나 노드를 리프로 추가하면 균형이 깨지는 조상 노드에 대해 어떻게 알 수 있습니까? 그래서 나는 그것에 회전을 적용 할 수 있습니다. 기대해 줘서 고마워. 당신이 (내 경우에는 왼쪽 하위 트리 (높이 - 우측 서브 트리의 높이)) 균형 요소를 일단

Answer 1

,

• 균형 요인은 1보다 큰 후 현재 노드가 불균형하고 있다면 우리 Left Left case 또는 Left Right case에 있습니다. 왼쪽 대소 문자 여부를 확인하려면 새로 삽입 된 키와 왼쪽 하위 트리 루트의 키를 비교하십시오.
• 균형 계수가 -1보다 작 으면 현재 노드는 언밸런스이며 Right Right case 또는 Right Left case 중 하나입니다. 오른쪽 대문자 여부를 확인하려면 새로 입력 된 키와 오른쪽 하위 트리 루트의 키를 비교하십시오.

이 질문에 대한 답변?

Answer 2

잎을 추가하면 부모에게 하나씩 루트쪽으로 이동하고 높이 (또는 원하는 경우 깊이)를 업데이트합니다. 나무 높이를 업데이트 할 때 균형이 깨져 균형을 조정하는지 확인합니다. 그런 다음 계속해서 다시 위로 움직입니다. 덕분에 많이 알았어요

이는 AVL 트리의 루트에 대한 모든 잎에서 경로 인 이후 O(log(n)) 작업입니다는 O(log(n)) 노드를 포함하고 노드는