1. Toy模板网首页
  2. > Toy博客

【C++进阶3-二叉搜索树】强，但没貌似还不够？

9月前 作者：周杰偷奶茶 分类：Toy博客 阅读(33) 违法举报

这篇具有很好参考价值的文章主要介绍了【C++进阶3-二叉搜索树】强，但没貌似还不够？。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

今天，带来二叉搜索树的讲解。

文中不足错漏之处望请斧正！

是什么

二叉搜索树（Binary Search Tree）又称二叉排序树。

它可以是一棵空树，也可以是具有以下性质的二叉树:

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

实现

二叉搜索树有两种搜索模型——Key搜索模型和<Key, Value>搜索模型。

Key搜索模型

Key模型的BST每个结点内存一个Key值，即用Key作为关键码，Key本身就是搜索需要找到的值。

结构

template<class K>
struct BSTreeNode
{
    BSTreeNode(const K& key)
    :_left(nullptr),
    _right(nullptr),
    _key(key)
    {}
    
    BSTreeNode<K>* _left = nullptr;
    BSTreeNode<K>* _right = nullptr;
    K _key;
};

template<class K>
class BSTree
{
    typedef BSTreeNode<K> Node;
public:
		Node* _root = nullptr;
};

Insert

思路：key小往左走，key大往右走。

参考代码

		//依照key值找插入位置（BST元素不重复）
    bool Insert(const K& key)
    {
        if(_root == nullptr)
        {
            _root = new Node(key);
            return true;
        }
        
        Node* cur = _root, *parent = nullptr;
        while(cur)
        {
            if(cur->_key < key)
            {
                parent = cur;
                cur = cur->_right;
            }
            else if(key < cur->_key)
            {
                parent = cur;
                cur = cur->_left;
            }
            else
                return false;
        }
        
        cur = new Node(key);
        if(parent->_key < key)
            parent->_right = cur;
        else
            parent->_left = cur;
        
        return true;
    }

Erase

思路：

1. 要删的是根/没有孩子的结点

【C++进阶3-二叉搜索树】强，但没貌似还不够？

：直接删

2. 要删的有左孩子/右孩子

【C++进阶3-二叉搜索树】强，但没貌似还不够？

：将左/右孩子托付给自己的父。

3. 要删的有左右孩子

【C++进阶3-二叉搜索树】强，但没貌似还不够？

【C++进阶3-二叉搜索树】强，但没貌似还不够？

替换法删除：找一个合适的结点替换删除。

找谁？

左子树最大 / 右子树最小都可以。

  • BST规则：左子树的全部结点都比右子树小，也可以说右子树的全部结点都比左子树的大。
  • 左子树最大的上来作根：比左子树的都大，比右子树的都小（）
  • 右子树最小的上来作根：比右子树的都小，比左子树的都大（BST规则：左子树的全部都比右子树小）

参考代码

		bool Erase(const K& key) //删除 = 删除 + 链接
    {
        if(Empty()) return false;
        
        Node* cur = _root, *parent = nullptr;
        while(cur)
        {
            if(cur->_key < key)
            {
                parent = cur;
                cur = cur->_right;
            }
            else if(key < cur->_key)
            {
                parent = cur;
                cur = cur->_left;
            }
            else break;
        }
        
        if(cur == nullptr) return false;
        
        //走到这，cur即要删除的结点
        
        //要删的是根 / 要删的结点没有孩子都可以直接包含在这种条件内（复用代码）
        //2. 要删的结点有右孩子 ==> 将右子树托孤
        if(cur->_left == nullptr)
        {
            if(cur == _root)
            {
                _root = cur->_right;
            }
            else
            {
                if(cur == parent->_left)
                    parent->_left = cur->_right;
                else
                    parent->_right = cur->_right;
            }
            delete cur;
            return true;
        }
        //2. 要删的结点有左孩子 ==> 将左子树托孤
        else if(cur->_right == nullptr)
        {
            if(cur == _root)
            {
                _root = cur->_left;
            }
            else
            {
                if(cur == parent->_left)
                    parent->_left = cur->_left;
                else
                    parent->_right = cur->_left;
            }
            delete cur;
            return true;
        }
        //3. 要删的结点有左右孩子 ==> 替换法删除
        else
        {
            Node* minRight = cur->_right, *parent = cur;
            while(minRight->_left) //此分支内，minRight肯定不为空，可以直接解引用
            {
                parent = minRight;
                minRight = minRight->_left;
            }
            
						//覆盖掉要删的
            cur->_key = minRight->_key; 
            if(minRight == parent->_left)
                parent->_left = minRight->_right;
            else
                parent->_right = minRight->_right;
            //我已经去作老大了，这里得清理干净
            delete minRight;
            return true;
        }
        
        return false;
    }

