文章目录
前言
本章呢我们来看看数据结构中的二叉搜索树。关于这章呢小编会从插入，查找和删除这三个方面来分享。当然还有搜索二叉树的运用场景
一、二叉搜索树的感念以及性质
二叉搜索树又称二叉排序树。其性质如下：
- 如果左子树不为空，那左子树上的所有节点的值都小于等于根节点的值
- 如果右子树不为空，那右子树上的所有节点的值都大于等于根节点的值。
- 左右子树也分别为二叉搜索树
- 二叉搜索树既可以支持插入相同的值，也可以不支持，这得要看运用场景.
二、二叉搜索树的性能分析
- 最优情况下，⼆叉搜索树为完全⼆叉树(或者接近完全⼆叉树)，其⾼度为： log2 N
- 最差情况下，⼆叉搜索树退化为单⽀树(或者类似单⽀)，其⾼度为： N
- 所以综合⽽⾔⼆叉搜索树增删查改时间复杂度为： O(N)
注意：二分查找可以实现O(log2 N) 级别的查找效率，但是二分查找有两大缺陷：
- 必须是储存在可以支持随机访问且有序的结构中
- 插入和删除的效率低，都需要移动数据
三、二叉搜索树的插入
1.插入的思路：
- 如果是空树，直接给root赋值新增节点
- 树不为空，按照二叉搜索树性质，插入值比当前节点大就往右边走，比当前节点值小就往左边走，找到空位后再新增节点，然后在插入
- 当插入相同的值的时候，既可以往右走也可以往左走，但是为了保持逻辑一致性，插入的值不能一会往右一会往左走。
实例：
如图所示：我们插入两个数16,3。我们以16为例:根据搜索二叉树的性质，当插入16时，由于8<16,所以往右走，然后10<16,继续往右边走，14<16,继续往右走，然后走到空，然后在插入16.同样，3的插入也是一样的。但是在插入的过程中有一个难点就是如何把新节点和他的根节点连接起来。因为上面的逻辑是在便利二叉树找到空位并没有记录它的根节点，这里我们只需要在便利的过程里用一个变量来记录它的根节点，最后在连接起来就行了。
2.插入的实现（非递归）：
#include<iostream>
using namespace std;
template<class K>
struct BSTNode//二叉树的节点
{
K _key;
BSTNode<K>* left;
BSTNode<K>* right;
BSTNode(const K& key)
:_key(key)
, left(nullptr)
, right(nullptr)
{}
};
template<class K>
class BSTree
{
public:
typedef BSTNode<K> Node;
bool Insert(const K& key)//插入
{
if (_root == nullptr)//空树的情况
{
_root = new Node(key);//直接给根节点赋值新节点
return true;
}
else//不是空树的情况
{
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);
parent->_key > key ? parent->left = cur : parent->right = cur;//如果新节点比父亲节点的值要大，那就插在右边，反之插入在左边
return true;
}
}
private:
Node* _root = nullptr;
};
四、⼆叉搜索树的查找
1.查找的思路：
- 从跟节点开始比较，如果要查找的值是X，那就按照搜索二叉树的性质去查找。X比根节点的大，那就往右边走，反之往左边走。
- 最多查找高度次，如果走到了空，说明没有找到，这个值不存在。
注意： 如果不支持插入相同的值 ，那么找到即可返回，如果支持 插入相同的值，那么就意味着有多个值的存在，一般返回中序的第一个值。
2.查找的代码实现（非递归）
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;//没有找到
}
五、⼆叉搜索树的删除
相比前面的插入和查找，删除搜索二叉树中的数据的难度要大很多。首先要查找是否存在要删除的数据。然后数据存在的话，有以下四种情况（假设要删除的节点是N）
- 要删除的节点N的左右孩子均为空
- 要删除的节点N的左子树为空，但右子树不为空时
- 要删除的节点N的右子树为空，但左子树不为空时
- 要删除的节点N的左右子树均不为空时
以下是以上四种的解决方法，
- 把N结点的⽗亲对应孩⼦指针指向空，直接删除N结点（情况1可以当成2或者3处理，效果是⼀样的）
- 把N结点的⽗亲对应孩⼦指针指向N的右孩⼦，直接删除N结点
- 把N结点的⽗亲对应孩⼦指针指向N的左孩⼦，直接删除N结点
- ⽆法直接删除N结点，因为N的两个孩⼦⽆处安放，只能⽤替换法删除。找N左⼦树的值最⼤结点R(最右结点)或者N右⼦树的值最⼩结点R(最左结点)替代N，因为这两个结点中任意⼀个，放到N的位置，都满⾜⼆叉搜索树的规则。替代N的意思就是N和R的两个结点的值交换，转⽽变成删除R结点，R结点符合情况2或情况3，可以直接删除。
2.删除的代码实现（非递归）
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
parent->left == cur ? parent->left = cur->right :parent->right = cur->right;
delete cur;
return true;
}
else if (cur->right == nullptr)//右子树为空
{
if (parent == nullptr)//删除根节点
{
_root = cur->left;
}
else//判断要删除的节点在父亲节点的左边还是右边，
parent->right == cur ? parent->right = cur->left :parent->left = cur->left;
delete cur;
return true;
}
else//左右子树均不为空时
{
Node* replateparent = cur;//这里不能为空，如果是空的话，那么在删除8的时候就会出现问题
//对空指针解引用
Node* replate = cur->right;
while (replate->left)
{
replateparent = replate;
replate = replate->left;
}
cur->_key = replate->_key;
replateparent->left == replate ?replateparent->left = replate->left :replateparent->right = replate->right;
delete replate;
return true;
}
}
}
}
六、 ⼆叉搜索树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），单词存在，则++单词对应的次数。
七、二叉搜索树的实现
template<class K>
struct BSTNode
{
K _key;
BSTNode<K>* left;
BSTNode<K>* right;
BSTNode(const K& key)
:_key(key)
, left(nullptr)
, right(nullptr)
{}
};
template<class K>
class BSTree
{
public:
typedef BSTNode<K> Node;
bool Insert(const K& key)//插入
{
if (_root == nullptr)
{
_root = new Node(key);
return true;
}
else
{
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);
parent->_key > key ? parent->left = cur : parent->right = cur;
return true;
}
}
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;//没有找到
}
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
parent->left == cur ? parent->left = cur->right :parent->right = cur->right;
delete cur;
return true;
}
else if (cur->right == nullptr)//右边没有孩子时
{
if (parent == nullptr)//删除根节点
{
_root = cur->left;
}
else//判断在父亲节点的左边还是右边，
parent->right == cur ? parent->right = cur->left :parent->left = cur->left;
delete cur;
return true;
}
else//左右子树均不为空时
{
Node* replateparent = cur;//这里不能为空，如果是空的话，那么在删除8的时候就会出现问题
//对空指针解引用
Node* replate = cur->right;
while (replate->left)
{
replateparent = replate;
replate = replate->left;
}
cur->_key = replate->_key;
replateparent->left == replate ?replateparent->left = replate->left :replateparent->right = replate->right;
delete replate;
return true;
}
}
}
}
BSTree& operator=(BSTree tmp)
{
std::swap(_root, tmp._root);
return *this;
}
BSTree() = default;
BSTree(const BSTree& t)
{
_root = Copy(t._root);
}
~BSTree()
{
Destroy(_root);
_root = nullptr;
}
void InOrder()
{
_InOrder(_root);
}
private:
Node* Copy(Node* root)//拷贝构造
{
if (root == nullptr)
return nullptr;
Node* newRoot = new Node(root->_key);
newRoot->left = Copy(root->left);
newRoot->right = Copy(root->right);
return newRoot;
}
void Destroy(Node* root)
{
if (root == nullptr)
{
return;
}
Destroy(root->left);
Destroy(root->right);
delete root;
}
void _InOrder(Node* root)
{
if (root == nullptr)
{
return;
}
_InOrder(root->left);
cout << root->_key << " ";
_InOrder(root->right);
}
private:
Node* _root = nullptr;
};
int main()
{
BSTree<int> t;
int a[] = { 8, 3, 1, 10, 6, 4, 7, 14, 13 };
for (auto x : a)
{
t.Insert(x);
}
t.InOrder();
cout << endl;
t.Erase(3);
t.InOrder();
for (auto x : a)
{
t.Erase(x);
}
}
八、key/value⼆叉搜索树代码实现
注意： key/value二叉搜索二叉树和二叉树搜索树的代码是差不多的。只是多了一个变量value，而且只有在插入的时候value会参与之外，其他的都不会参与。
namespace KeyValue
{
template<class K, class V>
struct BSTNode
{
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
{
public:
typedef BSTNode<K, V> Node;
bool Insert(const K& key, const V& value)//插入
{
if (_root == nullptr)
{
_root = new Node(key, value);
return true;
}
else
{
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);
parent->_key > key ? parent->left = cur : parent->right = cur;
return true;
}
}
Node* 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 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
parent->left == cur ? parent->left = cur->right :
parent->right = cur->right;
delete cur;
return true;
}
else if (cur->right == nullptr)//右边没有孩子时
{
if (parent == nullptr)//删除根节点
{
_root = cur->left;
}
else
parent->right == cur ? parent->right = cur->left :
parent->left = cur->left;
delete cur;
return true;
}
else//两边都有孩子
{
Node* replateparent = cur;
Node* replate = cur->right;
while (replate->left)
{
replateparent = replate;
replate = replate->left;
}
cur->_key = replate->_key;
replateparent->left == replate ?
replateparent->left = replate->left :
replateparent->right = replate->right;
delete replate;
return true;
}
}
}
}
BSTree &operator=(BSTree tmp)//赋值重载
{
std::swap(_root, tmp._root);
return *this;
}
BSTree() = default;//默认构造
BSTree(const BSTree&t)//拷贝构造
{
_root = Copy(t._root);
}
~BSTree()//析构函数
{
Destroy(_root);
_root = nullptr;
}
void InOrder()//中序遍历
{
_InOrder(_root);
}
private:
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;
}
void Destroy(Node*root)
{
if (root == nullptr)
{
return ;
}
Destroy(root->left);
Destroy(root->right );
delete root;
}
void _InOrder(Node* root)//中序遍历
{
if (root == nullptr)
{
return;
}
_InOrder(root->left);
cout << root->_key << ":" << root->_value << endl;
_InOrder(root->right);
}
Node* _root = nullptr;
};
}
int main()
{
string arr[] = { "苹果", "西瓜", "苹果", "西瓜", "苹果", "苹果", "西瓜",
"苹果", "香蕉", "苹果", "香蕉" };
KeyValue::BSTree<string, int> countTree;
for (const auto& str : arr)
{
// 先查找⽔果在不在搜索树中
// 1、不在，说明⽔果第⼀次出现，则插⼊<⽔果, 1>
// 2、在，则查找到的结点中⽔果对应的次数++
//BSTreeNode<string, int>* ret = countTree.Find(str);
auto ret = countTree.Find(str);
if (ret == NULL)
{
countTree.Insert(str, 1);
}
else
{
ret->_value++;
}
}
countTree.InOrder();
KeyValue::BSTree<string, int> countTre= countTree;
countTre.InOrder();
/*KeyValue::BSTree<string, string> v;//实现英文翻译成汉语
v.Insert ("left", "左");
v.Insert("right", "右");
v.Insert("up", "上");
v.Insert("down", "下");
string str;
while (cin >> str)
{
auto ret= v.Find(str);
if (ret == nullptr)
{
cout << "没有找到" << endl;
}
else
cout << ret->_key << " ";
}*/
}
总结
今天的分享就到这啦，有什么问题咋们评论区一起讨论吧，咋们下期再见！拜拜咯
