【C++】二叉搜索树Binary Search Tree

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

二叉搜索树的概念

二叉搜索树又被称为二叉排序树,顾名思义,当我们使用中序遍历时,会得到一个有序的序列。二叉搜索树有如下的性质:
1.若它的左子树不为空,则左子树上每个节点的值都小于根节点的值。
2.若它的右子树不为空,则右子树上每个节点的值都大于根节点的值。
3.左右子树也是二叉搜索树
【C++】二叉搜索树Binary Search Tree
如图所示,就是一颗二叉搜索树。它的中序遍历结果为:1,3,4,6,7,8,10,13,14

二叉搜索树的操作

二叉搜索树的操作有:查找,插入,删除。
查找
1.从根开始比较,查找,比根大则往右边走查找,比根小则往左边走查找
2.最多查找高度次,走到到空,还没找到,这个值不存在

插入
分为树是否为空:
若为空树:树为空,则直接新增节点,赋值给root指针
若不为空树:按二叉搜索树性质查找插入位置,插入新节点

删除

首先要查找要删除的节点是否在二叉树中,若不存在,则直接返回,若存在,分情况进行删除。
a.要删除的节点没有孩子
b.要删除的节点只有左孩子
c.要删除的节点只有右孩子
d.要删除的节点左右孩子都有

实际上,对于删除操作来说,可以要删除没有孩子节点或删除只有一个孩子节点的情况,操作是相同的,都是直接将要删除的节点的双亲节点的指针指向当前删除节点的孩子节点。(当前节点如果没有孩子节点,实际上当前节点的孩子节点是nullptr,当前节点有孩子节点,实际上也是将双亲指向当前的孩子节点)

因此,可以将四种情况中a和b情况进行合并,那么就只有三种情况了。
a.要删除的节点没有孩子或者只有右孩子-------将双亲节点指向当前节点的右孩子,然后直接删除当前节点
b.要删除的节点只有左孩子-------将双亲节点指向当前节点的左孩子,然后直接删除当前节点
c.要删除的节点左右孩子都有------在它的右子树下找到最小的一个节点(右子树的最左侧),用它的值填补到被删除节点中,再处理该节点的删除问题

二叉搜索树的实现

查找

1.从根开始比较,查找,比根大则往右边走查找,比根小则往左边走查找
2.最多查找高度次,走到到空,还没找到,这个值不存在

Node* Find(const T& data)
	{
		Node* cur = _root;
		while (cur)
		{
			if (data > cur->_data)
			{
				cur = cur->_right;
			}
			else if (data < cur->_data)
			{
				cur = cur->_left;
			}
			else
				return cur;
		}
		return nullptr;
	}

插入

分为树是否为空:
若为空树:树为空,则直接新增节点,赋值给root指针
若不为空树:按二叉搜索树性质查找插入位置,插入新节点

bool Insert(const T& data)
	{
		//空树,插入成功后就是根节点
		if (_root == nullptr)
		{
			_root = new Node(data);
			return true;
		}
		//非空就需要找到待插入的位置。
		Node* cur = _root;
		Node* parent = nullptr;
		while (cur)
		{
			parent = cur;
			if (cur->_data > data)
				cur = cur->_left;
			else if (cur->_data < data)
				cur = cur->_right;
			else
				return false;
		} 
		cur = new Node(data);
		if (cur->_data > parent->_data)
		{
			parent->_right = cur;
		}
		else
			parent->_left = cur;
		return true;
	}

删除

首先要查找要删除的节点是否在二叉树中,若不存在,则直接返回,若存在,分情况进行删除。
a.要删除的节点没有孩子
b.要删除的节点只有左孩子
c.要删除的节点只有右孩子
d.要删除的节点左右孩子都有

实际上,对于删除操作来说,可以要删除没有孩子节点或删除只有一个孩子节点的情况,操作是相同的,都是直接将要删除的节点的双亲节点的指针指向当前删除节点的孩子节点。(当前节点如果没有孩子节点,实际上当前节点的孩子节点是nullptr,当前节点有孩子节点,实际上也是将双亲指向当前的孩子节点)

因此,可以将四种情况中a和b情况进行合并,那么就只有三种情况了。
a.要删除的节点没有孩子或者只有右孩子-------将双亲节点指向当前节点的右孩子,然后直接删除当前节点
b.要删除的节点只有左孩子-------将双亲节点指向当前节点的左孩子,然后直接删除当前节点
c.要删除的节点左右孩子都有------在它的右子树下找到最小的一个节点(右子树的最左侧),用它的值填补到被删除节点中,再处理该节点的删除问题

最终我们可以将情况分为上述的a b c三种情况,

对于情况a来说,其内部又可以分为两大类:要删除的是根节点要删除的不是根节点
对于情况b来说,其内部又可以分为两大类:要删除的是根节点要删除的不是根节点
对于情况c来说,我们是通过步骤:1.在待删除节点的右子树中找到最小的节点(替代节点) 2.将替代节点的值赋给待删除的节点 3.删除找到的替代节点.

