3. **二叉搜索树的删除

• 情况b：删除该结点且使被删除节点的双亲结点指向被删除节点的左孩子结点--直接删除
• 情况c：删除该结点且使被删除节点的双亲结点指向被删除结点的右孩子结点--直接删除
• 情况d：在它的右子树中寻找中序下的第一个结点(关键码最小)，用它的值填补到被删除节点

 1.3 二叉搜索树的实现

template<class T>
struct BSTNode
{
	BSTNode(const T& data = T())
		: _pLeft(nullptr), _pRight(nullptr), _data(data)
	{}
	BSTNode* _pLeft;
	BSTNode* _pRight;
	T _data;
};
template<class T>
class BSTree
{
	typedef BSTNode Node;
	typedef Node* PNode;
public:
	BSTree() : _pRoot(nullptr)
	{}
	//自己实现，与二叉树的销毁类似
	~BSTree();
	// 根据二叉搜索树的性质查找：找到值为data的节点在二叉搜索树中的位置
	PNode Find(const T& data);
	bool Insert(const T& data)
	{
		// 如果树为空，直接插入
		if (nullptr == _pRoot)
		{
			_pRoot = new Node(data);
			return true;
		}
		// 按照二叉搜索树的性质查找data在树中的插入位置
		PNode pCur = _pRoot;
		// 记录pCur的双亲，因为新元素最终插入在pCur双亲左右孩子的位置
		PNode pParent = nullptr;
		while (pCur)
		{
			pParent = pCur;
			if (data < pCur->_data)
				pCur = pCur->_pLeft;
			else if (data > pCur->_data)
				pCur = pCur->_pRight;  // 元素已经在树中存在
			else
				return false;
		}
		// 插入元素
		pCur = new Node(data);
		if (data < pParent->_data)
			pParent->_pLeft = pCur;
		else
			pParent->_pRight = pCur;
		return true;
	}
	bool Erase(const T& data)
	{
		// 如果树为空，删除失败
		if (nullptr == _pRoot)
			return false;
		// 查找在data在树中的位置
		PNode pCur = _pRoot;
		PNode pParent = nullptr;
		while (pCur)
		{
			if (data == pCur->_data)
				break;
			else if (data < pCur->_data)
			{
				pParent = pCur;
				pCur = pCur->_pLeft;
			}
			else
			{
				pParent = pCur;
				pCur = pCur->_pRight;
			}
		}
		// data不在二叉搜索树中，无法删除
		if (nullptr == pCur)
			return false;
		// 分以下情况进行删除，同学们自己画图分析完成
		if (nullptr == pCur->_pRight)
		{
			// 当前节点只有左孩子或者左孩子为空---可直接删除
		}
		else if (nullptr == pCur->_pRight)
		{
			// 当前节点只有右孩子---可直接删除
		}
		else
		{
			// 当前节点左右孩子都存在，直接删除不好删除，可以在其子树中找一个替代结点，
			//比如：
				/* 找其左子树中的最大节点，即左子树中最右侧的节点，或者在其右子树中最小的节
				点，即右子树中最小的节点*/
				// 替代节点找到后，将替代节点中的值交给待删除节点，转换成删除替代节点
		}
		return true;
	}
	//自己实现
	void InOrder();
private:
	PNode _pRoot;
};

1.4 二叉搜索树的应用

1. K 模型： K 模型即只有 key 作为关键码，结构中只需要存储 Key 即可，关键码即为需要搜索到

的值 。

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

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

2. KV 模型：每一个关键码 key ，都有与之对应的值 Value ，即 的键值对 。该种方

式在现实生活中非常常见：

• 比如英汉词典就是英文与中文的对应关系，通过英文可以快速找到与其对应的中文，英文单词与其对应的中文就构成一种键值对；
• 再比如统计单词次数，统计成功后，给定单词就可快速找到其出现的次数，单词与其出现次数就是就构成一种键值对。

// 改造二叉搜索树为KV结构
template<class K, class V>
struct BSTNode
{
	BSTNode(const K& key = K(), const V& value = V())
		: _pLeft(nullptr), _pRight(nullptr), _key(key), _Value(value)
	{}
	BSTNode* _pLeft;
	BSTNode* _pRight;
	K _key;
	V _value
};
template<class K, class V>
class BSTree
{
	typedef BSTNode Node;
	typedef Node* PNode;
public:
	BSTree() : _pRoot(nullptr) {}
	PNode Find(const K& key);
	bool Insert(const K& key, const V& value)
		bool Erase(const K& key)
private:
	PNode _pRoot;
};
void TestBSTree3()
{
	// 输入单词，查找单词对应的中文翻译
	BSTree dict;
	dict.Insert("string", "字符串");
	dict.Insert("tree", "树");
	dict.Insert("left", "左边、剩余");
	dict.Insert("right", "右边");
	dict.Insert("sort", "排序");
	// 插入词库中所有单词
	string str;
	while (cin >> str)
	{
		BSTreeNode* ret = dict.Find(str);
		if (ret == nullptr)
		{
			cout << "单词拼写错误，词库中没有这个单词:" << str << endl;
		}
		else
		{
			cout << str << "中文翻译:" << ret->_value << endl;
		}
	}
}
void TestBSTree4()
{
	// 统计水果出现的次数
	string arr[] = { "苹果", "西瓜", "苹果", "西瓜", "苹果", "苹果", "西瓜",
   "苹果", "香蕉", "苹果", "香蕉" };
	BSTreeint> countTree;
	for (const auto& str : arr)
	{
		// 先查找水果在不在搜索树中
		// 1、不在，说明水果第一次出现，则插入<水果, 1>
		// 2、在，则查找到的节点中水果对应的次数++
		//BSTreeNode* ret = countTree.Find(str);
		auto ret = countTree.Find(str);
		if (ret == NULL)
		{
			countTree.Insert(str, 1);
		}
		else
		{
			ret->_value++;
		}
	}
	countTree.InOrder();
}

1.5 二叉搜索树的性能分析

插入和删除操作都必须先查找，查找效率代表了二叉搜索树中各个操作的性能。 对有 n 个结点的二叉搜索树，若每个元素查找的概率相等，则二叉搜索树平均查找长度是结点在二 叉搜索树的深度的函数，即结点越深，则比较次数越多。 但对于同一个关键码集合，如果各关键码插入的次序不同，可能得到不同结构的二叉搜索树：

 

最优情况下，二叉搜索树为完全二叉树 ( 或者接近完全二叉树 ) ，其平均比较次数为： $log_2 N$

最差情况下，二叉搜索树退化为单支树 ( 或者类似单支 ) ，其平均比较次数为： $\frac{N}{2}$

问题：如果退化成单支树，二叉搜索树的性能就失去了。那能否进行改进，不论按照什么次序插入关键码，二叉搜索树的性能都能达到最优？那么我们后续章节学习的AVL 树和红黑树就可以上场了。