【C++】二叉搜索树的原理及实现

这篇具有很好参考价值的文章主要介绍了【C++】二叉搜索树的原理及实现。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

简介

  二叉搜索树(Binary Search Tree,BST)是一种常用的数据结构,本文将介绍二叉搜索树的原理与特性,并给出C++代码实现,最后对其性能进行详细的分析。 

【C++】二叉搜索树的原理及实现,C++,数据结构,c++ 

文章目录

简介

一、二叉搜索树的概念

二、二叉搜索树的操作及实现

2、1 二叉搜索树的插入

2、1、1 插入的原理

2、1、2 插入的代码实现

2、2 二叉搜索树的查找

2、2、1 查找的原理

2、2、2 查找的代码实现

2、3 二叉搜索树的删除

2、3、1 删除的原理

2、3、2 删除的代码实现

2、4 二叉搜索树的中序遍历

2、5 递归实现二叉树的操作

三、二叉搜索树的性能分析


🙋‍♂️ 作者:@Ggggggtm 🙋‍♂️

👀 专栏:C++  👀

💥 标题:二叉搜索树💥

 ❣️ 寄语:与其忙着诉苦,不如低头赶路,奋路前行,终将遇到一番好风景 ❣️ 

【C++】二叉搜索树的原理及实现,C++,数据结构,c++

 

一、二叉搜索树的概念

  二叉搜索树又称二叉排序树,二叉搜索树是一种二叉树,其中每个节点的值大于其左子树中的任何节点,并且小于其右子树中的任何节点。这个特性使得二叉搜索树具有高效的查找、插入和删除操作。下图即为二叉搜索树:

【C++】二叉搜索树的原理及实现,C++,数据结构,c++ 

二、二叉搜索树的操作及实现

  由于二叉搜索树的特性,使得二叉搜索树具有高效的查找、插入和删除操作。在我们分析各个操作的效率和实现原理之前,我们先把二叉树的大体结构列出,代码如下:

template<class K>
struct BSTreeNode
{
	BSTreeNode<K>* _left;
	BSTreeNode<K>* _right;
	K _key;

	BSTreeNode(const K& key)
		:_left(nullptr)
		,_right(nullptr)
		,_key(key)
	{}
};

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

2、1 二叉搜索树的插入

2、1、1 插入的原理

  插入一个新的值时,我们需要遵守二叉搜索树的特性。首先,我们从根节点开始找到合适的插入位置。具体操作是,将新值与当前节点的值比较,若新值小于当前节点的值,则往左子树方向找到合适的叶子节点进行插入;反之,若新值大于当前节点的值,则往右子树方向找到合适的叶子节点进行插入

  合适的叶子节点指的是一直往下查找,直到该位置为空(nullptr)时,此时新值就应该插入该位置。即使我们找到了合适的位置,如果不知道该位置的父节点的话,似乎并不能连接到该树中。所以在查找合适位置的同时,还需要维护一个父节点。但是我们需要注意,二叉搜索树中没有重复的值。如果插入重复的值,那么就会插入失败

  同时,我们再插入前,要判断该树是否为空。否则就会出现意想不到的bug。

