二叉树进阶——手撕二叉搜索树

troop主页：troop

手撕二叉搜索树

  • 1.二叉搜索树的定义
  • 2.实现（非递归）
    • 补充结构
    • 2.1查找
    • 2.2插入
    • 2.3删除（==重要==）
      • 情况1(无孩子&&一个孩子）
  • 3.二叉搜索树的应用
    • 3.1K模型
    • 3.2KV模型
      • 3.2.1KV模型的实现
  • 总结
  • 二叉搜索树源代码

1.二叉搜索树的定义

二叉搜索树又称二叉排序树，它或者是一棵空树，或者是具有以下性质的二叉树：

  • 若它的左子树不为空，则左子树上的所有节点的值都小于根节点的值
  • 若它的右子树不为空，则右子树上的所有节点的值都大于根节点的值

在这里插入图片描述

2.实现（非递归）

补充结构

//struct BinarySearchTreeNode
template<class K>
struct BSTreeNode
{
	typedef BSTreeNode<K> Node;
	Node* _left;
	Node* _right;
	K _key;

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

/class BinarySearchTree
template<class K>
class BSTree
{
	typedef BSTreeNode<K> Node;
public:
	BSTree() = default;
	BSTree(const BSTree<K>& t)
	{
		_root = copy(t._root);
	}
	Node* copy(Node* root)
	{
		if (root == nullptr)
			return nullptr;
		Node* newroot = new Node(root->_val);
		newroot->_left = copy(root->_left);
		newroot->_right = copy(root->_right);
		return newroot;
	}

	~BSTree()
	{
		Destroy();
	}
	void Destroy()
	{
		return _Destroy(_root);
	}
	void _Destroy(Node* root)
	{
		if (root == nullptr)
			return;
		_Destroy(root->_left);
		_Destroy(root->_right);
		delete root;
	}
private:
	Node* _root;
};

2.1查找

根据它的定义查找就是，跟节点比，比节点大就去它的右子树中寻找，比他小就去它的左子树中寻找。

	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.2插入

在这里插入图片描述
插入也很简单，例如上图我们要插入16，我们就先找到要插入的位置，然后为了方便我们记录整个过程我们需要一个父节点。

	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->_left=cur;
		}
		else
		{
			parent->_right=cur;
		}
		return true;
	}

现在可以进行测试代码的正确性。
在这里插入图片描述
注意，搜索二插入要有序它走的是中序遍历。

2.3删除（重要）

删除比插入麻烦的多，我们删除值原则就是要保证它还是搜索二叉树，它的性质不可以改变。这就挺麻烦的，所以我们在删除这里用替换删除
替换删除：找到一个可以替换的节点，交换值，转换删除它。
可以替换的节点是：左子树的最大or右子树的最小。

下面我们来分析一下删除的各种情况

  1. 删除孩子节点
  2. 删除只有一个孩子的节点
  3. 删除两个孩子的节点
    这里总结下，情况1和2可以归为一类。情况3我们就要用到替换删除法

情况1(无孩子&&一个孩子）

在这里插入图片描述

//找到了开始删除
				//第一种
				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;
				}

###情况二（两个孩子）
在这里插入图片描述
找到右子树的最小，把它的值复制给cur，就转换成了删除叶子节点

				else//第二种(俩孩子)替换删除法
				{
					Node* rightMinparent = cur;
					Node* rightMin = cur->_right;
					while (cur->_right)
					{
						rightMinparent = rightMin;
						rightMin = rightMin->_left;
					}
					cur->_key = rightMin->_key;
					if (rightMin == rightMinparent->_left)
					{
						rightMinparent->_left = rightMin->_right;
					}
					else
					{
						rightMinparent->_right = rightMin->_right;
					}
					delete rightMin;
					return true;
				}

3.二叉搜索树的应用

3.1K模型

K模型即只有key作为关键码，结构中只需要存储Key即可，关键码即为需要搜索到
的值。
比如：给一个单词word，判断该单词是否拼写正确。这个就是普通的二叉搜索树