InsertR

可以用递归实现一下，有个很妙的点。

我们插入和删除最大的难点就是链父，插入了，我的父是谁，删除了，我的父是谁？

在递归里，这样的场景我们可以用引用做参数——使得root是父亲的左/右孩子的引用。

		bool _InsertR(Node*& root, const K& key)
    {
        //最大的问题是链父，root作引用，是父结点的left/right
        if(root == nullptr)
        {
            root = new Node(key); //root是父结点的left/right的引用，这一步赋值相当于链父了
            return true;
        }
        
        if(root->_key < key)
            return _InsertR(root->_right, key);
        else if(key < root->_key)
            return _InsertR(root->_left, key);
        else
            return false;
    }

EraseR

递归里我们不能用替换法直接覆盖删了，但是思路一样，还是需要替换，不过绕了个弯子。

我们可以替换，让左子树最大/右子树最小，也可以说是最左/最右结点作根，原本的根换下去。

有两个点：

  1. 最左结点/最右结点必然有一侧是空的，那就可以直接删除或托孤
  2. 替换后不符合BST规则：整体来说不符合，但是从局部来说还符合

局部符合有什么用？
【C++进阶3-二叉搜索树】强，但没貌似还不够？

局部符合我们就可以在局部删！

	bool _EraseR(Node*& root, const K& key)
    {
        if(root == nullptr) return false;
        
        if(root->_key < key)
            return _EraseR(root->_right, key);
        else if(key < root->_key)
            return _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* minRight = root->_right;
                while(minRight->_left)
                    minRight = minRight->_left;
                //交换法：直接找key删，没法删，找替换节点交换，交换后可以删替换节点
                //(因为是最左/最右结点，一定有一侧是空的，也就可以托孤)
                swap(root->_key, minRight->_key);
                //交换后，root为根的子树不符合BST，无法递归，会找不到key
                //但是，因为找来的替换节点是右子树的最左节点，替换后右子树保持BST
                //就可以转换成到root->_right为根的子树找，而交换后，我们可以用托孤的方式删除minRight/maxLeft
                _EraseR(root->_right, key);
            }
            
            delete del;
            
            return true;
        }
    }

子函数

我们把这些需要传递私有成员的函数都作为子函数，或是弄一层函数重载——外面调用时是无法访问私有成员，所以无法传参。

*其实可以写一个GetRoot这种函数给外面提供，但是暴露底层了，不好

子函数：

		//外面可以直接调用
		void InOrder()
		{
			 _InOrder(_root); 
		}
		//封一层
		void _InOrder(Node* root)
    { ... }

函数重载：

		//给外面调用
		void InOrder()
		{
			 InOrder(_root); 
		}
		//给内部调用
		void _InOrder(Node* root)
    { ... }

还有一些拷贝构造和析构什么的，完善一下就好了。

*整体代码在文末

<Key, Value>搜索模型

KV模型的BST每个结点内存一个pair键值对，即用pair中的Key作为关键码，Key对应的Value是需要找到的值。

关于键值对，它存放了一个键和相应值的对，键用于在树中进行查找，而值则相当于查找键所得到的结果。

C++中的pair类模板是一种将两个值组合成一个单元的数据结构。这对于需要将一对值作为一个单元处理的情况非常有用。pair模板具有两个模板参数，一个表示第一个值的类型，另一个表示第二个值的类型。例如，pair<int, string>是一个由int和string类型组成的单元。我们此处用它来将key和value组合成一个单元，实现KV搜索模型。

实现

实现上我们从简，只玩儿精华，看到它和K模型的区别即可。

//KV查找模型：key value
namespace KV
{
template<class K, class V>
struct BSTreeNode
{
    BSTreeNode<K, V>* _left = nullptr;
    BSTreeNode<K, V>* _right = nullptr;
    K _key;
    V _val;
    
    BSTreeNode(const K& key, const V& val)
    :_left(nullptr),
    _right(nullptr),
    _key(key),
    _val(val)
    {}
};

template<class K, class V>
class BSTree
{
public:
    typedef BSTreeNode<K, V> Node;
    
