二叉搜索树（c++版）

前言

在前面我们介绍过二叉树这个数据结构，今天我们更进一步来介绍二叉树的一种在实现中运用的场景——二叉搜索树。二叉搜索树顾名思义其在“搜索”这个场景下有不俗的表现，之所以会这样是因为它在二叉树的基础上添加了一些属性。下面我们就来简单的介绍一下二叉搜索树

概念

二叉搜索树又称搜索二叉树，它可以是一颗空树，如果有节点那么它的任意一个节点都必须满足如下的要求：

该节点的左树为空树或者该节点的值大于等于左树上所有节点的值

该节点的右树为空树或者该节点的值小于等于右树上所有节点的值

该节点的左右子树必须也为二叉搜索树

⼆叉搜索树中可以⽀持插⼊相等的值，也可以不⽀持插⼊相等的值，具体看使⽤场景定义

map/set/multimap/multiset系列容器底层就是⼆叉搜索树，其中map/set不⽀持插⼊相等
值，multimap/multiset⽀持插⼊相等值

性能分析

前面我们将它在搜索的场景下有不俗的表现，下面我们就来简单的看一下它的性能如何

当它接近于平衡二叉树时，搜索的时间复杂的可以达到O(logN)，但我们无法保证这一点（这里的无法保证指的是普通的搜索二叉树，暂不包含红黑树等加入调整算法的搜索二叉树）。当我们给搜索二叉树插入一段有序的数据，⼆叉搜索树退化为单⽀树(或者类似单⽀)，，此时的时间复杂的就是O(N)

为此我们需要不断的引入调整算法，让这颗二叉树更接近平衡，或者说让它不至于退化，

这就涉及到⼆叉搜索树的变形，平衡⼆叉搜索树AVL树和红⿊树，才能适⽤于我们在内存中存储和搜索数据。这不是我们今天的重点，我们今天只介绍最简单的形态

当然了如果只是想要实现O(logN)的搜索算法，二分法也可以实现，但二分法相比于我们今天介绍的数据结构在某些层面还是不足的，比如二分法想要存储在支持下标随机访问的结构中，二分法在插入删除的场景下天然弱势……

实现

下面我们就来简单的实现一个类似于标准库中set的结构（标准库的搜索二叉树有调整算法，我们就不在这里实现了），不允许存储相同元素（如果需要实现存储相同元素，只需要在插入的逻辑中如果遇到相同元素都放在此相同元素的左树的最右节点或者右树的最左节点）

下面我们边实现边理解其中的逻辑

节点类

我们需要实现一个节点类，这个节点应该包含此节点存储元素的值的信息和此节点左子节点和右子节点的信息

我们实现一个支持泛型的

	template<class K>
	class BSTreeNode
	{

	public:

	private:
		K val = K();
		BSTreeNode<K>* left = nullptr;
		BSTreeNode<K>* right = nullptr;

	};

构造函数

		BSTreeNode(const K& val = K(), BSTreeNode* left = nullptr, BSTreeNode* right = nullptr)
			:val(val),
			left(left),
			right(right)
		{}

<<重载

实现一个<<运算符重载，让节点支持cout打印

先声明一个友元，因为我们要调用节点类的私有成员

template<class K>
		friend ostream& operator<<(ostream& cout, BSTreeNode<K>* node);

 实现

template<class K>
	ostream& operator<<(ostream& cout, BSTreeNode<K>* node)
	{
		if (node != nullptr)
			cout << node->key;
		return cout;
	}

搜索二叉树类

我们还需要实现一个搜索二叉树的类，这个类会保存根节点的地址，和一些方法

方法我们后面再展开，就先实现框架

这里我们将节点类重命名一下，方便我们后续的使用

template<class K>
	class BSTree
	{
		typedef BSTreeNode<K> Node;
private:
		Node* root = nullptr;
	};

声明节点类的友元类