2、1、2 插入的代码实现

  我们看代码实现:

    bool Insert(const K& key)
	{
		if (_root == nullptr)
		{
			_root = new Node(key);
			return true;
		}

		Node* parent = nullptr;
		Node* cur = _root;
		while (cur)
		{
			if (cur->_key < key)
			{
				parent = cur;
				cur = cur->_right;
			}
			else if(cur->_key > 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;
	}

2、2 二叉搜索树的查找

2、2、1 查找的原理

  其实在上述的插入中,我们不就进行了查找吗?!为了查找一个特定的值,我们从根节点开始向下遍历二叉树,根据当前节点的值与目标值的大小关系来选择往左子树或者右子树进行遍历。如果找到目标值,则返回成功;否则,如果遍历到叶子节点还未找到目标值,则返回失败。

2、2、2 查找的代码实现

	bool Find(const K& key)
	{
		Node* cur = _root;
		while (cur)
		{
			if (cur->_key < key)
			{
				cur = cur->_right;
			}
			else if (cur->_key > key)
			{
				cur = cur->_left;
			}
			else
			{
				return true;
			}
		}

		return false;
	}

2、3 二叉搜索树的删除

2、3、1 删除的原理

  删除操作是相对复杂的,因为我们需要处理不同的情况。具体步骤如下:

  1. 如果要删除的节点没有子节点,直接删除即可。【C++】二叉搜索树的原理及实现,C++,数据结构,c++
  2. 如果要删除的节点只有一个子节点,将子节点替换为要删除的节点即可。【C++】二叉搜索树的原理及实现,C++,数据结构,c++
  3. 如果要删除的节点有两个子节点,需要用其右子树中最小的节点替换要删除的节点,并且删除右子树中最小的节点。【C++】二叉搜索树的原理及实现,C++,数据结构,c++

  对上述的情况在进行分析和总结,一共可分为如下情况:

  1. 要删除的结点只有左孩子结点 。删除该结点且使被删除节点的双亲结点指向被删除节点的左孩子结点--直接删除。
  2. 要删除的结点只有右孩子结点 。删除该结点且使被删除节点的双亲结点指向被删除结点的右孩子结点--直接删除。
  3. 要删除的结点有左、右孩子结点。在它的右子树中寻找中序下的第一个结点(关键码最小),用它的值填补到被删除节点中,再来处理该结点的删除问题--替换法删除

  为什么是上述的三种情况呢?我们详细分析一下是为什么。

  假如我们要删除的节点没有子节点,我们可以把这种情况看成要删除的结点只有左孩子结点或者只有右孩子结点。把另一个存在的孩子看成空(nullptr)。这样删除后,直接可让其父节点指向空(nullptr),而不是野指针。

  要删除的结点只有左孩子结点或者要删除的结点只有右孩子结点是两种不同的情况。因为他们的操作是不同的。

  要删除的结点有左、右孩子结点这种情况较为复杂。首先我们应该找到能够填充该位置的节点。根据二叉搜索树的特性每个节点的值大于其左子树中的任何节点,并且小于其右子树中的任何节点,我们找到的值应该也满足此特点。有两个节点的只满足该情况:该节点左子树的最大值、该节点右子树的最小值。本篇文章讲述的是左子树的最大值。找左子树的最大值,就是该子树最右边的节点。找到后交值换再删除。

  要删除的结点有左、右孩子结点这种情况,在找左子树的最大值时也应该维护一个父节点。为什么呢?因为我们找到左子树的最大值时,与要删除的节点的值交换后,要删除该节点(交换前的左子树最大值的节点)。此时该节点的右节点一定为空(nullptr),只需要关心左节点就行。

2、3、2 删除的代码实现

	bool Erase(const K& key)
	{
		Node* parent = nullptr;
		Node* cur = _root;

		while (cur)
		{
			if (cur->_key < key)
			{
				parent = cur;
				cur = cur->_right;
			}
			else if (cur->_key > key)
			{
				parent = cur;
				cur = cur->_left;
			}
			else // 找到了
			{
				 // 左为空
				if (cur->_left == nullptr)
				{
					if (cur == _root)
					{
						_root = cur->_right;
					}
					else
					{
						if (parent->_right == cur)
						{
							parent->_right = cur->_right;
						}
						else
						{
							parent->_left = cur->_right;
						}
					}
				}// 右为空
				else if (cur->_right == nullptr)
				{
					if (cur == _root)
					{
						_root = cur->_left;
					}
					else
					{
						if (parent->_right == cur)
						{
							parent->_right = cur->_left;
						}
						else
						{
							parent->_left = cur->_left;
						}
					}					
				} // 左右都不为空 
				else
				{
					// 找替代节点
					Node* parent = cur;
					Node* leftMax = cur->_left;
					while (leftMax->_right)
					{
						parent = leftMax;
						leftMax = leftMax->_right;
					}

					swap(cur->_key, leftMax->_key);

					if (parent->_left == leftMax)
					{
						parent->_left = leftMax->_left;
					}
					else
					{
						parent->_right = leftMax->_left;
					}

					cur = leftMax;
				}

				delete cur;
				return true;
			}
		}

		return false;
	}

2、4 二叉搜索树的中序遍历

  二叉搜索树又称二叉排序树,为什么又名二叉排序树呢?二叉搜索树的中序遍历的结果就是一个有序的结果。代码如下:

public:
    Inorder()
    {
        _Inorder(_root);
    }
private:   
    void _Inorder(Node* root)                                                                                                                                
    {    
        if(root==nullptr)    
        {    
            return ;    
        }    
    
        _Inorder(root->left);    
        cout<<root->_key<<" ";    
        _Inorder(root->right);    
    } 

2、5 递归实现二叉树的操作

  我们上述讲解的是非递归形式的二叉搜索树的各个操作。当我们了解非递归形式的二叉搜索树的各个操作后,我们下面给出递归形式的二叉搜索树的各个操作的代码,思路就不在讲解:

public:
    bool eraseR(const K& key)
    {
        return _eraseR(_root,key);
    }
                                                                                                                                                             
    bool insertR(const K& key)
    {
        return _insertR(_root,key);
    }

    bool findR(const K& key)
    {
        return _findR(_root,key);
    }
private:
    bool _findR(Node* root,const K& key)
    {
        if(root==nullptr)
        {                                                                                                                                                    
            return false;
        }

        
        if(root->_key>key)
        {
            _findR(root->left,key);
        }
        else if(root->_key<key)
        {
            _findR(root->right,key);
        }
        else
        {
            return true;
        }
    }

    bool _eraseR(Node*& root,const K& key)
    {
        if(root==nullptr)
        {
            return false;
        }                                                                                                                                                    

        if(root->_key>key)
        {
            _eraseR(root->left,key);
        }
        else if(root->_key<key)
        {
            _eraseR(root->right,key);
        }
        else
        {
            Node* del=root;
            if(root->left==nullptr)
            {
                root=root->right;
            }
            else if(root->right==nullptr)
            {
                root=root->left;
            }
            else
            {
                Node* min=root->right;
                while(min->left)
                {
                    min=min->left;
                }

                swap(root->_key,min->_key);
                                                                                                                                                             
                return _eraseR(root->right,key);
            }

            delete del;
            return true;
        }
                
    }

    bool _insertR(Node*& root,const K& key)
    {
        if(root==nullptr)
        {
            root=new Node(key);
            return true;
        }

        if(root->_key>key)
        {
            _insertR(root->left,key);
        }                                                                                                                                                    
        else if(root->_key<key)
        {
            _insertR(root->right,key);
        }
        else
        {
            return false;
        }
    }

三、二叉搜索树的性能分析

  插入和删除操作都必须先查找,查找效率代表了二叉搜索树中各个操作的性能。对有n个结点的二叉搜索树,若每个元素查找的概率相等,则二叉搜索树平均查找长度是结点在二叉搜索树的深度的函数,即结点越深,则比较次数越多。 但对于同一个关键码集合,如果各关键码插入的次序不同,可能得到不同结构的二叉搜索树:

【C++】二叉搜索树的原理及实现,C++,数据结构,c++

  通过上述我们也发现,二叉搜索树的性能主要取决于树的平衡度。最理想的情况下,树是完全平衡的,即左子树节点数目和右子树节点数目相差不超过1。在这种情况下,查找、插入和删除操作的平均时间复杂度为 O(log n)。但是,最坏情况下,树可能变得非平衡,导致这些操作的时间复杂度退化为O(n),其中n是树中节点的总数。

  为了避免二叉搜索树在使用过程中出现不平衡的情况,可以使用自平衡的二叉搜索树,如红黑树或AVL树。这些树通过旋转、调整节点颜色等策略来保持树的平衡度,从而提高了整体性能。

  总结起来,二叉搜索树在C++编程语言中的实现非常灵活且易于理解。但需要注意的是,对于大型数据集合,建议使用自平衡的二叉搜索树,以确保操作的效率和性能。文章来源地址https://www.toymoban.com/news/detail-620277.html

到了这里,关于【C++】二叉搜索树的原理及实现的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

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

领支付宝红包 赞助服务器费用

相关文章

  • 【数据结构】搜索二叉树(C++实现)

    ​ ​📝个人主页:@Sherry的成长之路 🏠学习社区:Sherry的成长之路(个人社区) 📖专栏链接:数据结构 🎯 长路漫漫浩浩,万事皆有期待 上一篇博客:【C++】C++模板进阶 —— 非类型模板参数、模板的特化以及模板的分离编译 二叉搜索树又称二叉排序树,它或者是一棵空

    2024年02月07日
    浏览(52)
  • 【数据结构进阶】之搜索二叉树(C++实现)

    📃 博客主页: 小镇敲码人 💞 热门专栏:数据结构与算法 🚀 欢迎关注:👍点赞 👂🏽留言 😍收藏 🌏 任尔江湖满血骨,我自踏雪寻梅香。 万千浮云遮碧月,独傲天下百坚强。 男儿应有龙腾志,盖世一意转洪荒。 莫使此生无痕度,终归人间一捧黄。🍎🍎🍎 ❤️ 什么

    2024年04月08日
    浏览(48)
  • 【数据结构】—搜索二叉树(C++实现,超详细!)

                                                           🎬 慕斯主页 : 修仙—别有洞天                                                        ♈️ 今日夜电波 :消えてしまいそうです—真夜中                                              

    2024年02月05日
    浏览(40)
  • 数据结构——二叉搜索树(附带C++实现版本)

    二叉搜索树又叫二叉排序树 ,二叉搜索树也是一种树形结构。 它是一课满足以下性质的搜索树: 若它的左子树不为空,则左子树上所有节点的值都小于根节点的值 若它的右子树不为空,则右子树上所有节点的值都大于根节点的值 它的左右子树也分别是二叉搜索树 注意,二

    2024年02月12日
    浏览(38)
  • C++------利用C++实现二叉搜索树【数据结构】

    什么是二叉搜索树,二叉搜索树就是指左孩子永远比根小右孩子永远比根大。这个规则适用于所有的子树。 上面的就是一棵二叉搜索树,我们还可以发现这棵树走一个中序遍历序列是有序的,所以它又被称为二叉排序树。 二叉搜索树的操作主要分为以下几点,查找, 插入,

    2024年02月11日
    浏览(41)
  • [数据结构进阶 C++] 二叉搜索树(BinarySearchTree)的模拟实现

    二叉搜索树又称二叉排序树,它或者是一棵空树,或者是具有以下性质的二叉树: 若它的左子树不为空,则左子树上所有节点的值都小于根节点的值 若它的右子树不为空,则右子树上所有节点的值都大于根节点的值 它的左右子树也分别为二叉搜索树 我们先给出两个示例: 此

    2024年02月04日
    浏览(42)
  • 数据结构与算法—二叉树数组表示(ArrayBinTree)、二叉树的链式表示(LinkedBinTree)的基于C++模板代码实现

    1、二叉树的顺序表示:ArrayBinTree.h 二叉树的顺序表示法操作方便,但缺点是容易造成存储空间浪费。 这是一个用数组实现的二叉树类模板。它可以创建一个空树,也可以在指定的位置插入结点并设置结点的值,可以删除子树,并支持逐层遍历。使用该类时,需要提供一个元

    2024年02月06日
    浏览(44)
  • 【C++】二叉搜索树的原理及实现

      二叉搜索树(Binary Search Tree,BST)是一种常用的数据结构,本文将介绍二叉搜索树的原理与特性,并给出C++代码实现,最后对其性能进行详细的分析。    文章目录 简介 一、二叉搜索树的概念 二、二叉搜索树的操作及实现 2、1 二叉搜索树的插入 2、1、1 插入的原理 2、1、2

    2024年02月14日
    浏览(53)
  • 数据结构——常见二叉树的分类(完全二叉树、满二叉树、平衡二叉树、二叉搜索树、红黑树)

    专业术语 中文 描述 Root 根节点 一棵树的顶点 Child 孩子结点 一个结点含有的子树的根节点称为该结点的子节点 Leaf 叶子结点 没有孩子的节点 Degree 度 一个节点包含子树的数量 Edge 边 一个节点与另外一个节点的连接 Depth 深度 根节点到这个节点经过边的数量 Height 节点高度 从

    2024年02月03日
    浏览(44)
  • 【C++】AVL(平衡二叉搜索树)树的原理及实现

    文章目录 一、引言 二、AVL树的概念 三、AVL树的插入 3、1 AVL树的简单插入 3、2 旋转分类  3、2、1 新节点插入较高右子树的右侧:左单旋 3、2、2 新节点插入较高左子树的左侧:右单旋 3、2、3 新节点插入较高左子树的右侧:左右双旋(先左后右) 3、2、4 新节点插入较高右

    2024年02月13日
    浏览(49)

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

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

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

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

二维码1

领取红包

二维码2

领红包