3.2KV模型

KV模型：每一个关键码key，都有与之对应的值Value，即<Key, Value>的键值对。
通过key值快速查找另外一个值在不在。我们用二叉搜索树这个用的是比较多的
生活中的KV模型例如：商场车库，进去都可以进入（记录车牌（key）进入时间（value））
出：付费出（通过车牌（key），查询进入的时间（value））。
还有字典查询，高铁身份证进站等等。

3.2.1KV模型的实现

这个就是多加了一个对象，实现直接CV上面的代码

namespace key_value
{
	template<class K, class V>
	struct BSTreeNode
	{
		typedef BSTreeNode<K, V> Node;
		Node* _left;
		Node* _right;
		K _key;
		V _value;

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


	template<class K, class V>
	class BSTree
	{
		typedef BSTreeNode<K, V> Node;
	public:
		//插入
		bool Insert(const K& key, const V& value)
		{
			if (_root == nullptr)
			{
				_root = new Node(key, value);
				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 true;
				}
			}

			cur = new Node(key, value);
			if (parent->_key < key)
			{
				parent->_right = cur;
			}
			else
			{
				parent->_left = cur;
			}
			return true;
		}
		//
		Node* 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 cur;
				}
			}
			return nullptr;
		}
		//中序遍历
		void _InOrder(Node* root)
		{
			if (root == nullptr)
				return;
			_InOrder(root->_left);
			std::cout << root->_val << " ";
			_InOrder(root->_right);
		}

		void InOrder()
		{
			_InOrder(_root);
			cout << endl;
		}
		//3.删除
		bool Erase(const K& key)
		{
			Node* parent = nullptr;
			Node* cur = _root;
			while (cur)
			{
				if (cur->_val < key)
				{
					parent = cur;
					cur = cur->_right;
				}
				else if (cur->_val > key)
				{
					parent = cur;
					cur = cur->_left;
				}
				else
				{
					//找到了开始删除
					//第一种（无孩子&&一个孩子）
					if (cur->_left == nullptr)//我的左为空
					{
						if (cur == _root)
						{
							_root = cur->_right;
						}
						else
						{
							if (parent->_left == cur)
							{
								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 (parent->_left == cur)
							{
								parent->_left = cur->_left;
							}
							else//我是父亲的右节点
							{
								parent->_right = cur->_left;
							}
						}
						delete cur;
						return true;
					}

					else//第二种（有两个孩子）替换删除法
					{
						Node* rightMinparent = cur;
						Node* rightMin = cur->_right;
						while (rightMin->_left)
						{
							rightMinparent = rightMin;
							rightMin = rightMin->_left;
						}
						cur->_val = rightMin->_val;
						if (rightMin == rightMinparent->_left)
							rightMinparent->_left = rightMin->_right;
						else
							rightMinparent->_right = rightMin->_right;
						delete rightMin;
						return true;
					}
				}
			}
			return false;
		}
		//void InOrder()
		//{
		//	_InOrder(_root);
		//	cout << endl;
		//}
	//private:
	//	void _InOrder(Node* root)
	//	{
	//		if (root == nullptr)
	//			return;

	//		_InOrder(root->_left);
	//		cout << root->_key << " ";
	//		_InOrder(root->_right);
	//	}

	private:
		Node* _root = nullptr;
	};
}

我们可以用哥=个例子来玩一玩这个KV模型

void TestBSTree()
{
	key_value::BSTree<string, string> dict;
	dict.Insert("insert", "插入");
	dict.Insert("erase", "删除");
	dict.Insert("left", "左边");
	dict.Insert("string", "字符串");

	string str;
	while (cin >> str)
	{
		auto ret = dict.Find(str);
		if (ret)
		{
			cout << str << ":" << ret->_value << endl;
		}
		else
		{
			cout << "单词拼写错误" << endl;
		}
	}
}

