【高阶数据结构】二叉搜索树

Ne0inhk

— 17 min read
【高阶数据结构】二叉搜索树

二叉搜索树

1.二叉搜索树的概念

二叉搜索树又称搜索二叉树，它或者是一棵空树，或者是具有以下性质的⼆叉树：

若它的左子树不为空，则左子树上所有结点的值都小于等于根结点的值。若它的右子树不为空，则右子树上所有结点的值都大于等于根结点的值。它的左右子树也分别为⼆叉搜索树。

⼆叉搜索树中可以支持插入相等的值，也可以不支持插入相等的值，具体看使用场景定义，map/set/multimap/multiset 系列容器底层就是⼆叉搜索树，其中map/set不支持插入相等值，multimap/multiset支持插入相等值。

在这里插入图片描述

2.二叉搜索树的性能分析

最优情况下，二叉搜索树为完全二叉树（或者接近完全⼆叉树），其高度为：O(logN)最差情况下，二叉搜索树退化为单支树（或者类似单支），其高度为：O(N)所以综合而言二叉搜索树增删查改时间复杂度为：O(N)
在这里插入图片描述

那么这样的效率显然是无法满足我们需求的，所以有了⼆叉搜索树的变形，平衡⼆叉搜索树。

平衡⼆叉搜索树：AVL树和红黑树平衡多叉搜索树：B树系列（B+树…）

它们适用于我们在内存中存储和搜索数据，另外需要说明的是，⼆分查找也可以实现O(logN) 级别的查找效率，但是⼆分查找有两大缺陷：

需要存储在支持下标随机访问的结构中，并且有序。插入和删除数据效率很低，因为存储在下标随机访问的结构中，插入和删除数据一般需要挪动数据。

这里也就体现出了平衡⼆叉搜索树的价值。

3.二叉搜索树的实现

1.二叉搜索树的结构

  1. 准备树的节点（存放两个自己类型的指针找到左右孩子 + 保存某个类型的数据）
  2. 准备二叉搜索树：存放根节点。
  3. 这里实现的是不能含有重复的数据。
namespace xzy {template<classK>structBSNode{ BSNode<K>* _left; BSNode<K>* _right; K _key;BSNode(const K& key =K()):_left(nullptr),_right(nullptr),_key(key){}};template<classK>classBSTree{public://以下两种功能一样：都是取别名//typedef BSNode<K> Node;using Node = BSNode<K>;private: Node* _root =nullptr;//给出缺省值};}

2.二叉搜索树的插入

插入的具体过程如下：

树为空：则直接新增结点，赋值给root指针。树不空：按⼆叉搜索树性质，插入值比当前结点大往右走，插入值比当前结点小往左走，找到空位置，插入新结点。如果支持插入相等的值，插入值跟当前结点相等的值可以往右走，也可以往左走，找到空位置，插入新结点。（要注意的是要保持逻辑⼀致性，插入相等的值不要一会往右走，一会往左走）
在这里插入图片描述
在这里插入图片描述
//迭代boolInsert(const K& key){//若树为空：将要插入的节点赋值给根节点if(_root ==nullptr){ _root =newNode(key);returntrue;}//若树不为空：查找要插入的位置 + 它的父亲节点 Node* parent =nullptr; Node* cur = _root;while(cur){if(cur->_key > key){ parent = cur; cur = cur->_left;}elseif(cur->_key < key){ parent = cur; cur = cur->_right;}else{returnfalse;//相等，则无法插入}}//找到了要插入的位置 + 它的父亲节点, 然后判断插入的位置 Node* newnode =newNode(key);if(parent->_key > key){ parent->_left = newnode;}elseif(parent->_key < key){ parent->_right = newnode;}returntrue;}//递归public:voidInsert(const K& key){ _root =_Insert(_root, key);}private: Node*_Insert(Node* root,const K& key){if(root ==nullptr)returnnewNode(key);if(root->_key < key) root->_right =_Insert(root->_right, key);elseif(root->_key > key) root->_left =_Insert(root->_left, key);return root;}

3.二叉搜索树的查找

从根开始比较，查找x，x比根的值大则往右边走查找，x比根值小则往左边走查找。最多查找高度次，走到到空，还没找到，这个值不存在。如果不支持插入相等的值，找到x即可返回。如果支持插入相等的值，意味着有多个x存在，一般要求查找中序的第一个x。如下图，查找3，要找到1的右孩子的那个3返回。
在这里插入图片描述
//循环boolFind(const K& key){ Node* cur = _root;while(cur){if(cur->_key < key){ cur = cur->_right;}elseif(cur->_key > key){ cur = cur->_left;}else{returntrue;//找到了}}returnfalse;//未找到}
//递归public:boolFind(const K& key){return_Find(_root, key);}private:bool_Find(Node* _root,const K& key){if(_root ==nullptr)returnfalse;bool ret1 =false;bool ret2 =false;if(_root->_key == key){returntrue;}elseif(_root->_key < key){ ret1 =Find(_root->_right, key);}else{ ret2 =Find(_root->_left, key);}return ret1 || ret2;}

4.二叉搜索树的删除

首先查找元素是否在⼆叉搜索树中，如果不存在，则返回false。如果查找元素存在则分以下四种情况分别处理：

要删除结点N左右孩子均为空。要删除的结点N左孩子为空，右孩子结点不为空。要删除的结点N右孩子为空，左孩子结点不为空。要删除的结点N左右孩子结点均不为空。

对应以上四种情况的解决方案：

