二叉搜索树

欢迎来到本期节目- - -
二叉搜索树(去重版)

二叉搜索树的概念

定义：

二叉搜索树不支持修改key值，否则会破会搜索树结构；

性能：

需要从两种极端情况综合来看；

• 理想情况：
  一颗二叉搜索树的最佳情况是一颗完全二叉树或者接近完全二叉树；

  此时，高度为logN
  二叉搜索树的插入、删除、查找效率为Ο(logN)

• 最差情况：

  此时退化成了单支树，高度为N
  二叉搜索树的插入、删除、查找效率为Ο(N)

在实际运用中，很少机率是最佳情况，所以综合来看，二叉搜索树的增、删、查的效率是O(N).

二叉搜索树的插入

逻辑过程：

向一颗二叉搜索树tree插入一个节点Node;

如果tree是空树，则Node为根，插入成功；
如果tree是非空树，那么需要知道在哪插入；

• 可以给两个指针cur和parent，cur从tree的根开始，parent记录cur的父亲节点；
  • 如果cur的key值小于Node的key值，让cur往右子树走；
  • 如果cur的key值大于Node的key值，让cur往左子树走；
  • 如果等于，插入失败；
• 直到cur走到空为止，然后parent连接Node节点，插入成功；

动图演示：

代码实操：

public:
	bool Insert(const K& key,const V& val)
	{
		BSTNode* node = new BSTNode(key, val);
		if (_root == nullptr)
		{
			_root = node;
			return true;
		}
		else
		{
			BSTNode* cur = _root;
			BSTNode* parent = nullptr;
			while (cur)
			{
				if (key > cur->_key)
				{
					parent = cur;
					cur = cur->_right;
				}
				else if (key < cur->_key)
				{
					parent = cur;
					cur = cur->_left;
				}
				else
				{
					return false;
				}
			}
	
			if (key > parent->_key)
			{
				parent->_right = node;
			}
			else
			{
				parent->_left = node;
			}
			return true;
		}
	}

二叉搜索树的删除

逻辑过程：

在一颗二叉搜索树tree中删除一个节点Node;

如果tree为空树，删除失败;
如果tree为非空树，依据key寻找对应删除节点；

  用cur记录当前节点，parent记录cur的父亲；
  如果没找到，删除失败；
  如果找到了：

• 1.目标节点cur的左右子树都为空；
  那么直接删除cur，让parent指向nullptr;

• 2.目标节点cur只有一个左子树；
  该节点cur的右子树为空，左子树不为空，依据搜索树规则有：
  cur如果在parent的左子树，说明cur的左子树也在parent左边，则cur的左子树小于parent，让cur的左子树做parent的左子树；
  cur如果在parent的右子树，说明cur的左子树也在parent右边，则cur的左子树大于parent，让cur的左子树做parent的右子树；

• 3.目标节点cur只有一个右子树；
  和上一情况类似；

• 4.目标节点cur左右子树都不为空；
  该节点cur的左右子树均不为空，则需要使用替换法；
  将cur的左子树的最右节点或者右子树的最左节点替换cur；
  这样既保持了二叉搜索树结构，也把删除问题转换为了上述情况，因为最左节点的左子树一定为空；最右节点的右子树一定为空；

总的来说，可以把1,2,3情况归为一类，将4转换为上述的一类情况；

动图演示：

代码实操：

public:
	bool Erase(const K& key)
	{
		BSTNode* parent = nullptr;
		BSTNode* cur = _root;
		while (cur)
		{
			if (key > cur->_key)
			{
				parent = cur;
				cur = cur->_right;
			}
			else if (key < cur->_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;
				}
				
				BSTNode* replacement = cur;
				BSTNode* replaceparent = cur->_right;
				while (replacement->_left)
				{
					replaceparent = replacement;
					replacement = replacement->_left;
				}
				cur->_key = replacement->_key;
				cur->_val = replacement->_val;
				if (replaceparent->_left == replacement)
				{
					replaceparent->_left = replacement->_right;
				}
				else
				{
					replaceparent->_right = replacement->_right;
				}
				delete replacement;
				return true;
				}
			}
		return false;
	}

二叉搜索树的查找

逻辑过程：

在一颗二叉搜索树tree中查找一个节点Node;

如果tree为空，则查找失败；
如果tree为非空；

• 给cur记录当前节点，parent记录cur的父亲节点；
  • 如果cur的key值小于Node的key值，让cur往右子树走；
  • 如果cur的key值大于Node的key值，让cur往左子树走；
  • 如果等于，查找成功；
