目录

二叉搜索树的概念

二叉树的实现

结点类 

函数接口总览

实现二叉树

二叉搜索树的应用

K模型

KV模型

二叉搜索树的性能分析

二叉搜索树的概念

    二叉搜索树（Binary Search Tree，简称BST）是一种特殊的二叉树，其具有以下几个性质：

1. 每个节点至多有两个子节点：分别称为左子节点和右子节点。
2. 左子树上的所有节点的值都小于根节点的值。
3. 右子树上的所有节点的值都大于根节点的值。
4. 每个节点的左右子树也都是二叉搜索树。

这些性质确保了在二叉搜索树中进行查找、插入和删除操作具有良好的性能。具体地，这些操作在平均情况下的时间复杂度为 O(logn)，其中 n 是树中节点的数量。不过，在最坏情况下（树退化成链表），时间复杂度可能会降为 O(n)。

下面是一个二叉搜索树的示例：

在这个二叉搜索树中：

• 根节点是 8。
• 根节点的左子树包含节点 3、1、6、4 和 7，这些节点的值都小于 8。
• 根节点的右子树包含节点 10、14 和 13，这些节点的值都大于 8。

二叉树的实现

结点类 

要实现二叉搜索树，我们首先需要实现一个结点类：

• 结点类当中包含三个成员变量：结点值、左指针、右指针。
• 结点类当中只需实现一个构造函数即可，用于构造指定结点值的结点。

template<class K>
struct BSTreeNode
{
	K _key;                 // 结点值
	BSTreeNode<K>* _left;   // 左指针
	BSTreeNode<K>* _right;  // 右指针

	// 构造函数
	BSTreeNode(const K& key = K())
		: _key(key)
		, _left(nullptr)
		, _right(nullptr)
	{}
};

函数接口总览

//二叉搜索树
template<class K>
class BSTree
{
	typedef BSTreeNode<K> Node;
public:
	//构造函数
	BSTree();

	//拷贝构造函数
	BSTree(const BSTree<K>& t);

	//赋值运算符重载函数
	BSTree<K>& operator=(BSTree<K> t);

	//析构函数
	~BSTree();

	//插入函数
	bool Insert(const K& key);

	//删除函数
	bool Erase(const K& key);

	//查找函数
	Node* Find(const K& key);

	//中序遍历
	void InOrder();
private:
	Node* _root; //指向二叉搜索树的根结点
};

    为了在实现其他接口的过程中方便随时检查，最好实现一个二叉搜索树的中序遍历接口，当我们对二叉搜索树进行一次操作后，可以调用中序遍历接口对二叉搜索树进行遍历，若二叉搜索树进行操作后的遍历结果仍为升序，则可以初步判断所实现的接口是正确。

//中序遍历的子函数
void _InOrder(Node* root)
{
	if (root == nullptr)
		return;
	_InOrder(root->_left); //遍历左子树
	cout << root->_key << " "; //遍历根结点
	_InOrder(root->_right); //遍历右子树
}
//中序遍历
void InOrder()
{
	_InOrder(_root);
	cout << endl;
}

实现二叉树

代码如下:

// 定义二叉搜索树模板类
template<class K>
class BSTree
{
private:
	BSTreeNode<K>* _root;  // 树的根结点

	// 辅助函数：递归拷贝树
	BSTreeNode<K>* CopyTree(BSTreeNode<K>* root)
	{
		if (root == nullptr)
			return nullptr;

		BSTreeNode<K>* newNode = new BSTreeNode<K>(root->_key);
		newNode->_left = CopyTree(root->_left);
		newNode->_right = CopyTree(root->_right);
		return newNode;
	}

	// 辅助函数：递归销毁树
	void DestroyTree(BSTreeNode<K>* root)
	{
		if (root != nullptr)
		{
			DestroyTree(root->_left);   // 递归销毁左子树
			DestroyTree(root->_right);  // 递归销毁右子树
			delete root;                // 删除当前结点
		}
	}

	// 辅助函数：递归插入
	BSTreeNode<K>* InsertRecursive(BSTreeNode<K>* root, const K& key)
	{
		if (root == nullptr)
		{
			return new BSTreeNode<K>(key);  // 找到插入位置后创建新结点
		}
		if (key < root->_key)
		{
			root->_left = InsertRecursive(root->_left, key);  // 递归插入左子树
		}
		else if (key > root->_key)
		{
			root->_right = InsertRecursive(root->_right, key); // 递归插入右子树
		}
		return root;
	}

	// 辅助函数：递归删除
	BSTreeNode<K>* DeleteRecursive(BSTreeNode<K>* root, const K& key)
	{
		if (root == nullptr)
			return root;

		if (key < root->_key)
		{
			root->_left = DeleteRecursive(root->_left, key);  // 在左子树中删除
		}
		else if (key > root->_key)
		{
			root->_right = DeleteRecursive(root->_right, key); // 在右子树中删除
		}
		else
		{
			if (root->_left == nullptr)
			{
				BSTreeNode<K>* temp = root->_right;
				delete root;  // 删除当前结点
				return temp;
			}
			else if (root->_right == nullptr)
			{
				BSTreeNode<K>* temp = root->_left;
				delete root;  // 删除当前结点
				return temp;
			}
			BSTreeNode<K>* temp = MinValueNode(root->_right);  // 找到右子树中最小值结点
			root->_key = temp->_key;  // 用右子树中最小值替换当前结点
			root->_right = DeleteRecursive(root->_right, temp->_key);  // 删除右子树中的最小值结点
		}
		return root;
	}

