搜索二叉树_SearchBinaryTree_搜索二叉树的时间复杂度

目录

搜索二叉树的原理

搜索二叉树的搜索时间复杂度

二叉搜索树实现_key 模型

节点

构造函数

查找

中序遍历

插入

循环

递归

删除

循环

1.删除叶子节点

2.删除有一个孩子的节点

3.左右孩子都不为空

递归

析构函数

拷贝构造

operator=

key_value 模型

节点

查找

插入

---

搜索二叉树的原理

搜索二叉树是通过根节点大于左子树节点，小于右子树节点来完成快速查找的。

搜索二叉树的搜索时间复杂度

搜索二叉树的时间复杂度是O(logN) ~ O(N)的。

如果是上面这样那么查找的时间复杂度就接近于 logN, 但是二叉搜索树不一定为满二叉树，或者接近满二叉树，所以如果二叉搜索树是下面这个样子，甚至退化为列表，那么查找的时间复杂度就是 N 了

 

二叉搜索树实现_key 模型

节点

二叉搜索树的节点可以保存它的左孩子，还有右孩子，以及就是它里面存储的值，并且二叉搜索树还需要可以存储任意类型的值，所以需要是模板类型。

    template<class K>
    struct BSTNode
    {
        BSTNode<K>* _left;
        BSTNode<K>* _right;
        K _key;
​
        BSTNode(K key)
            :_left(nullptr)
            , _right(nullptr)
            , _key(key)
        {}
    };
​
    template<class K>
    class BSTree
    {
     public:
        typedef BSTNode<K> Node;
     private:
        Node*  _root;
    };

上面就是二叉搜索树的成员变量。

构造函数

构造函数我们只需要将里面的 _root 成员变量初始化为空即可。

        BSTree()
            :_root(nullptr)
        {}

查找

对于搜索二叉树而言，它的根小于右子树节点，大于左子树节点，所以当我们要查找一个值是否存在的时候，只需要判断大小，如果大于根节点，那么就到右子树查找，小于根节点就去左子树查找，如若查找到空，那么就是没有查找到。

        bool find(Node* root, const K& key)
        {
            while (root)
            {
                if (root->_key < key)
                    root = root->_right;
                else if (root->_key > key)
                    root = root->_left;
                else
                    return true;
            }
            return false;
        }

上面就是我们的 find 函数，但是我们还是需要多一个根节点，但是我们在外面有无法访问根节点，那怎么办呢？

• 解决方案1：写一个 getRoot() 函数

• 封装

下面我们就使用封装来完成。

        bool find(const K& key)
        {
            return _find(_root, key);
        }
        
        bool _find(Node* root, const K& key)
        {
            while (root)
            {
                if (root->_key < key)
                    root = root->_right;
                else if (root->_key > key)
                    root = root->_left;
                else
                    return true;
            }
            return false;
        }

这里我们建议把子函数进行私有，子函数不对外公布。

所以我们用封装来解决类似的问题还是一个很好的办法，我们下面遇到的这种情况就是直接使用封装了。

中序遍历

中序遍历就是对一颗二叉树进行先访问左子树，在访问根节点，最后访问右子树，对于搜索二叉树而言，中序遍历就是排序，因为我们的左子树小于根节点，根节点小于右子树，所以对搜索二叉树进行中序遍历那么就是排序。

遍历也是需要传入根节点的，所以这里还是使用上面的套路（封装）。

        void InOrder()
        {
            _InOrder(_root);
            cout << endl;
        }
​
        void _InOrder(Node* root)
        {
            if (root == nullptr) return;
​
            _InOrder(root->_left);
            cout << root->_key << " ";
            _InOrder(root->_right);
        }

插入

插入，我们需要在插入后还要保证是我们的树是搜索二叉树，所以插入也是需要遵守根大于左子树，小于右子树的规则，所以这里就是需要查找，找到空为止，如果找到相同的值，那么就不能继续插入。

循环

