이진 검색 트리에서 삭제

Question

선생님은 이진 검색 트리에서 노드를 삭제하기위한이 알고리즘을 설명했지만 삭제할 노드가 한 자식 만 있으면 작동하는 방법을 이해할 수 없습니다 (이미 이론적으로 작동하는 방법을 이미 알고 있음).

알고리즘 :

abc_delete(T, z) // z is the node that must be eliminated 
{
        if((z.left == NULL) && (z.right == NULL))
                y = z;
        else
                y = abr_successor(z);

        if(y.left != NULL)
                    x = y.left;
        else
                    x = y.right;

        if(x != NULL)
                x.p = y.p;

        if(y.p == NULL)
                T.root = x;
        else
        {
                if(y == (y.p).left)
                        (y.p).left = x;
                else
                        (y.p).right = x;
        }

        if(y != z)
                z.key = y.key;
        return y;
}

abr_successor(x)
{
        if(x == NULL)
                return NULL;
        if(x.right != NULL)
                return abr_min(x.right)
        y = x.p;
        while(y != NULL && x == y.right)
        {
                x = y;
                y = y.p;
        }
        return y;
}

.

예를 들어 노드 번호 $ 7 $ 을 삭제하고 싶습니다.

그러나 최종 결과가 이렇게해서는 안됩니다.

Answer 1

선택한 것은 확실히 정확합니다.

그러나 선생님의 코드에는 아무런 문제가 없습니다. 여기 CLRS에서 발췌 한 것입니다.

삽입 및 삭제의 작동 원인 이진 검색 트리가 변경하여 바이너리 검색 트리가 표시하는 동적 세트를 발생시킵니다. 이 변경 사항을 반영하도록 데이터 구조를 수정해야하지만 이진 검색 트리 속성이 계속 유지되는 방식으로 데이터 구조를 수정해야합니다.

우리는 가장 쉬운 방법이나 가장 빠른 방법으로 작업을 선호합니다. 그러나 가장 쉬운 방법으로 또는 쉽게 방법으로 수정을 수행 해야하는 요구 사항은 없습니다. 또한 가장 빠른 방법으로 또는 심지어 빠른 방법으로 수정이 필요하지 않습니다. 모든 것이 삭제 작업이 특정 노드가없는 주어진 이진 검색 트리에서 모든 노드가있는 다른 바이너리 검색 트리를 생성해야합니다 (더 이상 노드가 없음). 나머지 노드가 바이너리 검색 트리를 형성하는 방법은 완전히 구속이 완전히 없습니다.

교사의 코드는 아마도 일을하는 가장 짧은 클리어 코드 일 것입니다. 더 많이 공부할수록 더 많은 독창성이 있습니다.

Answer 2

도면이 올바른 솔루션이지만 UR 교사 코드에 대한 구문 분석은 정확하지 않습니다 (u는 코드를 interePreted 코드를 interepreted)

ur qi가 코드를 철저히 읽지 못했을 때 (첫 번째 그림 / 도면에서) ur 선생님이 상대 주문보다 추가 조건을 가진 특별한 종류의 BST에 대한 삭제 작업을 수행하고 있지만 이것은

의 경우가 아닙니다

BST에서 삭제할 때 (UR 코드 변수를 따르려고, z는 삭제할 노드입니다)

z가 리프 노드 (자식 없음) 인 경우, 부모 포인터를 NULL로 바꾸면

z가 1 자녀가있는 경우 (왼쪽 또는 오른쪽이 중요하지 않은 경우) 상위 포인터가 유일한 자식

를 가리 킵니다.

매우 간단한 코딩, 반 의사 코드

if (z.left== null) {physical_delete (z, zright); 반환(); // 우리는 오른쪽 하위 트리 만 있거나 없음 }

// 여기서 우리는 왼쪽 하위 트리가 있는지 확실합니다

if (Z. 오른쪽== null) {physical_delete (z, z.left); 반환(); }

// physical_delete는 두 번째 매개 변수로서 대체품을 보유하고 있으며, UR 교사 코드의 모든 루프는 incase 우리가 두 개의 하위 트리를 가지고있는 것을 알아 보는 것입니다

z가 2 명의 자녀가있는 경우, 그 중 하나를 선택하여 그 자리를 차지해야하며, 여기에서는 선생님의 코드 (이전 사례가 아님)

UR PIC u r r r r 삭제 "5"이 긴 코드는 2 자녀의 나머지 하위 트리를 조정하기위한 것입니다 (BST 제한을 유지하는 방법으로 7 & 3 및 노드 12를 링크하는 방법)

우리는 상세한 추적이 필요하면 우리는 그 일을 할 수 있습니다. 그러나 이것이 시작하여 도움이되는 경우에만