目录
一. 二叉搜索树的概念
二叉搜索树又称二叉排序树，它如果不是一棵空树，就是具有以下性质的二叉树：
若它的左子树不为空，则左子树上所有节点的值都小于等于根节点的值
若它的右子树不为空，则右子树上所有节点的值都大于等于根节点的值
它的左右子树也分别为二叉搜索树
二叉搜索树中可以支持插入相等的值，也可以不支持插入相等的值，具体看使用场景定义。map/set/multimap/multiset系列容器的底层就是二叉搜索树(红黑树)，其中map/set不支持插入相等值，multimap/multiset支持插入相等值
二. 二叉搜索树的实现
1. 二叉搜索树的插入
插入步骤为：
1. 树为空，则直接新增节点，赋值给root指针
2. 树不空，按二叉搜索树性质，插入值比当前节点大往右走，插入值比当前节点小往左走，找到空位置，插入新节点。
3. 如果支持插入相等的值，插入值跟当前节点相等的值可以往右走，也可以往左走，找到空位置，插入新节点。
我们若给上图插入一个元素7，比较过程如下图所示
递归实现代码为，因为对象不能直接访问私密成员函数所以通过this指针来替换，其中K为我们使用模版定义的类型
void Insert(STree<K> &st, K key)
{
Insertdfs(st._root, key);
}
void Insertdfs(Node*& cur,int key)
{
if (cur == nullptr)
{
cur = new Node(key);
}
else
{
if (cur->_key >= key)
{
if (cur->left == nullptr)
{
Node* child = new Node(key);
if (cur->_key >= key)
cur->left = child;
else
cur->right = child;
}
else
Insertdfs(cur->left, key);
}
else
{
if (cur->right == nullptr)
{
Node* child = new Node(key);
if (cur->_key >= key)
cur->left = child;
else
cur->right = child;
}
else
Insertdfs(cur->right, key);
}
}
}但是循环实现插入并不比递归复杂
void Insert(K key)
{
if (_root == nullptr)
_root = new Node(key);
else
{
Node* parent = _root;
Node* child = _root;
while (child)
{
if (child->_key>=key)
{
parent = child;
child = parent->left;
}
else if (child->_key < key)
{
parent = child;
child = parent->right;
}
}
child = new Node(key);
if (parent->_key >= key)
parent->left = child;
else
parent->right = child;
}
}2. 二叉搜索树的查找
思路步骤
1. 从根开始比较，查找x，x比根的值大则往右边走查找，x比根值小则往左边走查找。
2. 最多查找高度次，走到空还没找到的话，这个值不存在。
3. 如果不支持插入相等的值，找到x返回即可，如果支持插入相等的值，意味着有多个x存在，一般要求查找中序的第一个x。
找到最左边的x的话可以用一个值记录下来，在更左边找到值的话就更新，否则就直到循环结束返回记录的值，没找到就返回nullptr
如下图
Node* Find(K key)
{
if (_root == nullptr)
return nullptr;
Node* parent = _root;
Node* tmp = _root;//先找到要删除的节点
Node* tmpNode = nullptr;
while (tmp)
{
if (tmp->_key >= key)
{
if(tmp->_key==key)
tmpNode = tmp;
parent = tmp;
tmp = tmp->left;
}
else if (tmp->_key < key)
{
parent = tmp;
tmp = tmp->right;
}
}
return tmpNode;
}3. 二叉搜索树的删除
首先查找元素是否在二叉搜索树中，如果不存在，则返回false。
如果查找元素存在则分一下四种情况分别处理：(假设要删除的节点为N)
1. 要删除的节点N左右节点孩子均为空
2. 要删除的节点N左孩子为空，右孩子不为空
3. 要删除的节点N右孩子为空，左孩子不为空
4. 要删除的节点N左右孩子均不为空
四种情况如下图所示
四种情况的解决方法如下
1. 把N节点的父亲对应孩子指针指向空，直接删除N节点(情况1可以当做2或者3处理，效果一样)。
2. 把N节点的父亲对应孩子指针指向N的右孩子，直接删除N节点(由于情况1左右孩子都是空话所以将N节点的父亲指向N的左右孩子都可以)
3. 把N节点的父亲对应孩子指针指向N的左孩子，直接删除N节点
4. 无法直接删除N节点，因为N的两个孩子就无处安放了，只能用替换法删除。找N左子树的值最大的节点(左子树的最右节点)或者N右子树的值最小节点(右子树最左节点)代替N，因为这两个节点任意一个放到N的位置都满足二叉搜索树的规则。代替N的意思就是N和所找到节点的值进行交换，转而变成删除我们所找到的节点，此节点一定符合情况2和情况三可以直接删除。
利用递归实现的话先利用this指针将根节点传到实现递归的函数，如下所示
bool Erase(STree<K>& st, K key)
{
return Erasedfs(st._root, nullptr, key);
}其中第二个参数用来记录，我们寻找节点的父亲节点，用来连接新节点。
前三种情况，我们如果找到了要删除的节点但是其是根节点，那直接改变成员变量_root即可，反之利用parent来连接节点，实现代码如下
bool Erasedfs(Node* tmp,Node* parent,K key)
{
if (tmp == nullptr)
return false;
if (tmp->_key > key)
{
return Erasedfs(tmp->left,tmp, key);
}
else if (tmp->_key < key)
return Erasedfs(tmp->right,tmp, key);
//四种情况
if (tmp->left == nullptr)//将tmp是叶子节点的情况归到这里
{
if (tmp == _root)//是根节点的情况
_root = tmp->right;
else
{
if (parent->left == tmp)
{
parent->left = tmp->right;
}
else
{
parent->right = tmp->right;
}
}
delete tmp;
return true;
}
else if (tmp->right == nullptr)
{
if (tmp == _root)
_root = tmp->right;
else
{
if (parent->left == tmp)
{
parent->left = tmp->left;
}
else
{
parent->right = tmp->left;
}
}
delete tmp;
return true;
}
else//两边都有
{
//寻找左子树最大值，或者右子树最小值
parent = tmp;
Node* rbig = tmp->left;//左子树最大值
while (rbig->right)
{
parent = rbig;
rbig = rbig->right;
}
tmp->_key = rbig->_key;
if (parent->left == rbig)
parent->left = rbig->left;
else
parent->right = rbig->left;
delete rbig;
return true;
}
}不利用递归思路也是如此，如果成员变量(树的根)是空就直接返回反之先找到要删除的节点，找不到就返回false找到了就根据情况执行删除操作，但是只需要一个参数，其余自己定义即可
bool Erase(K key)
{
if (_root == nullptr)
return false;
Node* parent = _root;
Node* tmp=_root;//先找到要删除的节点
while (tmp)
{
if (tmp->_key > key)
{
parent = tmp;
tmp = tmp->left;
}
else if (tmp->_key < key)
{
parent = tmp;
tmp = tmp->right;
}
else
{
//四种情况
if (tmp->left == nullptr)//将tmp是叶子节点的情况归到这里
{
if (tmp == _root)
_root = tmp->right;
else
{
if (parent->left == tmp)
{
parent->left = tmp->right;
}
else
{
parent->right = tmp->right;
}
}
delete tmp;
return true;
}
else if (tmp->right == nullptr)
{
if (tmp == _root)
_root = tmp->right;
else
{
if (parent->left == tmp)
{
parent->left = tmp->left;
}
else
{
parent->right = tmp->left;
}
}
delete tmp;
return true;
}
else//两边都有
{
//寻找左子树最大值，或者右子树最小值
parent = tmp;
Node* rbig = tmp->left;//左子树最大值
while (rbig->right)
{
parent = rbig;
rbig = rbig->right;
}
tmp->_key = rbig->_key;
if (parent->left == rbig)
parent->left = rbig->left;
else
parent->right = rbig->left;
delete rbig;
}
}
}
return false;
}三. 二叉搜索树的性能分析
1. 时间复杂度
最好情况下，二叉搜索树为完全二叉树(或者接近完全二叉树)，其高度为：O(㏒₂ N)
最差情况下，二叉搜索树退化为单支树(或者类似单支)，其高度为：O(½N)
综合而言二叉搜索树的增删查改时间复杂度为：O(N)
这样的效率还是太慢了，所以就有了平衡搜索二叉树AVL树和红黑树才能适用于我们在内存中的存储和搜索数据。
二分查找也可以实现O(longN)级别的查找效率，但是二分查找有两大缺陷：
1. 需要存储在支持下标随机访问的结构中，并且有序。
2. 插入和删除数据效率很低，因为存储在下标随机访问的结构中，插入和删除数据一般需要挪动数据。
2. 空间复杂度
O(N)
四. 二叉搜索树的实现代码
#include<iostream>
#include<algorithm>
using namespace std;
template<class K>
class STNode
{
//typedef STNode<K> Node;
using Node = STNode<K>;
public:
STNode(K key)
{
_key = key;
Node* left = nullptr;
Node* right = nullptr;
}
K _key;
Node* left = nullptr;
Node* right = nullptr;
};
template<class K>
class STree
{
typedef STNode<K> Node;
public:
//STree() = default;
STree()
{
}
STree(const STree<K>& st)
{
_root = copy(st._root);
}
~STree()
{
Destroy(_root);
}
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* newnode = new Node(root->_key);
newnode->left = copy(root->left);
newnode->right = copy(root->right);
return newnode;
}
void Insert(STree<K> &st, K key)
{
Insertdfs(st._root, key);
}
void Insertdfs(Node*& cur,int key)
{
if (cur == nullptr)
{
cur = new Node(key);
}
else
{
if (cur->_key >= key)
{
if (cur->left == nullptr)
{
Node* child = new Node(key);
if (cur->_key >= key)
cur->left = child;
else
cur->right = child;
}
else
Insertdfs(cur->left, key);
}
else
{
if (cur->right == nullptr)
{
Node* child = new Node(key);
if (cur->_key >= key)
cur->left = child;
else
cur->right = child;
}
else
Insertdfs(cur->right, key);
}
}
}
void Insert(K key)
{
if (_root == nullptr)
_root = new Node(key);
else
{
Node* parent = _root;
Node* child = _root;
while (child)
{
if (child->_key>=key)
{
parent = child;
child = parent->left;
}
else if (child->_key < key)
{
parent = child;
child = parent->right;
}
}
child = new Node(key);
if (parent->_key >= key)
parent->left = child;
else
parent->right = child;
}
}
void InOrder()
{
_InOrder(_root);
cout << endl;
}
Node* Find(K key)
{
if (_root == nullptr)
return nullptr;
Node* parent = _root;
Node* tmp = _root;//先找到要删除的节点
Node* tmpNode = nullptr;
while (tmp)
{
if (tmp->_key >= key)
{
if(tmp->_key==key)
tmpNode = tmp;
parent = tmp;
tmp = tmp->left;
}
else if (tmp->_key < key)
{
parent = tmp;
tmp = tmp->right;
}
}
return tmpNode;
}
bool Erase(STree<K>& st, K key)
{
return Erasedfs(st._root, nullptr, key);
}
bool Erasedfs(Node* tmp,Node* parent,K key)
{
if (tmp == nullptr)
return false;
if (tmp->_key > key)
{
return Erasedfs(tmp->left,tmp, key);
}
else if (tmp->_key < key)
return Erasedfs(tmp->right,tmp, key);
//四种情况
if (tmp->left == nullptr)//将tmp是叶子节点的情况归到这里
{
if (tmp == _root)//是根节点的情况
_root = tmp->right;
else
{
if (parent->left == tmp)
{
parent->left = tmp->right;
}
else
{
parent->right = tmp->right;
}
}
delete tmp;
return true;
}
else if (tmp->right == nullptr)
{
if (tmp == _root)
_root = tmp->right;
else
{
if (parent->left == tmp)
{
parent->left = tmp->left;
}
else
{
parent->right = tmp->left;
}
}
delete tmp;
return true;
}
else//两边都有
{
//寻找左子树最大值，或者右子树最小值
parent = tmp;
Node* rbig = tmp->left;//左子树最大值
while (rbig->right)
{
parent = rbig;
rbig = rbig->right;
}
tmp->_key = rbig->_key;
if (parent->left == rbig)
parent->left = rbig->left;
else
parent->right = rbig->left;
delete rbig;
return true;
}
}
bool Erase(K key)
{
if (_root == nullptr)
return false;
Node* parent = _root;
Node* tmp=_root;//先找到要删除的节点
while (tmp)
{
if (tmp->_key > key)
{
parent = tmp;
tmp = tmp->left;
}
else if (tmp->_key < key)
{
parent = tmp;
tmp = tmp->right;
}
else
{
//四种情况
if (tmp->left == nullptr)//将tmp是叶子节点的情况归到这里
{
if (tmp == _root)
_root = tmp->right;
else
{
if (parent->left == tmp)
{
parent->left = tmp->right;
}
else
{
parent->right = tmp->right;
}
}
delete tmp;
return true;
}
else if (tmp->right == nullptr)
{
if (tmp == _root)
_root = tmp->right;
else
{
if (parent->left == tmp)
{
parent->left = tmp->left;
}
else
{
parent->right = tmp->left;
}
}
delete tmp;
return true;
}
else//两边都有
{
//寻找左子树最大值，或者右子树最小值
parent = tmp;
Node* rbig = tmp->left;//左子树最大值
while (rbig->right)
{
parent = rbig;
rbig = rbig->right;
}
tmp->_key = rbig->_key;
if (parent->left == rbig)
parent->left = rbig->left;
else
parent->right = rbig->left;
delete rbig;
}
}
}
return false;
}
private:
void _InOrder(Node* root)//可以在外面再弄一个通过this指针访问
{
if (root == nullptr)
return;
_InOrder(root->left);
cout << root->_key << " ";
_InOrder(root->right);
}
Node* _root = nullptr;
};
int main()
{
STree<int> t;
int a[10] = { 8,3,10,1,3,6,14,4,7,13 };
for (auto e : a)
{
t.Insert(t,e);
}
//STNode<int>* node = t.Find(3);
//cout << node->_key << endl;
//cout << (node->right == nullptr) << endl;
t.InOrder();
//for (auto e : a)
//{
// t.Erase(t,e);
// t.InOrder();
//}
return 0;
}五. 二叉搜索树key和key/value使用场景
1. key搜索场景
只有key作为关键码，结构中只需要存储key即可，关键码即为需要搜索到的值，搜索场景只需要判断key在不在。key的搜索场景支持增删差但不支持修改，因为修改key会破坏搜索树的结构。
使用场景1：
小区无人值守⻋库，小区车库买了⻋位的业主车才能进小区，那么物业会把买了车位的业主的车牌号录⼊后台系统，⻋辆进入时扫描⻋牌在不在系统中，在则抬杆，不在提示本小区⻋辆，无法进⼊。
使用场景2 ：
检查⼀篇英文文章单词拼写是否正确，将词库中所有单词放⼊⼆叉搜索树，读取文章中的单 词，查找是否在⼆叉搜索树中，不在则波浪线标红提示。
2. key/value搜索场景
每一个关键码key，都有与之对应的值value，value可以是任意对象。树的节点中除了存储key还要存储与之对应的的value，增删查还是以key为关键字走二叉搜索树的规则进行比较，可以快速查找key对应的value。key/value的搜索场景实现的二叉搜索树支持修改，但是不支持修改key，修改key还是会破坏树的结构，可以修改value。
使用场景1：
简单中英互译字典，树的结构中(结点)存储key(英⽂)和vlaue(中文)，搜索时输⼊英文，则同时查找到了英文对应的中⽂。
使用场景2：
商场无人值守车库，入口进场时扫描⻋牌，记录车牌和⼊场时间，出口离场时，扫描车牌，查找入场时间，用当前时间-入场时间计算出停⻋时长，计算出停车费用，缴费后抬杆，车辆离场。
使用场景3：
统计⼀篇文章中单词出现的次数，读取⼀个单词，查找单词是否存在，不存在这个说明第⼀次出现，(单词，1)，单词存在，则++单词对应的次数。
这篇就到这里啦，ヾ(￣▽￣)Bye~Bye~
标签：tmp,right,parent,二叉,概念,搜索,key,root,left From： https://blog.csdn.net/m0_68142120/article/details/142319042