#include <iostream>
#include <string>
using namespace std;
template <class T> class bst;
template <class T> class btNode{
friend class bst<T>;
public:
btNode(): lchild(0),rchild(0),parent(0) {};
btNode(T x): key(x),lchild(0),rchild(0),parent(0) {};
private:
T key;
btNode<T> *lchild,*rchild,*parent;
};
template <class T> class bst{
public:
bst(): root(0) {};
void trave(btNode<T> *p);
void traverse();
void insert(T x);
void DeleteBST(T KEY);
btNode<T>* search(T x);
private:
btNode<T> *root;
btNode<T>* leftmost(btNode<T> *p);
btNode<T>* Successor(btNode<T> *current);
btNode<T>* rightmost(btNode<T> *p);
btNode<T>* Predecessor(btNode<T> *current);
};
template <class T> btNode<T>* bst<T>::leftmost(btNode<T>* p){
while(p->lchild) p=p->lchild;
return p;
}
template <class T> btNode<T>* bst<T>::Successor(btNode<T> *current){
if (current->rchild != NULL){
return leftmost(current->rchild);
}
btNode<T> *new_node = current->parent;
while (new_node != NULL && current == new_node->rchild) {
current = new_node;
new_node = new_node->parent;
}
return new_node;
}
template <class T> btNode<T>* bst<T>::rightmost(btNode<T> *p){
while(p->rchild) p=p->rchild;
return p;
}
template <class T> btNode<T>* bst<T>::Predecessor(btNode<T> *current){
if (current->lchild != NULL){
return rightmost(current->lchild);
}
btNode<T> *new_node = current->parent;
while (new_node != NULL && current == new_node->lchild) {
current = new_node;
new_node = new_node->parent;
}
return new_node;
}
template <class T> void bst<T>::insert(T x){
btNode<T> *p=new btNode<T>(x);
if(!root) this->root=p;
else {
btNode<T> *q,*r;
q=root;
while(q){
r=q;
if(p->key < q->key) q=q->lchild;
else q=q->rchild;
}
//now r become parent of insert node
p->parent=r;
//insert p to its parent
if (p->key < r->key) {r->lchild=p;}
else r->rchild=p;
}
}
template <class T> btNode<T>* bst<T>::search(T x){
btNode<T> *p;
while(p){
if(x == p->key) break;
else if (x < p->key) p=p->lchild;
else p=p->rchild;
}
return p;
}
template <class T> void bst<T>::DeleteBST(T KEY){ // 要刪除具有KEY的node
btNode<T> *delete_node = search(KEY); // 先確認BST中是否有具有KEY的node
if (delete_node == NULL) return;
btNode<T> *y = 0; // 真正要被刪除並釋放記憶體的node
btNode<T> *x = 0; // 要被刪除的node的"child"
if (delete_node->lchild == NULL || delete_node->rchild == NULL){
y = delete_node;
}
else{
y = Successor(delete_node); // 將y設成delete_node的Successor
} // 經過這組if-else, y調整成至多只有一個child
// 全部調整成case1或case2來處理
if (y->lchild != NULL){
x = y->lchild; // 將x設成y的child, 可能是有效記憶體,
} // 也有可能是NULL
else{
x = y->rchild;
}
if (x != NULL){ // 在y被刪除之前, 這個步驟把x接回BST
x->parent = y->parent; // 此即為圖二(c)中, 把基紐接回龜仙人的步驟
}
// 接著再把要被釋放記憶體的node之"parent"指向新的child
if (y->parent == NULL){ // 若刪除的是原先的root, 就把x當成新的root
this->root = x;
}
else if (y == y->parent->lchild){ // 若y原本是其parent之left child
y->parent->lchild = x; // 便把x皆在y的parent的left child, 取代y
}
else{ // 若y原本是其parent之right child
y->parent->rchild = x; // 便把x皆在y的parent的right child, 取代y
}
// 針對case3
if (y != delete_node) { // 若y是delete_node的替身, 最後要再將y的資料
delete_node->key = y->key; // 放回delete_node的記憶體位置, 並將y的記憶體位置釋放
// 圖二(d), y即是達爾, delete_node即是西魯
}
delete y; // 將y的記憶體位置釋放
y = 0;
}
template <class T> void bst<T>::trave(btNode<T> *p){
cout << p->key << ' ';
if(p->lchild) trave(p->lchild);
if(p->rchild) trave(p->rchild);
}
template <class T> void bst<T>::traverse(){
if(!root) return;
trave(root);
cout << endl;
}
int main(){
bst<int> bt;
string cmd;
while(cin >> cmd && !cin.eof()){
if(cmd == "Traverse") bt.traverse();
else if (cmd == "Insert") {int x; cin >> x; bt.insert(x);}
else if (cmd == "Delete") {int x; cin >> x; bt.DeleteBST(x);}
}
}
