AOJ

# # 解答


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

Node *root, *NIL;

void insert(int key) {
Node *y = NIL;
Node *x = root;
Node *z = (Node *)malloc(sizeof(Node));

z->key = key;
z->left = NIL;
z->right = NIL;

while (x != NIL) {
y = x;
if (key < x->key) {
x = x->left;
} else {
x = x->right;
}
};

z->parent = y;

if (y == NIL) {
root = z;
return;
}

if (key <= y->key) {
y->left = z;
} else {
y->right = z;
}
};

Node *findNode(Node *node, int key) {
Node* cur = node;
while (cur != NIL && cur->key != key) {
if (key < cur->key) {
cur = cur->left;
} else {
cur = cur->right;
}
}

return cur;
}

bool find(Node *node, int key) {
return findNode(node, key) != NIL;
}

Node *tMin(Node *node) {
while (node->left != NIL) {
node = node->left;
}

return node;
}

Node *tSuccessor(Node *node) {
if (node->right != NIL) {
return tMin(node->right);
}

Node *y = node->parent;
while (y != NIL && node == y->right) {
node = y;
y = y->parent;
}

return y;
}

void tDelete(Node *z) {
Node *y, *x;

if (z->left == NIL || z->right == NIL) y = z;
else y = tSuccessor(z);

if (y->left != NIL) {
x = y->left;
} else {
x = y->right;
}

if (x != NIL) {
x->parent = y->parent;
}

if (y->parent == NIL) {
root = x;

} else {
if (y == y->parent->left) {
y->parent->left = x;
} else {
y->parent->right = x;
}
}

if (y != z) {
z->key = y->key;
}

free(y);
}

void preorder(Node *node) {
if (node == NIL) return;
cout << " " << node->key;
preorder(node->left);
preorder(node->right);
}

void inorder(Node *node) {
if (node == NIL) return;
inorder(node->left);
cout << " " << node->key;
inorder(node->right);
}

int main() {
int n, x;
string op;
cin >> n;
for (int i=0; i<n; i++) {
cin >> op;
if (op[0] == 'i') {
cin >> x;
insert(x);
continue;
}
else if (op[0] == 'd') {
cin >> x;
tDelete(findNode(root, x));
continue;
}

else if (op[0] == 'f') {
cin >> x;
if (find(root, x)) {
cout << "yes" << endl;
} else {
cout << "no" << endl;
}
continue;
}
else if (op[0] == 'p') {
inorder(root); cout << endl;
preorder(root); cout << endl;
continue;
}
}

return 0;
}


リモートフリーランス。ウェブサービス、スマホアプリエンジニア。

お仕事のご依頼・お問い合わせはこちら