이진탐색트리 노드 삭제 개념, 구현

 

 

 

●노드 삭제 경우 3가지

- 자식 노드가 없는 경우

- 자식 노드가 한 개인 경우

- 자식 노드가 두 개인 경우

 

 

 

- 자식 노드가 없는 경우

위의 트리에서 3번 노드를 없애려고 한다.

3번노드 삭제 -> 3번노드의 부모인 2번노드에 NULL을 넘겨준다.

 

 

 

- 자식 노드가 한 개인 경우

2번노드를 없애려고 한다.

2번노드를 바로 없애버리면 1번노드의 정보가 사라진다.

그래서 temp 임시변수를 하나 만들어서 1번노드의 주소를 저장한다.

 

과정: temp에 1번노드 저장 -> 2번노드 삭제 -> 1번노드의 주소값을 4번노드에 넘겨준다.

 

 

 

- 자식 노드가 두 개인 경우

루트인 8번노드를 없애려고 한다.

왼쪽 자식중 최댓값을 구해서 삭제하려는 위치로 덮어쓰기 한다.

위의 트리에서는 왼쪽 최댓값이 7이므로 원래 8자리에 7을 덮어씌워준다.

그리고나서 7이 중복되므로 원래 있던 최댓값인 7을 삭제해준다.

 

즉 쉽게 생각하면 왼쪽에 있던 최댓값을 부모노드의 자리에 옮겨준다고 생각하면 된다.

 

 

---

 

 

이제 이것을 코드로 구현해보자.

 

 

먼저 해야할 것은

내가 삭제하려는 노드가 어디있는지 검색부터 해야한다.

 

- 자식 노드가 없는 경우

3번노드를 삭제하려고 한다.

그러면 먼저 루트부터 3번까지 이동을 한다.

 

 

 

완성된 코드

typedef struct TREE {
  int value;
  struct TREE* left;
  struct TREE* right;
} TREE;

TREE* remove(TREE* t, int delData) {
  TREE* temp;
  if(t) {
    if(delData == t->value) {
      
      //삭제
      //1.자식 노드가 없는 경우 = 왼쪽 오른쪽 둘다 주소값이 NULL
      if(t->left = NULL && t->right = NULL) {
        free(t);
        return NULL;
      }
      else {
        if(t->left = NULL) {
          temp = t->right;
          free(t);
          return temp;
        }
        if(t->right = NULL) {
          temp = t->left;
          free(t);
          return temp;
        }
        temp = findMax(t->left);
        t->value = temp->value;
        t->left = remonve(t->left, temp->value);
      }
    }
    
    //왼쪽 이동
    else if(delData < t->value)
      t->left = remonve(t->left, delData);
    
    //오른쪽 이동
    else
      t->right = remove(t->right, delData);
  }
  return t;
}

 

 

 

t가 존재하고

삭제하려는 데이터와 t가 가리키는 값이 같으면 삭제한다.

if(t) {
  if(delData == t->value) {
    //삭제
  }

 

 

 

같지 않으면 노드삽입했을 때와 같은 과정을 거친다.

t보다 데이터가 작으면 왼쪽으로, 데이터가 크면 오른쪽으로 이동한다.

위 예시 그림에서는 3번을 삭제하려고 했는데 t->value는 8이기 때문에 왼쪽으로 이동한다.

//왼쪽 이동
else if(delData < t->value)
  t->left = remonve(t->left, delData);
    
//오른쪽 이동
else
  t->right = remove(t->right, delData);

 

 

재귀호출을 반복하다보면 삭제할 데이터를 찾게된다. delData == t->value

그러면 이제 삭제를 하면 되는데 고려해야할 점이 3가지 있다.

 

- 자식 노드가 없는 경우

- 자식 노드가 한 개인 경우

- 자식 노드가 두 개인 경우

 

 

 

- 자식 노드가 없는 경우

자식 노드가 없을 때는 왼쪽, 오른쪽 주소값이 모두 NULL인 경우이다.

그냥 삭제 -> 호출한 곳에 NULL을 넘김

//1.자식 노드가 없는 경우 = 왼쪽 오른쪽 둘다 주소값이 NULL
if(t->left = NULL && t->right = NULL) {
  free(t);
  return NULL;
}

 

 

 

- 자식 노드가 한 개인 경우

자식 노드가 한 개인 경우는 그 노드를 바로 지울 수 없다.

그림을 보면 2번을 지우려면 1번 노드를 잠시 저장해야 한다.

 

과정: 1번노드 저장 -> 그 다음 2번 노드 삭제 -> 1번 노드 주소값을 리턴 -> 1번, 4번 연결됨

 

자식이 1개가 되기 위해서는

왼쪽 자식이 있다면 오른쪽 자식이 NULL이 되어야 하고

오른쪽 자식이 있다면 왼쪽 자식이 NULL이 되어야 한다.

//왼쪽이 NULL = 오른쪽 자식만 존재
if(t->left = NULL) {
  temp = t->right;
  free(t);
  return temp;
}

//오른쪽이 NULL = 왼쪽 자식만 존재
if(t->right = NULL) {
  temp = t->left;
  free(t);
  return temp;
}

 

 

 

- 자식 노드가 두 개인 경우

temp = findMax(t->left);
t->value = temp->value;
t->left = remonve(t->left, temp->value);

t->left인 왼쪽 자식중에 최대값을 구하고

그 값을 삭제할 위치에 넣어준다. 그러면 최댓값이 부모노드 위치로 덮어씌워진다.

그 다음 노드가 곂치면 안되니 원래 있던 그 최댓값을 삭제하면 완료된다.

삭제하는 과정은 재귀호출로 가장 위에 있는 t->left부터 찾아서 삭제해준다.