AVL 트리에서 요소를 삭제하는 것은 트리 균형을 다시 조정해야 한다는 점을 제외하면 BST에서 요소를 삭제하는 것과 동일합니다. BST에서 요소 삭제 섹션에서 설명한 대로 이진 트리에서 요소를 삭제하기 위해 알고리즘은 먼저 요소가 포함된 노드를 찾습니다. 현재는 이진 트리의 요소를 포함하는 노드를 가리키고 부모는 현재 노드의 부모를 가리킵니다. 현재 노드는 부모 노드
의 왼쪽 자식 또는 오른쪽 자식일 수 있습니다. 요소를 삭제할 때 두 가지 경우가 발생합니다.

사례 1: 아래 그림(a)에 표시된 것처럼 현재 노드에는 왼쪽 자식이 없습니다. 현재 노드를 삭제하려면 아래 그림 (b)와 같이 현재 노드의 오른쪽 하위 노드와 상위 노드를 연결하기만 하면 됩니다. 부모 노드에서 루트까지의 경로를 따라 노드의 높이가 감소했을 수 있습니다. 트리의 균형이 맞는지 확인하려면

balancePath(parent.element);

사례 2: 현재 노드에는 왼쪽 자식이 있습니다. rightMost는 현재 노드의 왼쪽 하위 트리에서 가장 큰 요소를 포함하는 노드를 가리키고 parentOfRightMost는 rightMost의 상위 노드를 가리킵니다. 노드는 아래 그림 (a)와 같습니다. rightMost 노드는 오른쪽 자식을 가질 수 없지만 왼쪽 자식은 가질 수 있습니다. 현재 노드의 요소 값을 rightMost 노드의 요소 값으로 바꾸고, parentOfRightMost 노드를 rightMost 노드를 삭제하고, 아래 그림 (b)와 같이 rightMost 노드를 삭제합니다.

parentOfRightMost에서 루트까지의 경로를 따라 노드의 높이가 감소했을 수 있습니다. 트리의 균형이 맞는지 확인하려면

balancePath(parentOfRightMost);