    BSTree()
    :_root(nullptr)
    {}

    bool Insert(const K& key, const V& val)
    {
        if(_root == nullptr)
        {
            _root = new Node(key, val);
            return true;
        }
        
        Node* cur = _root, *parent = nullptr;
        while(cur)
        {
            if(cur->_key < key)
            {
                parent = cur;
                cur = cur->_right;
            }
            else if(key < cur->_key)
            {
                parent = cur;
                cur = cur->_left;
            }
            else
                return false;
        }
        
        cur = new Node(key, val);
        if(parent->_key < key)
            parent->_right = cur;
        else
            parent->_left = cur;
        
        return true;
    }
    
    void InOrder()
    {
        _InOrder(_root); //递归必须要传root：子函数内部传参，不想写GetRoot暴露root
        cout << endl;
    }
    
    Node* Find(const K& key)
    {
        Node* cur = _root;
        while(cur)
        {
            if(cur->_key == key)
                return cur;
            else if(cur->_key < key)
                cur = cur->_right;
            else
                cur = cur->_left;
        }
        return nullptr;
    }

    void _InOrder(Node* root)
    {
        if(root == nullptr) return;
        
        _InOrder(root->_left);
        
        cout << "["
                << root->_key
                << ", "
                << root->_val
            << "]" << endl;
        
        _InOrder(root->_right);
    }
private:
    
    Node* _root = nullptr;
};

BST性能分析

最优情况

是或接近完全二叉树，据key搜索一次需要比较logN次，时间复杂度为O(N)。

【C++进阶3-二叉搜索树】强，但没貌似还不够？
还是很不错的哦！

最差情况

是或接近单支树，据key搜索一次需要比较N次，时间复杂度为O(N)。

【C++进阶3-二叉搜索树】强，但没貌似还不够？
但是会退化，感觉不够强……

K模型BST的整体参考代码

整体参考代码

//Key搜索模型
template<class K>
struct BSTreeNode
{
    BSTreeNode(const K& key)
    :_left(nullptr),
    _right(nullptr),
    _key(key)
    {}
    
    BSTreeNode<K>* _left = nullptr;
    BSTreeNode<K>* _right = nullptr;
    K _key;
};

template<class K>
class BSTree
{
    typedef BSTreeNode<K> Node;
public:
    BSTree()
    :_root(nullptr)
    {}
    
    ~BSTree()
    {
        Destroy(_root);
    }
    
    BSTree(const BSTree<K>& t)
    {
        _root = Copy(t._root);
    }
    
    BSTree<K>& operator=(BSTree<K> t)
    {
        swap(_root, t._root);
        return *this;
    }
    
    //依照key值找插入位置（BST元素不重复）
    bool Insert(const K& key)
    {
        if(_root == nullptr)
        {
            _root = new Node(key);
            return true;
        }
        
        Node* cur = _root, *parent = nullptr;
        while(cur)
        {
            if(cur->_key < key)
            {
                parent = cur;
                cur = cur->_right;
            }
            else if(key < cur->_key)
            {
                parent = cur;
                cur = cur->_left;
            }
            else
                return false;
        }
        
        cur = new Node(key);
        if(parent->_key < key)
            parent->_right = cur;
        else
            parent->_left = cur;
        
        return true;
    }
    
    void InOrder()
    {
        _InOrder(_root); //递归必须要传root：子函数内部传参，不想写GetRoot暴露root
        cout << endl;
    }
    
    bool Find(const K& key)
    {
        Node* cur = _root;
        while(cur)
        {
            if(cur->_key == key)
                return true;
            else if(cur->_key < key)
                cur = cur->_right;
            else
                cur = cur->_left;
        }
        return false;
    }
    
    bool Empty() { return _root == nullptr;}
    
