本文将介绍二叉搜索树，将为后面set与map的学习作铺垫。
概念
二叉搜索树的概念（特征）
二叉搜索树又称二叉排序树，它或是一颗空树，或者是其左子树上所有孩子结点的值小于根节点的值，且右子树上所有孩子结点的值大于根节点的值同时，其根节点左右子树也分别为二叉搜索树。
比如如下所示的二叉树就是一颗二叉搜索树，int a [] = {5,3,4,1,7,8,2,6,0,9};
二叉搜索树的性能分析
在之前数据结构中我们知道分析一种结构要分析其时间复杂度以及空间复杂度。那么我们来分析一下二叉搜索树查找的效率，首先由于二叉搜索树的特征，对有n个结点的二叉搜索树，若每个元素查找的概率相等，则二叉搜索树平均查找长度是结点在二叉搜索树的深度的函数，即结点越深，则比较次数越多。
但对于同一个关键码集合，如果各关键码插入的次序不同，可能得到不同结构的二叉搜索树：
如上图所示，最优情况下，二叉搜索树为完全二叉树，其平均比较次数为：log2N;最差情况下，二叉搜索树退化为单支树，其平均比较次数为：N/2。
操作
查找
由于搜索二叉树的特征，其查找无需遍历整棵树，只要通过key值的比较即可快速确定要找的结点：
插入
二叉搜索树的插入操作并不算复杂。具体过程如下：
删除
二叉树的删除较为复杂，具体要分为以下几种情况：
- 空树
- 叶子结点（没有孩子结点）
- 只有一个孩子
- 有两个孩子
首先，对于第一种情况，即空树，返回false即可；其次，对于第二种情况，直接删除叶子结点；然后，对于第三种情况，若要删除的结点只有左孩子结点，则删除该结点且使被删除节点的双亲结点指向被删除节点的左孩子结点，若要删除的结点只有右孩子结点，则删除该结点且使被删除节点的双亲结点指向被删除结点的右孩子结点。
最后，对于第四种情况，我们采用替代法删除结点，即找到该节点左子树中key值最大的结点或者找到其右子树key值最小的结点，把该节点的值赋给要删除的结点，然后将这个替代的结点删除即可。
模拟实现
这里我们实现key-value二叉搜索树模型。
搜索二叉树类的构建
在实现二叉搜索树之前先将其类的大致轮廓实现：
template <class K, class V>
struct BSTreeNode//二叉搜索树结点
{
BSTreeNode<K, V>* _left;
BSTreeNode<K, V>* _right;
K _key;
V _value;
BSTreeNode(const K& key, const V& value)
:_left(nullptr)
,_right(nullptr)
,_key(key)
,_value(value)
{}
};
template <class K, class V>
class BSTree//二叉搜索树，BinarySearchTree
{
public:
typedef BSTreeNode<K, V> Node;
private:
Node* _root = nullptr;
};
查找操作实现
由上述介绍的逻辑不难写出二叉搜索树的查找操作代码：
Node* Find(const K& key)
{
if (_root == nullptr)
return nullptr;
Node* cur = _root;
while (cur)
{
if (key > cur->_key)
cur = cur->_right;
else if (key < cur->_key)
cur = cur->_left;
else
return cur;
}
return nullptr;
}
插入操作实现
由于我们这里实现的二叉搜索树不允许数据冗余，故可能出现插入失败的情况，因此，插入操作的返回值设置为bool，具体操作如下：
bool Insert(const K& key, const V& value)
{
if (_root == nullptr)
{
_root = new Node(key, value);
return true;
}
Node* cur = _root;
Node* parent = _root;
while (cur)
{
parent = cur;
if (key > cur->_key)
cur = cur->_right;
else if (key < cur->_key)
cur = cur->_left;
else//数据冗余，不插入
return false;
}
//找到要插入的位置
cur = new Node(key, value);
if (key > parent->_key)
parent->_right = cur;
else
parent->_left = cur;
return true;
}
注意，这里由于要保留链接关系，因此需要定义一个父亲指针始终指向cur的父亲结点。
删除操作实现
删除操作的逻辑稍显复杂，与插入操作类似的是，同样要设置父亲指针保证链接关系；其次通过画图可以很容易的将思路转化为代码：
bool Erase(const K& key)
{
if (_root == nullptr)
return false;
Node* cur = _root;
Node* parent = _root;
//先找到要删的结点
while (cur)
{
if (key > cur->_key)
{
parent = cur;
cur = cur->_right;
}
else if (key < cur->_key)
{
parent = cur;
cur = cur->_left;
}
else
break;
}
if (cur == nullptr)//没有找到要删的结点
return false;
//要删的结点有一个孩子问空
if (cur->_left == nullptr)
{
if (cur == parent->_left)
parent->_left = cur->_left;
else if (cur == parent->_right)
parent->_right = cur->_left;
else
_root = parent->_right;
}
else if (cur->_right == nullptr)
{
if (cur == parent->_left)
parent->_left = cur->_right;
else if (cur == parent->_right)
parent->_right = cur->_right;
else
_root = parent->_left;
}
else//要删的结点两个孩子都不为空
{
//先找到该结点右子树最小的结点
Node* minRight = cur->_right;
Node* minRight_parent = cur;
while (minRight->_left)
{
minRight_parent = minRight;
minRight = minRight->_left;
}
cur->_key = minRight->_key;
cur->_value = minRight->_value;
cur = minRight;
if (minRight_parent == _root)
minRight_parent->_right = cur->_right;
else
minRight_parent->_left = cur->_right;
}
delete cur;
return true;
}
递归版本
这里稍微介绍以下几个操作的递归版本，由于递归的性能较差，且占用空间较多，故稍作了解即可。
在递归操作中，非常巧妙的使用了引用传值，从而保证在不定义父亲指针的情况下保留了链接关系。
public:
bool InsertR(const K& key, const V& value)
{
return _InsertR(_root, key, value);
}
Node* FindR(const K& key)
{
return _FindR(_root, key);
}
bool EraseR(const K& key)
{
return _EraseR(_root, key);
}
private:
bool _InsertR(Node*& root, const K& key, const V& value)
{
if (root == nullptr)//找到要插入的位置
{
//由于传入的是引用，故链接关系保留
root = new Node(key, value);
return true;
}
if (key > root->_key)
_InsertR(root->_right, key, value);
else if (key < root->_key)
_InsertR(root->_left, key, value);
else
return false;
}
Node* _FindR(Node* root, const K& key)
{
if (root == nullptr)
return nullptr;
if (key > root->_key)
_FindR(root->_right, key);
else if (key < root->_key)
_FindR(root->_left, key);
else
return root;
}
bool _EraseR(Node*& root, const K& key)
{
if (root == nullptr)//没有找到要删除的结点
return false;
if (key > root->_key)
_EraseR(root->_right, key);
else if (key < root->_key)
_EraseR(root->_left, key);
else//找到要删除的结点
{
//两个孩子中有空
Node* del = root;
if (root->_left == nullptr)
root = root->_right;//由于是引用，故链接关系不变
else if (root->_right == nullptr)
root = root->_left;
else//两个孩子均非空
{
Node* minRight = root->_right;
Node* minRight_parent = root;
while (minRight->_left)//找到右子树中最小的结点
minRight = minRight->_left;
root->_key = minRight->_key;
root->_value = minRight->_value;
//通过递归删除替代结点
return _EraseR(root->_right, minRight->_key);
//while (minRight->_left)//找到右子树中最小的结点
//{
// minRight_parent = minRight;
// minRight = minRight->_left;
//}
//root->_key = minRight->_key;
//root->_value = minRight->_value;
//if (minRight_parent == root)
// minRight_parent->_right = minRight->_right;
//else
// minRight_parent->_left = minRight_parent->_right;
//del = minRight;
}
delete del;
return true;
}
}
二叉搜索树的应用
K模型
K模型：K模型即只有key作为关键码，结构中只需要存储Key即可，关键码即为需要搜索到的值。
比如：给一个单词word，判断该单词是否拼写正确，具体方式如下：
以单词集合中的每个单词作为key，构建一棵二叉搜索树。
在二叉搜索树中检索该单词是否存在，存在则拼写正确，不存在则拼写错误。
KV模型
KV模型：每一个关键码key，都有与之对应的值Value，即<Key, Value>的键值对。该种方式在现实生活中非常常见：比如英汉词典就是英文与中文的对应关系，通过英文可以快速找到与其对应的中文，英文单词与其对应的中文<word, chinese>就构成一种键值对；再比如统计单词次数，统计成功后，给定单词就可快速找到其出现的次数，单词与其出现次数就是<word, count>就构成一种键值对。
比如：实现一个简单的英汉词典dict，可以通过英文找到与其对应的中文，具体实现方式如下：
<单词，中文含义>为键值对构造二叉搜索树，注意：二叉搜索树需要比较，键值对比较时只比较Key查询英文单词时，只需给出英文单词，就可快速找到与其对应的key。
//统计词语出现的次数
string strs[] = { "苹果", "西瓜", "苹果", "樱桃", "苹果", "樱桃", "苹果", "樱桃", "苹果" };
// 统计水果出现的次
BSTree<string, int> countTree;
for (auto str : strs)
{
auto ret = countTree.Find(str);
if (ret == NULL)
{
countTree.Insert(str, 1);
}
else
{
ret->_value++;
}
}
countTree.InOrder();