我们这里先写一个循环版本的，下面还会有一个递归版本的，该循环版本就是我们需要查找到插入位置，我们循环遍历，当然在查找过程中我们还需要记录父节点，但是这里也是需要注意，如果根节点就是空，那么就是直接插入即可，在循环查找空的时候如果插入元素大于根那么就去右边插入，小于就去左边，直到找到空为止，此时也找到了空位置的父亲节点，然后new 一个节点连接起来，这里我们还是需要判断大小的，因为这里并不知道是连接到父亲节点的左子树还是右子树，所以还是需要判断的。

        bool insert(const K& key)
        {
            if (_root == nullptr)
            {
                _root = new Node(key);
            }
            else
            {
                // 查找插入位置
                Node* parent = nullptr;
                Node* cur = _root;
                while (cur)
                {
                    if (key < cur->_key)
                        parent = cur, cur = cur->_left;
                    else if (key > cur->_key)
                        parent = cur, cur = cur->_right;
                    else
                        return false;
                }
                // 找到了
                cur = new Node(key);
                if (key < parent->_key)
                    parent->_left = cur;
                else
                    parent->_right = cur;
            }
​
            return true;
        }

递归

递归，我们这里使用的是封装的写法，因为这里需要递归所以我们需要找到插入的位置，这里插入是空就插入，这里我们是直接修改指针的，为什么可以直接修改指针呢，并且不考录父亲节点的连接呢？因为我们这里使用引用，这里我们如果直接就是空（根节点就是空，所以此时我们的 root 变量就是根节点的引用，我们修改root,也就是直接修改了根节点的指向），那么我们这里的引用其实在同一层是没有什么作用的，这里只有在下一层的时候才有作用（下一层就是该节点传下去的那一层），我们分析一下，如果这里我们插入的元素大于根节点，所以我们继续调用该函数，到下一层的时候我们的root节点就是上一层root节点的右子树的引用，所以我们修改root节点，也就是直接修改了上一层root节点的右子树指向，所以这里的引用在当前层没有发挥作用，如果插入的节点小于根节点，那么就是调用该函数去左子树进行插入，而这一层的root节点也就是上一层root节点的左子树的引用，所以修改该层的root节点也就是修改了上一层左子树的节点，直到查找到nullptr为止，然后进行插入，如果并未查找到 nullptr 节点那么就插入失败了。

        bool insertR(const K& key)
        {
            return _insertR(_root, key);
        }
        
        bool _insertR(Node*& root, const K& key)
        {
            if (root == nullptr)
            {
                root = new Node(key);
                return true;
            }
​
            if (root->_key < key)
                return _insertR(root->_right, key);
            else if (root->_key > key)
                return _insertR(root->_left, key);
            else
                return false;
        }

删除

删除和插入一样，同样有循环和递归两个版本。

循环

循环删除我们同样是要先找要删除的节点，如果找到了才可恶意进行删除，如果查找为空，表示删除失败，要想删除一个点，我们同样需要记录删除节点的父亲节点。

对于删除而言，我们删除的位置不同，难易程度也是不同的。

1.删除叶子节点

如果我们这里删除的是节点 7， 那么我们这里就可以直接删除，然后将节点 8 的左子树置为空，所以删除叶子节点直接删除，然后将父亲节点的与该节点连接的孩子节点置为空即可。

2.删除有一个孩子的节点

 

 如果这里删除的是只有一个节点，那么我们就可以删除掉该节点，然后将该节点的孩子节点连接到父亲节点上。

我们将节点 5 的孩子节点连接到节点3 上，所以删除有一个孩子的节点，我们可以将它的孩子节点给父亲，然后删除掉该节点。

3.左右孩子都不为空

左右孩子都不为空是最难删除的，我们下面看一下怎么删除。

节点 10 左右孩子都不为空，我们如果想删掉该节点，那么我们就需要找一个可以代替节点10 的孩子节点，那么根据二叉搜索树的规则，我们应该保持删掉后还要让该树的所有节点都是根大于左子树，小于右子树所以我们可以找到左子树的最大节点，或者是右子树的最小节点，在查找右子树的最小，或者左子树的最大的时候，我们还是需要记录替换节点的父亲节点，因为我们最后查找到替换后，就是删除替换后的节点，所以这里需要记录替换你节点的父亲节点，那么10节点的左子树的最大节点就是9，右子树的最小节点就是15，也就是左子树的最右节点，左子树的最右节点一定是左子树的最大节点，右子树的最小节点就是右子树的最左节点，右子树的最左节点也就一定是右子树的最小节点，找到代替节点后，我们就可以交换，然后删掉交换后的节点，但是交换后的节点不一定没有左右孩子，对于左子树的最右节点一定没有右孩子，但是不一定没有左孩子，所以如果右左孩子的话，还需要将该节点删除后，还要将该节点的左孩子给查到到父亲，如果是右子树的话，那么查找到的最左孩子一定没有左节点，但是不一定没有右节点，所以如果有右节点还是需要将右节点也该查到到的该节点的父亲。