    bool Erase(const K& key) //删除 = 删除 + 链接
    {
        if(Empty()) return false;
        
        Node* cur = _root, *parent = nullptr;
        while(cur)
        {
            if(cur->_key < key)
            {
                parent = cur;
                cur = cur->_right;
            }
            else if(key < cur->_key)
            {
                parent = cur;
                cur = cur->_left;
            }
            else break;
        }
        
        if(cur == nullptr) return false;

        if(cur->_left == nullptr)
        {
            if(cur == _root)
            {
                _root = cur->_right;
            }
            else
            {
                if(cur == parent->_left)
                    parent->_left = cur->_right;
                else
                    parent->_right = cur->_right;
            }
            delete cur;
            return true;
        }
        else if(cur->_right == nullptr)
        {
            if(cur == _root)
            {
                _root = cur->_left;
            }
            else
            {
                if(cur == parent->_left)
                    parent->_left = cur->_left;
                else
                    parent->_right = cur->_left;
            }
            delete cur;
            return true;
        }
        else
        {
            Node* minRight = cur->_right, *parent = cur;
            while(minRight->_left) //此分支内，minRight肯定不为空
            {
                parent = minRight;
                minRight = minRight->_left;
            }
            
            cur->_key = minRight->_key; //左子树最大 / 右子树最小都符合
            if(minRight == parent->_left)
                parent->_left = minRight->_right;
            else
                parent->_right = minRight->_right;
            
            delete minRight;
            return true;
        }
        
        return false;
    }
    

    
    bool InsertR(const K& key)
    {
        return _InsertR(_root, key);
    }
    
    bool EraseR(const K& key)
    {
        return _EraseR(_root, key);
    }

    bool FindR(const K& key)
    {
        return _FindR(_root, key);
    }

private:
    void Destroy(Node* root)
    {
        if(root == nullptr) return;
        
        Destroy(root->_left);
        Destroy(root->_right);
        
        delete root;
    }
    
    Node* Copy(Node* root)
    {
        if(root == nullptr) return nullptr;
        
        Node* newRoot = new Node(root->_key);
        newRoot->_left = Copy(root->_left);
        newRoot->_right = Copy(root->_right);
        
        return newRoot;
    }
    
    void _InOrder(Node* root)
    {
        if(root == nullptr) return;
        
        _InOrder(root->_left);
        cout << root->_key << " ";
        _InOrder(root->_right);
    }
    
    bool _InsertR(Node*& root, const K& key)
    {
        //最大的问题是链父，root作引用，是父结点的left/right
        if(root == nullptr)
        {
            root = new Node(key); //root是父结点的left/right的引用，这一步赋值相当于链父了
            return true;
        }
        
        if(root->_key < key)
            return _InsertR(root->_right, key);
        else if(key < root->_key)
            return _InsertR(root->_left, key);
        else
            return false;
    }
    
    bool _EraseR(Node*& root, const K& key)
    {
        if(root == nullptr) return false;
        
        if(root->_key < key)
            return _EraseR(root->_right, key);
        else if(key < root->_key)
            return _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* minRight = root->_right;
                while(minRight->_left)
                    minRight = minRight->_left;
                //交换法：直接找key删，没法删，找替换节点交换，交换后可以删替换节点
                //(因为是最左/最右结点，一定有一侧是空的，也就可以托孤)
                swap(root->_key, minRight->_key);
                _EraseR(root->_right, key);
            }
            
            delete del;
            
            return true;
        }
    }
    
    bool _FindR(Node*& root, const K& key)
    {
        if(root == nullptr) return false;
        
        if(root->_key < key)
            return _FindR(root->_right, key);
        else if(key < root->_key)
            return _FindR(root->_left, key);
        else
            return true;
    }
    
    
    Node* _root = nullptr;
};

今天的分享就到这里了，感谢您能看到这里。

这里是培根的blog，期待与你共同进步！文章来源地址https://www.toymoban.com/news/detail-446975.html

到了这里，关于【C++进阶3-二叉搜索树】强，但没貌似还不够？的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处： 如若内容造成侵权/违法违规/事实不符，请点击违法举报进行投诉反馈，一经查实，立即删除！

分享到：
领支付宝红包 赞助服务器费用

