제5장 트리 - Binary search tree에서 하나의 노드를 삭제하는 함수.

소개글

5. 이진 탐색트리에서 하나의 키를 삭제하는 반복 C 함수를 작성하라. 작성된 함수의 공간 복잡도는 O(1) 이어야 한다. 이를 증명하라 또 작성된 함수의 시간 복잡도는 얼마인가?
Time Complexity :
삭제할 노드를 찾는 시간 :
search 함수 : 해당 트리의 높이가 h 일 경우 O(h)

1) line by line으로 주석이 상세하게 달려있습니다.

부분적인 소스입니다.

목차

vc++ 6.0

본문내용

/************************************************************************
* 1. 삭제할 노드를 찾는다.
*
* 2. 1) 삭제할 노드의 자식이 둘 다 있을 경우
* 후속자(Successor)자가 실질적으로 삭제되는 노드가 된다.
* 2) 삭제할 노드의 자식이 최대 하나 일 경우
* 실질적으로 삭제 되는 노드는 자기 자신이 된다.
*
* 3. 실질적으로 삭제될 노드가 자식이 있을 경우
* 그것의 자식의 위치를 임시로 저장. (2개일리는 없다.)
*
* 4. 실질적으로 삭제될 노드
* 1) 그것의 부모노드가 존재 할 시
* 그것을 3번에서 저장했던 자식노드와 위치를 바꾼다.
* 2) 부모노드가 없으면 3번에서 저장했던 자식노드를 루트로 한다.
*
* 4. 삭제할 노드의 값과 실질적으로 삭제될 노드의 값을 바꾼다.
*
* 5. 실질적으로 삭제 되는 노드 삭제
*************************************************************************/

typedef struct NODE* PNODE;
typedef struct _NODE{
int key; // key

참고 자료

없음