在这里插入图片描述

总结

总的来说二叉搜索树，比较难的地方就是删除部分，多画图多思考。
下篇我们就要深入二叉搜索树。

二叉搜索树源代码

#pragma once
#include<iostream>
using namespace std;
//struct BinarySearchTreeNode
template<class K>
struct BSTreeNode
{
	typedef BSTreeNode<K> Node;
	Node* _left;
	Node* _right;
	K _key;

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

//class BinarySearchTree
template<class K>
class BSTree
{
	typedef BSTreeNode<K> Node;
public:
	BSTree() = default;
	BSTree(const BSTree<K>& t)
	{
		_root = copy(t._root);
	}
	Node* copy(Node* root)
	{
		if (root == nullptr)
			return nullptr;
		Node* newroot = new Node(root->_val);
		newroot->_left = copy(root->_left);
		newroot->_right = copy(root->_right);
		return newroot;
	}

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

	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;
	}

	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->_left=cur;
		}
		else
		{
			parent->_right=cur;
		}
		return true;
	}
	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 (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* rightMinparent = cur;
					Node* rightMin = cur->_right;
					while (cur->_right)
					{
						rightMinparent = rightMin;
						rightMin = rightMin->_left;
					}
					if (rightMinparent->_left == rightMin)
					{
						rightMinparent->_left = rightMin->_right;
					}
					else
					{
						rightMinparent->_right = rightMin->_right;
					}
				}
			}
		}
		return false;
	}
	void Inorder()
	{
		_Inorder(_root);
		cout << endl;
	}
private:
	void _Inorder(Node* root)
	{
		if (root == nullptr)
			return;
		_Inorder(root->_left);
		cout << root->_key << " ";
		_Inorder(root->_right);
	}
private:
	Node* _root=nullptr;
};

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：/a/520761.html

如若内容造成侵权/违法违规/事实不符，请联系我们进行投诉反馈qq邮箱809451989@qq.com，一经查实，立即删除！

相关文章

RUST语言值所有权之内存复制与移动

RUST语言值所有权之内存复制与移动

1.RUST中每个值都有一个所有者,每次只能有一个所有者 String::from函数会为字符串hello分配一块内存 内存示例如下: 在内存分配前调用s1正常输出 在分配s1给s2后调用报错 因为s1分配给s2后,s1的指向自动失效 s1被move到s2 s1自动释放 字符串克隆使用
阅读更多...
I2C驱动实验：读取AP3216C设备中寄存器的数据

I2C驱动实验：读取AP3216C设备中寄存器的数据

一. 简介 经过前面几篇文章的学习&#xff0c;已经完成了I2C驱动框架&#xff0c;字符设备驱动框架&#xff0c;编写了 读写 I2C设备中寄存器的数据的代码&#xff0c;文章如下&#xff1a; I2C驱动实验&#xff1a;实现读/写I2C设备寄存器的函数-CSDN博客 本文在此基础上&a…
阅读更多...
C#开发中一些常用的工具类分享

C#开发中一些常用的工具类分享

一、配置文件读写类 用于在开发时候C#操作配置文件读写信息 1、工具类 ReadIni 代码 using System; using System.Collections.Generic; using System.IO; using System.Linq; using System.Runtime.InteropServices; using System.Text; using System.Threading.Tasks;namesp…
阅读更多...
不同设备使用同一个Git账号

不同设备使用同一个Git账号

想要在公司和家里的电脑上用同一个git账号来pull, push代码 1. 查看原设备的用户名和邮箱 第1种方法&#xff0c; 依次输入 git config user.name git config user.email第2种方法&#xff0c; 输入 cat ~/.gitconfig2. 配置新设备的用户名和邮箱 用户名和邮箱与原设备保持…
阅读更多...
高效学习方法：冥想背诵，看一句念一句，再每个词分析位置及语法等合理性，忘记哪个词再看猜下为什么会忘，跟自己的表达哪里不一样。