这里删除节点10不好演示，删除节点3，看一下。

如果这里要删除节点3，那么先查找要删除的节点，然后我们查找到了节点 3 由于节点3左右孩子都不为空，所以我们需要找一个代替的节点，我们这里选择左子树的最大节点，我们查找到了1，由于节点5的父亲节点就是节点3，所以我们直接替换，然后我们将替换节点的左子树给删除节点的父亲节点，然后我们在删除掉删除节点。

 

此时找到删除节点，然后查找左孩子的最大值，和它的父亲节点。

 

查找到了，这里左孩子的最大节点就是 1 ，它的父亲就是cur节点，然后这里交换。

 

交换后，然后我们将 leftMax 的孩子节点给 leftMaxParent 进行管理，最后删除掉 leftMax。

 

 

这里演示完毕后我们开始看代码。

在写代码之前，我们先总结一下，我们如果删除的节点是叶子节点或者是左孩子为空或者是右孩子为空的节点，那么我们可以分为一类，也就是叶子节点可以认为是只有一个孩子节点，这样我们更方便处理，如果我们只有一个孩子节点，那么我们就可以直接让删除节点的父亲节点指向另外一个孩子节点。

也就是下面这样

    if(cur->left == nullptr) // cur 表示要删除的节点
    {
        // 左为空，让父亲指向自己的右
        if(cur == parent->left)
            parent->left = cur->right;
        else
            parent->right = cur->right;
    }
    else
    {
        // 右为空，让父亲指向自己的左
         if(cur == parent->left)
            parent->left = cur->left;
        else
            parent->right = cur->left;
    }

但是这里还是有一个需要注意的地方，那就是如果我们的根节点就是删除的点呢？所以这时候我们的parent就是空，并且我们的根节点没有左子树或者右子树，那么就会让parent解引用，然后就是对空进行解引用最后报错，也就是我们上面的那一段代码。

那么这里怎么办？我们可以进去后继续判断一下，cur == _root ，如果等于那么就只需要将 _root 变成它的左子树或者右子树，然后删除掉该节点。

剩下的我们基本都清楚了，下面就看代码。

        bool erase(const K& key)
        {
            Node* parent = nullptr;
            Node* cur = _root;
            // 查找
            while (cur)
            {
                if (key < cur->_key)
                {
                    parent = cur;
                    cur = cur->_left;
                }
                else if (key > cur->_key)
                {
                    parent = cur;
                    cur = cur->_right;
                }
                else
                {
                    // 找到了
                    if (cur->_left == nullptr)
                    {
                        // cur 的左子树为空
                        if (cur == _root)
                        {
                            // 说明此时parent 为空,并且此时该树还没有左子树
                            _root = cur->_right;
                        }
                        else
                        {
                            if (cur == parent->_left)
                            {
                                parent->_left = cur->_right;
                            }
                            else if (cur == parent->_right)
                            {
                                parent->_right = cur->_right;
                            }
                        }
                    }
                    else if (cur->_right == nullptr)
                    {
                        // cur 的右子树为空
                        if (cur == _root)
                        {
                            // 说明此时parent 为空,并且此时该树还没有右子树
                            _root = cur->_left;
                        }
                        else
                        {
                            if (cur == parent->_left)
                            {
                                parent->_left = cur->_left;
                            }
                            else if (cur == parent->_right)
                            {
                                parent->_right = cur->_left;
                            }
                        }
                    }
                    else
                    {
                        // cur 的左右子树都不为空
                        Node* rightMinParent = cur;
                        Node* rightMin = cur->_right;
                        // 查找右子树的最左节点
                        while (rightMin->_left)
                        {
                            rightMinParent = rightMin;
                            rightMin = rightMin->_left;
                        }
                        swap(cur->_key, rightMin->_key);
                        if (rightMin == rightMinParent->_left)
                        {
                            rightMinParent->_left = rightMin->_right;
                        }
                        else
                        {
                            rightMinParent->_right = rightMin->_right;
                        }
                        cur = rightMin;
                    }
​
                    delete cur;
                    return true;
                }
            }
            // 没找到
            return false;
        }

递归

递归删除就是我们传入根节点，然后我们在传入删除节点，如果该节点就是删除的节点，那么就在判断该节点的孩子是只有一个还是左右孩子节点都不为空，如果是只有一个孩子节点或者为叶子节点的话，那么就直接删除，如果既有左孩子也有右孩子，那么就是查找左子树的最大，或者右子树的最小，找到后交换，然后递归去删除。

