이진 검색 트리에서 삭제가 대칭입니까?

Question

노드 x를 삭제 한 다음 노드 y를 삭제하거나 y와 x를 삭제하면 삭제 한 후에 동일한 이진 검색 트리를 유지하게됩니까?

나는 몇 가지 예를 시도했는데, 사실이라고 생각합니다.

하지만 어떻게 증명할 수 있습니까?

Answer 1

거짓입니다. 나무를 고려하십시오.

4 
/\ 
1 5 
\ 
    2 
    \ 
    3 , 

일부 순서로 4와 5가 삭제됩니다. 순서는 다음 4 5의 경우 주문 후 4 ~ 5 인 경우, 결과는

1 
\ 
    2 
    \ 
    3 . 

이다, 결과가 될 수있다 우리는 두 아이를 가진 노드를 제거 할 때, 그 가정

3 
/
1 
\ 
    2 , 

, 우리는 그 값을 그 이전의 선행자의 값으로 대체하고 선행자를 삭제합니다. (제로 노드와 하나의 자식 노드에 대한 표준 삭제 절차를 가정합니다.)

이 예제를 직접 찾았지만 컴퓨터 지원을 자주 참조합니다.