高效学习方法：冥想背诵，看一句念一句，再每个词分析位置及语法等合理性，忘记哪个词再看猜下为什么会忘，跟自己的表达哪里不一样。

原则&#xff1a;易学则易行&#xff0c;则效果最好。《易经》 你提到的这种学习方法结合了多种记忆和理解技巧&#xff0c;可以帮助提高学习效率。下面是对这种方法的一个详细解释和一些建议&#xff1a; 冥想背诵&#xff1a;通过冥想来集中注意力&#xff0c;可以帮助你在没…
阅读更多...
数据如何才能供得出、流得动、用得好、还安全

数据如何才能供得出、流得动、用得好、还安全

众所周知&#xff0c;数据要素已经列入基本生产要素&#xff0c;同时成立国家数据局进行工作统筹。目前数据要素如何发挥其价值&#xff0c;全国掀起了一浪一浪的热潮。 随着国外大语言模型的袭来&#xff0c;国内在大语言模型领域的应用也大放异彩&#xff0c;与此同时&#x…
阅读更多...
使用YOLOv8训练自己的【目标检测】数据集

使用YOLOv8训练自己的【目标检测】数据集

文章目录 1.收集数据集1.1 使用开源已标记数据集1.2 爬取网络图像1.3 自己拍摄数据集1.4 使用数据增强生成数据集1.5 使用算法合成图像 2.标注数据集2.1确认标注格式2.2 开始标注 3.划分数据集4.配置训练环境4.1获取代码4.2安装环境 5.训练模型5.1新建一个数据集yaml文件5.2预测…
阅读更多...
java中的正则表达式和异常

java中的正则表达式和异常

正则表达式&#xff1a; 作用一&#xff1a;用来校验数据格式是否合法 作用二&#xff1a;在文本中查找满足要求的内容 不用正则表达式&#xff1a;检验QQ号是否合法&#xff0c;要求全部是数字&#xff0c;长度在6-20&#xff0c;不能以0开头 public class test {public stat…
阅读更多...
手机扫码查看视频如何实现？扫描二维码在线看视频的制作技巧

手机扫码查看视频如何实现？扫描二维码在线看视频的制作技巧

现在的学校或者幼儿园会需要拍摄学生的视频&#xff0c;然后展示给其他人查看&#xff0c;为了能够方便用户能够快速的获取文件内容&#xff0c;所以经常会通过生成视频二维码的方法&#xff0c;将二维码分享之后手机扫码来获取视频内容&#xff0c;有效提升用户获取内容的体验…
阅读更多...
PTA C 1050 螺旋矩阵（思路与优化）

PTA C 1050 螺旋矩阵（思路与优化）

本题要求将给定的 N 个正整数按非递增的顺序&#xff0c;填入“螺旋矩阵”。所谓“螺旋矩阵”&#xff0c;是指从左上角第 1 个格子开始&#xff0c;按顺时针螺旋方向填充。要求矩阵的规模为 m 行 n 列&#xff0c;满足条件&#xff1a;mn 等于 N&#xff1b;m≥n&#xff1b;且…
阅读更多...
160.相交链表

160.相交链表

题目描述 解题思路 ————看评论区大神的思路———— 设「第一个公共节点」为 node &#xff0c;「链表 headA」的节点数量为 aaa &#xff0c;「链表 headB」的节点数量为 bbb &#xff0c;「两链表的公共尾部」的节点数量为 ccc &#xff0c;则有&#xff1a; 头节点 …
阅读更多...
CSS设置字体样式

CSS设置字体样式

目录 前言&#xff1a; 1.font-family&#xff1a; 2.font-style&#xff1a; 3.font-weight&#xff1a; 4.font-size&#xff1a; 5.font-variant&#xff1a; 6.font&#xff1a; 前言&#xff1a; 在网页中字体是重要的组成部分&#xff0c;使用好字体可以让网页更…
阅读更多...
第一次在msf控制台中运行search命令提示Module database cache not built yet问题解决

