이 이식 기능이 왜 이진 검색 트리에서 작동합니까?

CLRS의 이진 탐색 트리에있는 장에서 노드 u을 노드 v으로 바꾼 이식 기능이 부모 요소에서 적절하게 변경되었습니다.이 이식 기능이 왜 이진 검색 트리에서 작동합니까?

void transplant(Node* root, Node* u, Node* v) 
{ 
    if(u->parent == NULL) 
     root = v; 
    else if(u == u->parent->left) 
     u->parent->left = v; 
    else 
     u->parent->right = v; 
    if(v != NULL) 
     v->parent = u->parent; 
}

그것은이 어떻게 작동하는지 이해하지 않는 것이 아니지만이 작품 이유 : 는 여기에 내가 이식 기능을 위해 쓴 코드입니다. 함수 호출을 할 때 기본적으로 포인터의 복사본을 함수 오른쪽에 root, u, v 보내는 중입니까? 그래서 함수에서 변경 한 내용은 포인터를 반환하거나 원래의 루트를 실제로 변경하지 않으면 실제로 루트에 반영되어서는 안됩니다. 루트를 전역 변수로 정의했는데, 아무것도 바뀌 었습니까?

출처

2012-09-22 Aryan

어떻게 함수를 호출합니까? 그리고 어떻게'루트'가 만들어 졌는가? –

'u'가'root'이면 작동하지 않아야합니다. 실제로는'root'의 로컬 복사본 만 변경합니다. 다른 경우에는 포인터가 실제'Node's를 가리키고이를 변경합니다. –

'transplant (root, z, z-> right)'함수를 호출했습니다.'root'는 전역 적으로'Node * root = NULL'로 정의 된 구조체에 대한 포인터입니다. – Aryan

u->parent가 NULL 경우, 함수는이 경우에 작동하지 않습니다는, 로컬 변수 만 root는 v에 함수 변화 외부에서 액세스 아무것도 설정되지 않습니다.

는 u->parent != NULL, u->parent->left 및 u->parent->right 경우 Node의 회원 u->parent가 가리키는이며, 사람들은 덮어 쓰기 때문에 변화는 main에서 볼 수 있습니다.

출처

2012-09-22 14:14:39

이 이식 기능이 왜 이진 검색 트리에서 작동합니까?

답변

관련 문제