二叉搜索树（二叉排序树、二叉查找树）
- 一、定义
- 二、操作
- （一）中序遍历
- （二）查找
- （三）插入
- （四）删除
- 三、二叉搜索树的应用
- 四、二叉搜索树操作的性能分析
- 五、总结
一、定义
二叉搜索树（BST：Binary Search Tree）也叫二叉排序树，也叫二叉查找树。
二叉搜索树要么是一颗空树，要么是具有以下性质的树：
若它的左子树不为空，则左子树上所有节点的值都小于根节点的值
若它的右子树不为空，则右子树上所有节点的值都大于根节点的值
它的左右子树也分别为二叉搜索树
从定义可以看出：二叉搜索树中不能有两个值相等的结点
比如：
二、操作
下面是二叉搜索树的定义（为了满足多种情况，定义成了一个模板）：
template<class T>
class BSTreeNode //二叉搜索树结点
{
public:
BSTreeNode(T val = T()) :
_val(val), _left(nullptr), _right(nullptr)
{
}
BSTreeNode* _left;
BSTreeNode* _right;
T _val;
};
template<class T>
class BSTree //二叉搜索树
{
typedef BSTreeNode<T> Node;
public:
Node* Find(const T& key);
bool Insert(const T& key);
bool Erase(const T& key);
void InOrder();
private:
Node* _root = nullptr;
};
（一）中序遍历
同二叉树的中序遍历
void _InOrder(Node* root)
{
if (root == nullptr)
return;
_InOrder(root->_left); //中序遍历左子树
cout << root->_val << " ";
_InOrder(root->_right); //中序遍历右子树
}
void InOrder()
{
_InOrder(_root); //递归
cout << "\n";
}
（二）查找
从根开始比较查找，比根小则去左子树中查找，比根大则去右子树中查找，在左右子树中以同样的方式继续查找，如果走到空还没找到，这个值就不存在。最多查找树的高度次。
下面是递归和非递归两种实现方法：
Node* _Find(Node* root, const T& key)
{
if (root == nullptr) //没找到返回nullptr
return nullptr;
if (root->_val > key) //在右子树中查找
return _Find(root->_left, key);
else if (root->_val < key) //在左子树中查找
return _Find(root->_right, key);
else //找到了
return root;
}
Node* Find(const T& key)
{
//递归
//return _Find(_root, key);
//非递归
Node* root = _root;
while (root)
{
if (root->_val == key)
return root;
else if (root->_val > key)
root = root->_left;
else if (root->_val < key)
root = root->_right;
}
return root;
}
（三）插入
创建一个二叉搜索树的过程，也就是不断的插入。插入的具体过程如下：
1、树为空，则直接新增节点，赋值给root指针
2、树不空，按二叉搜索树性质查找插入位置，插入新节点
3、每次插入的结点都是叶子结点
比如：
下面是递归和非递归两种实现方法：
bool _Insert(Node*& root, const T& key)
{
if (root == nullptr)
{
root = new Node(key);
return true;
}
if (root->_val > key)
return _Insert(root->_left, key);
else if (root->_val < key)
return _Insert(root->_right, key);
else
return false;
}
bool Insert(const T& key)
{
//递归
//return _Insert(_root, key);
//非递归
Node* newnode = new Node(key); //创建一个新结点
if (_root == nullptr) //空树特殊处理
{
_root = newnode;
return true;
}
Node* root = _root, *pre = nullptr; //pre指向root的双亲
while (root) //寻找插入的位置
{
if (root->_val == key) //已经存在，无需插入
return false;
else if (root->_val > key) //在左子树中查找插入位置
{
pre = root;
root = root->_left;
}
else if (root->_val < key) //在右子树中查找插入位置
{
pre = root;
root = root->_right;
}
}
//判断插入到左孩子还是右孩子
if (pre->_val > key)
pre->_left = newnode;
else
pre->_right = newnode;
return true;
}
（四）删除
首先查找元素是否在二叉搜索树中，如果不存在，则返回，否则要删除的结点可能分下面四种情况：
1、要删除的结点无孩子结点
2、要删除的结点只有左孩子结点
3、要删除的结点只有右孩子结点
4、要删除的结点有左、右孩子结点
情况1：直接删除该结点–直接删除
情况2：删除该结点且使被删除节点的双亲结点指向被删除节点的左孩子结点–直接删除
情况3：删除该结点且使被删除节点的双亲结点指向被删除结点的右孩子结点–直接删除
情况4：在它的右子树中寻找中序遍历下的第一个结点(右子树中值最小，也就是右子树中最左边的结点，并且该结点一定没有左子树)，用它的值填补到被删除结点中，再来处理该结点的删除问题（该结点删除问题下面注意中会说明）–替换法删除。或者在它的左子树中寻找中序遍历下的最后一个结点（左子树中值最大，也就是左子树中最右边的结点，并且该结点一定没有右子树），用它的值填补到被删除结点中，再来处理该结点的删除问题–替换法删除。
注意：
a：其中可以发现，情况1可以当作情况2或情况3处理，因为情况1删除之后，它的双亲指向空，当作情况2处理的话，虽然它没有左孩子，但是可以看作是null左孩子，然后将null赋值给它的双亲，他的双亲仍然是指向空，情况3也是同理。这样的做的好处是归纳整理可以更好的编程。
b：情况4中用替换法删除，替换的那个结点删除问题该怎么处理，如果用右子树中最小关键字结点替换，该结点一定没有左子树，那么删除该结点就变成了情况3。如果是用左子树中最大关键字结点替换，该结点一定没有右子树，那么删除该结点就变成了情况2。这样一来删除任何一个结点都很容易，要么直接删除，要么替换删除后再使用一次直接删除。
c：对于b中那种处理方法之外还有一种方法，一直用替换法删除替换的那个结点，直到最后一次用叶子结点替换，然后将叶结点删除。如果树的高度很高并且树的性状不理想的情况下，可能需要使用很多次替换法，所有这种方法没有b快。
比如：
下面是递归和非递归两种实现方法：
bool _Erase(Node*& root, const T& key)
{
if (root == nullptr) //没找到
return false;
if (root->_val > key)
return _Erase(root->_left, key);
else if (root->_val < key)
return _Erase(root->_right, key);
else
{
Node* del = root;
//分三种情况（思想同非递归）
if (root->_left == nullptr)
root = root->_right;
else if (root->_right == nullptr)
root = root->_left;
else if (root->_left != nullptr && root->_right != nullptr)
{
//用右子树中最左边结点替换
Node* tmp = root->_right;
while (tmp->_left)
tmp = tmp->_left;
swap(root->_val, tmp->_val); //库函数，交换两个结点的值
return _Erase(root->_right, key); //递归删除替换的那个结点（这一步也可不使用递归，非递归也行）
//（注意这里并不是从根重新开始查找删除值为key的结点,因为我们上一步交换了待删除结点root和替换结点tmp的值。要是从根结点开始查找，是找不到值为key的结点。而是从结点root的右子树开始删除值为key的结点）
}
delete del;
return true;
}
}
bool Erase(const T& key)
{
//递归
//return _Erase(_root, key);
//非递归
//一、查找
Node* root = _root, *pre = nullptr; //pre指向root的双亲
while (root)
{
if (root->_val == key)
break;
else if (root->_val > key)
{
pre = root;
root = root->_left;
}
else if (root->_val < key)
{
pre = root;
root = root->_right;
}
}
//二、删除
if (root == nullptr) //没找到
return false;
else //找到
{
//找到后，删除的结点分三种情况
if (root->_left == nullptr) //情况2
{
if (root == _root) //根节点特殊处理（主要是因为根结点的时候pre为nullptr，不能用pre进行操作）
_root = _root->_right;
else
{
//判断当前结点时双亲的左孩子还是右孩子
if (pre->_left == root)
pre->_left = root->_right;
else if (pre->_right == root)
pre->_right = root->_right;
}
delete root;
}
else if (root->_right == nullptr) //情况3
{
if (root = _root) //根节点特殊处理
_root = _root->_left;
else
{
//判断当前结点时双亲的左孩子还是右孩子
if (pre->_left == root)
pre->_left = root->_left;
else if (pre->_right == root)
pre->_right = root->_left;
}
delete root;
}
else if (root->_left != nullptr && root->_right != nullptr) //情况4
{
//用右子树中最左边的结点替换
//1、找右子树中最左边结点
Node* tmp = root->_right, *father = root; //tmp指向右子树中最左边结点，father是指向tmp的双亲结点
while (tmp->_left)
{
father = tmp;
tmp = tmp->_left;
}
//2、替换（仅赋值）
root->_val = tmp->_val;
//3、删除替换结点（有可能root的右孩子就是右子树中最左边结点，有可能不是，所有需要判断赋值）
if (father->_left == tmp)
father->_left = tmp->_right;
else if (father->_right == tmp)
father->_right = tmp->_right;
delete tmp;
}
return true;
}
}
三、二叉搜索树的应用
K模型：K模型即只有key作为关键码，结构中只需要存储Key即可，关键码即为需要搜索到的值。
比如：私人小区停车场，只允许该小区的车辆进入。每次只需要识别进入车辆的车牌是否在小区的系统中，所有只需要将车牌信息存入系统即可，这里的车牌就是key。
KV模型：每一个关键码key，都有与之对应的值Value，即<Key, Value>的键值对。
比如：商场停车场，所有外来车辆都可以进入，并且按停车时长收费。每次车辆进入时记录车辆的车牌号和入场时间，将车牌作为key，入场时间作为value。每次车辆离场时，只需要在系统中查找到该车牌号，然后就能找到车牌对应的入场时间，就可以算出停车费用。KV模型的实现在K的基础上增加一个value就可以。
四、二叉搜索树操作的性能分析
插入和删除操作都必须先查找，因此查找效率代表了二叉搜索树中各个操作的性能。查找的效率取决于结点在树中的深度。
对于同一个关键码集合，如果各关键码插入的次序不同，可能得到不同结构的二叉搜索树。
最优情况下，二叉搜索树为完全二叉树(或者接近完全二叉树)，其平均比较次数为：
l
o
g
2
N
log_2 N
log2N
最差情况下，二叉搜索树退化为单支树(或者类似单支)，其平均比较次数为：
N
2
\frac{N}{2}
2N
五、总结
插入和删除这两个操作多注意一些细节和特殊情况，无论是插入还是删除，都需要知道插入位置和待删除结点的双亲结点，并且删除的时候，删除根节点的时候要特殊处理一下。
