수다닷컴

질문 제목 : 시간복잡도, 공간복잡도 구하기.질문 요약 :시간복잡도, 공간복잡도 구하기.질문 내용 :
밑의 함수 공간 복잡도가
왜
O(1)인지
시간복잡도는 무엇인거 왠지 좀 설명해주세요 ㅠㅠㅠ// 노드 삭제 함수.
void DeleteNode(PNODE* root , int key)
{
PNODE freeNode = NULL; // 실질적으로 해제( free() )되는 노드
PNODE del = Search(g_root,key); // 삭제할려는 노드.
PNODE parent = NULL ; // 삭제할려는 노드의 부모 노드.
PNODE child = NULL; // 임시 노드. 삭제 혹은 해제 되는 노드의 자식노드 저장.
if (!del) {
printf( 키값을 가진 노드가 없음\n);
return;
}
// 최대 하나의 자식 노드를 가지면. 삭제될 노드는 해당노드.
if ((del-leftChild==NULL) || (del-rightChild==NULL))
freeNode = del;
// 그렇지 않은경우에는 후속자가 free될 노드.
else
freeNode = Successor(del);
// 만약에 후속자,혹은 자식노드의 leftChild가 존재하면.
if ( freeNode-leftChild != NULL )
child = freeNode-leftChild;
//left Child가 존재 하지 않으면(즉 트리하부에 있는 후속자에 해당.)
//right child를 임시포인터에 저장.(null이라면 degree is zero)
else
child = freeNode-rightChild;
// 삭제 해야할 노드의 parent node
parent = SearchParent( g_root , freeNode-key );
// parent node가 널이라면 ,
// 즉 삭제 해야할 key값이 있는 노드는 root
if(parent == NULL)
root = child;
// 그렇지 않다면 internal node
else
{ // 실질적으로 삭제할 노드를 대체.
// 해제되는 노드가 왼쪽에 존재 하였다면.
if (freeNode == parent-leftChild)
// 해제되는 노드의 child node를 왼쪽에 위치 하도록.
parent-leftChild = child;
else
// 해제되는 노드의 child node를 오른쪽 위치 하도록.
parent-rightChild = child;
}
/* data copy */
if (freeNode != del ) // 삭제 할노드가 메모리 해제되는 노드 자신이 아닐시
{ /* data copy */
del-key = freeNode-key;
// other process
}
// 삭제
if ( freeNode )free(freeNode);
}

신청하기