引入
当我们用有序数组储存数据时，查找某个数据可以用折半查找，时间复杂度为LogN；但是当我们要插入或删除数据时需要一步一步挪动数据，消耗非常大。为此引入了二叉搜索树这个数据结构。
二叉搜索树的规则
二叉搜索树又称二叉排序树，只要它不是空树，就满足一下规则：
1.若左子树不为空，则左子树上的所有节点值都小于等于根节点的值
2.若右子树不为空，则右子树上的所有节点值都大于等于根节点的值
3.它的左右子树也分别为二叉搜索树
4.二叉搜索树中可以支持插入相等的值，也可以不支持插入相等的值，具体看应用场景。
二叉搜索树的性能
最优情况下，二叉搜索树为完全二叉树，高度为log2N。
最差情况下，二叉树搜索树为单只树，高度为N。
所以综合来看，二叉搜索树的增删查改时间复杂度为：O(N)
这样的效率和数组相比优势不明显，无法满足我们的需求，后面将会学习 AVL和红黑树来解决效率问题。这两种二叉搜索树的增删查改的时间复杂度为：O(logN)。二分查找也能达到这个时间复杂度；为什么还要用二叉搜索树呢？这里就要提到能用二分查找的前提条件了：1.要保证有序2.要支持下标随机访问。而且用二分的结构大多在插入删除时需要挪动数据，消耗非常大。
二叉搜索树的插入
1.插入前树为空：
直接新增一个节点，赋值给root指针。
2.插入前树不为空：
插入值和当前节点值进行比较，比当前节点值小则与左子树值比较，为空时插入；比当前节点值大则与右子树值比较，为空时插入。
当插入值与当前节点值相等时，自由安排往左往右都可以；但是要注意逻辑连贯性，第一次往左了下次也得往左。
bool Insert(const K& key)
{
if (_root == nullptr)
{
_root = new Node(key);
return true;
}
Node* parent = nullptr;
Node* cur = _root;
while (cur)
{
if (cur->_key < key)
{
parent = cur;
cur = cur->_right;
}
else if (cur->_key > key)
{
parent = cur;
cur = cur->_left;
}
else
{
return false;//不应许处插入相同的值
}
}
cur = new Node(key);
if (parent->_key < key)
{
parent->_right = cur;
}
else
{
parent->_left = cur;
}
return true;
}二叉搜索树的查找
1.从根节点开始比较，查找x，比查找值大则往右走，反之往左走。
2.若最后找到空节点则未找到。
3.如果未支持插入相等值，找到第一个就返回
4.如果支持插入相等的值，那么可能存在多个要查找的x，返回中序的第一个x。
如果要查找3，找到第一个3后，继续向下查找，直至找到空节点，返回最后一个找到的值为3的节点，为中序的第一个节点。
代码实现：
bool find(const K& key)
{
Node* cur = _root;
while (cur)
{
if (cur->_key > key)
{
cur = cur->_left;
}
else if (cur->_key < key)
{
cur = cur->_right;
}
else
{
return true;
}
return false;
}
}二叉搜索树的删除
要删除二叉搜索树中的元素，首先要找到查找二叉搜索树中的元素，如果找不到，即不存在，返回false。因为一个节点有两个子节点，排列组合就有四种情况。
1.要删除的节点左右孩子都为空
这种情况最简单，直接删除就可以（把该节点的父节点指向此节点的路径指向空），不会影响整棵树的访问顺序。
2.节点左孩子为空，右孩子不为空
把父节点指向此节点的右孩子，直接删除此节点。
3.节点右孩子为空，左孩子不为空
把父节点指向左节点，直接删除该节点。
4.左右均不为空
这种情况最难处理，此节点的两个孩子要想办法安放。在讲堆和top-k问题时【数据结构】 -- 堆 （堆排序）（TOP-K问题）_高度为 k的二叉树最大的结点数为( )。-CSDN博客，我们插入一个元素，可以插入到末尾，然后再向上调整。其实这里有点类似这个的逆过程。
按照中序遍历，访问此节点前访问的元素时左子树中最大的元素，访问此节点后访问的第一个元素是右子树中最小的元素。用他俩中任意一个来替换此节点，中序遍历的结果都一样（具体用哪一个替换看自己喜好）。替换之后，此节点左右都为空，满足情况1，直接删除就好了。
bool Erase(const K& key)
{
Node* parent = nullptr;
Node* cur = _root;
//从根节点开始查找
while (cur)
{
if (cur->_key < key)
{
parent = cur;
cur = cur->_right;
}
else if (cur->_key > key)
{
parent = cur;
cur = cur->_left;
}
else//cur->_key == key
{
//左右至少有一个为空的情况，直接改变指向
if (cur->_left == nullptr)
{
if (parent == nullptr)
{
_root = cur->_right;
}
else
{
if (parent->_left == cur)
parent->_left = cur->_right;
else
parent->_right = cur->_right;
}
delete cur;
return true;
}
else if (cur->_right == nullptr)
{
if (parent == nullptr)
{
_root = cur->_left;
}
else
{
if (parent->_left == cur)
parent->_left = cur->_left;
else
parent->_right = cur->_left;
}
delete cur;
return true;
}
else {
//两个子树都有孩子的情况，用右子树最小或左子树最大来替换
// ⼀定要把cur给rightMinP，否会报错。
//注意右子树的第一个值就是最小值的情况
Node* rightMinP = cur;
Node* rightMin = cur->_right;
while (rightMin->_left)//找出最左边的，就是右子树最小的
{
rightMinP = rightMin;
rightMin = rightMin->_left;
}
cur->_key = rightMin->_key;//把右子树中最小值替换到cur->_key
if (rightMinP->_left == rightMin)
rightMinP->_left = rightMin->_right;
else//右子树的第一个值就是最小值的情况
rightMinP->_right = rightMin->_right;
delete rightMin;
return true;
}
}
}
return false;
}二叉搜索树key和key/value使用场景
key搜索场景
一个节点只储存key这一个数据，这样实现的二叉搜索树只能实现增删查，不支持改动。
key/value搜索场景
每一个key,都有与之对应的值value，value可以是任意类型对象。树的结构中纪要储存key，也要储存value。这种二叉搜索树，还是按照key值来建立和搜索，key的值同样不能改变，但是value的值是可以改变的。就像按学号生成一个班级的二叉树，一个节点代表一个同学，就可以用这个节点的value记录该同学的成绩，每次考试成绩是可以改变的，value就更新。
代码实现：
#include<iostream>
using namespace std;
#include<string>
template < class K, class V>
struct BSTNode
{
// pair<K, V> _kv;
K _key;
V _value;
BSTNode<K, V>* _left;
BSTNode<K, V>* _right;
BSTNode(const K & key, const V & value)
:_key(key)
, _value(value)
, _left(nullptr)
, _right(nullptr)
{}
};
template<class K, class V>
class BSTree
{
typedef BSTNode<K, V> Node;
public:
BSTree() = default;
BSTree(const BSTree<K, V>& t)
{
_root = Copy(t._root);
}
BSTree<K, V>& operator=(BSTree<K, V> t)
{
swap(_root, t._root);
return *this;
}
~BSTree()
{
Destroy(_root);
_root = nullptr;
}
bool Insert(const K& key, const V& value)
{
if (_root == nullptr)
{
_root = new Node(key, value);
return true;
}
Node* parent = nullptr;
Node* cur = _root;
while (cur)
{
if (cur->_key < key)
{
parent = cur;
cur = cur->_right;
}
else if (cur->_key > key)
{
parent = cur;
cur = cur->_left;
}
else
{
return false;
}
}
cur = new Node(key, value);
if (parent->_key < key)
{
parent->_right = cur;
}
else
{
parent->_left = cur;
}
return true;
}
Node* Find(const K& key)
{
Node* cur = _root;
while (cur)
{
if (cur->_key < key)
{
cur = cur->_right;
}
else if (cur->_key > key)
{
cur = cur->_left;
}
else
{
return cur;
}
}
return nullptr;
}bool Erase(const K& key)
{
Node* parent = nullptr;
Node* cur = _root;
while (cur)
{
if (cur->_key < key)
{
parent = cur;
cur = cur->_right;
}
else if (cur->_key > key)
{
parent = cur;
cur = cur->_left;
}
else
{
if (cur->_left == nullptr)
{
if (parent == nullptr)
{
_root = cur->_right;
}
else
{
if (parent->_left == cur)
parent->_left = cur->_right;
else
parent->_right = cur->_right;
}
delete cur;
return true;
}
else if (cur->_right == nullptr)
{
if (parent == nullptr)
{
_root = cur->_left;
}
else
{
if (parent->_left == cur)
parent->_left = cur->_left;
else
parent->_right = cur->_left;
}
delete cur;
return true;
}
else
{
Node* rightMinP = cur;
Node* rightMin = cur->_right;
while (rightMin->_left)
{
rightMinP = rightMin;
rightMin = rightMin->_left;
}
cur->_key = rightMin->_key;
if (rightMinP->_left == rightMin)
rightMinP->_left = rightMin->_right;
else
rightMinP->_right = rightMin->_right;
delete rightMin;
return true;
}
}
}
return false;
}
void InOrder()
{
_InOrder(_root);
cout << endl;
}
private:
void _InOrder(Node* root)
{
if (root == nullptr)
{
return;
}
_InOrder(root->_left);
cout << root->_key << ":" << root->_value << endl;
_InOrder(root->_right);
}
void Destroy(Node* root)
{
if (root == nullptr)
return;
Destroy(root->_left);
Destroy(root->_right);
delete root;
}
Node* Copy(Node* root)
{
if (root == nullptr)
return nullptr;
Node* newRoot = new Node(root->_key, root->_value);
newRoot->_left = Copy(root->_left);
newRoot->_right = Copy(root->_right);
return newRoot;
}
private:
Node* _root = nullptr;
};
//int main()
//{
// BSTree<string, string> dict;
// //BSTree<string, string> copy = dict;
// dict.Insert("left", "左边");
// dict.Insert("right", "右边");
// dict.Insert("insert", "插⼊");
// dict.Insert("string", "字符串");
// string str;
// while (cin >> str)
// {
// auto ret = dict.Find(str);
// if (ret)
// {
// cout << "->" << ret->_value << endl;
// }
// else
// {
// cout << "无此单词，请重新输⼊" << endl;
// }
// }
// return 0;
//}
int main()
{
string arr[] = { "蔡徐坤","陈立农","宋亚轩","范丞丞","黄明昊" };
BSTree<string, int> countTree;
for (const auto& str : arr)
{
// 先查找idol在不在搜索树中
// 1、不在，说明idol第⼀次出现，则插⼊<idol, 1>
// 2、在，则查找到的结点中idol对应的次数++
//BSTreeNode<string, int>* ret = countTree.Find(str);
auto ret = countTree.Find(str);
if (ret == NULL)
countTree.Insert(str, 1);
else
{
ret->_value++;
}
countTree.InOrder();
return 0;
}
}