搜索二叉树

搜索二叉树是一棵空树，或者是具有以下性质的二叉树：

• 若它的左子树不为空，则左子树上所有结点的值都小于根结点的值。
• 若它的右子树不为空，则右子树上所有结点的值都大于根结点的值。
• 它的左右子树也分别是二叉搜索树。

插入数据

根据二叉搜索树的性质，有以下情况：

1. 如果是空树，则直接将插入结点作为二叉搜索树的根结点
2. 如果不是空树，则按照二叉搜索树的性质进行结点的插入

• 若待插入结点的值小于根结点的值，则需要将结点插入到左子树当中
• 若待插入结点的值大于根结点的值，则需要将结点插入到右子树当中
• 若待插入结点的值等于根结点的值，则插入结点失败

删除数据

• 若是在二叉树当中没有找到待删除结点，则直接返回false表示删除失败
• 若是找到了待删除结点，有以下四种情况：

待删除结点左子树为空

待删除结点的左子树为空，让其父结点指向该结点的右孩子结点，然后将该结点释放便完成了该结点的删除

待删除结点右子树为空

待删除结点的右子树为空，让其父结点指向该结点的左孩子结点，然后将该结点释放便完成了该结点的删除

待删除结点左右子树均为空

直接删除

待删除结点左右子树均为非空

在遇到待删除结点的左右子树均不为空的情况时，采用的处理方法如下：

使用minParent标记待删除结点右子树当中值最小结点的父结点。 使用minRight标记待删除结点右子树当中值最小的结点。 当找到待删除结点右子树当中值最小的结点时，先将待删除结点的值改为minRight的值，之后直接判断此时minRight是minParent的左孩子还是右孩子，然后对应让minParent的左指针或是右指针转而指向minRight的右孩子（注意：minRight的左孩子为空），最后将minRight结点进行释放即可。

代码实现

//BSTree结点类
template<class K>
class BSTreeNode {
public:
    K key;                 //结点值
    BSTreeNode<K> *left;   //左指针
    BSTreeNode<K> *right;  //右指针
public:
    //构造函数
    explicit BSTreeNode(const K &key = 0) : key(key), left(nullptr), right(nullptr) {}
};

// BSTree类
template<class K>
class BSTree {
public:
    // 根结点
    BSTreeNode<K> *root;
public:
    //构造函数
    BSTree() : root(nullptr) {}

    //拷贝构造函数
    BSTree(const BSTree<K> &tree) {
        if (tree == nullptr)
            return;
        BSTreeNode<K> newroot = new BSTreeNode<K>(tree.root->key);
        newroot.left = tree.root->left;
        newroot.right = tree.root->right;
        this->root = newroot;
    }

    //赋值运算符重载函数:深拷贝
    //现代写法
    BSTree<K> &operator=(BSTree<K> tree) //编译器接收右值的时候自动调用拷贝构造函数
    {
        swap(root, tree.root);  //交换这两个对象的二叉搜索树
        return *this;           //支持连续赋值
    }

    //释放树中结点
    void destory(BSTreeNode<K> *rt) {
        if (rt == nullptr) //空树无需释放
            return;
        destory(rt->left); //释放左子树中的结点
        destory(rt->right); //释放右子树中的结点
        delete rt; //释放根结点
    }

    //析构函数
    ~BSTree() {
        destory(root);
        delete root;
    }

    bool insertPart(const K &key, BSTreeNode<K> *&rt) {
        if (rt == nullptr) {
            rt = new BSTreeNode<K>(key);
            return true;
        } else if (key < rt->key)
            return insertPart(key, rt->left);
        else if (key > rt->key)
            return insertPart(key, rt->right);
        else
            return false;
    }

    //插入函数
    bool insert(const K &key) {
        return insertPart(key, root);
    }

    bool erasePart(const K &key, BSTreeNode<K> *&rt) {
        if (rt == nullptr) {
            return false;
        } else if (key < rt->key)
            return erasePart(key, rt->left);
        else if (key > rt->key)
            return erasePart(key, rt->right);
            // 找到了该结点
        else {
            if (rt->left == nullptr && rt->left == nullptr) {
                delete rt;
                rt = nullptr;
            } else if (rt->left != nullptr && rt->left == nullptr) {
                BSTreeNode<K> *temp = rt;
                rt = rt->left;
                delete temp;
            } else if (rt->left == nullptr && rt->right != nullptr) {
                BSTreeNode<K> *temp = rt;
                rt = rt->right;
                delete temp;
            } else {
                // 重要
                // 寻找右子树中最小的节点（即后继节点）
                BSTreeNode<K> *minright = rt->right;
                BSTreeNode<K> *minparent = rt;
                while (minright->left != nullptr) {
                    minparent = minright;
                    minright = minright->left;
                }
                // 将后继节点的数据复制到当前节点
                rt->key = minright->key;
                // 删除后继节点
                // 此时minRight的_left为空
                if (minright == minparent->left) {
                    minparent->left = minright->right;

                } else {
                    minparent->right = minright->right;
                }
                delete minright;
            }
            return true;
        }
    }

    //删除函数
    bool erase(const K &key) {
        return erasePart(key, root);
    }

    BSTreeNode<K> *searchPart(const K &key, BSTreeNode<K> *&rt) {
        if (rt == nullptr || rt->key == key)
            return rt;
        else if (key < rt->key)
            return searchPart(key, rt->left);
        else if (key > rt->key)
            return searchPart(key, rt->right);
    }

    //查找函数
    BSTreeNode<K> *search(const K &key) {
        return searchPart(key, root);
    }

    //中序遍历
    void inorderPart(BSTreeNode<K> *&rt) {
        if (rt == nullptr)
            return;
        inorderPart(rt->left);
        cout << rt->key << " ";
        inorderPart(rt->right);
    }

    void inOrder() {
        inorderPart(root);
        cout << endl;
    }

};


int main() {
    BSTree<int> bsTree;
    bsTree.insert(100);
    bsTree.insert(23);
    bsTree.insert(10);
    bsTree.insert(56);
    bsTree.insert(999);
    bsTree.insert(1);
    bsTree.insert(19);

    bsTree.inOrder();
    bsTree.erase(23);
    bsTree.erase(999);
    bsTree.inOrder();

    if (bsTree.search(100) == nullptr)
        cout << "未找到" << endl;
    else
        cout << "找到了" << endl;
    return 0;
}

K模型和KV模型

K模型:即只有key作为关键码，结构中只需存储key即可，关键码即为需要搜索到的值，像STL中的set容器。

KV模型:对于每一个关键码key，都有与之对应的值value，即<key, value>的键值对，像STL中的map容器。

• 最优的情况下，二叉搜索树为完全二叉树，其平均比较次数为：O(logN)
• 最差的情况下，二叉搜索树退化为单支树，其平均比较次数为：O(N/2)