被 二叉搜索树 手撕

#include<iostream>
#include<cmath>
using namespace std;
typedef  struct Node {
	long val;
	Node* left;
	Node* right;
	Node(long _val,Node*_left=nullptr,Node*_right=nullptr):
		val(_val),left(_left),right(_right){}
}Node;
Node* root = nullptr;

long factorySize = 0;
bool insert(Node*& root, long wood) {
	if (root == nullptr) {
		factorySize++;
		root = new Node(wood);
		return true;
	}
	else if (root->val == wood) {
		return false;
	}
	else if (root->val < wood) {
		return insert(root->right, wood);
	}
	else {
		return insert(root->left, wood);
	}
}

Node* find_parent_node(Node* node,Node*ultimate) {
	Node* temp = ultimate;
	while (temp) {
		if (temp->left == node || temp->right == node) {
			return temp;
		}
        else if(temp->val<node->val){
          temp=temp->right;
        }
        else{
          temp=temp->left;
        }
    }
	return nullptr;
}

void delete_node(Node* node) {
	factorySize--;
	Node* ultimate = new Node(-100, nullptr, root);//如果输入的木头长度为负数，那么这里可能会出现bug
  //cout<<"there1"<<endl;
	Node* parent = find_parent_node(node,ultimate);
  //cout<<"there2"<<endl;
	//if parent==nullptr, then there must be some bug
	if (!node->left && !node->right) {
		if (parent->left == node) {
			parent->left = nullptr;
		}
		else {
			parent->right = nullptr;
		}
		delete node;
	}
	else if (!node->left) {
		if (parent->left == node) {
			parent->left = node->right;
		}
		else {
			parent->right = node->right;
		}
		delete node;
	}
	else if (!node->right) {
		if (parent->left == node) {
			parent->left = node->left;
		}
		else {
			parent->right = node->left;
		}
		delete node;
	}
	else {
		//这种情况最容易产生bug
		Node* node_pre = nullptr;//我要找node的pre节点，肯定可以找到，因为node有左子树
		Node* temp = ultimate->right;
		while (temp) {
			if (temp->val < node->val) {
				if (!node_pre || temp->val > node_pre->val) {
					node_pre = temp;
				}
				temp = temp->right;
			}
			else {
				temp = temp->left;
			}
		}
		Node* node_pre_parent = find_parent_node(node_pre, ultimate);
		swap(node_pre->val, node->val);
		if (node_pre_parent->left == node_pre) {
			node_pre_parent->left = node_pre->left;
			delete node_pre;
		}
		else {
			node_pre_parent->right = node_pre->left;
			delete node_pre;
		}
	}
	root = ultimate->right;
}

long getout(Node* root, long wood) {
	Node* pre = nullptr;//前缀
	Node* temp = root;
	while (temp) {
		if (temp->val == wood) {
			delete_node(temp);
			return wood;
		}
		else if(temp->val<wood) {
			if (!pre || pre->val < temp->val) {
				pre = temp;
			}
			temp = temp->right;
		}
		else {
			temp = temp->left;
		}
	}
	//be cautions : pre may be a null pointer
	/*cout << "Test: pre=";
	if (!pre) {
		cout << "nullptr" << endl;
	}
	else {
		cout << pre->val << endl;
	}*/


	Node* pass = nullptr;//后缀
	temp = root;
	while (temp) {
		if (temp->val == wood) {
			delete_node(temp);
			return wood;
		}
		else if (temp->val < wood) {
			temp = temp->right;
		}
		else {
			if (!pass || pass->val < temp->val) {
				pass = temp;
			}
			temp = temp->left;
		}
	}
	//be cautions : pass may be a null pointer
	/*cout << "Test: pass=";
	if (!pass) {
		cout << "nullptr" << endl;
	}
	else {
		cout << pass->val << endl;
	}*/

	if (!pre && !pass) {
		cout << "this case is not allowed" << endl;
		return -1;
	}
	else if (!pre) {
		long res = pass->val;
		delete_node(pass);
		return res;
	}
	else if (!pass) {
		long res = pre->val;
		delete_node(pre);
		return res;
	}
	else {
		//pre和pass都不是空指针
		if (fabs(pre->val - wood) <= fabs(pass->val - wood)) {
			long res = pre->val;
			delete_node(pre);
			return res;
		}
		else {
			long res = pass->val;
			delete_node(pass);
			return res;
		}
	}
}

int main() {
	long N;
	cin >> N;
	int order;
	long wood;
	for (long i = 0; i < N; i++) {
		cin >> order >> wood;
		if (order == 1) {
			if (!insert(root, wood)) {
				cout << "Already Exist" << endl;
			}
		}
		else {
			if (factorySize == 0) {
				cout << "Empty" << endl;
			}
			else {
				long res = getout(root, wood);
				if (res == -1) {
					cout << "Error case" << endl;
				}
				else {
					cout << res << endl;
				}
			}
		}
	}
	return 0;
}