这里也是用引用，这样就可以不用记录父亲节点了。

        bool eraseR(const K& key)
        {
            return _eraseR(_root, key);
        }
​
        bool _eraseR(Node*& root, const K& key)
        {
            if (root == nullptr)
                return false;
​
            if (root->_key < key)
                _eraseR(root->_right, key);
            else if (root->_key > key)
                _eraseR(root->_left, key);
            else
            {
                Node* del = root;
                // 相等
                if (root->_left == nullptr) // 左边为空，将右边给父亲
                    root = root->_right;
                else if (root->_right == nullptr) // 右边为空，将左边给父亲
                    root = root->_left;
                else
                {
                    // 两边都不为空
                    Node* rightMin = root->_right;
                    while (rightMin->_right) rightMin = rightMin->_right; // 查找有边的最小值
                    swap(rightMin->_key, root->_key);
                    // 递归删除root->_right 
                    return _eraseR(root->_right, key);
                }
                delete del;
            }
        }

析构函数

析构函数我们可以后续遍历删除。我们写一个 destroy 函数去后续遍历删除。

        ~BSTree()
        {
            destroy(_root);
        }
​
        void destroy(Node*& root)
        {
            if (root == nullptr) return;
​
            destroy(root->_left);
            destroy(root->_right);
            delete root;
            root = nullptr;
        }

拷贝构造

拷贝构造我们也可以递归的去构造该函数。这里看代码可以直接明白。

        BSTree(const BSTree& BST)
        {
            _root = copy(BST._root);
        }
​
        Node* copy(Node* root)
        {
            if (root == nullptr)
                return nullptr;
​
            Node* copyNode = new Node(root->_key);
            copyNode->_left = copy(root->_left);
            copyNode->_right = copy(root->_right);
            return copyNode;
        }

operator=

赋值重载，我们可以使用现代写法也是很简单。

        BSTree<K>& operator=(BSTree<K> t)
        {
            std::swap(_root, t._root);
            return *this;
        }

key 模型就到这里，下面我们看 key_value 模型

key_value 模型

其实 key 模型改 key_value 模型还是比较简单的，我们只需要加一个一个 value 就可以了，我们让 key 与 value 映射起来。

节点

key_value 模型与key 的差别就是多了一个 value 所以我们在写的时候模板还需要多加一个 value，我们使用 key 进行查找等，然后与 value 进行映射。

namespace key_value
{
    template<class K, class V>
    struct BSTNode
    {
        BSTNode<K, V>* _left;
        BSTNode<K, V>* _right;
        K _key;
        V _value;
​
        BSTNode(K key, V value)
            :_left(nullptr)
            , _right(nullptr)
            , _key(key)
            ,_value(value)
        {}
    };
    
    tempalte<class K, class V>
    class BSTree
    {
        public:
        typedef BSTNode<k, V> Node;
        private:
        Node* _root;
    };
}

查找

这里的查找基本还是没有变化的，我们知识返回值不同，如果是 key_value 模型的话，那么我们是需要返回查找的节点的指针的，所以我们的 find 函数只是返回值不同。

这里的 find 是用递归写的，上面也可以用递归只是这个 find 太简单了，就没有用递归是实现。

        Node* findR(const K& key)
        {
            return _findR(_root, key);
        }
​
        Node* _findR(Node* root, const K& key)
        {
            if (root == nullptr)
                return root;
​
            if (root->_key < key)
                return _findR(root->_right, key);
            else if (root->_key > key)
                return _findR(root->_left, key);
            else
                return root;
        }

插入

对于 key_value 模型来说，我们只有这么三个函数是不一样的（构造函数就不说了），我们 key_value 模型的插入也就是比 key 模型多了一个插入 value，所以这个并不难。

        bool insertR(const K& key, const V& value)
        {
            return _insertR(_root, key, value);
        }
​
        bool _insertR(Node*& root, const K& key, const V& value)
        {
            if (root == nullptr)
            {
                root = new Node(key, value);
                return true;
            }
​
            if (root->_key < key)
                return _insertR(root->_right, key, value);
            else if (root->_key > key)
                return _insertR(root->_left, key, value);
            else
                return false;
        }

上面就是我们今天要讲的，二叉搜索树的，key 模型 和 key_value 模型。

下次再见~