网站策划案怎么写范文,教做吃的网站,东莞健康app下载,番禺网站推广公司在初阶数据结构中我学习了树基础的概念以及了解了顺序结构的二叉树——堆和链式结构二叉树该如何实现#xff0c;那么接下来我们将进一步的学习二叉树#xff0c;在此会先后学习到二叉搜索树、AVL树、红黑树#xff1b;通过这些的学习将让我们更易于理解后面set、map、哈希等…在初阶数据结构中我学习了树基础的概念以及了解了顺序结构的二叉树——堆和链式结构二叉树该如何实现那么接下来我们将进一步的学习二叉树在此会先后学习到二叉搜索树、AVL树、红黑树通过这些的学习将让我们更易于理解后面set、map、哈希等的使用以及对底层结构的了解。在此先本篇中我们将了解二次搜索树的概念以及实现二叉搜索树插入、删除等的操作在了解了这些之后相信在下一篇的set和map的学习你将轻松许多接下来就开始本篇的学习吧 1.二叉搜索树的概念
二叉搜索树又称二叉排序树它或者是⼀棵空树或者是具有以下性质的二叉树: • 若它的左子树不为空则左子树上所有结点的值都小于等于根结点的值• 若它的右子树不为空则右子树上所有结点的值都大于等于根结点的值• 它的左右子树也分别为二叉搜索树• 二叉搜索树中可以支持插入相等的值也可以不支持插入相等的值具体看使用场景定义后续我们学习map/set/multimap/multiset系列容器底层就是二叉搜索树其中map/set不支持插入相等值multimap/multiset支持插入相等值 例如以下左边图示的就是不支持插入相等值得二叉搜索树右边就是支持插入相等值得二叉搜索树 2. 二叉搜索树的性能分析
最好得情况下在此在二叉搜索树当中最为完全二叉树(或者接近完全二叉树)其高度为
例如以下示例 最差情况下在此⼆叉搜索树退化为单支树(或者类似单支)其高度为
例如以下示例 那么通过以上对二叉树最好和最坏情况的分析就可以得出综合而言二叉搜索树增删查改时间复杂度为 那么通过以上的分析可以看出二叉搜索树这样的效率显然无法满足我们需求的我们后续需要继续讲解二叉搜索树的变形平衡二叉搜索树AVL树和红黑树才能适用于我们在内存中存储和搜索数据。
在此你可能会想到在二叉搜索树中查找数据不就类似与二分查找吗那么直接使用之前学习的二分查找不就可以了吗二分查找的效率相比二叉搜索树还更好那为什么还要学习了解二叉搜索树呢在此二分查找也可以实现 O(logN) 级别的查找效率但是二分查找有两大缺陷 1. 需要存储在支持下标随机访问的结构中并且有序。 在使用到二分查找示我们使用的是数据对应的下标来实现查找这就使得当被查找的一系列数据不是存储在数组里时就需要先将数据都存储在数组当中并且还要将数据排序成升序在这个过程中就会有时间和空间上的损耗了 2. 插入和删除数据效率很低因为存储在下标随机访问的结构中插入和删除数据⼀般需要挪动数据。 在二分查找当中以上提到的缺点其实还不是最致命的最要命的是当一组数据已经存储在数组当中时并且已经排序好时如果之后我们要在这组数据当中再插入新的元素或者是要将原数据中的一个元素删除那么通过之前顺序表的学习我们就知道每插入或者是删除一个元素时间复杂度都为O(N)若多次进行操作这就使得时间复杂度非常高了
int a[] {8, 3, 1, 10, 6, 4, 7, 14, 13};
通过以上的分析这里也就体现出了平衡二叉搜索树的价值在插入元素或者是删除元素都相比使用二分查找要有优势。 3. 二叉搜索树的插入
3.1插入分析 在此在二叉搜索树当中插入新的节点就要按照以下步骤进行分析1. 树为空则直接新增结点赋值给root指针2. 树不空按二叉搜索树性质插入值比当前结点大往右走插入值比当前结点小往左走找到空位置插入新结点。3. 如果支持插入相等的值插入值跟当前结点相等的值可以往右走也可以往左走找到空位置插入新结点。要注意的是要保持逻辑⼀致性插入相等的值不要⼀会往右走⼀会往左走 例如以下示例 假设我们要将以下的数组元素依次插入到二叉搜索树当中
int a[] {8, 3, 1, 10, 6, 4, 7, 14, 13}; 所以元素插入完之后二叉搜索树的形式就如下所示 这时如果我们要再插入值为16的元素在二叉搜索树中过程图就如下所示 再插入值为3的元素在二叉搜索树中过程图就如下所示 3.2 插入代码实现
在实现二叉搜索树的插入代码之前我们先要来实现二叉搜索树大体的结构代码
在此我们先创建一个BSTree.h的头文件在该文件当中来实现二叉搜索树的结构以及各个功能再创建一个test.cpp的文件用于测试我们实现的二叉搜索树的各个功能是否能满足要求
实现了文件的创建之后接下来就来实现二叉搜索树的大体结构。在此由于二叉搜索树是由各个节点构成的那么和之前实现链式结构的二叉树一样先要实现表示节点的结构体 #includeiostream
using namespace std;templateclass K
struct BSTreeNode
{K _key;BSTreeNodeK* left;BSTreeNodeK* right;BSTreeNode(const K key):_key(key),left(nullptr),right(nullptr){}
}; 在此就创建一个结构体BSTreeNode来表示二叉树内节点在节点当中有三个变量分别是_key表示节点内的数据、_left存储该节点左孩子节点的指针、_right存储该节点右孩子节点的指针。并且将该结构体实现成模板这样就可以支持节点内的元素是任意类型的数据还有在结构体当中还实现了构造函数。 实现了节点的结构体之后接下来就可以来实现表示二叉搜索树的类在此我们将类命名为BSTree实现的是模板类实现的大体结构如下所示
templateclass K
class BSTree
{typedef BSTreeNodeK Node;public://使用编译器生成的默认构造函数BSTree() default;//实现各种功能的成员函数……private://头节点Node* _root nullptr;};
完成了以上操作接下来就可以来实现插入函数的代码了
注以下实现的插入函数是数据不支持冗余的情况也就是二叉树当中不支持插入相等的值
bool Insert(const K key)
{//当根节点为空时if (_root nullptr){_root new Node(key);return true;}Node* cur _root;//节点的父节点Node* parentcur nullptr;while (cur){//当key小于当前节点的值if (cur-_key key){parentcur cur;cur cur-right;}当key大于当前节点的值else if (cur-_key key){parentcur cur;cur cur-left;}//当key等于当前节点的值else{return false;}}cur new Node(key);//当新节点内的值大于父节点内的值时if (parentcur-_key key){parentcur-right cur;}//当新节点内的值小于父节点内的值时else{parentcur-left cur;}return true;} 4. 二叉搜索树的查找
4.1查找分析 在二叉搜索树中查找节点就要按照以下步骤进行分析 1. 从根开始比较查找xx比根的值大则往右边走查找x比根值小则往左边走查找。2. 最多查找高度次走到到空还没找到这个值不存在。3. 如果不支持插入相等的值找到x即可返回4. 如果支持持插入相等的值意味着有多个x存在⼀般要求查找中序的第⼀个x。 例如以下示例
当要查找3时要找到1的右孩子的那个3值返回 4.2 查找代码实现
在进行了二叉搜索树的节点查找的分析之后接下来我们就来实现查找代码
注以下实现的查找函数是数据不支持冗余的情况也就是二叉树当中不支持插入相等的值
Node* Find(const K key)
{//当根结点为空时if (_root nullptr){return nullptr;}Node* cur _root;Node* parentcur nullptr;while (cur){//当key大于当前节点的值if (cur-_key key){parentcur cur;cur cur-right;}//当key小于当前节点的值else if (cur-_key key){parentcur cur;cur cur-left;}//当key等于当前节点的值else{return cur;}}//当前二叉树中找不到值为key的节点return nullptr;
} 5. 二叉搜索树的删除
5.1 删除分析
在二叉搜索树当中节点的删除相比插入和查找就复杂一些了在此会出现以下的多种情况接下来就来一一分析
在此要删除的节点会有以下的四种情况 1.要删除结点N左右孩子均为空 当要删除节点的节点左右孩子节点都为空时就需要把N结点的父亲对应孩子指针指向空直接删除N结点
例如以下示例 在以上二叉搜索树当中要删除值为1的节点就需要将节点1删除之后再将其父节点的左孩子节点指向空 2. 要删除的结点N左孩子位空右孩子结点不为空 当要删除节点的节点左孩子节点为空时就需要把N结点的父亲对应孩子指针指向N的右孩子之后直接删除N结点
例如以下示例 在以上二叉搜索树当中要删除值为10的节点就需要将其父节点的左孩子变为原节点的右孩子节点之后再将节点10删除 3.要删除的结点N右孩子位空左孩子结点不为空 当要删除节点的节点右孩子节点为空时就需要把N结点的父亲对应孩子指针指向N的左孩子之后直接删除N结点
例如以下示例 在以上二叉搜索树当中要删除值为14的节点就需要将其父节点的左孩子变为原节点的左孩子节点之后再将节点14删除 4. 要删除的结点N左右孩子结点均不为空 当要删除的节点左右孩子节点都不为空时这是就不能像以上的情况一样简单的改变要删除节点的父节点指针这时由于无法直接删除N结点这是因为N的两个孩⼦无处安放只能用替换法删除。在此根据二叉搜索树的性质就需要找N左子树的值最大结点R(最右结点)或者N右子树的值最小结点R(最左结点)替代N因为这两个结点中任意⼀个放到N的位置都满足⼆叉搜索树的规则。替代N的意思就是N和R的两个结点的值交换转而变成删除R结点R结点符合情况2或情况3可以直接删除。
例如以下示例 在以上二叉搜索树当中要删除节点值为8的节点和值为3的节点由于这两个节点都是左右孩子节点都不为空的节点因此要删除值为8的节点就需要找到其左子树最右的节点或者是右子树最左的节点在此我们是找右子树最左的节点 之后交换要删除的节点和找出的节点的值 最后删除交换之后值为8的节点即可 注要删除值为3的节点和以上的方式也类型在此就不再细致的讲解 5.2 删除代码实现 bool Erase(const K key)
{//当根节点为空时if (_root nullptr){return false;}//当前节点Node* cur _root;//当前节点的父节点Node* parentcur _root;while (cur){//当key的值大于当前节点的值if (cur-_key key){parentcur cur;cur cur-right;}//当key的值大于当前节点的值else if (cur-_key key){parentcur cur;cur cur-left;}//当key的值等于当前节点的值else{//当要删除的节点左孩子节点为空if (cur-leftnullptr){//当要删除的节点为根结点时直接改变_root指针的指向之后再将原根结点释放if (cur _root){Node* Right cur-right;delete cur;_root Right;}else{//当要删除的节点cur是其父节点的左节点时if (cur parentcur-left){parentcur-left cur-right;delete cur;}//当要删除的节点cur是其父节点的右节点时else if (cur parentcur-right){parentcur-right cur-right;delete cur;}}return true;}//当要删除的节点右孩子节点为空else if (cur-rightnullptr){//当要删除的节点为根结点时直接改变_root指针的指向之后再将原根结点释放if (cur _root){Node* Left cur-left;delete cur;_root Left;}else{//当要删除的节点cur是其父节点的左节点时if (cur parentcur-left){parentcur-left cur-left;delete cur;}//当要删除的节点cur是其父节点的右节点时else if (cur parentcur-right){parentcur-right cur-left;delete cur;}}return true;}//当要删除的节点左右孩子节点都为空else{Node* minrightParent cur;Node* minright cur-right;//找出当前节点右子树中的最左节点while (minright-left){minrightParent minright;minright minright-left;}cur-_key minright-_key;//当最左节点为其父节点的左节点时if (minrightParent-left minright){minrightParent-left minright-right;}//当最左节点为其父节点的右节点时else {minrightParent-right minright-right;}delete minright;return true; }}}//当找不到要删除的节点就返回falsereturn false;} 6. 二叉搜索树遍历
由于二叉搜索树的性质一棵二叉搜索树中序遍历输出的结果就是递增的那么接下来我们就试着来实现中序遍历的代码
void Inorder()
{_Inorder(_root);cout endl;
}void _Inorder(Node* root)
{if (root nullptr){return;}_Inorder(root-left);cout root-_key ;_Inorder(root-right);
}
在此我们实现的中序遍历代码如上所示那么这时你可能就会有疑问了为什么要实现两个中序遍历的函数不是直接使用一个函数就可以满足要求了吗
在此要考虑到的是在BsTree类以外用户是无法得到二叉搜索树的根节点的但是在调用中序遍历的函数根据之前我们使用递归的方式是需要一开始就需要将二叉树的根结点作为中序遍历函数的参数的。因此为了解决该问题就再在BSTree类内实现一个函数来调用中序遍历的成员函数由于是在类的内部在此是可以访问私有的成员变量的在类外部用户要使用中序遍历时就只需要调用无参的成员函数Inorder就可以得到二叉搜索树中序遍历的结果了。 7. 二叉搜索树完整代码
#includeiostream
using namespace std;templateclass K
struct BSTreeNode
{K _key;BSTreeNodeK* left;BSTreeNodeK* right;BSTreeNode(const K key):_key(key), left(nullptr), right(nullptr){}
};templateclass K
class BSTree
{typedef BSTreeNodeK Node;public://使用编译器生成的默认构造函数BSTree() default;bool Insert(const K key){//当根节点为空时if (_root nullptr){_root new Node(key);return true;}Node* cur _root;//节点的父节点Node* parentcur nullptr;while (cur){//当key小于当前节点的值if (cur-_key key){parentcur cur;cur cur-right;}当key大于当前节点的值else if (cur-_key key){parentcur cur;cur cur-left;}//当key等于当前节点的值else{return false;}}cur new Node(key);//当新节点内的值大于父节点内的值时if (parentcur-_key key){parentcur-right cur;}//当新节点内的值小于父节点内的值时else{parentcur-left cur;}return true;}Node* Find(const K key){//当根结点为空时if (_root nullptr){return nullptr;}Node* cur _root;Node* parentcur nullptr;while (cur){//当key大于当前节点的值if (cur-_key key){parentcur cur;cur cur-right;}//当key小于当前节点的值else if (cur-_key key){parentcur cur;cur cur-left;}//当key等于当前节点的值else{return cur;}}//当前二叉树中找不到值为key的节点return nullptr;}bool Erase(const K key){//当根节点为空时if (_root nullptr){return false;}//当前节点Node* cur _root;//当前节点的父节点Node* parentcur _root;while (cur){//当key的值大于当前节点的值if (cur-_key key){parentcur cur;cur cur-right;}//当key的值大于当前节点的值else if (cur-_key key){parentcur cur;cur cur-left;}//当key的值等于当前节点的值else{//当要删除的节点左孩子节点为空if (cur-left nullptr){//当要删除的节点为根结点时直接改变_root指针的指向之后再将原根结点释放if (cur _root){Node* Right cur-right;delete cur;_root Right;}else{//当要删除的节点cur是其父节点的左节点时if (cur parentcur-left){parentcur-left cur-right;delete cur;}//当要删除的节点cur是其父节点的右节点时else if (cur parentcur-right){parentcur-right cur-right;delete cur;}}return true;}//当要删除的节点右孩子节点为空else if (cur-right nullptr){//当要删除的节点为根结点时直接改变_root指针的指向之后再将原根结点释放if (cur _root){Node* Left cur-left;delete cur;_root Left;}else{//当要删除的节点cur是其父节点的左节点时if (cur parentcur-left){parentcur-left cur-left;delete cur;}//当要删除的节点cur是其父节点的右节点时else if (cur parentcur-right){parentcur-right cur-left;delete cur;}}return true;}//当要删除的节点左右孩子节点都为空else{Node* minrightParent cur;Node* minright cur-right;//找出当前节点右子树中的最左节点while (minright-left){minrightParent minright;minright minright-left;}cur-_key minright-_key;//当最左节点为其父节点的左节点时if (minrightParent-left minright){minrightParent-left minright-right;}//当最左节点为其父节点的右节点时else{minrightParent-right minright-right;}delete minright;return true;}}}//当找不到要删除的节点就返回falsereturn false;}void Inorder(){_Inorder(_root);cout endl;}private://头节点Node* _root nullptr;void _Inorder(Node* root){if (root nullptr){return;}_Inorder(root-left);cout root-_key ;_Inorder(root-right);}}; 8. 二叉搜索树key和key/value使用场景
8.1 key搜索场景
key搜索场景的形式如下所示 只有key作为关键码结构中只需要存储key即可关键码即为需要搜索到的值搜索场景只需要判断key在不在。key的搜索场景实现的二叉树搜索树支持增删查但是不支持修改修改key破坏搜索树结构了。 在以上我们了解实现的二叉搜索树其实是适用于key的场景那么接下来就来看看那么场景是属于key的场景
场景1小区无人值守车库小区车库买了车位的业主车才能进小区那么物业会把买了车位的业主的车牌号录入后台系统⻋辆进入时扫描⻋牌在不在系统中在则抬杆不在则提示非本小区⻋辆无法进入。 场景2检查⼀篇英文文章单词拼写是否正确将词库中所有单词放入二叉搜索树读取文章中的单词查找是否在二叉搜索树中不在则波浪线标红提示。 8.2 key/value搜索场景 key/value搜索场景的形式如下所示 每⼀个关键码key都有与之对应的值valuevalue可以任意类型对象。树的结构中(结点)除了需要存储key还要存储对应的value增/删/查还是以key为关键字走二叉搜索树的规则进行比较可以快速查找到key对应的value。key/value的搜索场景实现的二叉树搜索树支持修改但是不支持修改key修改key破坏搜索树结构了可以修改value。 接下来就来将以上我们实现的key二叉搜索树修改为key/value⼆叉搜索树代码实现代码如下所示
#includeiostream
using namespace std;templateclass K,class V
struct BSTreeNode
{K _key;V _value;BSTreeNodeK ,V* left;BSTreeNodeK ,V* right;BSTreeNode(const K key, const V value):_key(key);_value(value), left(nullptr), right(nullptr){}
};templateclass K,class V
class BSTree
{typedef BSTreeNodeK,V Node;public://使用编译器生成的默认构造函数BSTree() default;bool Insert(const K key, const V value){//当根节点为空时if (_root nullptr){_root new Node(key,value);return true;}Node* cur _root;//节点的父节点Node* parentcur nullptr;while (cur){//当key小于当前节点的值if (cur-_key key){parentcur cur;cur cur-right;}//当key大于当前节点的值else if (cur-_key key){parentcur cur;cur cur-left;}//当key等于当前节点的值else{return false;}}cur new Node(key, value);//当新节点内的值大于父节点内的值时if (parentcur-_key key){parentcur-right cur;}//当新节点内的值小于父节点内的值时else{parentcur-left cur;}return true;}Node* Find(const K key){//当根结点为空时if (_root nullptr){return nullptr;}Node* cur _root;Node* parentcur nullptr;while (cur){//当key大于当前节点的值if (cur-_key key){parentcur cur;cur cur-right;}//当key小于当前节点的值else if (cur-_key key){parentcur cur;cur cur-left;}//当key等于当前节点的值else{return cur;}}//当前二叉树中找不到值为key的节点return nullptr;}bool Erase(const K key){//当根节点为空时if (_root nullptr){return false;}//当前节点Node* cur _root;//当前节点的父节点Node* parentcur _root;while (cur){//当key的值大于当前节点的值if (cur-_key key){parentcur cur;cur cur-right;}//当key的值大于当前节点的值else if (cur-_key key){parentcur cur;cur cur-left;}//当key的值等于当前节点的值else{//当要删除的节点左孩子节点为空if (cur-left nullptr){//当要删除的节点为根结点时直接改变_root指针的指向之后再将原根结点释放if (cur _root){Node* Right cur-right;delete cur;_root Right;}else{//当要删除的节点cur是其父节点的左节点时if (cur parentcur-left){parentcur-left cur-right;delete cur;}//当要删除的节点cur是其父节点的右节点时else if (cur parentcur-right){parentcur-right cur-right;delete cur;}}return true;}//当要删除的节点右孩子节点为空else if (cur-right nullptr){//当要删除的节点为根结点时直接改变_root指针的指向之后再将原根结点释放if (cur _root){Node* Left cur-left;delete cur;_root Left;}else{//当要删除的节点cur是其父节点的左节点时if (cur parentcur-left){parentcur-left cur-left;delete cur;}//当要删除的节点cur是其父节点的右节点时else if (cur parentcur-right){parentcur-right cur-left;delete cur;}}return true;}//当要删除的节点左右孩子节点都为空else{Node* minrightParent cur;Node* minright cur-right;//找出当前节点右子树中的最左节点while (minright-left){minrightParent minright;minright minright-left;}cur-_key minright-_key;//当最左节点为其父节点的左节点时if (minrightParent-left minright){minrightParent-left minright-right;}//当最左节点为其父节点的右节点时else{minrightParent-right minright-right;}delete minright;return true;}}}//当找不到要删除的节点就返回falsereturn false;}void Inorder(){_Inorder(_root);cout endl;}private://头节点Node* _root nullptr;void _Inorder(Node* root){if (root nullptr){return;}_Inorder(root-left);cout root-_key : root-_val ;_Inorder(root-right);}}; 在以上我们了解实现的二叉搜索树其实是适用于key的场景那么接下来就来看看那么场景是属于key的场景
场景1商场无人值守车库入⼝进场时扫描⻋牌记录车牌和入场时间出口离场时扫描牌查找入场时间用当前时间-⼊场时间计算出停⻋时长计算出停车费用缴费后抬杆车辆离场。 场景1简单中英互译字典树的结构中(结点)存储key(文)和vlaue(中文)搜索时输⼊英文则同时查找到了英文对应的中文。场景3统计⼀篇文章中单词出现的次数读取⼀个单词查找单词是否存在不存在这个说明第⼀次出现单词1单词存在则单词对应的次数。 以下的两个简单的示例就是使用二叉搜索树的key/val来解决
#includeBSTree.hint main()
{//示例1
//将以下英文单词和对应的中文翻译绑定到一起当用户输入输入正确的单词就输出其中文意思否则就输出单词拼写错误BSTreestring, string dict;dict.Insert(insert, 插入);dict.Insert(erase, 删除);dict.Insert(left, 左边);dict.Insert(string, 字符串);string str;while (cin str){auto ret dict.Find(str);if (ret){cout str : ret-_val endl;}else{cout 单词拼写错误 endl;}}//示例2
//统计字符串数组当中各个水果的出现次数string strs[] { 苹果, 西瓜, 苹果, 樱桃, 苹果, 樱桃, 苹果, 樱桃, 苹果 };// 统计水果出现的次BSTreestring, int countTree;for (auto str : strs){auto ret countTree.Find(str);if (ret NULL){countTree.Insert(str, 1);}else{ret-_val;}}countTree.Inorder();return 0;
}以上就是本篇的区别内容了希望能得到你的点赞和收藏 ❤️
