자료구조 homework 6

반복적 노드 추가 

 
1. 삽입할 노드 생성
 
2. 두 개의 포인터 초기화 
curr은 root를 가리키고 prev는 null을 가리킴 
 
3. curr!= NULL동안 다음 수행 
  3.1 이전을 curr로 업데이트하여 탐색을 유지 
  3.2 curr->data > key 인 경우 curr를 curr->left로 설정하고 오른쪽 하위 트리 삭제 
  3.3 curr->data < key 인 경우 curr를 curr->right로 설정하고 왼쪽 사위 트리 삭제 
 
4. prev == NULL이면 트리가 비어있음을 의미. root 노드 만들기 
 
5. 그렇지 않으면 prev->data > key이면 prev의 왼쪽에 toinsert를 삽입 
 prev->left  = toinsert
 
6. 그렇지 않으면 prev->data < key인 경우 prev의 오른쪽에 toinsert를 삽입하고 prev->right = toinsert를 삽입 
 

void insert(Node* &root, int key)
{
    Node* toinsert = NewNode(key);
    Node* curr = root;
    Node* prev = NULL;
    
    while(curr != NULL) {
    	prev = curr;
        if(key <curr->key)
        	curr = curr->left;
        else
        	curr - curr->right;
    }
    if(prev == NULL ) //트리가 비어있으므로 루트 노드 생성 
    {
    	prev = toinsert;
        root = prev;
    }
    else if (key < prev->key)
    	prev->left = toinsert;
    else
    	prev->right = toinsert;
  }

 
 

반복적 노드 삭제 

 
3가지 경우 
1. 삭제노드가 단말 노드인 경우 
 - 삭제할 노드의 부모 노드가 있다면 부모 노드의 자식 노드를 NULL로 만들고 삭제할 노드를 삭제 (메모리 해제)
 
2. 삭제 노드가 하나의 왼쪽이나 오른쪽 서브 트리 중 하나만 가지고 있는 경우 
  - 삭제되는 노드가 왼쪽이나 오른쪽 서브 트리중 하나만 갖고 있을 때, 그 노드는 삭제하고 서브 트리는 부모 노드에 붙여줌
 - 삭제할 노드의 자식 노드를 삭제할 노드의 부모 노드가 가리키게 하고 해당 노드를 삭제 

 
3. 삭제 노드가 두 개의 서브트리를 모두 가지고 있는 경우 
 - 삭제하려는 노드가 두 개의 서브트리를 갖고 있는 경우 
  : 삭제 노드와 가장 비슷한 값을 가진 노드를 삭제 노드 위치로 가져옴 
 
- 삭제할 노드 오른쪽 서브 트리의 가장 작은 자손을 해당 노드의 자리를 올림 
 

 
 

TreeNode* delete_node(TreeNode* root, int key) {
    TreeNode* del = NULL; //삭제할 노드 
    TreeNode* parent = NULL; //삭제할 노드의 부모 노드 
    TreeNode* successor = NULL; //삭제할 노드의 왼쪽 서브트리에서 가장 큰 노드 
    TreeNode* predecessor = NULL; //successor의 부모 노드 
    TreeNode* child = NULL; //삭제할 노드의 자식 노드 
    
    del = root;
    while(del != NULL) { //삭제할 노드 탐색 
    	if(key == del->key) {
        	break;
        }
        parent = del;
        if(key <del->key) {
        	del = del->left;
        } else {
        	del = del -> right;
        }
  }
  
  if(del == NULL) {
  	printf("Error");
    return root;
 }
 
 if(del->left == NULL && del->right == NULL) {
 //삭제할 노드의 자식 노드가 없는 경우 
 if(parent->elft != NULL) {
 	if(parent->left == del) {
   		parent->left = NULL;
    }else {
    	parent->right = NULL; 
    }
 }
 else if(del->left != NULL && del->right != NULL) {
 //왼쪽 서브트리에서 가장 큰 값 찾기 
 predecessor = del;
 successor = del ->left;
 
 while(successor->right != NULL) {
 //왼쪽 서브트리에서 가장 큰 값 
 	predecessor = successor;
    successor = successor->right;
 }
 
 if(predecessor->left == successor) {
 	predecessor->left= succesor->left'
 } else {
 	predecessor->right = successor->left;
 }
 
 del->key = successor->key;
 del = successor;
 
} else {
	//삭제할 노드의 자식 노드가 1개인 경우 
    if(del->left != NULL) {
    	//왼쪽 노드 
        child = del->left;
    }else {
    	//오른쪽 노드 
    	child = del->right;
    }
    
    if(parent != NULL) {
    	if(parent->left == del) {
        //부모노드의 왼쪽 노드로 삭제할 노드의 자식 노드 연결
        	parent->left = child;
        }else {
        	parent->right = child;
        }
    }else {
    	root = child;
    }
}

free(del); //메모리 해제 
return root;

 
방문한 노드의 수 
- 모르겠삼