• 二叉搜索树

    目录

    二叉搜索树

    • 什么是二叉搜索树？

    二叉搜索树首先是个二叉树，这个二叉树有这么一个特点，左子树的所有节点都比根节点小，右子树的所有节点都比根节点大。 并且左右子树也都满足这个条件
    二叉搜索树又叫二叉排序树，因为它的中序遍历是有序的。

    二叉搜索树的实现——K模型

    K模型只存k值

    二叉搜索树的每一个节点都有一个值，以及两个指针，指向左节点的指针，指向右节点的指针。

    template<class K>
struct BSTreeNode//sturct默认访问权限是公有，因为要访问该节点的成员
{
	BSTreeNode* _left;
	BSTreeNode* _right;
	K key;
	BSTreeNode(const K& k)
		:_left(nullptr),
		_right(nullptr),
		key(k)
	{}
};

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 下面实现二叉搜索树

    二叉搜索树的成员变量只有一个根节点的指针

    template<class K>
class BSTree
{
	template BSTreeNode<K> Node;
	Node* root=nullptr;
public:

};

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8

    插入

    根据二叉搜索树的特点，我们从根节点开始查找：

    1. 如果k值小于该节点的值，去左树查找
    2. 如果k值大于该节点的值，去右树查找
    3. 如果相等返回false

    结束的标志：该节点为空，然后插入进去即可。

    注意：

    1. 当树为空的时候，那么插入的节点就是根节点
    2. 找到空的时候，不能直接插入，因为那是临时变量，要从它的父节点的位置把子节点链接上。
    	bool Insert(const K& k)
	{
		if (root == nullptr)
		{
			root = new Node(k);
			return true;
		}
		Node* cur = root;
		Node* parent = nullptr;
		while (cur)
		{
			if (k > cur->key)
			{
				parent = cur;
				cur = cur->_right;
			}
			else if (k < cur->key)
			{
				parent = cur;
				cur = cur->_left;
			}
			else
				return false;
		}
		cur = new Node(k);
		if (parent->key>k)
			parent->_left = cur;
		else
			parent->_right = cur;
		return true;
	}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31

    通过这里我们可以看出二叉搜索树天然去重——没有相同的元素

    • 递归式写法

    该递归写法中，用到了引用，那么就不需要去找父节点了，引用就是别名（不就是本身嘛），而我们就是要插入它本身。

    	bool _Insert(Node* &root, const K& k)
	{
		if (root == nullptr)
		{
			root = new Node(k);
			return true;
		}
		if (k > root->key)
			return _Insert(root->_right, k);
		else if (k < root->key)
			return _Insert(root->_left, k);
		else
			return false;
	}
	bool Insert(const K& k)
	{
		return _Insert(root, k);
	}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18

    查找

    查找其实还是比较简单的，根据该树的性质查找即可

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

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 递归式写法
    	bool _Find(Node* root, const K& k)
	{
		if (root == nullptr)
			return false;

		if (k > root->key)
			return _Find(root->_right, k);
		else if (k < root->key)
			return _Find(root->_left, k);
		else
			return true;
	}
	bool Find(const K& k)
	{
		return _Find(root, k);
	}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16

    删除

    删除操作还是挺麻烦的，有很多要注意的地方，因为删除之后要保证该树依然是搜索二叉树。
    下面是注意的几点：

    1. 删除的节点为叶子节点——没有左右子树。
    2. 删除的节点只有一颗子树——该节点只有左子树或者只有右子树。
    3. 删除的该节点，既有左子树，又有右子树。
    • 解决

    对于1，2两个，我们可以合并成一个问题，把1问题看成：左右子树都为空即可。
    1，2问题 ：
    image.png

    • 当节点没有左子树的时候，比如删除1，那么我们怎么操作呢？——3的左子树链接到2上就可以。父节点的左（或右）指针指向删除节点的右子树。左右指针的确定看父节点于子节点的位置关系
    				//左为空
				if (cur->_left == nullptr)
				{
					if (cur == root)
						root = cur->_right;
					else
					{
						if(father->_left==cur)
							father->_left = cur->_right;
						else
							father->_right = cur->_right;
					}
					delete cur;
				}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 当节点没有右子树的时候，比如删除14，那么我们怎么操作呢？——10的右子树连接到13上就可以了。父节点的左（右）指针指向删除节点的左子树。左右指针的确定看父节点于子节点的位置关系
    				//右为空
				else if (cur->_right == nullptr)
				{
					if (cur == root)
						root = cur->_left;
					else
					{
						if (father->_left == cur)
							father->_left = cur->_left;
						else
							father->_right = cur->_left;
					}
					delete cur;
				}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 极端情况——该节点是根节点，此时我们只要改变根节点指针的的指向，然后删除掉原来的根节点即可。image.png比如删除3

    对于第3个问题：

    我们采用交换的方法：
    image.png
    比如要删除这里的3，根据二叉搜索树的性质，左边都是比它小的，右边都是比它大的。
    那么我们解决问题的方法就有两种了：

    1. 找到它左子树最大的那个节点（上图的2节点），然后和它交换。——根据该树的性质，该最大的节点在左子树的最右边。然后可以直接删除节点吗？——不可以，因为2左边可能有左子树，所以我们要该节点的父节点（本图为1）的右指针指向交换之后改节点的左子树。

    这里不需要确定父节点和子节点的关系，是因为关系已经确定了。——在删除根节点的时候，就需要从新确定一下他们的关系了

    如下图：
    image.png
    2. 找到它右子树最小的那个节点（节点4），然后和它交换。——根据该树的性质，该节点在右子树的最左边。交换之后改节点也不能直接进行删除，因为它可能有右子树，我们要把它的父节点的左指针指向它的右子树。

    如下图：

    image.png
    注意：
    当删除的该节点为根节点的时候，就和上面的规则不一样了。比如删除8这个节点，我们和右子树最小的那个节点10进行交换，如果按照上面的规则——要把它的父节点的左指针指向它的右子树。
    就会变成这样：
    image.png
    这就不是二叉搜索树了。
    我们想一下，为什么会发生这种状况呢？对于上面两个情况，改节点的左指向的就是需要删除的，而对于根节点却截然不同，因为它的左不需要动。
    解决方案：父节点的哪个指针指向的节点值等于删除节点的值，那么该指针指向删除节点的右子树（对应解决方法2），该指针指向删除节点的左子树（对应解决方案1）。

    				else
				{
					Node* mincur = cur->_right;
					father = cur;
					while (mincur->_left)
					{
						father = mincur;
						mincur = mincur->_left;
					}
					swap(cur->key, mincur->key);
					if (father == root)
					{
						if (father->_left == mincur)
							father->_left = mincur->_right;
						else
							father->_right = mincur->_right;
					}
					else
						father->_left = mincur->_right;
					delete mincur;
				}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    非递归写法
    	bool Erase(const K& k)
	{
		if (root == nullptr)
			return false;

		Node* cur = root;
		Node* father = cur;
		while (cur)
		{
			if (k > cur->key)
			{
				father = cur;
				cur = cur->_right;
			}	
			else if (k < cur->key)
			{
				father = cur;
				cur = cur->_left;
			}
			else
			{
				//左为空
				if (cur->_left == nullptr)
				{
					if (cur == root)
						root = cur->_right;
					else
					{
						if(father->_left==cur)
							father->_left = cur->_right;
						else
							father->_right = cur->_right;
					}
					delete cur;
				}
				//右为空
				else if (cur->_right == nullptr)
				{
					if (cur == root)
						root = cur->_left;
					else
					{
						if (father->_left == cur)
							father->_left = cur->_left;
						else
							father->_right = cur->_left;
					}
					delete cur;
				}
				//都不为空
				else
				{
					Node* mincur = cur->_right;
					father = cur;
					while (mincur->_left)
					{
						father = mincur;
						mincur = mincur->_left;
					}
					swap(cur->key, mincur->key);
					if (father == root)
					{
						if (father->_left == mincur)
							father->_left = mincur->_right;
						else
							father->_right = mincur->_right;
					}
					else
						father->_left = mincur->_right;
					delete mincur;
				}
				return true;
			}

		}
		return false;

	}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    • 48
    • 49
    • 50
    • 51
    • 52
    • 53
    • 54
    • 55
    • 56
    • 57
    • 58
    • 59
    • 60
    • 61
    • 62
    • 63
    • 64
    • 65
    • 66
    • 67
    • 68
    • 69
    • 70
    • 71
    • 72
    • 73
    • 74
    • 75
    • 76
    • 77
    • 78
    递归写法

    对于递归的写法：
    第一，处理归的条件
    第二，处理左树，右树的逻辑
    第三，处理当前逻辑

    1. 归：为空的时候归
    2. k值比根值大，去删右树，k值比根值小，去删左树
    3. 相等的时候为当前逻辑，左树为空，直接把它的右子树连接上去，因为传的是引用，右子树为空的时候，直接把它的左子树连接上去。当左右子树都不为空的时候，还是哪个交换逻辑，交换之后，我们只需继续进行树的删除操作即可（对于下面的处理，我们只需要在右子树上进行删除即可）
    bool _Erase(Node*& root, const K& k)
	{
		if (root == nullptr)
			return false;

		if (k > root->key)
			return _Erase(root->_right, k);
		else if (k < root->key)
			return _Erase(root->_left, k);
		else
		{
			Node* cur = root;
			if (root->_left == nullptr)
			{
				root = root->_right;
				delete cur;
			}
			else if (root->_right == nullptr)
			{
				root = root->_left;
				delete cur;
			}
			else
			{
				cur = cur->_right;
				while (cur->_left)
				{
					cur = cur->_left;
				}
				swap(cur->key, root->key);
				return _Erase(root->_right, k);
			}
			return true;
		}
	}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35

    拷贝

    二叉搜索树的拷贝是个深拷贝，在拷贝的过程中要注意保持该树的特性。
    该思路为：我们拷贝好一棵树，然后root指向该树的根节点就创建完成了。
    _copy，我们把copynode作为树的根节点，
    我们先处理该层逻辑：把值给节点，然后处理左树，再处理右树。

    	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;
	}
	BSTree(const BSTree<K>& Tree)
	{
		root = _copy(Tree.root);
	}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14

    当然拷贝的过程我们用前序遍历的方式进行拷贝

    	void ProOrder(Node* &root, Node* const& Troot)
	{
		if (Troot == nullptr)
			return;
		root = new Node(Troot->key);
		ProOrder(root->_left, Troot->_left);
		ProOrder(root->_right, Troot->_right);

	}
	BSTree(const BSTree<K>& Tree)
	{
		ProOrder(root, Tree.root);
	}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13

    赋值

    直接借用拷贝构造

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

    • 1
    • 2
    • 3
    • 4
    • 5

    KV模型

    一个k对应一个v，共同储存，和python中的字典差不多
    对于kv模型，需要改变的地方也比较少

    • 成员添加一个值
    template<class K,class V>