树节点难免会使用到节点类的私有成员，左右节点的地址和节点的值都是需要广泛被使用的，我们直接声明为节点类的友元类

template<class K>
		friend class BSTree;

构造函数

这里只需要处理root的指向即可，没有指向可以指向nullptr

BSTree(Node* root = nullptr)
			:root(root)
		{}

插入

我们这里实现的插入是不允许重复的，可以将函数返回值设计为bool值来标识是否插入成功。

插入逻辑就是一直比较当前节点的值和插入的值大小，去往正确的子树，直到找到nullptr在nullptr这个位置插入，注意记得标识父节点。遇到相同值返回false插入失败即可

bool insert(const K& x)
		{
			if (root == nullptr)
			{
				root = new Node(x);
				return true;
			}
			Node* ptr = root;
			Node* chi = root;
			while (chi != nullptr)
			{
				if (x > chi->val)
				{
					ptr = chi;
					chi = chi->right;
				}
				else if (x < chi->val)
				{
					ptr = chi;
					chi = chi->left;
				}
				else
					return false;
			}
			if (x < ptr->val)
			{
				ptr->left = new Node(x);
			}
			else
			{
				ptr->right = new Node(x);
			}
			return true;
		}

查找元素

一直比较当前节点的值和插入的值大小，去往正确的子树，直到找到nullptr或者相同的值，返回bool标识是否存在

		bool isExistence(const K& key)
		{
			Node* cut = this->root;
			while (cut != nullptr)
			{
				if (key > cut->val)
				{
					cut = cut->right;
				}
				else if (key < cut->val)
				{
					cut = cut->left;
				}
				else
					return true;
			}
			return false;
		}

遍历

这里我们实现一个中序遍历，中序遍历即可将二叉树按顺序遍历一边

我们这里使用递归实现

		void midOrder()
		{
			_midOrder(this->root);
			cout << endl;
		}

封装一个子函数可以保证接口的简洁

		void _midOrder(Node*& root)
		{
			if (root == nullptr)
			{
				return;
			}
			_midOrder(root->left);
			cout << root->val << " ";
			_midOrder(root->right);
		}

赋值重载和拷贝构造

显然如果要实现将一棵树拷贝/赋值给另一棵树是需要深拷贝的，因为浅拷贝会使这树对象指向同一棵树

注意，树的拷贝不能简单的认为是遍历+值插入，应该包含逻辑结构的拷贝

拷贝构造

BSTree(const BSTree& tree)
		{
			this->root = assign(tree.root);
		}

封装一个子函数，这个子函数采用后续遍历，先创建好root节点，在创建好左右子树，再将左右子树串联上根节点

Node* assign(Node* n2)
		{
			if (n2 == nullptr)
				return nullptr;
			Node* n = new Node(n2->key);
			n->left = assign(n2->left);
			n->right = assign(n2->right);
			return n;
		}

赋值重载

我们使用现代写法，先使用拷贝构造创建临时对象，再将this里的root和临时对象的root交换实现两颗树的交换，离开函数，临时对象会被自动释放

BSTree& operator=(BSTree tree)
		{
			//swap(*this, tree); 
			swap(this->root, tree.root);
			return *this;
		}

注意，两个树的交换我们可以通过交换root实现

析构函数和清除节点

析构函数应该遍历一边这棵树，逐一释放节点，使用中序遍历即可保证释放完左右子树的时候总是可以回到root节点释放root

~BSTree()
		{
			clear();
		}

我们这里还是封装一个函数，这个函数有些用处就不设为子函数，这个函数作用是清除节点

void clear()
		{
			_clear(this->root);
            this->root = nullptr;
		}

还是使用一个子函数封装

void _clear(Node* root)
		{
			if (root == nullptr)
			{
				return;
			}
			_clear(root->left);
			_clear(root->right);
			delete root;
		}

删除节点

删除节点还是有些复杂的，复杂在于有些节点是不能直接删除的，直接删除会败坏树的结构，我们采用的思路是替换删除