	// 辅助函数：找到最小值结点
	BSTreeNode<K>* MinValueNode(BSTreeNode<K>* node)
	{
		BSTreeNode<K>* current = node;
		while (current && current->_left != nullptr)
		{
			current = current->_left;  // 找到最左端的结点即为最小值结点
		}
		return current;
	}

	// 辅助函数：递归查找
	BSTreeNode<K>* SearchRecursive(BSTreeNode<K>* root, const K& key) const
	{
		if (root == nullptr || root->_key == key)
			return root;

		if (key < root->_key)
			return SearchRecursive(root->_left, key);  // 在左子树中查找

		return SearchRecursive(root->_right, key); // 在右子树中查找
	}

public:
	// 构造函数，初始化空树
	BSTree()
		: _root(nullptr)
	{}

	// 拷贝构造函数
	BSTree(const BSTree<K>& other)
		: _root(nullptr)
	{
		_root = CopyTree(other._root);  // 深拷贝另一棵树
	}

	// 赋值运算符重载函数
	BSTree<K>& operator=(const BSTree<K>& other)
	{
		if (this != &other)
		{
			DestroyTree(_root);  // 销毁当前树
			_root = CopyTree(other._root);  // 深拷贝另一棵树
		}
		return *this;
	}

	// 析构函数，销毁树
	~BSTree()
	{
		DestroyTree(_root);  // 递归销毁树中所有结点
	}

	// 插入函数（非递归）
	void InsertIterative(const K& key)
	{
		if (_root == nullptr)
		{
			_root = new BSTreeNode<K>(key);  // 插入根结点
			return;
		}
		BSTreeNode<K>* parent = nullptr;
		BSTreeNode<K>* current = _root;
		while (current != nullptr)
		{
			parent = current;
			if (key < current->_key)
			{
				current = current->_left;  // 移动到左子结点
			}
			else if (key > current->_key)
			{
				current = current->_right; // 移动到右子结点
			}
			else
			{
				return;  // 不插入重复值
			}
		}
		if (key < parent->_key)
		{
			parent->_left = new BSTreeNode<K>(key);  // 插入左子结点
		}
		else
		{
			parent->_right = new BSTreeNode<K>(key); // 插入右子结点
		}
	}

	// 插入函数（递归）
	void Insert(const K& key)
	{
		_root = InsertRecursive(_root, key);  // 调用递归插入函数
	}

	// 删除函数（非递归）
	void DeleteIterative(const K& key)
	{
		BSTreeNode<K>* parent = nullptr;
		BSTreeNode<K>* current = _root;
		while (current != nullptr && current->_key != key)
		{
			parent = current;
			if (key < current->_key)
			{
				current = current->_left;  // 移动到左子结点
			}
			else
			{
				current = current->_right; // 移动到右子结点
			}
		}
		if (current == nullptr)
			return;

		if (current->_left == nullptr || current->_right == nullptr)
		{
			BSTreeNode<K>* newCurrent;
			if (current->_left == nullptr)
			{
				newCurrent = current->_right;
			}
			else
			{
				newCurrent = current->_left;
			}

			if (parent == nullptr)
			{
				_root = newCurrent;  // 删除根结点
			}
			else if (current == parent->_left)
			{
				parent->_left = newCurrent;  // 删除左子结点
			}
			else
			{
				parent->_right = newCurrent; // 删除右子结点
			}
			delete current;
		}
		else
		{
			BSTreeNode<K>* p = nullptr;
			BSTreeNode<K>* temp;
			temp = current->_right;
			while (temp->_left != nullptr)
			{
				p = temp;
				temp = temp->_left;
			}
			if (p != nullptr)
			{
				p->_left = temp->_right;
			}
			else
			{
				current->_right = temp->_right;
			}
			current->_key = temp->_key;
			delete temp;
		}
	}

	// 删除函数（递归）
	void Delete(const K& key)
	{
		_root = DeleteRecursive(_root, key);  // 调用递归删除函数
	}

	// 查找函数（非递归）
	BSTreeNode<K>* SearchIterative(const K& key) const
	{
		BSTreeNode<K>* current = _root;
		while (current != nullptr && current->_key != key)
		{
			if (key < current->_key)
			{
				current = current->_left;  // 移动到左子结点
			}
			else
			{
				current = current->_right; // 移动到右子结点
			}
		}
		return current;  // 返回找到的结点或 nullptr
	}

	// 查找函数（递归）
	BSTreeNode<K>* Search(const K& key) const
	{
		return SearchRecursive(_root, key);  // 调用递归查找函数
	}
};