• 如果cur走到空节点，查找失败；

查找和插入类似，所以不做动图演示了；

代码实操：

public:
	BSTNode* Find(const K& key)
	{
		BSTNode* cur = _root;
		while (cur)
		{
			if (key > cur->_key)
			{
				cur = cur->_right;
			}
			else if (key < cur->_key)
			{
				cur = cur->_left;
			}
			else
			{
				return cur;
			}
		}
		return nullptr;
	}

二叉搜索树的遍历

逻辑过程：

二叉搜索树最明显的特征就是中序遍历的结果是递增；
遇到根先打印左子树，然后再打印根，然后再打印右子树；

动图演示：

private:
	void _Inorder(BSTNode* _root)
	{
		if (_root)
		{
			_Inorder(_root->_left);
			cout << _root->_key << ":" << _root->_val << endl;
			_Inorder(_root->_right);
		}
	}

二叉搜索树的实现

#pragma once
#include<iostream>
#include<string>
using namespace std;

template<class K, class V>
class BSTNode
{
public:
	K _key;
	V _val;
	BSTNode<K, V>* _left;
	BSTNode<K, V>* _right;

	BSTNode(const K& key = K(), const V& val = V())
	{
		_key = key;
		_val = val;
		_left = _right = nullptr;
	}
};


template<class K,class V>
class BSTree
{
	typedef BSTNode<K, V> BSTNode;
public:
	BSTree() = default;
	BSTree(const BSTree& tree)
	{
		_root = copy(tree._root);
	}
	BSTree& operator=(BSTree tree)
	{
		std::swap(_root, tree._root);
		return *this;
	}
	bool Insert(const K& key,const V& val)
	{
		BSTNode* node = new BSTNode(key, val);
		if (_root == nullptr)
		{
			_root = node;
			return true;
		}
		else
		{
			BSTNode* cur = _root;
			BSTNode* parent = nullptr;
			while (cur)
			{
				if (key > cur->_key)
				{
					parent = cur;
					cur = cur->_right;
				}
				else if (key < cur->_key)
				{
					parent = cur;
					cur = cur->_left;
				}
				else
				{
					return false;
				}
			}
	
			if (key > parent->_key)
			{
				parent->_right = node;
			}
			else
			{
				parent->_left = node;
			}
			return true;
		}
	}
	bool Erase(const K& key)
	{
		BSTNode* parent = nullptr;
		BSTNode* cur = _root;
		while (cur)
		{
			if (key > cur->_key)
			{
				parent = cur;
				cur = cur->_right;
			}
			else if (key < cur->_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;
				}
				
				BSTNode* replacement = cur;
				BSTNode* replaceparent = cur->_right;
				while (replacement->_left)
				{
					replaceparent = replacement;
					replacement = replacement->_left;
				}
				
				cur->_key = replacement->_key;
				cur->_val = replacement->_val;
				if (replaceparent->_left == replacement)
				{
					replaceparent->_left = replacement->_right;
				}
				else
				{
					replaceparent->_right = replacement->_right;
				}
				delete replacement;
				return true;
				}
			}
		return false;
	}
	BSTNode* Find(const K& key)
	{
		BSTNode* cur = _root;
		while (cur)
		{
			if (key > cur->_key)
			{
				cur = cur->_right;
			}
			else if (key < cur->_key)
			{
				cur = cur->_left;
			}
			else
			{
				return cur;
			}
		}
		return nullptr;
	}
	void Inorder()
	{
		_Inorder(_root);
	}
	~BSTree()
	{
		_destory(_root);
		_root = nullptr;
	}
private:
	BSTNode* _root = nullptr;
	void _Inorder(BSTNode* _root)
	{
		if (_root)
		{
			_Inorder(_root->_left);
			cout << _root->_key << ":" << _root->_val << endl;
			_Inorder(_root->_right);
		}
	}
	void _destory(BSTNode* _root)
	{
		if (_root)
		{
			_destory(_root->_left);
			_destory(_root->_right);
			delete _root;
		}
	}
	BSTNode* copy(BSTNode* _root)
	{
		if (_root == nullptr)
			return nullptr;

		BSTNode* newroot = new BSTNode(_root->_key, _root->_val);
		newroot->_left = copy(_root->_left);
		newroot->_right = copy(_root->_right);
		return newroot;
	}
};

希望本片文章对您有帮助，请点赞支持一下吧😘💕