2 명의 어린이가있는 BST 트리에서 노드를 삭제하는 방법?

Question

나는이 질문을 게시하기 전에 여러 개의 자습서를 읽고 여러 BST 노드 삭제 알고리즘 설명을 보았습니다. 어떤 이유로, BST 노드 삭제 알고리즘에 대한 완전한 설명을 찾을 수 없습니다.

바이너리 검색 트리에서 2 명의 아이들과 노드를 제거하는 4 개의 알고리즘을 발견했습니다 :
1) 오른쪽 하위 트리에서 가장 작은 노드를 찾아 삭제하려는 노드로 바꿉니다.

2) 왼쪽 하위 트리에서 가장 큰 노드를 찾아 삭제하려는 노드로 교체하십시오.
3) 오른쪽 하위 트리에서 가장 왼쪽 가장 왼쪽 노드를 찾아 삭제하려는 노드로 바꿉니다.
4) 왼쪽 하위 트리에서 가장 깊은 가장 오른쪽 노드를 찾아 삭제하려는 노드로 바꿉니다.

분명히, 그 중 어느 것도 다음 유스 케이스를 위해 작동하지 않습니다 (나는 누락되었거나 무엇인가를 이해하지 못하기 때문에 가장 가능성이 있음). 사용 사례는 다음 트리에서 요소 5를 제거하는 것입니다.

첫 번째 알고리즘의 경우 요소 6을 선택하고 올바른 서브 트리를 잃을 것입니다. 두 번째 알고리즘의 경우 요소 4를 선택하고 왼쪽 하위 트리를 잃을 것입니다. 제 3 회 알고리즘을 위해 우리는 요소 7을 선택했으며 BST 규칙을 위반할 것입니다. 4 번째 알고리즘을 위해 우리는 BST 규칙을 위반하는 요소 3을 선택했습니다.

그러한 유스 케이스의 올바른 알고리즘은 무엇입니까?

Answer 1

옳습니다. 일반적으로 노드가 한 자식이있는 경우 노드가 두 자식이 줄어든 경우

두 자녀가있는 노드를 고려하십시오. 이 노드를 BST (즉, 왼쪽 하위 트리의 가장 오른쪽 노드)의 전임자와 스왑하거나, 투여 적으로 대칭 - 후속 (오른쪽 하위 트리의 가장 왼쪽 노드) 스왑을 스왑하십시오.

이제 제거 할 노드는 대부분의 한 자식에 있습니다 (우리가 올바른 자식을 가질 수없는 전임자를 위해 갔을 경우에 대비해서). 어린이가없는 경우 노드를 삭제하고 완료됩니다.

노드에 하나의 자식이있는 경우 노드를 제거하고 해당 하위 트리로 바꿉니다. 우리는 다시 BST를 얻습니다.

우리는 5를 제거하고 전임자와 함께 그것을 바꾸고 싶습니다. 이제 4는 루트에 있습니다. 5는 어린이를 떠났습니다 3. 마지막으로 우리는 자녀 3을 그 자리에 옮기고 자식 3을 그 자리에 두는 것입니다. 지금 3은 2의 올바른 아이입니다.

ps. 이 메서드는 한 노드에서 다른 노드로 복사 되므로이 방법은 "복사하여 복사하여 삭제"라고합니다. 일부는 두 가지 이유로이 과정을 승인하지 않습니다. 첫 번째 복사는 값 비싼 작업 일 수 있으며 두 번째 참조가 손실됩니다 (다른 데이터 구조가 특정 값을 가진 노드를 가리키는 경우). 대신 포인터 만 변경합니다.