【AOJ ALDS1_8】C: Binary search trees - Binary Search Tree III

問題

二分探索木削除 | アルゴリズムとデータ構造 | Aizu Online Judge

方針

二分探索木の削除を実装する問題
削除するノードを以下の3つの条件で場合分けし処理を行う.
1. 子ノードを持たない
2. 子ノードを1つだけ持つ
3. 子ノードを2つ持つ
1, 2の場合は対象ノードを取り除くだけで良い.（取り除いてその子ノードを親ノードに繋げば良い）
3の場合は, 右部分木の最小ノードを削除したいノードに置き換える.

コード

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<ctime>
#include<cctype>
#include<climits>
#include<iostream>
#include<string>
#include<vector>
#include<map>
#include<list>
#include<queue>
#include<deque>
#include<algorithm>
#include<numeric>
#include<utility>
#include<complex>
#include<memory>
#include<functional>

#define rep(i, n) REP(i, 0, n)
#define REP(i, a, n) for(int i = a ; i < (int)n ; i++)

using namespace std;

struct Node{
  int data;
  Node *parent, *left, *right;
};

Node *root;

Node* findNode(int x){
  Node *r = root;
  while(r != NULL && r->data != x){
    if(x < r->data){
      r = r->left;
    }else{
      r = r->right;
    }    
  }
  return r;
}

Node* getMinNode(Node *u){
  while(u->left != NULL) u = u->left;
  return u;
}

Node* getSuccessor(Node *u){
  if(u->right != NULL) return getMinNode(u->right);
  Node *p = u->parent;
  while(p != NULL && p->right == u){
    u = p;
    p = p->parent;
  }
  return p;
}

void deleteNode(Node *u){
  Node *target;
  Node *child;

  // 削除対象ノードを決める
  // 子ノードが無い or 1個だけの場合, 削除対象ノードはuそのもの
  // 子が２つある場合, uの次接点となる.
  if(u->left == NULL || u->right == NULL){ // 子ノードがない or 1個
    target = u;
  }else{
    target = getSuccessor(u);
  }
  
  // 削除対象ノードの子ノードを求める
  if(target->left != NULL){
    child = target->left;
  }else{
    child = target->right;
  }

  // 子ノードがある場合, 子ノードの親ノードを削除対象ノードの親ノードにする
  if(child != NULL){
    child->parent = target->parent;
  }

  // 左 or 右のノードに子ノードを格納
  if(target->parent == NULL){
    root = child;    
  }else{
    if(target == target->parent->left){
      target->parent->left = child;
    }else{
      target->parent->right = child;
    }
  }
  
  // 削除対象が異なる場合はdataを入れ替え
  if(target != u) u->data = target->data;
  free(target);  
}

void insertNode(int x){
  Node *root_tmp = root;
  Node *elem;

  elem = (Node *)malloc(sizeof(Node));
  elem->data = x;
  elem->left = NULL;
  elem->right = NULL;
  
  Node *prev = NULL;

  while(root_tmp != NULL){
    prev = root_tmp;
    if(elem->data < root_tmp->data){
      root_tmp = root_tmp->left;
    }else{
      root_tmp = root_tmp->right;
    }
  }

  elem->parent = prev;

  if(elem->parent == NULL){
    root = elem;
  }else{
    if(elem->parent->data < elem->data){
      elem->parent->right = elem;
    }else{
      elem->parent->left = elem;
    }
  }
}

// 先行巡回
void preorder(Node *u){
  if(u == NULL) return; 
  cout << " " << u->data;
  preorder(u->left);
  preorder(u->right);
}

// 中間巡回
void inorder(Node *u){
  if(u == NULL) return; 
  inorder(u->left);
  cout << " " << u->data;
  inorder(u->right);
}

signed main(){
  int n;
  string command;
  int elem;

  cin >> n;
  rep(i, n){
    cin >> command;
    if(command == "insert"){
      cin >> elem;
      insertNode(elem);
    }else if(command == "find"){
      cin >> elem;
      if(findNode(elem)!=NULL) cout << "yes" << endl;
      else cout << "no" << endl;
    }else if(command == "delete"){
      cin >> elem;
      deleteNode(findNode(elem));
    }else{
      inorder(root);
      cout << "\n";
      preorder(root);
      cout << "\n";
    }
  }
}