第一次在msf控制台中运行search命令提示Module database cache not built yet问题解决

0x00 问题描述 在新装的kali虚拟机中使用msfconsole执行search命令时提示Module database cache not built yet问题&#xff0c;显然&#xff0c;是我们相关的数据库缓存存在问题。 故障现象&#xff1a; 0x01 启动数据库服务 msf中的search功能是基于postgresql来实现的&am…
阅读更多...
python学习25：python中的元组(tuple)

python学习25：python中的元组(tuple)

python中的元组(tuple) 1.什么是元组&#xff1f; 元组也是容器数据类型的一种&#xff0c;同列表几乎是一样的&#xff0c;都是可以在里面封装多个&#xff0c;不同类型的元素在内&#xff1b;与列表最大的不同就是&#xff1a; 元组一旦被定义&#xff0c;就不能修改 2.元组…
阅读更多...
物理层习题及其相关知识（谁看谁不迷糊呢）

物理层习题及其相关知识（谁看谁不迷糊呢）

1. 对于带宽为50k Hz的信道&#xff0c;若有4种不同的物理状态来表示数据&#xff0c;信噪比为20dB 。&#xff08;1&#xff09; 按奈奎斯特定理&#xff0c;信道的最大传输数据速率是多少&#xff1f;&#xff08;2&#xff09; 按香农定理&#xff0c;信道的最大传输数据速度…
阅读更多...
Java设计模式—享元（FlyWeight）模式

Java设计模式—享元（FlyWeight）模式

享元模式&#xff08;Flyweight&#xff09;&#xff0c;运用共享技术有效地支持大量细粒度的对象 public abstract class Piece {protected PieceColor m_color;protected PiecePos m_pos;public Piece(PieceColor color ,PiecePos pos){m_color color;m_pos pos;}public ab…
阅读更多...
Java笔试总结

Java笔试总结

. 操作系统中关于竞争和死锁的关系下面描述正确的是&#xff1f; A 竞争一定会导致死锁 B 死锁一定由竞争引起 C 竞争可能引起死锁 D 预防死锁可以防止竞争 答案: C 进程的控制信息和描述信息存放在()。 A JCB B PCB C AFT D SFT 答案: B 当系统发生抖动&#xff08;thrash…
阅读更多...
元宇宙虚拟空间的场景的渲染（五）

元宇宙虚拟空间的场景的渲染（五）

前言 该文章主要讲元宇宙虚拟空间的场景的渲染&#xff0c;基本核心技术点&#xff0c;不多说&#xff0c;直接引入正题。 场景的渲染 下面第二个图中的代码是一个循环渲染逻辑&#xff0c;首先getDelta 获取2次时间的时间间隔&#xff0c;requestAnimationFrame请求我们的一…
阅读更多...
Qt Creator 界面

Qt Creator 界面

&#x1f40c;博主主页&#xff1a;&#x1f40c;​倔强的大蜗牛&#x1f40c;​ &#x1f4da;专栏分类&#xff1a;QT❤️感谢大家点赞&#x1f44d;收藏⭐评论✍️ 目录 一、认识 Qt Creator 界面 1、总览 2、左边栏 3、代码编辑区 4、UI设计界面 5、构建区 一、认识 …
阅读更多...
99%的人不知道，Oracle resetlogs强制开库需要推进SCN？

99%的人不知道，Oracle resetlogs强制开库需要推进SCN？

&#x1f4e2;&#x1f4e2;&#x1f4e2;&#x1f4e3;&#x1f4e3;&#x1f4e3; 哈喽&#xff01;大家好&#xff0c;我是【IT邦德】&#xff0c;江湖人称jeames007&#xff0c;10余年DBA及大数据工作经验 一位上进心十足的【大数据领域博主】&#xff01;&#x1f61c;&am…
阅读更多...
最新文章

Copyright @ 2022~2023