typedef int DataType;
struct TreeNode {
    DataType data;
    std::shared_ptr<TreeNode> left_node;
    std::shared_ptr<TreeNode> right_node;
    TreeNode() : data(0), left_node(nullptr), right_node(nullptr) {};
    TreeNode(DataType value) : data(value), left_node(nullptr), right_node(nullptr) {};
};


class BinarySearchTree {
public:
    BinarySearchTree() {
        root_tree_node_ = std::make_shared<TreeNode>();
    }
    
    // 搜索 target 是否属于该树
    bool Find(DataType target) {
        return Find(target, root_tree_node_);
    }
    
    bool Find(DataType target, std::weak_ptr<TreeNode> tree_node) {
        if(tree_node.expired()) {
            return false;
        }
        auto node_ptr = tree_node.lock();
        if(node_ptr->data == target) {
            return true;
        }
        else if(node_ptr->data > target){
            return Find(target, node_ptr->left_node);
        }
        else {
            return Find(target, node_ptr->right_node);
        }
    }
    
    //插入一个元素
    void InsertData(DataType target) {
        auto insert_node = std::make_shared<TreeNode>(target);
        auto temp_node = root_tree_node_.get();
        while(temp_node) {
            if(target < temp_node->data) {
                if(!temp_node->left_node) {
                    temp_node->left_node = insert_node;
                    num++;
                    return;
                }
                else {
                    temp_node = temp_node->left_node.get();
                }
            }
            //对于相等的情况，按大于当前节点处理
            else {
                if(!temp_node->right_node) {
                    temp_node->right_node = insert_node;
                    num++;
                    return;
                }
                else {
                    temp_node = temp_node->right_node.get();
                }
            }
        }
    }
    
    //删除一个元素
    bool DeleteData(DataType target) {
        if(!root_tree_node_) {
            return false;
        }
        auto tree_node = root_tree_node_;
        std::shared_ptr<TreeNode> node_base = nullptr;
        //找到待删除元素对应的节点
        while(tree_node != nullptr && tree_node->data != target) {
            node_base = tree_node;
            if(tree_node->data < target) {
                tree_node = tree_node->right_node;
            }
            else {
                tree_node = tree_node->left_node;
            }
        }
        if(!tree_node) {
            return false;
        }
        
        //删除节点有两个子节点
        if(tree_node -> left_node && tree_node->right_node) {
            std::shared_ptr<TreeNode> min_node = tree_node->right_node;
            std::shared_ptr<TreeNode> min_node_base = tree_node;
            //寻找右子树的最小节点，将它赋给当前待删除节点
            while(min_node->left_node) {
                min_node_base = min_node;
                min_node = min_node->left_node;
            }
            tree_node->data = min_node->data;
            tree_node = min_node;
            node_base = min_node_base;
        }
        
        //删除节点是叶节点或仅有1个节点
        std::shared_ptr<TreeNode> child_node;
        if(!tree_node -> left_node) {
            child_node = tree_node->left_node;
        }
        else if(!tree_node->right_node){
            child_node = tree_node->right_node;
        }
        else {
            child_node = nullptr;
        }
        
        if(!node_base) {
            root_tree_node_ = child_node;
        }
        else if(tree_node == node_base->left_node) {
            node_base->left_node = child_node;
        }
        else
            node_base->right_node = child_node;
        return true;
    }
    
private:
    int num = 1;
    std::shared_ptr<TreeNode> root_tree_node_;
};