C++之二叉搜索树及其实现

发布于：2025-06-24 ⋅ 阅读:(13) ⋅ 点赞:(0)

二叉搜索树


在这里插入图片描述

搜索二叉树（Binary Search Tree，简称BST）是一种基础且重要的数据结构，它在查找、插入和删除操作上具有高效性。本文将围绕搜索二叉树的原理，结合C++代码实现，深入探讨这一数据结构的核心特性与具体实现。

一.二叉搜索树的基本概念

二叉搜索树（Binary Search Tree，简称 BST）是一种特殊的二叉树，它满足以下性质：
对于树中的每个节点，其左子树中所有节点的值都小于该节点的值
对于树中的每个节点，其右子树中所有节点的值都大于该节点的值
左右子树也分别是二叉搜索树
这种特性使得二叉搜索树在查找、插入和删除操作上具有较高的效率，平均时间复杂度为 O (log n)。
在这里插入图片描述

二.二叉搜索树的性能分析

最优情况下，⼆叉搜索树为完全⼆叉树(或者接近完全⼆叉树)，其⾼度为：log2 N
最差情况下，⼆叉搜索树退化为单⽀树(或者类似单⽀)，其⾼度为：N
所以综合⽽⾔⼆叉搜索树增删查改时间复杂度为：O(N)

⼆分查找也可以实现O(log2N) 级别的查找效率，但是⼆分查找有两⼤缺陷：

  1. 需要存储在⽀持下标随机访问的结构中，并且有序。

  2. 插⼊和删除数据效率很低，因为存储在下标随机访问的结构中，插⼊和删除数据⼀般需要挪动数据。

这⾥也就体现出了平衡⼆叉搜索树的价值。

三.二叉搜索树的实现

搜索二叉树的基本概念与特性

搜索二叉树是一种特殊的二叉树，它满足以下性质：

  • 若任意节点的左子树不为空，则左子树上所有节点的值均小于该节点的值
  • 若任意节点的右子树不为空，则右子树上所有节点的值均大于该节点的值
  • 任意节点的左、右子树也分别为搜索二叉树
  • 没有键值相等的节点

这些性质使得搜索二叉树在进行查找操作时具有天然的优势，我们可以利用节点值的大小关系快速缩小查找范围，类似于有序数组的二分查找。

搜索二叉树的节点结构设计

首先来看搜索二叉树的节点结构实现：

template<class K>
struct BSTreeNode
{
	K _key;
	BSTNode<K>* _left;
	BSTNode<K>* _right;
	BSTNode(const K& key)
		:_key(key)
		, _left(nullptr)
		, _right(nullptr)
	{
	}
};
  • _key：节点的关键字，用于比较和查找
  • _left：指向左子节点的指针
  • _right：指向右子节点的指针
  • 构造函数：初始化节点的关键字，并将左右子节点指针置为nullptr

节点采用模板设计，使得该结构可以存储任意类型的数据，只要该类型支持比较运算。

搜索二叉树的类结构与核心操作

类的基本结构

template<class K>
class BSTree
{
	typedef BSTreeNode<K> Node;
public:
	// 构造、拷贝构造、赋值运算符、析构函数
	BSTree() = default;
	BSTree(const BSTree<K>& t);
	BSTree<K>& operator=(BSTree<K> t);
	~BSTree();
	
	// 核心操作
	bool Insert(const K& key);
	bool Find(const K& key);
	bool Erase(const K& key);
	
	// 中序遍历
	void InOrder();
private:
	// 中序遍历的递归辅助函数
	void _InOrder(Node* root);
	// 拷贝构造的递归辅助函数
	Node* Copy(Node* root);
	// 析构函数的递归辅助函数
	void Destory(Node* root);
private:
	Node* _root = nullptr;
};

构造与析构函数

  • 默认构造函数：使用C++11的default关键字，生成默认的构造函数，将根节点初始化为nullptr
  • 拷贝构造函数：通过递归调用Copy函数实现深拷贝，确保新对象与原对象相互独立
  • 赋值运算符：采用"拷贝交换"技术，先创建传入对象的副本，然后交换当前对象与副本的根节点指针，保证异常安全性
  • 析构函数：调用Destory函数递归释放所有节点的内存，防止内存泄漏

插入操作（Insert）

插入操作是构建搜索二叉树的基础，其实现逻辑如下：

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

插入操作的步骤：

  1. 如果树为空，直接创建根节点
  2. 否则从根节点开始，比较当前节点值与插入值的大小：
    • 若当前节点值小于插入值，向右转
    • 若当前节点值大于插入值，向左转
    • 若相等，说明键值已存在，插入失败
  3. 找到合适的插入位置（空指针处）后，创建新节点并连接到父节点

查找操作（Find）

查找是搜索二叉树的核心功能，利用树的特性可以高效地定位目标节点：

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; // 未找到目标节点
}

查找操作的逻辑非常直观，与插入操作类似：

  • 从根节点开始，比较当前节点值与目标值
  • 根据大小关系决定向左还是向右查找
  • 若找到相等的值，返回true
  • 若遍历完所有可能的节点仍未找到，返回false

删除操作（Erase）

