검색 트리를 회전해 높이를 바꿉니다. 키의 중위 순서는 왜 유지되며 어떤 포인터를 함께 갱신하나요?

꼬리 질문을 독립 문항으로 확장했습니다. 원래 문항에서 맥락 보기 →

잠깐, 답변을 보기 전에
먼저 내 말로 설명해 볼까요?

답변과 점검 포인트 펼치기답변 접기

구두 답변

정의를 외우기보다, 원리와 조건을 연결해 설명해 보세요.

오른쪽 회전에서 부모의 왼쪽 자식이 새 루트가 되고 그 자식의 오른쪽 부분 트리가 옛 부모의 왼쪽으로 이동합니다. 각 부분 트리의 키 범위가 유지되므로 중위 순서는 바뀌지 않습니다.

x<y 관계를 가진 노드의 회전에서 사이에 있던 부분 트리는 두 키 사이에 남아야 합니다. 부모 링크·루트 포인터·높이·색·부분 크기 메타데이터를 함께 갱신합니다. 회전 중 독자에게 끊긴 링크가 보이지 않게 동기화하고 중위 순서와 균형을 각각 검사합니다.

이해가 드러나는 지점을 확인해 보세요.

오른쪽 회전에서 부모의 왼쪽 자식이 새 루트가 되고 그 자식의 오른쪽 부분 트리가 옛 부모의 왼쪽으로 이동합니다. 각 부분 트리의 키 범위가 유지되므로 중위 순서는 바뀌지 않습니다.
회전 중 독자에게 끊긴 링크가 보이지 않게 동기화하고 중위 순서와 균형을 각각 검사합니다.

놓치기 쉬운 조건과 오해를 짚어 보세요.

다음 핵심 구분을 반대로 설명하거나 성립 조건을 생략한다: 오른쪽 회전에서 부모의 왼쪽 자식이 새 루트가 되고 그 자식의 오른쪽 부분 트리가 옛 부모의 왼쪽으로 이동합니다.

하나 더 질문하며 이해의 범위를 넓혀 보세요.

득점·감점 포인트는 학습용 자기 점검 기준이며, 특정 회사의 실제 채점표가 아닙니다.

답변을 보충하는 개념·예제·슈도코드를 읽어 보세요.