如果这个节点没有子节点，那么直接删除这个节点，父节点指向这个删除节点一侧的指针置空

如果这个节点有左或者右其中的一个节点，那么父节点指向删除节点一侧的指针指向待删除节点非空子树

如果该节点左右都有节点可以找该节点左树的最右节点或者该节点右树的最左节点覆盖待删除节点的值，将问题转换为删除这个覆盖待删除节点的节点，可以保证这个节点至多只有一棵非空子树

注意如果删除的是根节点特殊处理一下

bool del(const K& key)
		{
			Node* par = nullptr;
			Node* chi = this->root;
			while (chi != nullptr)
			{
				if (key > chi->val)
				{
					par = chi;
					chi = chi->right;
				}
				else if (key < chi->val)
				{
					par = chi;
					chi = chi->left;
				}
				else
				{
					if (chi->left == nullptr)
					{
						if (par == nullptr)
						{
							root = root->right;
						}
						else
						{
							if (par->left == chi)
							{
								par->left = chi->right;
							}
							else {
								par->right = chi->right;
							}
						}
						delete chi;
					}
					else if (chi->right == nullptr)
					{
						if (par == nullptr)
						{
							root = root->left;
						}
						else
						{
							if (par->left == chi)
							{
								par->left = chi->left;
							}
							else {
								par->right = chi->left;
							}
						}
						delete chi;
					}
					else
					{
						Node* ptr = chi;
						Node* cut = chi->right;
						if (cut != nullptr)
						{
							while (cut->left != nullptr)
							{
								ptr = cut;
								cut = cut->left;
							}
							chi->val = cut->val;
							if (ptr->left == cut)
							{
								ptr->left = cut->right;
							}
							else {
								ptr->right = cut->right;
							}
						}
						else
						{
							if (par->left == chi)
							{
								par->left = ptr->left;
							}
							else
							{
								par->right = ptr->left;

							}
						}

						delete cut;
					}
					return true;
				}
			}
			return false;
		}

key和key-value

上面我们实现的是key结构的二叉树，只有key作为关键码，结构中只需要存储key即可，关键码即为需要搜索到的值，搜索场景只需要判断key在不在。key的搜索场景实现的⼆叉树搜索树⽀持增删查，但是不⽀持修改，修改key破坏搜索树结构

除此之外还有key-value的结构

每⼀个关键码key，都有与之对应的值value，value可以任意类型对象。树的结构中(结点)除了需要存储key还要存储对应的value，增/删/查还是以key为关键字⾛⼆叉搜索树的规则进⾏⽐较，可以快速查找到key对应的value。key/value的搜索场景实现的⼆叉树搜索树⽀持修改，但是不⽀持修改key，修改key破坏搜索树结构了，可以修改value

key-value二叉搜索树

下面我们实现一下key-value二叉搜索树，逻辑是完全一致的，注意存储的节点升级为key和value都要存储，查找时按key查找，value支持修改。具体细节我们就不在介绍了，可以参考以下代码实现。注意我们可以将这两种二叉树放在不同的命名空间里

namespace key_val
{
	template<class K, class V>
	class BSTreeNode
	{
		template<class K, class V>
		friend class BSTree;

		template<class K, class V>
		friend ostream& operator<<(ostream& cout, BSTreeNode<K, V>* node);
	public:
		BSTreeNode(const K& key = K(), const V& val = V(), BSTreeNode* left = nullptr, BSTreeNode* right = nullptr)
			:key(key),
			val(val),
			left(left),
			right(right)
		{}

		V getVal()
		{
			return this->val;
		}

	private:
		K key = K();
		V val = V();
		BSTreeNode<K, V>* left = nullptr;
		BSTreeNode<K, V>* right = nullptr;
	};

	template<class K, class V>
	ostream& operator<<(ostream& cout, BSTreeNode<K, V>* node)
	{
		if (node != nullptr)
			cout << node->key << ':' << node->val;
		return cout;
	}