相关文章

  • 二叉树进阶(搜索二叉树)

    二叉树进阶(搜索二叉树)

    目录 引言  1.二叉搜索树的模拟实现 1.1  链式二叉树的定义 1.2 二叉搜索树的模拟实现  1.2.1 二叉搜索树的结点类 1.2.2 二叉搜索树类的构造与中序遍历实现 1.2.3 增 1.非递归实现 2.非递归实现 1.2.4 查 1.非递归实现 2.递归实现  1.2.5 删 1.非递归实现 (1)情况分析 (2)解决方案  (

    2024年02月15日
    浏览(286)
  • 数据结构_进阶（1）：搜索二叉树

    数据结构_进阶（1）：搜索二叉树

    建议再看这节之前能对C++有一定了解 二叉树在前面C的数据结构阶段时有出过，现在我们对二叉树来学习一些更复杂的类型，也为之后C++学习的 map 和 set 做铺垫 1. map和set特性需要先铺垫二叉搜索树 ，而二叉搜索树也是一种树形结构 2. 二叉搜索树的特性了解，有助于更好的理

    2024年02月16日
    浏览(46)
  • 多种方法解决leetcode经典题目-LCR 155. 将二叉搜索树转化为排序的双向链表， 同时弄透引用变更带来的bug

    多种方法解决leetcode经典题目-LCR 155. 将二叉搜索树转化为排序的双向链表， 同时弄透引用变更带来的bug

    这段代码实际上是一个常见的算法题目的解法，目标是将一个二叉搜索树转换为一个排序的双向链表。整个过程是通过中序遍历来实现的，遍历过程中修改节点的左右指针来构建双向链表。代码中使用了一个额外的节点 dummy 来帮助构建双向链表，并使用 pre 节点来保存前一个

    2024年02月06日
    浏览(44)

  • 模型训练遇到数据量太大而导致内存不够问题？今天教你一招

    在比赛和工作中，我们经常会遇到数据量太大而导致内存不够的问题。这里可以细分为两种情况： 情况1：数据太大，无法加载到内存； 情况2：加载数据但训练时内存不够； 针对情况1可以考虑使用 Spark 或者 Dask 来逐步完成计算。对于情况2，则需要考虑从模型的角度入手。

    2024年02月04日
    浏览(43)
  • 今天给大家带来Python炫酷爱心代码

    今天给大家带来Python炫酷爱心代码

    前言： 这个是小编之前朋友一直要小编去做的，不过之前技术不够所以一直拖欠今天也完成之前的约定吧！ 至于他是谁，我就不多说了直接上代码 如果有需要的话，可以联系小编噢！

    2024年02月05日
    浏览(47)
  • 数据结构之进阶二叉树（二叉搜索树和AVL树、红黑树的实现）超详细解析，附实操图和搜索二叉树的实现过程图

    数据结构之进阶二叉树（二叉搜索树和AVL树、红黑树的实现）超详细解析，附实操图和搜索二叉树的实现过程图

    绪论​ “生命有如铁砧，愈被敲打，愈能发出火花。——伽利略”；本章主要是数据结构 二叉树的进阶知识，若之前没学过二叉树建议看看这篇文章一篇掌握二叉树，本章的知识从浅到深的 对搜索二叉树的使用进行了介绍和对其底层逻辑的实现进行了讲解 ，希望能对你有所

    2024年02月04日
    浏览(46)
  • 搜索二叉树【C++】

    搜索二叉树【C++】

    二叉搜索树又称为二叉排序树，它或者是一棵空树，或者是具有以下性质的二叉树： 若它的左子树不为空， 则左子树上所有结点的值都小于根结点的值。 若它的右子树不为空， 则右子树上所有结点的值都大于根结点的值。 它的左右子树也分别是二叉搜索树。 核心思路：

    2024年02月07日
    浏览(39)
  • 【C++】二叉搜索树

    【C++】二叉搜索树

    正文开始前给大家推荐个网站，前些天发现了一个巨牛的 人工智能 学习网站， 通俗易懂，风趣幽默 ，忍不住分享一下给大家。点击跳转到网站。 二叉搜索树的概念 二叉搜索树又称二叉排序树，它或者是一棵空树，或者是具有以下性质的二叉树: 若它的左子树不为空，则左

    2024年01月19日
    浏览(30)

  • 【C++】搜索二叉树

    搜索二叉树是一种二叉树，其中每个节点的左子节点的值都小于该节点的值，而右子节点的值都大于该节点的值。这种性质使得在BST中进行搜索、插入和删除操作的平均时间复杂度为 O(log n) ，其中 n 是树中节点的数量。 例子： 在定义和表示二叉搜索树（BST）的节点结构时，

    2024年02月12日
    浏览(39)
  • 二叉搜索树（C++）

    二叉搜索树（C++）

    在使用C语言写数据结构阶段时，对二叉树进行了讲解。本节内容是对二叉树的深入探索，也是二叉树部分的收尾 二叉搜索树也称二叉排序树（BST，Binary Search Tree）： 空树 非空树（要具有以下性质） 若它的左子树不为空，则左子树上所有节点的值都小于根节点的值 若它的右

    2024年02月11日
    浏览(33)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包，优惠每天领

二维码1

领取红包

二维码2

领红包