노드 삭제 전후에 AVL 트리의 균형을 유지합니까?

Question

이 연습에서는 학생에게 AVL 트리에서 노드를 삭제하도록 요청합니다. 이 경우 가장 깊은 깊이와 가장 얕은 깊이의 차이가 1보다 커지므로 균형을 잡아야합니다. 그러나 삭제 전후에 균형이 이루어져야합니까? 또는 그것은 중요하지 않습니까?

image of AVL tree in question

Answer 1

은 기본적으로 당신은 당신이 BST에서 사용할 때 같이 삭제합니다. 그런 다음 깊이 요소 (트리의 각 경로 길이)를 계산하고 어느 경로가 불균형한지에 따라 보통 삽입과 마찬가지로 회전을 수행합니다. 그래서 귀하의 질문에 대답하기 위해 당신은 당신이 삭제 한 후에 회전을합니다.