	template<class K, class V>
	class BSTree
	{
		typedef BSTreeNode<K, V> Node;
	public:
		BSTree(Node* root = nullptr)
			:root(root)
		{}

		~BSTree()
		{
			clear();
		}

		BSTree(const BSTree& tree)
		{
			this->root =  assign(tree.root);
		}

		BSTree& operator=(BSTree tree)
		{
			//swap(*this, tree); 
			swap(this->root, tree.root);
			return *this;
		}

		Node* assign( Node* n2)
		{
			if (n2 == nullptr)
				return nullptr;
			Node* n = new Node(n2->key,n2->val);
			n->left = assign(n2->left);
			n->right = assign(n2->right);
			return n;
		}

		void clear()
		{
			_clear(this->root);
		}

		bool insert(const K& key, const V& val)
		{
			if (root == nullptr)
			{
				root = new Node(key, val);
				return true;
			}
			Node* ptr = root;
			Node* chi = root;
			while (chi != nullptr)
			{
				if (key > chi->key)
				{
					ptr = chi;
					chi = chi->right;
				}
				else if (key < chi->key)
				{
					ptr = chi;
					chi = chi->left;
				}
				else
				{
					chi->val = val;
					return true;
				}
			}
			if (key < ptr->key)
			{
				ptr->left = new Node(key, val);
			}
			else
			{
				ptr->right = new Node(key, val);
			}
			return true;
		}

		void midOrder()
		{
			_midOrder(this->root);
			cout << endl;
		}

		Node* isExistence(const K& key)
		{
			Node* cut = this->root;
			while (cut != nullptr)
			{
				if (key > cut->key)
				{
					cut = cut->right;
				}
				else if (key < cut->key)
				{
					cut = cut->left;
				}
				else
					return cut;
			}
			return nullptr;
		}

		bool del(const K& key)
		{
			Node* par = nullptr;
			Node* chi = this->root;
			while (chi != nullptr)
			{
				if (key > chi->key)
				{
					par = chi;
					chi = chi->right;
				}
				else if (key < chi->key)
				{
					par = chi;
					chi = chi->left;
				}
				else
				{
					if (chi->left == nullptr)
					{
						if (par == nullptr)
						{
							root = root->right;
						}
						else
						{
							if (par->left == chi)
							{
								par->left = chi->right;
							}
							else {
								par->right = chi->right;
							}
						}
						delete chi;
					}
					else if (chi->right == nullptr)
					{
						if (par == nullptr)
						{
							root = root->left;
						}
						else
						{
							if (par->left == chi)
							{
								par->left = chi->left;
							}
							else {
								par->right = chi->left;
							}
						}
						delete chi;
					}
					else
					{
						Node* ptr = chi;
						Node* cut = chi->right;
						if (cut != nullptr)
						{
							while (cut->left != nullptr)
							{
								ptr = cut;
								cut = cut->left;
							}
							chi->key = cut->key;
							if (ptr->left == cut)
							{
								ptr->left = cut->right;
							}
							else {
								ptr->right = cut->right;
							}
						}
						else
						{
							if (par->left == chi)
							{
								par->left = ptr->left;
							}
							else
							{
								par->right = ptr->left;

							}
						}

						delete cut;
					}
					return true;
				}
			}
			return false;
		}

		

	private:
		Node* root = nullptr;

		void _midOrder(Node* root)
		{
			if (root == nullptr)
			{
				return;
			}
			_midOrder(root->left);
			cout << root << " ";
			_midOrder(root->right);
		}

		void _clear(Node* root)
		{
			if (root == nullptr)
			{
				return;
			}
			_clear(root->left);
			_clear(root->right);
			delete root;
		}

	};

}

结语

以上便是今天的全部内容。如果有帮助到你，请给我一个免费的赞。

因为这对我很重要。

编程世界的小比特，希望与大家一起无限进步。

感谢阅读！