1、二叉搜索树简介
?????如上图所示，我们可以知道二叉搜索树是在二叉树的基础上，加入某种规则生成的树形结构，它的规则就是：插入数值时把所有比根节点大的都放在右边，把比根节点小的放在根的左边。它查找的效率是O(N)。
2、二叉搜索树部分功能模拟实现
2.1、查找函数
?????二叉搜索树的查找：通过二叉树的规则，如果查找数值比当前节点小，就往当前节点的左边走，比当前节点大，就往当前节点的右边走，找到返回当前节点指针，找到空节点，返回nullptr。查找函数这边通过两种写法实现：一、普通迭代写法 二、递归写法，具体代码如下：
//普通写法
Node* Find(const K& key)
{
Node* move = _root;
while (move)
{
if (move->_key > key)
{
move = move->left;
}
else if (move->_key < key)
{
move = move->right;
}
else
{
return move;
}
}
return nullptr;
}
//查找函数递归写法
Node* _FindR(Node* t, const K& key)
{
if (t == nullptr)
{
return nullptr;
}
if (t->_key > key)
{
return _FindR(t->left, key);
}
else if (t->_key < key)
{
return _FindR(t->right, key);
}
else
{
return t;
}
}
Node* FindR(const K& key)
{
return _FindR(_root, key);
}
2.2、插入函数
?????二叉搜索树的插入步骤：(1)先得找到合适的插入位置，通过二叉树的规则，插入数值比当前节点小，就往当前节点的左边走，比当前节点大，就往当前节点的右边走，直到找到空位置，准备插入新节点。值得注意的是这个步骤不能使用查找函数代替，因为如果使用查找函数代替就找不到父节点，就无法正常插入新节点。(2)确定是插入到空节点的父节点的左边还是右边值，通过比较插入值和父节点的值的大小判断。插入函数这边通过两种写法实现：一、普通迭代写法 二、递归写法，具体代码如下：
//普通写法
bool Insert(const K& key, const V& val)
{
if (_root == nullptr)
{
_root = new Node(key,val);
return true;
}
Node* move = _root;
Node* parent = _root;
while (move)//查找插入位置
{
if (move->_key > key)
{
parent = move;
move = move->left;
}
else
{
parent = move;
move = move->right;
}
}
if (parent->_key > key)//判断插入到父节点的左边还是右边
{
parent->left = new Node(key,val);
}
else
{
parent->right = new Node(key, val);
}
return true;
}
//插入函数递归写法
bool _insertR(Node*& t, const K& key, const V& val)
{
if (t == nullptr)//直接把空节点替换位新节点
{
t = new Node(key, val);
return true;
}
if (t->_key > key)
{
return _insertR(t->left, key, val);
}
else
{
return _insertR(t->right, key, val);
}
}
bool insertR(const K& key, const V& val)
{
if (_FindR(_root, key))
{
return false;
}
else
{
return _insertR(_root, key, val);
}
}
2.3、删除函数
?????删除节点分为三种情况:(1)删除叶子节点，可以直接删除(2)删除的节点后面还有一个节点，必选让父节点链接后面节点(3)删除节点后面有两个节点，必须从后面的节点中选出一个当根节点。
?????解决方法如下:
?????情况1和情况2可以看成同一种情况解决，先查找待删除的节点(这个查找也不能用Find函数代替，因为和插入同样，删除需要父节点，用Find找不到)，让父节点和后面的节点链接，情况1就直接链接后面的空节点。
?????情况3在找到待删除的节点之后，需要找到一个节点替代根节点，如上图，我们假设要删除5，我们可以在5的左树找到最大的节点和5替换，我们可以看出4为左树最大，就可以拿4和5节点替换，然后把5删了，这样就不会破坏树形结构，其实我们也可以找到右树最小，也就是6和5的节点替换也可以达到同样的效果。本文中用的时左边最大值进行替换，具体代码如下所示：
bool Erase(const K& key)
{
Node* move = _root;
Node* parent = _root;
while (move)//找到要删的节点
{
if (move->_key > key)
{
parent = move;
move = move->left;
}
else if (move->_key < key)
{
parent = move;
move = move->right;
}
else
{
break;
}
}
if (move->left == nullptr)//情况1或情况2
{
if (_root == move)//防止删除头节点，把头节点丢失了
{
_root = move->right;
}
if (parent->left == move)
{
parent->left = move->right;
}
else
{
parent->right = move->right;
}
delete move;
}
else if (move->right == nullptr)//情况1或情况2
{
if (_root == move)//防止删除头节点，把头节点丢失了
{
_root = move->left;
}
if (parent->left == move)
{
parent->left = move->left;
}
else
{
parent->right = move->left;
}
parent->right = move->left;
delete move;
}
else//情况3，左右都有节点，找左边最大（左边最右）或找右边最小（右边最左）
{
Node* maxNode = move->left;
Node* maxNodepanrent = move;
while (maxNode->right)
{
maxNodepanrent = maxNode;
maxNode = maxNode->right;
}
swap(maxNode->_key, move->_key);
if (maxNodepanrent->left == maxNode)//链接后面节点
{
maxNodepanrent->left = maxNode->left;
}
else
{
maxNodepanrent->right = maxNode->left;
}
delete maxNode;
}
return true;
}