BST 삭제 메커니즘을 배우는 동안 이해하지 못한 점이 있습니다. Delete (Node * p, int key)가 호출 될 때마다 할당 (p-> rchild =, p-> lchild =)이있는 이유를 설명해 주시겠습니까? 사실, 저는 Delete (Node * p, int key) 메서드가 변이없이 계속 반환되므로 트리가 변경되지 않는다고 생각했습니다.
그리고 설명을 찾고있는 동안이 문장을 우연히 발견했습니다.
삭제 후 할당해야합니다. 그렇지 않으면 중복 노드가 생깁니다.
이 진술에 동의하면 설명해 주시겠습니까?
Node* BST::Delete(Node *p, int key) {
Node* q;
if (p == nullptr){
return nullptr;
}
if (p->lchild == nullptr && p->rchild == nullptr){
if (p == root){
root = nullptr;
}
delete p;
return nullptr;
}
if (key < p->data){
p->lchild = Delete(p->lchild, key);
} else if (key > p->data){
p->rchild = Delete(p->rchild, key);
} else {
if (Height(p->lchild) > Height(p->rchild)){
q = InPre(p->lchild);
p->data = q->data;
p->lchild = Delete(p->lchild, q->data);
} else {
q = InSucc(p->rchild);
p->data = q->data;
p->rchild = Delete(p->rchild, q->data);
}
}
return p;
}
를 호출 할 때마다 할당 (
p->rchild =,p->lchild =) 이있는 이유는Delete(Node* p, int key)무엇입니까?
데이터가 발견되면 목표는 노드가 하나 더 적은 트리를 갖는 것입니다. 알고리즘은 값 교환 메커니즘을 사용하여 실제로 제거 될 노드가 항상 리프 노드인지 확인합니다. 리프 노드 삭제는 두 가지 작업으로 구성됩니다.
알고리즘이 해당 리프 노드에 대해 바로 반복되므로이 단계에서 부모 노드에 사용할 수있는 참조가 없기 때문에 null 포인터를 부모에 설정할 수 없습니다. 그 위해 발신자는 발신자가 있기 때문에, 뭔가해야 않는 부모에 대한 참조를 가지고있다.
따라서 재귀 순회가 리프 노드에 도달하면 호출자에게이 노드를 분리해야 함을 전달해야합니다. 이것은 null 포인터를 반환함으로써 이루어지며, 합의는 호출자 (현재 노드 p가 부모)가 반환 된 포인터를 관련 자식 포인터에 할당해야한다는 것입니다. 이렇게하면 삭제 된 노드가 트리의 나머지 부분에서 실제로 분리됩니다.
사실 저는 그
Delete(Node* p, int key)방법이 변이없이 계속 돌아 오므로 나무가 변하지 않는다고 생각했습니다 .
확실히 트리는 노드가 삭제되도록 어떻게 든 변경되어야합니다. 변경은 p->lchild또는 에 대한 할당에서 발생합니다.p->rchild
나는이 문장을 우연히 발견했습니다.
삭제 후 할당해야합니다. 그렇지 않으면 중복 노드가 생깁니다.
사실입니다. 예제 트리를 보겠습니다.
7
/ \
3 8
/ \ \
1 5 9
/ / \
0 4 6
이제 우리가을 호출하면 어떻게되는지 봅시다 Delete(root, 3). p값이 7 인 노드를 가리 킵니다. 재귀 호출을 사용하여 왼쪽으로 이동합니다.
p->lchild = Delete(p->lchild, key);
재귀 적 실행 컨텍스트에서 우리 p는 값이 3 인 노드를 가리키는 새로운 것을 얻습니다. 이것은 우리가 찾고있는 값입니다. 그래서 우리는 외부 else블록으로 들어갑니다. 해당 노드 아래의 하위 트리 높이가 같기 때문에 내부 else블록에 들어갑니다. 거기에서 우리는 다음을 할당합니다.
q = InSucc(p->rchild);
이것은 q값이 4 인 노드를 참조합니다. 이제 중복이 발생합니다. 데이터를 q에서 p. 이는 트리에서 값 3을 삭제하는 것으로 귀결됩니다.
p->data = q->data;
그러나 이제 우리는 트리에서 값 4의 두 배가됩니다.
7
/ \
4* 8
/ \ \
1 5 9
/ / \
0 4* 6
따라서 알고리즘은 (오른쪽) 자식으로 내려 가고 이제 해당 하위 트리에서 값이 4 인 노드를 삭제하려고합니다.
p->rchild = Delete(p->rchild, q->data);
이 새로운 재귀 호출에서 우리 p는 값이 5 인 노드를 참조 하는 새로운 것을 다시 얻습니다 . 왼쪽으로 이동합니다.이 할당은 나중에 중요한 역할을합니다.
p->lchild = Delete(p->lchild, key);
이 마지막 재귀 호출에는 p우리가 찾고 있던 값이 4 인 노드를 참조 하는 새로운 항목 이 있습니다.
이번에는 이 노드가 리프 노드이기 때문에 if가있는 블록으로 끝납니다 delete. 노드가 해제되고 널 포인터가 호출자에게 리턴됩니다. 여기서부터 우리는 트리를 역 추적하기 시작합니다.
따라서 한 수준 위로, 값이 5 인 노드에서 재귀 호출 (널 포인터)에서 반환 값을 가져와 할당합니다.
p->lchild = Delete(p->lchild, key);
이 중요한 할당은 트리에서 중복 노드 (값 4)를 분리합니다. 이 할당이 이루어지지 않았을 경우 해제 된 메모리를 가리키고 있더라도 중복 값이있는 해당 노드에 대한 참조가 여전히 있음을 알 수 있습니다.
이제 나무가 최종 모양이되었습니다.
7
/ \
4 8
/ \ \
1 5 9
/ \
0 6
역 추적은 계속해서 루트로 돌아갑니다. 또한 일부 자식 포인터에 대한 할당이 이루어 지지만 이러한 모든 경우 return p;에서 호출자의 자식 포인터의 원래 값인을 반환 한 것처럼 트리를 변경하지 않습니다 .
주석에서 언급했듯이 코드에는 버그가 있습니다. 리프 노드를 삭제할 때이 노드에 실제로 삭제할 값이 있는지 확인하지 않습니다. 따라서 트리에서 발생하지 않는 값으로이 메서드를 호출하면 다른 값이있는 리프 노드를 삭제하게됩니다. 위의 예제 트리에서 :를 호출 Delete(root, 10)하면 값이 9 인 노드가 삭제됩니다.
이 버그를 수정하려면 다음 if블록을 이동하십시오 .
if (p->lchild == nullptr && p->rchild == nullptr){
... 외부 else블록 내부에 있는 첫 번째 문장입니다.
이 기사는 인터넷에서 수집됩니다. 재 인쇄 할 때 출처를 알려주십시오.
침해가 발생한 경우 연락 주시기 바랍니다[email protected] 삭제
몇 마디 만하겠습니다