删除操作是搜索二叉树中最复杂的操作，需要考虑多种情况：

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)
			{
				// 情况1：左子树为空
				if (cur == _root)
				{
					_root = _root->_right;
				}
				if (parent->_right == cur)
				{
					parent->_right = cur->_right;
				}
				else
				{
					parent->_left = cur->_right;
				}
				delete cur;
			}
			else if(cur->_right == nullptr)
			{
				// 情况2：右子树为空
				if (cur == _root)
				{
					_root = _root->_left;
				}
				if (parent->_right == cur)
				{
					parent->_right = cur->_left;
				}
				else
				{
					parent->_left = cur->_left;
				}
				delete cur;
			}
			else
			{
				// 情况3：左右子树都不为空
				Node* pMinRight = cur;
				Node* minRight = cur->_right;
				while (minRight->_left)
				{
					pMinRight = minRight;
					minRight = minRight->_left;
				}
				// 找到右子树中的最小节点（最左节点）
				swap(minRight->_key, cur->_key);
				// 删除右子树中的最小节点
				if (pMinRight->_left == minRight)
				{
					pMinRight->_left = minRight->_right;
				}
				else
				{
					pMinRight->_right = minRight->_right;
				}
				delete minRight;
			}
			return true;
		}
	}
	return false; // 未找到要删除的节点
}

删除操作需要处理三种情况：

  1. 左子树为空：直接用右子树替换当前节点
  2. 右子树为空：直接用左子树替换当前节点
  3. 左右子树都不为空：
    • 找到当前节点右子树中的最小节点（最左节点）
    • 将该最小节点的值与当前节点的值交换
    • 删除原来的最小节点（此时该节点最多只有一个右子树）

这种处理方式确保了删除节点后，搜索二叉树的性质仍然保持。

中序遍历（InOrder）

中序遍历可以将搜索二叉树中的节点按从小到大的顺序输出，这是搜索二叉树的一个重要特性：

void InOrder()
{
	_InOrder(_root);
	cout << endl;
}

private:
void _InOrder(Node* root)
{
	if (root == nullptr)
	{
		return;
	}
	_InOrder(root->_left);
	cout << root->_key << ' ';
	_InOrder(root->_right);
}

中序遍历的顺序是：左子树 → 根节点 → 右子树，对于搜索二叉树来说，中序遍历的结果正好是有序的。

搜索二叉树的性能分析

时间复杂度

  • 查找操作：在平均情况下，时间复杂度为O(log n)，其中n是树中节点的数量。这是因为每次比较都可以将查找范围缩小一半，类似于二分查找。
  • 插入操作：平均时间复杂度也是O(log n)，因为插入操作需要先找到合适的位置，这与查找操作的过程类似。
  • 删除操作：平均时间复杂度同样为O(log n)，删除操作的主要时间消耗在查找节点和处理不同情况上。

空间复杂度

  • 搜索二叉树的空间复杂度为O(n)，其中n是树中节点的数量，因为需要为每个节点分配内存空间。

最坏情况

搜索二叉树的性能依赖于树的高度，在最坏情况下（如插入的节点是有序的），搜索二叉树会退化为链表，此时所有操作的时间复杂度都会退化为O(n)。为了避免这种情况，可以使用平衡二叉树（如AVL树、红黑树等）来保证树的高度始终保持在O(log n)。

搜索二叉树的应用场景

搜索二叉树在实际应用中非常广泛，以下是一些常见的应用场景：

  • 字典和映射：可以用搜索二叉树实现字典结构，提供快速的查找、插入和删除操作。
  • 数据库索引：数据库中的索引结构通常基于搜索树的变种，如B树、B+树等，以支持高效的查询操作。
  • 编译器符号表：编译器在处理变量和函数声明时，需要快速查找和插入符号，搜索二叉树是一种合适的数据结构。
  • 文件系统目录结构：文件系统中的目录结构可以用搜索树来组织，以便快速查找文件和目录。
  • 优先队列：虽然优先队列更常用堆来实现，但搜索二叉树也可以用于实现优先队列。

总体代码实现

using namespace std;
template<class K>

struct BSTreeNode

{
	K _key;
	BSTNode<K>* _left;
	BSTNode<K>* _right;
	BSTNode(const K& key)
		:_key(key)
		, _left(nullptr)
		, _right(nullptr)
	{
	}
};


template<class K>
class BSTree
{
	typedef BSTreeNode<K> Node;
public:
	BSTree() = default;
	BSTree(const BSTree<K>& t)
	{
		_root = Copy(t._root);
	}
	BSTree<K>& operator=(BSTree<K> t)
	{
		swap(_root, t._root);
		return *this;
	}
	~BSTree()
	{
		Destory(_root);
		_root = nullptr;
	}
	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 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 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 = _root->_right;
					}
					if (parent->_right == cur)
					{
						parent->_right = cur->_right;
					}
					else
					{
						parent->_left = cur->_right;
					}
					delete cur;
				}
				else if(cur->_right == nullptr)
				{
					if (cur == _root)
					{
						_root = _root->_left;
					}
					if (parent->_right == cur)
					{
						parent->_right = cur->_left;
					}
					else
					{
						parent->_left = cur->_left;
					}
					delete cur;
				}
				else
				{
					Node* pMinRight = cur;
					Node* minRight = cur->_right;
					while (minRight->_left)
					{
						pMinRight = minRight;
						minRight = minRight->_left;
					}
					swap(minRight->_key, cur->_key);
					if (pMinRight->_left == minRight)
					{
						pMinRight->_left = minRight->_right;
					}
					else
					{
						pMinRight->_right = minRight->_right;
					}
					delete minRight;
				}
				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);
	}
	Node* Copy(Node* root)
	{
		if (root == nullptr)
			return;
		Node* copy = new Node(root->_key);
		copy->_left = Copy(root->_left);
		copy->_right = Copy(root->_right);
		return copy;
	}
	void Destory(Node* root)
	{
		if (root == nullptr)
		{
			return;
		}

		Destory(root->_left);
		Destory(root->_right);
		delete root;
	}
private:
	Node* _root = nullptr;
};

网站公告

今日签到

点亮在社区的每一天
去签到

热门文章

最新发布