而在a情况中,针对要删除的节点不是根节点,我们需要判断待删除的节点是其双亲节点的左孩子还是右孩子。因为到时候需要让双亲节点指向待删除节点的左孩子
而在b情况中,针对要删除的节点不是根节点,我们需要判断待删除的节点是其双亲节点的左孩子还是右孩子。因为到时候需要让双亲节点指向待删除节点的右孩子
而在c情况中,我们需要判断替代节点的是其双亲的左孩子还是右孩子。因为到时候需要让双亲节点指向待删除节点的右孩子

下图是上述分类情况的图示。

只有右孩子的场景
【C++】二叉搜索树Binary Search Tree
只有左孩子的场景
【C++】二叉搜索树Binary Search Tree

左右孩子均存在的场景
【C++】二叉搜索树Binary Search Tree
这个是对于删除操作需要分的情况:
【C++】二叉搜索树Binary Search Tree

针对上述分的情况,代码的实现

bool Erase(const T& data)
	{
		//找待删除节点的位置,并且保存双亲
		Node* cur = _root;
		Node* parent = nullptr;
		while (cur)
		{
			parent = cur ;
			if (data == cur->_data)
				break;
			else if (data < cur->_data)
			{
				parent = cur;
				cur = cur->_left;
			}
			else
			{
				parent = cur;
				cur = cur->_right;
			}
		}
		//值在BST中不存在值为data的节点
		if (cur == nullptr)
			return false;

		// 只有右孩子或者没有孩子
		if (cur->_left == nullptr)
		{
			// 1.双亲为空,说明为根节点
			if (parent == nullptr)
				_root = cur->_right;

			// 2.双亲非空,说明不是根节点
			else
			{
				//可能是双亲的左孩子
				if (cur = parent->_left)
					parent->_left = cur->_right;
				//也可能是双亲的右孩子
				else
					parent->_right = cur->_right;
			}
			delete cur;
		}
		//只有左孩子
		else if (cur->_right == nullptr)
		{
			// 1.双亲为空,是根节点
			if (parent == nullptr)
				_root = cur->_left;
			// 2.双亲不为空,不是根节点
			else
			{
				if (cur == parent->_left)
					parent->_left = cur->_left;
				else
					parent->_right = cur->_left;
			}
			delete cur;
		}

		//左右孩子均存在,
		//先在其右子树中找到最左边的节点,
		//将替代节点中的值赋给要删除的节点,
		//删除替代节点
		else
		{
			Node* tmp = cur->_right;
			parent = cur;
			//在cur的右子树中找替代节点
			while (tmp->_left)
			{
				parent = tmp;
				tmp = tmp->_left;
			}
			//用替代节点中的值替换待删除的节点
			cur->_data = tmp->_data;

			//删除替代节点
			if (parent->_left == tmp)
				parent->_left = tmp->_right;
			else
				parent->_right = tmp->_right;
			delete tmp;
		}
		return true;

二叉搜索树的应用

k模型和kv模型

k模型是指:只有key作为关键码,结构中只需要存储Key即可,关键码即为需要搜索到的值。
例如:要查找一个单词是否拼写正确,我们可以先将所有的单词作为key构建一个二叉搜索树。在这个二叉搜索树中去查找是否有我们想找到的单词,若可以找到,则证明拼写正确,若找不到,则证明拼写错误。

kv模型是指:每一个关键码key,都有与之对应的值Value,即<Key, Value>的键值对。
例如:英汉词典是一个典型的kv模型,通过英文可以快速找到与其对应的中文。英文和中文就构成了一对键值对

二叉搜索树的性能分析

因为对应二叉搜索树来说,插入和删除操作都要先进行查找,查找的效率高低直接决定了各个操作的性能。

对有n个结点的二叉搜索树,若每个元素查找的概率相等,则二叉搜索树平均查找长度是结点在二叉搜索树的深度的函数,即结点越深,则比较次数越多。

但对于同一个关键码集合,如果各关键码插入的次序不同,可能得到不同结构的二叉搜索树:
【C++】二叉搜索树Binary Search Tree
如果关键码集合,插入的次序接近于无序,则会构造出作图这样的二叉搜索树,而插入的次序如果是有序的,则会构造出右图这样的单支树。

而不同的二叉搜索树,其比较的平均次数是不同的。
最优情况下:二叉搜索树为完全二叉树(或者接近完全二叉树),其平均比较次数为:O(logN)(以2为底)
最差情况下,二叉搜索树退化为单支树(或者类似单支),其平均比较次数为:O(N)(以2为底)

正是由于插入的次序不同,会导致构造的二叉搜索树的结构不同,而退化成单枝时,二叉搜索树就失去了优势,因此如果需要按照任意次序插入时,都能让二叉搜索树的性能达到最优,就需要用到AVL树和红黑树了。文章来源地址https://www.toymoban.com/news/detail-465764.html

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

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

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

相关文章

  • 数据结构第四天: Complete Binary Search Tree 【搜索二叉树,完全二叉树】

     这道题需要的操作时排序并且需要遍历,最重要的一点它是个完全二叉树,所以数组是最适合的 这道题我的思路来自于浙江大学课件7.0.2完全二叉树 这道题说白就是将输入的样例构造成一个完全搜索二叉树。因为完全线索二叉树的 根节点一定是是一个处于左右子树中间的那

    2024年02月06日
    浏览(55)
  • 数据结构英文习题解析-第五章 二叉搜索树Binary Search Tree

    前言:最近快到FDS考试了,po重刷了一下学校的题目,自己整理了一些解析orz 因为po在自己找解析和学习的过程中非常痛苦,所以在此共享一下我的题目和自己写的解题思路,欢迎各位指出错误~全章节预计会陆续更新,可在专栏查看~ HW5 1.In a binary search tree, the keys on the same

    2024年04月09日
    浏览(48)
  • 二叉查找树(binary search tree)(难度7)

    C++数据结构与算法实现(目录) 答案在此:二叉查找树(binary search tree)(答案) 写在前面 部分内容参《算法导论》 基本接口实现 1 删除 删除值为value的第一个节点 删除叶子节点1 删除叶子节点1 (3)删除叶子节点1 删除有两个孩子的节点z 分成下面几个步骤进行: 1 找到

    2024年02月10日
    浏览(44)
  • 浙大数据结构第四周之04-树6 Complete Binary Search Tree

    A Binary Search Tree (BST) is recursively defined as a binary tree which has the following properties: The left subtree of a node contains only nodes with keys less than the node\\\'s key. The right subtree of a node contains only nodes with keys greater than or equal to the node\\\'s key. Both the left and right subtrees must also be binary search trees. A Comple

    2024年02月16日
    浏览(49)
  • 「二分搜索Binary Search」

    二分搜索其实也是双指针,左右指针。 题解 直接二分搜索解决。 Code 但是这个数有缺陷,假如有重复的数,例如[1,2,2,2,3],想要找左边界的2,应该返回索引为1,;或者右边界的2,返回索引3,但是发现找不了,只会给你返回中间的2,返回索引2,改进在下边。 结果 Code 注意此

    2024年02月15日
    浏览(37)
  • 二叉树(binary tree)

    二叉树(Binary Tree)是一种常见的树状数据结构,它由一组节点组成,每个节点最多有两个子节点,分别称为左子节点和右子节点。二叉树具有以下特点: 每个节点最多有两个子节点,分别称为左子节点和右子节点。 左子树和右子树也是二叉树,它们的结构与父节点类似。

    2024年02月09日
    浏览(42)
  • 平衡二叉树(Balanced Binary Tree)

    平衡二叉树是一种特殊的二叉搜索树,它具有以下特点: 每个节点的左子树和右子树的高度差不超过1。 所有的子树也都是平衡二叉树。 通过保持平衡性,平衡二叉树可以在最坏情况下仍然具有较好的性能,保证查找、插入和删除操作的时间复杂度为O(log n)。 平衡二叉树的常

    2024年02月09日
    浏览(36)
  • 数据结构与算法 | 二叉树(Binary Tree)

    二叉树(Binary Tree)是一种树形数据结构,由节点构成,每个节点最多有两个子节点:一个左子节点和一个右子节点。 \\\"二叉树\\\"(Binary Tree)这个名称的由来是因为二叉树的每个节点最多有两个子节点,一个左子节点和一个右子节点。其中,“二叉”指的是两个,因此“二叉树

    2024年02月08日
    浏览(41)
  • Java学数据结构(2)——树Tree & 二叉树binary tree & 二叉查找树 & AVL树 & 树的遍历

    1.树的出现:解决链表线性访问时间太慢,树的时间复杂度O(logN); 2.二叉树的定义,最多两个儿子节点; 3.二叉查找树,左小,右大,中居中;remove方法,两种,只有一个儿子节点,有两个儿子节点; 4.AVL树,在二叉查找树基础上加平衡条件,旋转方法,单旋转,双旋转;

    2024年02月10日
    浏览(49)
  • Java 【数据结构】 二叉树(Binary_Tree)【神装】

        登神长阶  第五神装 二叉树 Binary-Tree 目录  🎷一.树形结构 🪗1.概念 🎸2.具体应用 🎹 二.二叉树(Binary Tree) 🎺1.概念  🎻2.表现形式 🪕3.特殊类型 🥁3.1完全二叉树(Complete Binary Tree) 🪘3.2满二叉树(Full Binary Tree) 🔋4.性质  🪫5.二叉树的遍历 💿5.1前中后序遍历

    2024年04月27日
    浏览(45)

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

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

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

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

二维码1

领取红包

二维码2

领红包