Binary search tree implemented by C++.

BST.cpp

/*
 * @author  duruyao
 * @file    BST.cpp
 * @desc    
 * @date    2021-10-07
 * @version 1.0
 */

#include <vector>
#include <iostream>

template<typename T, int (*cmpFunc)(const T &, const T &)>
struct Node {
    T data;
    Node *left;
    Node *right;

    Node() = delete;

    Node(const Node<T, cmpFunc> &) = delete;

    Node &operator=(const Node<T, cmpFunc> &) = delete;

    Node(Node<T, cmpFunc> &&that) noexcept: data(that.data), left(that.left), right(that.right) {
        that.left = that.right = nullptr;
    }

    Node &operator=(Node<T, cmpFunc> &&that) noexcept {
        data = that.data;
        left = that.left;
        right = that.right;
        that.left = that.right = nullptr;
    }

    explicit Node(const T &t) : data(t), left(nullptr), right(nullptr) {}

    virtual ~Node() { release(); }

private:
    void release() {
        if (left) {
            if (left->left || left->right) {
                left->release();
            } else {
                delete left;
            }
        } else if (right) {
            if (right->left || right->right) {
                right->release();
            } else {
                delete right;
            }
        }
    }
};

template<typename T, int (*cmpFunc)(const T &, const T &)>
void addNode(Node<T, cmpFunc> **ppNode, const T &target) {
    auto pNode = *ppNode;
    if (!pNode) {
        *ppNode = new Node<T, cmpFunc>(target);
    } else if (cmpFunc(target, pNode->data) <= 0) {
        addNode(&(pNode->left), target);
    } else {
        addNode(&(pNode->right), target);
    }
}

template<typename T, int (*cmpFunc)(const T &, const T &)>
bool searchNode(Node<T, cmpFunc> *pNode, const T &target, T &result) {
    if (pNode) {
        if (cmpFunc(target, pNode->data) == 0) {
            result = pNode->data;
            return true;
        } else if (cmpFunc(target, pNode->data) < 0) {
            return searchNode(pNode->left, target, result);
        } else if (cmpFunc(target, pNode->data) > 0) {
            return searchNode(pNode->right, target, result);
        }
    }
    return false;
}

template<typename T, int (*cmpFunc)(const T &, const T &)>
bool deleteNode(Node<T, cmpFunc> **ppNode, const T &target) {
    auto pNode = *ppNode;
    if (pNode) {
        if (cmpFunc(target, pNode->data) == 0) {
            if (!pNode->left) {
                *ppNode = pNode->right;
            } else if (!pNode->left->right) {
                *ppNode = pNode->left;
                pNode->left->right = pNode->right;
            } else {
                auto parentOfMax = pNode->left;
                for (; parentOfMax && parentOfMax->right &&
                       parentOfMax->right->right; parentOfMax = parentOfMax->right);
                auto max = parentOfMax->right; // the largest node of the left subtree of the target
                *ppNode = max;
                max->right = pNode->right;
                auto min = max;
                for (; min && min->left; min = min->left); // the smallest child-node of the largest node of the left subtree of the target
                min->left = pNode->left;

                parentOfMax->right = nullptr;
            }
            pNode->left = pNode->right = nullptr;
            delete pNode;
        } else if (cmpFunc(target, pNode->data) < 0) {
            return deleteNode(&(pNode->left), target);
        } else if (cmpFunc(target, pNode->data) > 0) {
            return deleteNode(&(pNode->right), target);
        }
    }
    return false;
}

template<typename T, int (*cmpFunc)(const T &, const T &)>
void traverseNode(const Node<T, cmpFunc> *pNode, std::ostream &os) {
    if (pNode) {
        traverseNode(pNode->left, os);
        os << pNode->data << " ";
        traverseNode(pNode->right, os);
    }
}

template<typename T, int (*cmpFunc)(const T &, const T &)>
class BST {
private:
    Node<T, cmpFunc> *root;

public:
    BST() : root(nullptr) {}

    explicit BST(const std::vector<T> &input) : root(nullptr) {
        for (auto &it : input) { Add(it); }
    }

    inline void Add(const T &target) {
        addNode(&root, target);
    }

    inline bool Search(const T &target, T &result) const {
        return searchNode(root, target, result);
    }

    inline bool Delete(const T &target) {
        return deleteNode(&root, target);
    }

    virtual ~BST() { delete root; }

    friend std::ostream &operator<<(std::ostream &os, const BST<T, cmpFunc> &bst) {
        traverseNode(bst.root, os);
        return os;
    }
};

int cmpInt(const int &n1, const int &n2) {
    return n1 - n2;
}

template<typename T>
std::ostream &operator<<(std::ostream &os, const std::vector<T> &input) {
    for (auto &it : input) { os << it << " "; }
    return os;
}

int main(int argc, char **argv) {
    std::vector<int> array;
    for (int i = 0; i < 40; array.push_back(random() % 100), i++);
    auto bst = BST<int, cmpInt>(array);
    array.push_back(72);
    bst.Add(72);
    array.push_back(99);
    bst.Add(99);
    std::cout << array << std::endl;
    std::cout << bst << std::endl;

    auto target = 72, result = -1;
    if (bst.Search(target, result)) {
        std::cout << target << " is found" << std::endl;
    } else {
        std::cout << target << " is not found" << std::endl;
    }

    return 0;
}