struct BSTreeNode
{
	BSTreeNode* _left;
	BSTreeNode* _right;
	K key;
	V val;
	BSTreeNode(const K& k,const V& v)
		:_left(nullptr),
		_right(nullptr),
		key(k),
		val(v)
	{}
};

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 查找的时候返回节点的指针，用来修改值
    • 插入还是和k模型差不多
    • 删除没有改变，还是按键K进行删除

    源码在本博客代码链接

    二叉搜索树的性能分析

    对于它的查找的时间复杂度O(h)，h为数的高度，当该二叉树是个单支树的话，复杂度为O(N)，那么最坏的情况下就失去它的性能。

  • 相关阅读:
    Docker Images & Containers
    B站崩了，如果我们是那晚负责修复的开发人员
    深度学习的历史
    阿里云SLB之：基于URL调度场景的SLB七层负载均衡配置（十三）
    [Pandas技巧] 删除指定列值为空的行
    C#，入门教程——程序运行时的调试技巧与逻辑错误探针技术与源代码
    iVX低代码平台系列详解 -- 概述篇(一)
    洛谷 P2900 [USACO08MAR]Land Acquisition G（斜率优化dp）
    [附源码]计算机毕业设计springboot中小学课后延时服务管理系统
    Jupyter notebook在超算平台上使用的详细教程
  • 原文地址：https://blog.csdn.net/m0_60598323/article/details/128124918