二叉查找树

struct  {
	int value;
	int cnt;
	Node* lson;
	Node* rson;
	Node* parent;
	int pos;
	Node() {
		value = -1;
		lson = rson = parent = nullptr;
		cnt = pos = 0;
	}
	Node(int _value, Node* _parent, int _pos) :value(_value), parent(_parent), pos(_pos) {
		lson = rson = nullptr;
		cnt = 0;
	}
};
class BST {
private:
	Node* root;
	void _insert(Node *node, int x) {
		if (x == node->value) {
			node->cnt++;
			return;
		}
		if (x < node->value) {
			if (node->lson == nullptr) {
				node->lson = new Node(x, node, 1);
			}
			_insert(node->lson, x);
		}
		else {
			if (node->rson == nullptr) {
				node->rson = new Node(x, node, -1);
			}
			_insert(node->rson, x);
		}
	}
	Node* _find(Node *node, int x) {
		if (node == nullptr || x == node->value) {
			return node;
		}
		return _find(x < node->value ? node->lson : node->rson, x);
	}
	void _delete(Node *node) {
		Node* temp;
		if (node->lson != nullptr && node->rson != nullptr) {
			temp = node->lson;
			while (temp->rson != nullptr) {
				temp = temp->rson;
			}
			node->value = temp->value;
			node->cnt = temp->cnt;
			_delete(temp);
			return;
		}
		if (node->lson == nullptr && node->rson == nullptr) {
			if (node->pos == 0) {
				root = nullptr;
			}
			else {
				(node->pos == 1 ? node->parent->lson : node->parent->rson) = nullptr;
			}
		}
		else {
			temp = (node->lson == nullptr ? node->rson : node->lson);
			if (node->pos == 0) {
				root = temp;
				root->parent = root;
				root->pos = 0;
			}
			else {
				temp->pos = node->pos;
				temp->parent = node->parent;
				(node->pos == 1 ? node->parent->lson : node->parent->rson) = temp;
			}
		}
		delete node;
	}
	
public:
	void Insert(int x) {
		if (root == nullptr) {
			root = new Node(x, root, 0);
			root->cnt = 1;
			return;
		}
		_insert(root, x);
	}
	bool Find(int x) {
		return _find(root, x) != nullptr;
	}
	bool Delete(int x) {
		Node* n = _find(root, x);
		if (n == nullptr) {
			return false;
		}
		if (--n->cnt == 0) {
			_delete(n);
		}
		return true;
	}
};