AVL 트리 삭제 시뮬레이터

삽입은 넣은 자리에서 위로 올라가며 처음 만나는 무너진 조상 한 곳만 고치면 끝나지만, 삭제는 지운 자리의 부분나무 높이가 줄어들 수 있어 그 위 조상 전부를 다시 확인해야 합니다. 그래서 삭제 한 번에 회전이 여러 번(최악의 경우 경로 길이만큼) 일어날 수 있습니다.

그 노드의 오른쪽 부분나무에서 가장 작은 값(중위 후속자)을 찾아 그 값을 지울 자리에 복사하고, 후속자 자신을 오른쪽 부분나무에서 다시 지웁니다. 후속자는 왼쪽으로 끝까지 내려간 자리라 자식이 최대 하나뿐이라 재귀가 거기서 끝납니다.

네. 무너진 노드의 균형인수 부호와 무거운 쪽 자식의 균형인수 부호로 가르는 기준은 똑같습니다(dev/avl-rotation 참고). 다른 것은 이 판정을 경로 위 모든 조상에서 반복해야 한다는 점뿐입니다.

AVL 삭제는 표준 절차라 정답 자체는 모든 교재가 같습니다(외부 정답표가 필요 없는 자료구조 알고리즘). 대신 무작위로 만든 트리에 무작위 순서로 삭제를 반복하며 매 단계 「중위 순회가 오름차순인가」·「모든 노드의 균형인수가 ±1 이내인가」·「남은 키 집합이 정확히 일치하는가」 세 불변식이 항상 성립하는지 대조했습니다.