二叉查找树

定义

二叉查找树或者是一棵空树，或者是具有下列性质的二叉树

• 若左子树不空，则左子树上所有结点的值均小于它的根节点的值；
• 若右子树不空，则右子树上所有结点的值均大于它的根结点的值；
• 左、右子树也分别为二叉排序树；

二叉查找树.png

二叉查找树的删除算法

二叉查找树的删除分为3种情况：

• 待删节点是叶子节点
• 待删节点只有一棵子树
  • 只有左子树
  • 只有右子树
• 待删节点有左右子树

待删节点是叶子节点

叶子节点.jpg

直接将父结点的相应指针修改为空。

待删节点只有一棵子树

只有一棵子树.png

将要删除的父结点的相应子结点指针指向要删除的结点的唯一子结点

待删节点有左右子树

【1】 找到该右子树中最小的结点（即一直往左走）。
【2】 复制key。
【3】调整树。

有左右子树.png

template <typename Key>
void BSTree<Key>::remove(const Key &key) {
    root = deleteNode(key, root);
}

template <typename Key>
typename BSTree<Key>::BSTNodePtr BSTree<Key>::deleteNode(const Key& key, BSTNodePtr x) {
    if (x == nullptr)
        return nullptr;

    if (key > x->key )
        x->right = deleteNode(key, x->right);
    else if (key < x->key)
        x->left = deleteNode(key, x->left);
    else {
        /* 叶子节点 */
        if (x->right == nullptr && x->left == nullptr) {
            delete x;
            count--;
            return nullptr;
        }
        /* 只有一颗子树 */
        else if (x->left != nullptr && x->right == nullptr) {
            BSTNodePtr tmp = x->left;
            delete x;
            count--;
            return tmp;
        }
        else if (x->left == nullptr && x->right != nullptr) {
            BSTNodePtr tmp = x->right;
            delete x;
            count--;
            return x->right;
        }
        /* 有左右子树 */
        else {
            BSTNodePtr rightMinNode = minNode(x->right);
            x->key = rightMinNode->key;
            deleteMinNode(x->right);
        }
    }

    return x;
}

分析

• 在一棵二叉查找树中，所有操作在最坏情况下所需要的时间和树的高度成正比