  1. 把N结点的父亲对应孩子指针指向空，直接删除N结点（情况1可以当成情况2或者情况3处理，效果是一样的）
在这里插入图片描述
  1. 把N结点的父亲对应孩子指针指向N的右孩子，直接删除N结点。
在这里插入图片描述
  1. 把N结点的父亲对应孩子指针指向N的左孩子，直接删除N结点。
在这里插入图片描述
  1. 无法直接删除N结点，因为N的两个孩子无处安放，可以用替换法删除。找N左子树的值最大结点R（最右节点）或者N右子树的值最小结点R（最左节点）替代N，因为这两个结点中任意一个，放到N的位置，都满足二叉搜索树的规则。替代N的意思就是N和R的两个结点的值交换，转而变成删除R结点，R结点又符合情况2或情况3，可以直接删除。
在这里插入图片描述
boolErase(const K& key){ Node* parent =nullptr; Node* cur = _root;//找要删除的节点while(cur){if(cur->_key > key){ parent = cur; cur = cur->_left;}elseif(cur->_key < key){ parent = cur; cur = cur->_right;}else{//找到了，开始删除操作：删除cur，cur的父亲节点是parent//1.删除节点的左孩子为空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;}//2.删除节点的右孩子为空elseif(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;}//3.删除节点的左孩子和右孩子都为空else{//用要删除节点的左子树中最大值的节点替换要删除的节点（值覆盖）//当然也可以使用右子树中最小值的节点 Node* replace = cur->_left; Node* replaceParent = cur;while(replace->_right){ replaceParent = replace; replace = replace->_right;} cur->_key = replace->_key;//值覆盖//要删除的replace节点的孩子最多只有一个，复用情况1/2if(replaceParent->_left == replace){ replaceParent->_left = replace->_left;}else{ replaceParent->_right = replace->_left;}delete replace;}returntrue;}}returnfalse;//没有要删除的数据}

5.二叉搜索树的中序遍历

  1. 由于二叉搜索树的性质，左子树小于根，根又小于右子树，那么它的中序遍历就可以得到一个有序的数据
  2. 但是由于要传入根节点，而外面是访问不到根节点的，可以封装另一个接口，如下：
public:voidInOrder(){_InOrder(_root); cout << endl;}private:void_InOrder(Node* _root){if(_root ==nullptr)return;_InOrder(_root->_left); cout << _root->_key <<" ";_InOrder(_root->_right);}
intmain(){ vector<int> v ={8,3,1,10,6,4,7,14,13}; xzy::BSTree<int> t;for(auto& e : v){ t.Insert(e);} t.InOrder();//输出: 1 3 4 6 7 8 10 13 14return0;}

6.默认构造

//强制生成默认构造BSTree()=default;

7.拷贝构造

前序遍历构造二叉搜索树

public:BSTree(const BSTree& t){ _root =Copy(t._root);}private: Node*Copy(Node* root){if(root ==nullptr)returnnullptr; Node* newRoot =newNode(root->_key); newRoot->_left =Copy(root->_left); newRoot->_right =Copy(root->_right);return newRoot;}

8.赋值重载

现代写法：利用传值传参+拷贝构造

BSTree&operator=(BSTree tmp){swap(_root, tmp._root);return*this;}

9.析构函数

后序遍历析构二叉搜索树

public:~BSTree(){Destory(_root);}private:voidDestory(Node* _root){if(_root ==nullptr)return;Destory(_root->_left);Destory(_root->_right);delete _root;}

4.二叉搜索树key和key/value使用场景

1.key搜索场景（set容器）

只有key作为关键码，结构中只需要存储key即可，关键码即为需要搜索到的值，搜索场景只需要判断key在不在。key的搜索场景实现的二叉树搜索树支持增删查，但是不支持修改，修改key破坏搜索树结构了。

场景1：小区无人值守车库，小区车库买了车位的业主车才能进小区，那么物业会把买了车位的业主的车牌号录入后台系统，车辆进入时扫描车牌在不在系统中，在则抬杆，不在则提示非本小区车辆，无法进入。

场景2：检查一篇英文文章单词拼写是否正确，将词库中所有单词放入二叉搜索树，读取文章中的单词，查找是否在⼆叉搜索树中，不在则波浪线标红提示。

在这里插入图片描述

2.key/value搜索场景（map容器）

每一个关键码key，都有与之对应的值value，value可以任意类型对象。树的结构中（结点）除了需要存储key还要存储对应的value，增/删/查还是以key为关键字走二叉搜索树的规则进行比较，可以快速查找到key对应的value。key/value的搜索场景实现的⼆叉树搜索树支持修改，但是不支持修改key，修改key破坏搜索树结构了，可以修改value。

场景1：简单中英互译字典，树的结构中（结点）存储key（英文）和vlaue（中文），搜索时输入英文，则同时查找到了英文对应的中文。

场景2：商场无人值守车库，入口进场时扫描车牌，记录车牌和入场时间，出口离场时，扫描车牌，查找入场时间，用当前时间 - 入场时间计算出停车时长，计算出停车费用，缴费后抬杆，车辆离场。

场景3：统计一篇文章中单词出现的次数，读取一个单词，查找单词是否存在，不存在这个说明第一次出现（单词，1），单词存在，则++单词对应的次数。

在这里插入图片描述

5.key二叉搜索树代码

namespace key {template<classK>structBSNode{ BSNode<K>* _left; BSNode<K>* _right; K _key;BSNode(const K& key =K()):_left(nullptr),_right(nullptr),_key(key){}};template<classK>classBSTree{public://以下两种功能一样：都是取别名//typedef BSNode<K> Node;using Node = BSNode<K>;boolInsert(const K& key){//若树为空：将要插入的节点赋值给根节点if(_root ==nullptr){ _root =newNode(key);returntrue;}//若树不为空：查找要插入的位置 + 它的父亲节点 Node* parent =nullptr; Node* cur = _root;while(cur){if(cur->_key > key){ parent = cur; cur = cur->_left;}elseif(cur->_key < key){ parent = cur; cur = cur->_right;}else{returnfalse;//相等，则无法插入}}//找到了要插入的位置 + 它的父亲节点; 然后判断左右孩子 Node* newnode =newNode(key);if(parent->_key > key){ parent->_left = newnode;}elseif(parent->_key < key){ parent->_right = newnode;}returntrue;}boolFind(const K& key){ Node* cur = _root;while(cur){if(cur->_key < key){ cur = cur->_right;}elseif(cur->_key > key){ cur = cur->_left;}else{returntrue;}}returnfalse;}boolErase(const K& key){ Node* parent =nullptr; Node* cur = _root;//找要删除的节点while(cur){if(cur->_key > key){ parent = cur; cur = cur->_left;}elseif(cur->_key < key){ parent = cur; cur = cur->_right;}else{//找到了，开始删除操作：删除cur，cur的父亲节点是parent//1.删除节点的左孩子为空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;}//2.删除节点的右孩子为空elseif(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;}//3.删除节点的左孩子和右孩子都为空else{//用要删除节点的左子树中最大值的节点替换要删除的节点（值覆盖）//当然也可以使用右子树中最小值的节点 Node* replace = cur->_left; Node* replaceParent = cur;while(replace->_right){ replaceParent = replace; replace = replace->_right;} cur->_key = replace->_key;//值覆盖//要删除的replace节点的孩子最多只有一个，复用情况1/2if(replaceParent->_left == replace){ replaceParent->_left = replace->_left;}else{ replaceParent->_right = replace->_left;}delete replace;}returntrue;}}returnfalse;//没有要删除的数据}voidInOrder(){_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;};}intmain(){ vector<int> v ={8,3,1,10,6,4,7,14,13}; key::BSTree<int> t;for(auto& e : v){ t.Insert(e);}for(auto& e : v){ t.Erase(e); t.InOrder();}return0;}

6.key/value二叉搜索树代码

namespace key_value {template<classK,classV>structBSNode{ BSNode<K, V>* _left; BSNode<K, V>* _right; K _key; V _value;BSNode(const K& key =K(),const V& value =V()):_left(nullptr),_right(nullptr),_key(key),_value(value){}};template<classK,classV>classBSTree{public://以下两种功能一样：都是取别名//typedef BSNode<K> Node;using Node = BSNode<K, V>;boolInsert(const K& key,const V& value){//若树为空：将要插入的节点赋值给根节点if(_root ==nullptr){ _root =newNode(key, value);returntrue;}//若树不为空：查找要插入的位置 + 它的父亲节点 Node* parent =nullptr; Node* cur = _root;while(cur){if(cur->_key > key){ parent = cur; cur = cur->_left;}elseif(cur->_key < key){ parent = cur; cur = cur->_right;}else{returnfalse;//相等，则无法插入}}//找到了要插入的位置 + 它的父亲节点; 然后判断左右孩子 Node* newnode =newNode(key, value);if(parent->_key > key){ parent->_left = newnode;}elseif(parent->_key < key){ parent->_right = newnode;}returntrue;} Node*Find(const K& key){ Node* cur = _root;while(cur){if(cur->_key < key){ cur = cur->_right;}elseif(cur->_key > key){ cur = cur->_left;}else{return cur;}}returnnullptr;}boolErase(const K& key){ Node* parent =nullptr; Node* cur = _root;//找要删除的节点while(cur){if(cur->_key > key){ parent = cur; cur = cur->_left;}elseif(cur->_key < key){ parent = cur; cur = cur->_right;}else{//找到了，开始删除操作：删除cur，cur的父亲节点是parent//1.删除节点的左孩子为空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;}//2.删除节点的右孩子为空elseif(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;}//3.删除节点的左孩子和右孩子都为空else{//用要删除节点的左子树中最大值的节点替换要删除的节点（值覆盖） Node* replace = cur->_left; Node* replaceParent = cur;while(replace->_right){ replaceParent = replace; replace = replace->_right;} cur->_key = replace->_key;//值覆盖//要删除的replace节点的孩子最多只有一个，复用情况1/2if(replaceParent->_left == replace){ replaceParent->_left = replace->_left;}else{ replaceParent->_right = replace->_left;}delete replace;}returntrue;}}returnfalse;//没有要删除的数据}voidInOrder(){_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);}private: Node* _root =nullptr;};}inttest01(){ key_value::BSTree<string, string> 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;}}return0;}inttest02(){ string arr[]={"苹果","西瓜","苹果","西瓜","苹果","苹果","西瓜","苹果","香蕉","苹果","香蕉"}; key_value::BSTree<string,int> countTree;for(constauto& 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();return0;}

Read more

【优选算法必刷100题】第029-030题（前缀和）：和为k的子数组，和可被k整除的子数组

【优选算法必刷100题】第029-030题（前缀和）：和为k的子数组，和可被k整除的子数组

🔥个人主页：Cx330🌸 ❄️个人专栏：《C语言》《LeetCode刷题集》《数据结构-初阶》《C++知识分享》 《优选算法指南-必刷经典100题》《Linux操作系统》:从入门到入魔 🌟心向往之行必能至 🎥Cx330🌸的简介： 目录 前言： 29. 和为k的子数组 算法原理（前缀和+哈希）： 前缀和解法代码（C++）： 博主手记（字体还请见谅哈）： 30. 和可被k整除的子数组 算法原理（前缀和+哈希）： 前置知识补充： 前缀和解法代码（C++）： 博主手记（字体还请见谅哈）： 结尾： 前言： 聚焦算法题实战，系统讲解三大核心板块：“精准定位最优解”——优选算法，“简化逻辑表达，系统性探索与剪枝优化”——递归与回溯，“以局部最优换全局高效”——贪心算法，讲解思路与代码实现，帮助大家快速提升代码能力 前缀和专题 29.

By Ne0inhk
Redis魔法学院——第四课：哈希（Hash）深度解析：Field-Value 层级结构、原子性操作与内部编码优化

Redis魔法学院——第四课：哈希（Hash）深度解析：Field-Value 层级结构、原子性操作与内部编码优化

引言： 在Redis中，哈希结构还有一层更深的意义，跟我们习以为常的key-value的哈希结构有所不同的是，还有一层更深的意义，我们由此来引入filed这个概念~ Redis 自身已经是键值对结构了 Redis 自身的键值对就是通过 哈希 的方式来组织的. 把 key 这一层组织完成之后, 到了 value 这一层~~ value 的其中一种类型还可以再是哈希！ 形如 key="key"，value={{field1, value1},…, {fieldN,valueN }}，Redis 键值对和哈希类型二者的关系可以用下图表示。 field-value和key-value的深层次解析： 在Redis中，field-value和key-value是层级嵌套关系，其中key是全局唯一标识符，指向一个哈希（Hash）结构；而field是该哈希内部的字段名，与对应的value组成键值对，存储在哈希中。以下是具体分析： 1. 层级关系：全局Key → 哈希结构 → 多个Field-Value * 全局Key：Redis中的每个数据对象（

By Ne0inhk
【优选算法】双指针算法：专题一

【优选算法】双指针算法：专题一

目录 引言： 【283.移动零】 1、题目描述 2、实现核心及思路 解题思路： 思路可视化： 代码实现： 代码测试： 【1089.复写零】 1、题目描述 2、实现核心及思路 解题思路： 思路可视化： 代码实现： 代码测试： 【202. 快乐数】 1、题目描述 2、实现核心及思路 解题思路： 代码实现： 【11. 盛水最多容器】 1、题目描述 2、实现核心及思路 解题思路： 思路可视化： 代码实现： 引言： 常见的双指针有两种形式，一种是对撞指针，一种是快慢指针。 对撞指针：一般用于顺序结构中，也称左右指针。 • 对撞指针从两端向中间移动。一个指针从最左端开始，另一个从最右端开始，然后逐渐往中间逼近。

By Ne0inhk
【数据结构】深入解析选择排序与堆排序：从基础到高效实现的完全指南

【数据结构】深入解析选择排序与堆排序：从基础到高效实现的完全指南

文章目录 * 选择排序 * 1基本思想： * 2 直接选择排序: * 3. 堆排序 * 基本思想 * 堆排序的C语言实现 * 堆排序的工作原理 * 堆排序的性能分析 * 4. 选择排序与堆排序的比较 * 5. 选择排序的变种与优化 * 结语 * 结语 选择排序 1基本思想： 每一次从待排序的数据元素中选出最小（或最大）的一个元素，存放在序列的起始位置，直到全部待排序的 数据元素排完 。 2 直接选择排序: 在元素集合array[i]–array[n-1]中选择关键码最大(小)的数据元素 若它不是这组元素中的最后一个(第一个)元素，则将它与这组元素中的最后一个（第一个）元素交换 在剩余的array[i]–array[n-2]（array[i+1]–array[n-1]）集合中，

By Ne0inhk