用法和预期效果:

1. 构造函数

   • 用法：BSTree<int> tree;
   • 预期效果：创建一个空的二叉搜索树。

2. 拷贝构造函数

   • 用法：BSTree<int> tree2 = tree1;
   • 预期效果：深拷贝tree1，创建一个新的二叉搜索树tree2，其结构和tree1相同。

3. 赋值运算符重载函数

   • 用法：tree2 = tree1;
   • 预期效果：深拷贝tree1到tree2，覆盖tree2原来的内容。

4. 析构函数

   • 用法：当树对象生命周期结束时自动调用。
   • 预期效果：递归销毁树中所有结点，释放内存。

5. 插入函数（非递归）

   • 用法：tree.InsertIterative(10);
   • 预期效果：在树中插入值为10的结点。

6. 插入函数（递归）

   • 用法：tree.Insert(10);
   • 预期效果：在树中插入值为10的结点。

7. 删除函数（非递归）

   • 用法：tree.DeleteIterative(10);
   • 预期效果：在树中删除值为10的结点。

8. 删除函数（递归）

   • 用法：tree.Delete(10);
   • 预期效果：在树中删除值为10的结点。

9. 查找函数（非递归）

   • 用法：BSTreeNode<int>* node = tree.SearchIterative(10);
   • 预期效果：在树中查找值为10的结点，返回指向该结点的指针，如果未找到则返回nullptr。

10. 查找函数（递归）

    • 用法：BSTreeNode<int>* node = tree.Search(10);
    • 预期效果：在树中查找值为10的结点，返回指向该结点的指针，如果未找到则返回nullptr。

二叉搜索树的应用

二叉搜索树（BST）是一种重要的数据结构，广泛应用于各种算法和系统中。以下是一些常见的应用：

1. 符号表：在编译器中，二叉搜索树可以用来实现符号表，用于存储变量和函数的名称及其属性。
2. 字典：二叉搜索树可以用来实现字典（例如键值对存储），支持高效的插入、删除和查找操作。
3. 优先队列：可以使用二叉搜索树来实现优先队列，其中元素按照优先级排列，支持快速的插入和删除操作。
4. 数据库索引：在数据库系统中，二叉搜索树可以用作索引结构，以加速查询操作。
5. 排序和搜索：二叉搜索树天然地支持中序遍历，从而可以对元素进行排序和高效搜索。

K模型

    K模型是基于二叉搜索树的一种简化形式，主要用于处理单个键（key）的存储和查询。每个结点只包含一个键，不涉及值（value）。 

比如：给定一个单词，判断该单词是否拼写正确。具体方式如下：

1. 以单词集合中的每个单词作为key，构建一棵二叉搜索树。
2. 在二叉搜索树中检索该单词是否存在，存在则拼写正确，不存在则拼写错误。

KV模型

    KV模型是二叉搜索树的扩展形式，用于处理键值对（key-value）的存储和查询。每个结点包含一个键和一个值。 

比如：英汉词典就是英文与中文的对应关系，即<word, Chinese>就构成一种键值对。具体方式如下：

以<单词, 中文含义>为键值对，构建一棵二叉搜索树。注意：二叉搜索树需要进行比较，键值对比较时只比较key。
查询英文单词时，只需给出英文单词就可以快速找到与其对应的中文含义。

二叉搜索树的性能分析

时间复杂度

1. 查找、插入和删除

   • 最优情况：当树是平衡的（完全平衡二叉树），时间复杂度为O(log n)。
   • 最坏情况：当树退化成链表（每个结点只有一个子结点），时间复杂度为O(n)。

2. 遍历

   • 中序遍历、先序遍历、后序遍历的时间复杂度均为O(n)，因为需要访问每个结点。

空间复杂度

1. 空间使用

   • 空间复杂度为O(n)，n为树中的结点数。

2. 递归调用栈

   • 在最坏情况下（树退化成链表），递归调用栈的空间复杂度为O(n)。

平衡性

1. 平衡二叉树：如AVL树、红黑树等，保证在最坏情况下也能达到O(log n)的时间复杂度。
2. 普通二叉搜索树：如果输入数据是随机的，树大概率接近平衡。但如果输入数据是有序的（或接近有序），树可能退化为链表，导致性能下降。

性能优化

1. 自平衡二叉搜索树：如AVL树、红黑树、Splay树等，通过自动调整树的结构，保证树的平衡，从而提升性能。
2. B树和B+树：特别适用于数据库索引，支持高效的磁盘存取操作。
3. 散列：对于一些应用，哈希表（Hash Table）可以提供更快的查找、插入和删除操作，但不适用于需要排序的场景。

总结

二叉搜索树（BST）是一种基础而重要的数据结构，广泛应用于符号表、字典、优先队列和数据库索引等场景。K模型和KV模型分别处理集合和字典的需求。BST的性能在很大程度上取决于树的平衡性，使用自平衡树可以保证最坏情况下的性能。此外，对于特定应用场景，选择合适的数据结构（如B树或哈希表）也非常重要。