济南怎么做网站,制作软件下载,最优的锦州网站建设,网站开发实践实验报告目录
一、基本概念
二、性能分析
三、模拟实现
四、使用场景
1.key搜索场景
2.key/value搜索场景 一、基本概念
二叉搜索树#xff08;Binary Search Tree#xff09;#xff0c;看名字就知道,是可以用来搜索数据的一种二叉树。
它可以是空树#xff08;一个数据都…目录
一、基本概念
二、性能分析
三、模拟实现
四、使用场景
1.key搜索场景
2.key/value搜索场景 一、基本概念
二叉搜索树Binary Search Tree看名字就知道,是可以用来搜索数据的一种二叉树。
它可以是空树一个数据都没有的二叉搜索树也可以只有一个根结点这都是比较特殊的情况。但其实二叉搜索树都是从一个根节点开始构建的然后一个结点一个结点的插入就会形成一个比较大型的二叉搜索树。
像这样 仔细观察就可以发现对于每一个结点它的左孩子结点数据比它小右孩子结点数据比它大。 其实对于每一个结点它的左子树所有结点的数据都会比它小右子树所有结点的数据都会比它大它的左子树和右子树又分别也是一颗二叉搜索树。 另外看一下它的中序遍历序列[1,3,4,6,7,8,10,13,14]可以发现是升序的这是因为二叉搜索树的最小单元一父二子的中序遍历是升序的那么递归下来自然整个二叉搜索树的中序遍历序列也是升序的了。 肯定有人会疑惑左子树的结点数据也可能比根结点的数据大吧
这是不会的因为在二叉搜索树构建的过程中结点的插入是靠循环如果比当前结点数据大就往右走小就往左走。就像上面的图中根结点的左子树中最大数字位7如果是9那么9必然会在插入的时候就插入到根结点的右子树上。
二叉搜索树可以实现出两个版本支持插入相同数据/不支持插入相同数据两者要看应用场景来看具体使用哪一种情况。
到后面我们会学习map/set、multimap/multiset它们的底层就是二叉搜索树前一组不支持插入相等值二后一组支持。
二、性能分析
二叉搜索树听名字就知道是为查找而生。
以我们之前学习的经验查找效率取决于该二叉搜素树的高度。最坏情况下要进行最大高度次查找
如果该二叉搜索树是满二叉树那么就是比较理想的情况查找效率为OlogN
但是如果极端情况下像下图这样查找效率就会变成ON。 想要解决这种情况当然是有办法的也就是建立平衡二叉搜索树不过这个知识不是本博客的重点到后面的博客会详细说。
三、模拟实现
先说明我们的模拟实现对于增删查改只实现了增删查不实现改的操作很好理解如果把二叉搜索树某个结点的数据修改了那么这个二叉搜索树的结构也就可能被破坏掉了在后续需要进行的搜索操作中很容易出现错误。
如果你非得想实现改建议直接删除插入。 先搭建出整体框架
// BinarySearch.h
#pragma once
#include iostream
using namespace std;// K : key
templateclass K
struct BSTNode
{K _key;BSTNodeK* _left;BSTNodeK* _right;BSTNode(K key):_key(key),_left(nullptr),_right(nullptr){}
};templateclass K
class BSTree
{using Node BSTNodeK;public:private:Node* _root;
};
下面这里是中序遍历以及增查删除后面重点说
// BinarySearch.h
#pragma once
#include iostream
using namespace std;// K : key
templateclass K
struct BSTNode
{K _key;BSTNodeK* _left;BSTNodeK* _right;BSTNode(K key):_key(key),_left(nullptr),_right(nullptr){}
};templateclass K
class BSTree
{using Node BSTNodeK;
public:// 查找bool Find(const K key){Node* cur _root;while (cur){if (cur-_key key) cur cur-_right;else if (cur-_key key) cur cur-_left;else return true;}return false;}// 插入bool Insert(const K key){if (_root nullptr){_root new Node(key);return true;}// Node* newnode new Node(key);// 在下面直接让cur变成新结点就省去这一步了// 注意 *parentNode* cur _root, *parent _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);if (parent-_key key) parent-_left cur;else parent-_right cur;return true;}// 删除bool Erase(const K key){}// 中序遍历void 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;
};// Test.cpp
#include BinarySearch.hint main()
{BSTreeint bst;int a[] { 8, 3, 1, 10, 1, 6, 4, 7, 14, 13 };for (auto e : a){bst.Insert(e);}bst.InOrder();return 0;
}
二叉搜索树的删除
二叉搜索树的删除所需要删除的结点类型有种
1.叶子结点直接删就行父结点对应位置置空
2.只有一个孩子的父结点把唯一一个孩子给该父结点的父结点再删除该结点即可
3.有两个孩子的父结点这就有点麻烦了......
之前学过堆有可能能想出这种方法
让需要删除的结点和某个结点交换数据然后删除该结点再把交换上来的结点向下调整这种方法看起来确实可行那么就不妨一试。
选择的结点为哪个为了保证删除效率我们尽量减少交换后向下调整的次数所以尽量就是让它不需要向下调整即可。那么我们就可以达到交换删除结点搜索二叉树结构不被破坏即可成功删除指定结点。 结合这张图我们要删除3关于交换结点的选取我们可以这样想
1. 3的父结点是8以3为根结点的搜索二叉树后面叫3树的值都是小于8的所以无论交换3树上面的哪个结点都不会影响交换上来的结点与8的关系。
2. 3树中3把左右子树分成了小于和大于3的两部分值如果我们把3删去那么充当分界值的数字只能是紧挨3的数字在这里是1或43树的中序遍历13467紧挨3的是1和4所以用1或4与3交换都可以(不会破坏二叉搜索树的结构)。
3.紧接着2我们仔细观察搜索二叉树不难发现1是3左子树的最大数据4是3右子树的最小数据也就是说我们可以使要删除的结点与它左子树的最大数据结点或者右子树的最小数据结点交换然后再删除交换到左子树最大/右子树最小结点的待删除结点。
4.左子树的最大数据在左子树的最右侧右子树的最大数据在右子树的最左侧它们肯定至多只有一个孩子所以可以按照只有一个孩子的情况删除。
综合这4点有左右孩子的结点的删除就很简单了。
理解了原理代码就简单了不过还是有不少细节问题需要注意的大家看我的注释就ok了
// BinarySearch.h
#pragma once
#include iostream
using namespace std;// K : key
templateclass K
struct BSTNode
{K _key;BSTNodeK* _left;BSTNodeK* _right;BSTNode(K key):_key(key),_left(nullptr),_right(nullptr){}
};templateclass K
class BSTree
{using Node BSTNodeK;
public:// 删除bool Erase(const K key){// 这个判断其实无所谓因为_root是空的话也进不去查找结点的循环直接返回false了//if (_root nullptr) return false;// 要删除结点先查找这个结点如果没有找到cur最终会是nullptr随后会跳出循环返回falseNode* cur _root, * parent _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 (cur _root){_root cur-_right;}// 非根节点else{// 链接parent和右孩子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{// 链接parent和左孩子然后再delete掉curif (parent-_left cur) parent-_left cur-_left;else parent-_right cur-_left;}// 删除结点delete cur;}// 左右孩子都有else{// 这里如果把replaceParent初始化为nullptr那么就可能会出现没有进入循环后面nullptr-_right的尴尬情况Node* replaceParent cur;// 先右Node* replace cur-_right;// 左左左左找右子树最小数据while (replace-_left){replaceParent replace;replace replace-_left;}// 把找到的结点数据给给curcur-_key replace-_key;// 链接一下再删除// 这里的判断是必要的因为看似我们向cur的右之后一直左左左左那么应该一定是replaceParent-_left replace-_right// 但其实如果刚开始replaceParent curreplace cur-_right压根就没进入循环也就是cur的右孩子没有左孩子了那么就应该replaceParent-_right replace-_rightif (replaceParent-_right replace) replaceParent-_right replace-_right;else replaceParent-_left replace-_right;// 删除“cur”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 ;_InOrder(root-_right);}private:Node* _root nullptr;
};// Test.cpp
#include BinarySearch.hint main()
{BSTreeint bst;int a[] { 8, 3, 1, 10, 1, 6, 4, 7, 14, 13 };for (auto e : a){bst.Insert(e);}bst.InOrder();for (auto e : a){bst.Erase(e);bst.InOrder();}return 0;
}
四、使用场景
1.key搜索场景
这个很好理解就是在二叉搜索树中搜索有没有需要查找的K值这里的K是指在二叉搜索树建立过程中比较大小用的key值。
比如小区的车库管理系统系统识别出车的车牌号并在存储此小区所有车主车牌号的二叉搜索树中搜索如果找到了该车牌号那么就抬杆可以通过。如果没有找到那么就不抬杆不允许进入。这里的代表车牌号的字符串就是key我们上面模拟实现的也是key搜索场景的二叉搜索树。 这是刚刚实现过的key搜索场景的整体代码我把它用命名空间封装了一下以便和key/value场景的区分
// BinarySearch.h
#pragma once
#include iostream
using namespace std;namespace key
{// K : keytemplateclass Kstruct BSTNode{K _key;BSTNodeK* _left;BSTNodeK* _right;BSTNode(K key):_key(key), _left(nullptr), _right(nullptr){}};templateclass Kclass BSTree{using Node BSTNodeK;public:// 查找bool Find(const K key){Node* cur _root;while (cur){if (cur-_key key) cur cur-_right;else if (cur-_key key) cur cur-_left;else return true;}return false;}// 插入bool Insert(const K key){if (_root nullptr){_root new Node(key);return true;}// Node* newnode new Node(key);// 在下面直接让cur变成新结点就省去这一步了// 注意 *parentNode* cur _root, * parent _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);if (parent-_key key) parent-_left cur;else parent-_right cur;return true;}// 删除bool Erase(const K key){// 这个判断其实无所谓因为_root是空的话也进不去查找结点的循环直接返回false了//if (_root nullptr) return false;// 要删除结点先查找这个结点如果没有找到cur最终会是nullptr随后会跳出循环返回falseNode* cur _root, * parent _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 (cur _root){_root cur-_right;}// 非根节点else{// 链接parent和右孩子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{// 链接parent和左孩子然后再delete掉curif (parent-_left cur) parent-_left cur-_left;else parent-_right cur-_left;}// 删除结点delete cur;}// 左右孩子都有else{// 这里如果把replaceParent初始化为nullptr那么就可能会出现没有进入循环后面nullptr-_right的尴尬情况Node* replaceParent cur;// 先右Node* replace cur-_right;// 左左左左找右子树最小数据while (replace-_left){replaceParent replace;replace replace-_left;}// 把找到的结点数据给给curcur-_key replace-_key;// 链接一下再删除// 这里的判断是必要的因为看似我们向cur的右之后一直左左左左那么应该一定是replaceParent-_left replace-_right// 但其实如果刚开始replaceParent curreplace cur-_right压根就没进入循环也就是cur的右孩子没有左孩子了那么就应该replaceParent-_right replace-_rightif (replaceParent-_right replace) replaceParent-_right replace-_right;else replaceParent-_left replace-_right;// 删除“cur”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 ;_InOrder(root-_right);}private:Node* _root nullptr;};
}// Test.cpp
#include BinarySearch.hint main()
{key::BSTreeint bst;int a[] { 8, 3, 1, 10, 1, 6, 4, 7, 14, 13 };for (auto e : a){bst.Insert(e);}bst.InOrder();for (auto e : a){bst.Erase(e);bst.InOrder();}return 0;
}
2.key/value搜索场景
这个也比较好理解二叉搜索树建立过程中比较用的key值进行比较而每一个结点中除了key值还有与key值相对应的value值这个值可以是任何类型一般来说都是表示和key相关联的属性。
就比如
1.要统计一篇英语课文内出现的一些特定单词的出现次数那么此时代表特定单词的字符串就是string代表特定单词出现次数的就是value。建立一棵存储了这些特定单词的二叉搜索树value都置为0然后开始遍历这篇课文把出现的每个单词都在该二叉搜索树中查找如果找到了就value如果没有找到就不动。这样遍历下来就会得到一个存储了特定单词在课文中出现次数的二叉搜索树以后我们需要获取只需要在这个二叉搜索树中搜索此单词就能得到它在课文中出现的次数了。 2.商场地下停车场系统key是车牌号value是进入停车场的时间车出停车场的时候在树中搜索到该车牌号然后用当前的时间减去value存的进入时间计算得到需要支付的钱然后付费成功后再删除该车牌号的结点。
..............................
下面是key/value的代码只需要在key的基础上略做修改即可然后由于只有增删查的二叉搜索树还不是很完善所以增添了拷贝构造和赋值重载以及析构函数。
// BinarySearch.h#pragma once
#include iostream
#include algorithm
using namespace std;namespace key_value
{// K : key, V:valuetemplateclass K, class Vstruct BSTNode{K _key;V _value;BSTNodeK, V* _left;BSTNodeK, V* _right;BSTNode(K key, V value):_key(key),_value(value), _left(nullptr), _right(nullptr){}};templateclass K, class Vclass BSTree{using Node BSTNodeK, V;public:// 因为写拷贝构造了这里强制生成一下其它构造BSTree() default;// defaultC11,强制生成构造所有// 拷贝构造BSTree(const BSTree bst){_root Copy(bst._root);}// 析构~BSTree(){Destroy(_root);_root nullptr;}// 赋值运算符重载// 现代写法// 不能传const传了就寄bst._rootBSTree operator(BSTree bst){swap(_root, bst._root);return *this;}// 查找Node* Find(const K key){Node* cur _root;while (cur){if (cur-_key key) cur cur-_right;else if (cur-_key key) cur cur-_left;else return cur;}return nullptr;}// 插入bool Insert(const K key, const V value){if (_root nullptr){_root new Node(key, value);return true;}Node* cur _root, * parent _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);if (parent-_key key) parent-_left cur;else parent-_right cur;return true;}// 删除bool Erase(const K key){Node* cur _root, * parent _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 (cur _root){_root cur-_right;}// 非根节点else{// 链接parent和右孩子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{// 链接parent和左孩子然后再delete掉curif (parent-_left cur) parent-_left cur-_left;else parent-_right cur-_left;}// 删除结点delete cur;}// 左右孩子都有else{// 这里如果把replaceParent初始化为nullptr那么就可能会出现没有进入循环后面nullptr-_right的尴尬情况Node* replaceParent cur;// 先右Node* replace cur-_right;// 左左左左找右子树最小数据while (replace-_left){replaceParent replace;replace replace-_left;}// 把找到的结点数据给给curcur-_key replace-_key;// 链接一下再删除// 这里的判断是必要的因为看似我们向cur的右之后一直左左左左那么应该一定是replaceParent-_left replace-_right// 但其实如果刚开始replaceParent curreplace cur-_right压根就没进入循环也就是cur的右孩子没有左孩子了那么就应该replaceParent-_right replace-_rightif (replaceParent-_right replace) replaceParent-_right replace-_right;else replaceParent-_left replace-_right;// 删除“cur”delete replace;}return true;}}return false;}// 中序遍历void InOrder(){_InOrder(_root);cout endl;}private:// 要封装嘛所以返回新根节点给给public的拷贝构造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 ;_InOrder(root-_right);}private:Node* _root nullptr;};
}// Test.cpp
#include string
#include vector
using namespace std;#include BinarySearch.hint main()
{key_value::BSTreestring, int kvbst;vectorstring v { apple,banana,wohaoshuai,youxiaxieyige,haha,haha,apple,banana,wohaoshuai,haha };for (auto e : v){auto retNode kvbst.Find(e);if (retNode) retNode-_value;else kvbst.Insert(e, 1);}string s;cin s;cout s 出现了 kvbst.Find(s)-_value 次 endl;key_value::BSTreestring, int copy(kvbst);key_value::BSTreestring, int ass;ass kvbst;copy.InOrder();ass.InOrder();copy.Erase(apple);ass.Erase(haha);kvbst.InOrder();copy.InOrder();ass.InOrder();return 0;
} 完结撒花~~~~~~~
say顾拜~~~~~~~~~~~~~~~~~
“ψ(∇´)ψ
