９．４ 二分探索木（写経編）

これはアカンかったです。次節点の探索のところ、ややこしすぎませんか？

あっそういえばポインタの参照を久しぶりに使いました。（rootの入れ替えのところ）

#include <iostream>
#include <cstdio>
#include <memory>

using namespace std;

struct Node {
  int key;
  Node* parent;
  Node* left;
  Node* right;
  
  Node(int key = -1) : key(key), parent(nullptr), left(nullptr), right(nullptr) {};
};

struct Tree {
  Node* root;  
  
  Tree() : root(nullptr) {};
};

static void insert(Tree& tree, int v) {
  Node* z = new Node(v);
  Node* x(tree.root);
  Node* y(nullptr);
  while (x != nullptr) {
    y = x;
    if (z->key < x->key) {
      x = x->left;
    } else {
      x = x->right;
    }
  }
  
  z->parent = y;
  if (y == nullptr) {
    tree.root = z;
  } else if (z->key < y->key) {
    y->left = z;
  } else {
    y->right = z;
  }
}

static Node* find(Node* node, int v) {
  while (node != nullptr && node->key != v) {
    if (node->key > v) {
      node = node->left;
    } else {
      node = node->right;
    }
  }
  return node;
}

static Node* getSuccessor(Node* x) {
  if (x->right) {
    x = x->right;
    while (x->left) {
      x = x->left;
    }
    return x;
  }
  
  Node* y = x->parent;
  while (y && x == y->right) {
    x = y;
    y = y->parent;
  }
  return y;
}

static void deleteNode(Node*& root, int v) {
  Node* z = find(root, v);
  Node* y;
  if (!z->left || !z->right) {
    y = z;
  } else {
    y = getSuccessor(z);  
  }

  Node* x;
  if (y->left) {
    x = y->left;
  } else {
    x = y->right;
  }
  
  if (x) {
    x->parent = y->parent;
  }
  
  if (!y->parent) {
    root = x;    
  } else if (y == y->parent->left) {
    y->parent->left = x;
  } else {
    y->parent->right = x;
  }
  
  if (y != z) {
    z->key = y->key;  
  }
  delete y;
}

void preorderWalk(const Node* node) {
  if (!node) {
    return;
  }
  cout << " " << node->key;
  if (node->left != nullptr) {
    preorderWalk(node->left);
  }
  if (node->right != nullptr) {
    preorderWalk(node->right); 
  }
}

void inorderWalk(const Node* node) {
  if (!node) {
    return;
  }
  if (node->left != nullptr) {
    inorderWalk(node->left);
  }
  cout << " " << node->key;

  if (node->right != nullptr) {
    inorderWalk(node->right); 
  }
}

static Tree TREE;

int main() {
  int n;
  cin >> n;

  string command;
  int v;
  for (int i = 0; i < n; i++) {
    cin >> command;
    if (command[0] == 'i') {
      scanf("%d", &v);
      insert(TREE, v);
    } else if (command[0] == 'f') {
      scanf("%d", &v);
      Node* found = find(TREE.root, v);
      cout << (found ? "yes" : "no") << endl;
    } else if (command[0] == 'd') {
      scanf("%d", &v);
      deleteNode(TREE.root, v);
    } else {
      inorderWalk(TREE.root);
      cout << endl;
      preorderWalk(TREE.root);
      cout << endl;
    }
  }

  return 0;
}