网站怎么做查询系统,如何推广店铺呢,阿里云企业邮箱怎么申请,网站建设实施计划包括哪些方面✨✨小新课堂开课了#xff0c;欢迎欢迎~✨✨ #x1f388;#x1f388;养成好习惯#xff0c;先赞后看哦~#x1f388;#x1f388; 所属专栏#xff1a;C#xff1a;由浅入深篇 小新的主页#xff1a;编程版小新-CSDN博客 前言#xff1a; 我们在前面已经学习过有关… ✨✨小新课堂开课了欢迎欢迎~✨✨ 养成好习惯先赞后看哦~ 所属专栏C由浅入深篇 小新的主页编程版小新-CSDN博客 前言 我们在前面已经学习过有关二叉树的相关知识今天我们要学习的搜索二叉树和前面我们学习的普通树结构有什么区别呢我们来一起看看为啥称搜索二叉树是数据管理的智慧之选吧。这里要介绍的是普通的二叉搜索树像AVL树红黑树这种特殊的二叉搜索树我们单独放在一篇博客说明。 一.二叉搜索树的概念
二叉搜索树又称二叉排序树它或者是一棵空树或者是具有以下性质的二叉树: 若它的左子树不为空则左子树上所有结点的值都小于等于根结点的值若它的右子树不为空则右子树上所有结点的值都大于等于根结点的值它的左右子树也分别为二叉搜索树 示例以下就是两棵二叉搜索树 注意 二叉搜索树中可以支持插入相等的值也可以不支持插入相等的值具体看使用场景定义后续我们学习map/set/multimap/multiset系列容器底层就是二叉搜索树其中map/set不支持插入相等值multimap/multiset支持插入相等值。 二.二叉搜索树的常见操作
2.1插入操作 插入的具体过程如下 1. 树为空则直接新增结点赋值给root指针 2. 树不为空按二叉搜索树性质插入值比当前结点大往右走插入值比当前结点小往左走找到空位置插入新结点。 3. 如果支持插入相等的值插入值跟当前结点相等的值可以往右走也可以往左走找到空位置插入新结点。要注意的是要保持逻辑⼀致性插⼊相等的值不要一会往右走一会往左走 上面的插入过程就保证了在完成插入操作后这棵树仍然满足搜索二叉树的特点。 bool Insert(const K key)
{//如果树为空,直接新增节点赋值给_rootif (_root nullptr){_root new Node(key);return true;}//如果树不为空Node* parent nullptr;//parent的存在就是为了插入的我们要插入在parent的左孩子或者右孩子Node* cur _root;//找到空位置插入节点while (cur){//插入值比当前节点小往左走if (key cur-_key){parent cur;cur cur-_left;}else if (key cur-_key)//插入值比当前节点大往右走{parent cur;cur cur-_right;}else{return false;//我们不支持插入相同的值}}//找到了cur就是当前要插入的位置cur new Node(key);//判断是插入到parent的左边还是右边if (key parent-_key){//往左走parent-_left cur;}else{//往右走parent-_right cur;}return true;} 2.2查找操作 查找的具体过程如下 1. 从根开始比较查找xx比根的值大则往右边走查找x比根值小则往左边走查找。 2. 最多查找高度次走到到空还没找到这个值不存在。 3. 如果不支持插入相等的值找到x即可返回。 4. 如果支持插入相等的值意味着有多个x存在一般要求查找中序的第一个x。如下图查找3要找到1的右孩子的那个3返回。 通过上面的查找过程可以发现我们查找一个元素最多只需查找高度次就能得到结果在一定条件下这个查找效率还是蛮不错的但是当树严重不平衡时查找效率就变得非常低。
我们来举个例子如果搜索二叉树的插入顺序不当可能会导致树变得严重不平衡退化成链表结构。在这种情况下查找操作的时间复杂O(N). //实现的是不允许有相同值的搜索二叉树
bool Find(const K key)
{Node* cur _root;while (cur){if (key cur-_key){//小于往左走cur cur-_left;}else if (key cur-_key){//大于往右走cur cur-_right;}else//{return true;//找到了}}return false;//没找到
}
2.3删除操作
首先查找元素是否在二叉搜索树中如果不存在则返回false。 如果查找元素存在则分以下四种情况分别处理假设要删除的结点为N 1. 要删除结点N左右孩子均为空 2. 要删除的结点N左孩子为空右孩子结点不为空 3. 要删除的结点N右孩子为空左孩子结点不为空 4. 要删除的结点N左右孩子结点均不为空 对应以上四种情况的解决方案 1. 把N结点的父亲对应孩子指针指向空直接删除N结点情况1可以当成2或者3处理效果是一样的 2. 把N结点的父亲对应孩子指针指向N的右孩子直接删除N结点 3. 把N结点的父亲对应孩子指针指向N的左孩子直接删除N结点 4. 无法直接删除N结点因为N的两个孩子无处安放只能用替换法删除。 找N左子树的值最大结点R(最右结点)或者N右子树的值最小结点R(最左结点)替代N因为这两个结点中任意一个放到N的位置都满足二叉搜索树的规则。替代N的意思就是N和R的两个结点的值交换转而变成删除R结点R结点符合情况2或情况3可以直接删除。 bool Erase(const K key)
{Node* parent nullptr;Node* cur _root;while (cur){if (key cur-_key){//小于往左走parent cur;cur cur-_left;}else if (key cur-_key){//大于往右走parent cur;cur cur-_right;}else//找到了{//删除//左为空if (cur-_left nullptr){//根节点要特殊考虑根节点没有父亲if (cur _root){_root cur-_right;}else{if (parent-_left cur)//要删除节点是parent的左孩子{parent-_left cur-_right;//父亲对应孩子指针指向N的右孩子左为空}else//要删除节点是parent的右孩子{parent-_right cur-_right;//父亲对应孩子指针指向N的右孩子左为空}}delete cur;//直接删除}else if (cur-_right nullptr)//右为空{//根节点要特殊考虑根节点没有父亲if (cur _root){_root cur-_left;}else{if (parent-_left cur)//要删除节点是parent的左孩子{parent-_left cur-_left;//父亲对应孩子指针指向N的左孩子右为空}else//要删除节点是parent的右孩子{parent-_right cur-_left;//父亲对应孩子指针指向N的左孩子右为空}}delete cur;//直接删除}else{//左右都不为空采用替换法//以找右子树最左节点为例Node* replaceparent cur;Node* replace cur-_right;while (replace-_left)//左为空{replaceparent replace;replace replace-_left;}//交换值cur-_key replace-_key;//删除replace节点if (replaceparent-_left replace)//要删除节点是replaceparent的左孩子{replaceparent-_left replace-_right;// 父亲对应孩子指针指向N的右孩子左为空}else{replaceparent-_right replace-_right;// 父亲对应孩子指针指向N的右孩子左为空}delete replace;}return true;}}return false;
} 2.4二叉树搜索树实现代码
namespace key
{templateclass K//Binary Search Tree Nodestruct BSTNode{K _key;//树节点的数据BSTNodeK* _left;//树节点的左孩子BSTNodeK* _right;//树节点的右孩子BSTNode(const K key)//初始化根节点:_key(key), _left(nullptr), _right(nullptr){}};templateclass K//Binary Search Treeclass BSTree{//两种重命名的方式//typedef BSTNodeK Node;using Node BSTNodeK;public:bool Insert(const K key){//如果树为空,直接新增节点赋值给_rootif (_root nullptr){_root new Node(key);return true;}//如果树不为空Node* parent nullptr;//parent的存在就是为了插入的我们要插入在parent的左孩子或者右孩子Node* cur _root;//找到空位置插入节点while (cur){//插入值比当前节点小往左走if (key cur-_key){parent cur;cur cur-_left;}else if (key cur-_key)//插入值比当前节点大往右走{parent cur;cur cur-_right;}else{return false;//我们不支持插入相同的值}}//找到了cur就是当前要插入的位置cur new Node(key);//判断是插入到parent的左边还是右边if (key parent-_key){//往左走parent-_left cur;}else{//往右走parent-_right cur;}return true;}bool Find(const K key){Node* cur _root;while (cur){if (key cur-_key){//小于往左走cur cur-_left;}else if (key cur-_key){//大于往右走cur cur-_right;}else//{return true;//找到了}}return false;//没找到}bool Erase(const K key){Node* parent nullptr;Node* cur _root;while (cur){if (key cur-_key){//小于往左走parent cur;cur cur-_left;}else if (key cur-_key){//大于往右走parent cur;cur cur-_right;}else//找到了{//删除//左为空if (cur-_left nullptr){//根节点要特殊考虑根节点没有父亲if (cur _root){_root cur-_right;}else{if (parent-_left cur)//要删除节点是parent的左孩子{parent-_left cur-_right;//父亲对应孩子指针指向N的右孩子左为空}else//要删除节点是parent的右孩子{parent-_right cur-_right;//父亲对应孩子指针指向N的右孩子左为空}}delete cur;//直接删除}else if (cur-_right nullptr)//右为空{//根节点要特殊考虑根节点没有父亲if (cur _root){_root cur-_left;}else{if (parent-_left cur)//要删除节点是parent的左孩子{parent-_left cur-_left;//父亲对应孩子指针指向N的左孩子右为空}else//要删除节点是parent的右孩子{parent-_right cur-_left;//父亲对应孩子指针指向N的左孩子右为空}}delete cur;//直接删除}else{//左右都不为空采用替换法//以找右子树最左节点为例Node* replaceparent cur;Node* replace cur-_right;while (replace-_left)//左为空{replaceparent replace;replace replace-_left;}//交换值cur-_key replace-_key;//删除replace节点if (replaceparent-_left replace)//要删除节点是replaceparent的左孩子{replaceparent-_left replace-_right;// 父亲对应孩子指针指向N的右孩子左为空}else{replaceparent-_right replace-_right;// 父亲对应孩子指针指向N的右孩子左为空}delete replace;}return true;}}return false;}//在类外无法直接访问_rootvoid InOrder(){_InOrder(_root);cout endl;}private://中序遍历打印void _InOrder(Node* root){if (root nullptr){return;}_InOrder(root-_left);cout root-_key ;_InOrder(root-_right);}private:Node* _root nullptr;};}
三.二叉搜索树的性能分析
最优情况下二叉搜索树为完全二叉树(或者接近完全二叉树)其高度为 O(log2 N)。
最差情况下二叉搜索树退化为单支树(或者类似单支)其高度为 O( N)。 所以综合而言二叉搜索树增删查的时间复杂度为 O(N)。
那么这样的效率显然是无法满足我们需求的我们后续需要继续讲解⼆叉搜索树的变形平衡⼆叉搜索树AVL树和红黑树才能适用于我们在内存中存储和搜索数据。
另外需要说明的是二分查找也可以实现 O(logN) 级别的查找效率但是二分查找有两大缺陷 1. 需要存储在支持下标随机访问的结构中并且有序。
2. 插入和删除数据效率很低因为存储在下标随机访问的结构中插入和删除数据⼀般需要挪动数据。
这里也就体现出了平衡二叉搜索树的价值。我们后面一起了解。
四.二叉搜索树key和key/value使用场景
4.1 key搜索场景 只有key作为关键码结构中只需要存储key即可关键码即为需要搜索到的值搜索场景只需要判断key在不在。key的搜索场景实现的二叉树搜索树支持增删查但是不支持修改修改key破坏搜索树结构了。 场景1小区无人值守车库小区车库买了车位的业主车才能进小区那么物业会把买了车位的业主的车牌号录入后台系统车辆进入时扫描车牌在不在系统中在则抬杆不在则提示非本小区车辆无法进入。
场景2检查一篇英文文章单词拼写是否正确将词库中所有单词放入二叉搜索树读取问章中的单词查找是否在二叉搜索树中不在则波浪线标红线提示。
像我们在上面实现的二叉搜索树就满足key搜索场景。
4.2 key/value搜索场景 每一个关键码key都有与之对应的值valuevalue可以任意类型对象。树的结构中(结点)除了需要存储key还要存储对应的value增/删/查还是以key为关键字走二叉搜索树的规则进行比较可以快速查找到key对应的value。key/value的搜索场景实现的二叉树搜索树支持修改但是不支持修改key修改key破坏搜索树结构了可以修改value。 场景1简单中英互译字典树的结构中(结点)存储key(英文)和vlaue(中文)搜索时输入英文则同时查找到了英文对应的中文。
场景2商场无人值车库入口进场时扫描车牌记录车牌和入场时间出口离场时扫描车牌查找入场时间用当前时间-入场时间计算出停车时长计算出停车费用缴费后抬杆车辆离场。
场景3统计一篇文章中单词出现的次数读取⼀个单词查找单词是否存在不存在这个说明第一次出现单词1单词存在则单词对应的次数。
我们在原来实现的二叉搜索树的基础上做些简单的整改即可。
namespace key_value
{templateclass K, class Vstruct BSTNode{K _key;V _value;BSTNodeK, V* _left;BSTNodeK, V* _right;BSTNode(const K key, const V value):_key(key), _value(value), _left(nullptr), _right(nullptr){}};// Binary Search Tree// Key/valuetemplateclass K, class Vclass BSTree{//typedef BSTNodeK Node;using Node BSTNodeK, V;public:// 强制生成构造BSTree() default;BSTree(const BSTree t){_root Copy(t._root);}BSTree operator(BSTree tmp){swap(_root, tmp._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 (key cur-_key){parent cur;cur cur-_left;}else if (key cur-_key){parent cur;cur cur-_right;}else{return false;}}cur new Node(key, value);if (key parent-_key){parent-_left cur;}else{parent-_right cur;}return true;}Node* Find(const K key){Node* cur _root;while (cur){if (key cur-_key){cur cur-_left;}else if (key cur-_key){cur cur-_right;}else{return cur;//找到了}}return nullptr;}bool Erase(const K key){Node* parent nullptr;Node* cur _root;while (cur){if (key cur-_key){ parent cur;cur cur-_left;}else if (key cur-_key){parent cur;cur cur-_right;}else{//删除//左为空if (cur-_left nullptr){if (cur _root){_root cur-_right;}else{if (parent-_left cur){parent-_left cur-_right;}else{parent-_right cur-_right;}}delete cur;}else if (cur-_right nullptr)//右为空{if (cur _root){_root cur-_left;}else{if (parent-_left cur){parent-_left cur-_left;}else{parent-_right cur-_left;}}delete cur;}else{//左右都不为空Node* replaceparent cur;Node* replace cur-_right;while (replace-_left)//左为空{replaceparent replace;replace replace-_left;}cur-_key replace-_key;if (replaceparent-_left replace){replaceparent-_left replace-_right;}else{replaceparent-_right replace-_right;}delete replace;}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()
{string arr[] { 苹果, 西瓜, 苹果, 西瓜, 苹果, 苹果, 西瓜,苹果, 香蕉, 苹果, 香蕉 };key_value::BSTreestring, int countTree;for (const auto str : arr){// 先查找水果在不在搜索树中// 1、不在说明水果第一次出现则插入水果, 1// 2、在则查找到的结点中水果对应的次数//BSTreeNodestring, int* ret countTree.Find(str);auto ret countTree.Find(str);if (ret nullptr){countTree.Insert(str, 1);}else{// 修改valueret-_value;}}countTree.InOrder();key_value::BSTreestring, int copy countTree;copy.InOrder();return 0;
}
总结 二叉搜索树的基本特点及其使用场景我们已经介绍完了还有一些知识点我们没提我们后面先谈map/set/multimap/multiset系列容器它们的底层就是二叉搜索树之后再介绍平衡二叉搜索树AVL树和红黑树。大家快来一起学习吧。 感谢各位大佬的观看创作不易还请各位大佬点赞支持~
