网站怎么接广告,wordpress安装选择协议怎么写,服装销售网站建设策划书,php网站开发工程师招聘要求二叉搜索树
概念
二叉搜索树又称为二叉排序树#xff0c;它或为空树#xff0c;或为具有以下性质的二叉树#xff1a;
若它的左子树不为空#xff0c;则左子树上所有节点的值都小于等于根节点的值。若它的右子树不为空#xff0c;则右子树上所有节点的值都大于等于根节…二叉搜索树
概念
二叉搜索树又称为二叉排序树它或为空树或为具有以下性质的二叉树
若它的左子树不为空则左子树上所有节点的值都小于等于根节点的值。若它的右子树不为空则右子树上所有节点的值都大于等于根节点的值。它的左右子树也分别为二叉搜索树。二叉搜索树中可以支持插入相等的值也可以不支持插入相等的值具体看使用场景来定义在后续我们学习的 map / set / multimap / multiset 系列容器底层就是二叉搜索树其中 map / set 不支持插入相等值 multimap / multiset 支持插入相等值。 性能分析
最优情况下二叉搜索树为完全二叉树或接近完全二叉树其高度为logN。
最差情况下二叉搜索树退化为单支树或者类似单支其高度为N。
综合而言二叉搜索树增删查改时间复杂度为O(N)。
那么这样的效率显然是无法满足我们的需求的我们后续课程需要继续讲解二叉搜索树的变形平衡二叉搜索树AVL树和红黑树这两种才能适用于我们在内存中存储和搜索数据。
另外需要说明的是二分查找也可以实现O(logN)级别的查找效率但是存在两大缺陷
需要存储在支持下标随机访问的结构中并且有序。插入和删除数据效率很低因为存储在下标随机访问的结构中插入和删除数据一般需要挪动数据。
因此后续我们会学习平衡二叉搜索树二叉搜索树是为了后面的学习打基础。 代码演示
namespace Key
{//BSNode封装类templateclass Kclass BSNode{public:K _key;BSNodeK* _left;BSNodeK* _right;BSNode(const K key):_key(key),_left(nullptr),_right(nullptr){}};//BSTree封装类templateclass Kclass BSTree{typedef BSNodeK Node;public:bool Insert(const K key){//根节点为空时if (_root nullptr){_root new Node(key);return true;}// 根节点不为空Node* cur _root;Node* Parent nullptr;while (cur) //为空时退出{if (cur-_key key){Parent cur;cur cur-_left;}else if (cur-_key key){Parent cur;cur cur-_right;}else{//相等不插入return false;}}cur new Node(key);if (Parent-_key cur-_key)Parent-_left cur;elseParent-_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* cur _root;Node* Parent nullptr;while (cur){if (cur-_key key){Parent cur;cur cur-_left;}else if (cur-_key key){Parent cur;cur cur-_right;}else// 找到了{// 情况1、2、3if (cur-_left nullptr) //左孩子为空{if (Parent nullptr){_root cur-_right;}else{if (Parent-_left cur){Parent-_left cur-_right;}else{Parent-_right cur-_right;}}delete cur;return true;}else if (cur-_right nullptr)//右孩子为空{if (Parent nullptr){_root cur-_left;}else{if (Parent-_left cur){Parent-_left cur-_left;}else{Parent-_right cur-_left;}}delete cur;return true;}else //都不为空 情况4{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;elsereplaceParent-_right replace-_right;//删除替代节点delete replace;return true;}}}return false;}void Inorder(){_Inorder(_root);}private:void _Inorder(Node* root){if (root nullptr){return;}_Inorder(root-_left);cout root-_key ;_Inorder(root-_right);}private:Node* _root nullptr;};
}
BSNode 是一个模板类表示二叉树的节点。每个节点包含一个关键字 _key 和两个指向左右子节点的指针 _left 和 _right。节点的构造函数接受一个关键字 key 并初始化左右子节点为空指针。BSTree 是一个模板类表示二叉搜索树。其成员函数包括插入 (Insert)、查找 (Find)、删除 (Erase) 和中序遍历 (Inorder) 树。私有成员 _root 用于存储树的根节点。该方法通过比较待插入的值与当前节点的值沿着树的左右子树不断向下寻找合适的位置最终将节点插入。插入时需要更新父节点的指针。插入的具体过程如下 1. 树为空则直接新增结点赋值给 root 指针 2. 树不空按二叉搜索树性质插入值比当前结点大往右邹插入值比当前结点小往左走找到空位置插入新结点。 3. 如果支持插入相等的值插入值跟当前结点相等的值可以往右走也可以往左走找到空位置插入新结点。要注意的是要保持逻辑⼀致性插⼊相等的值不要⼀会往右走⼀会往左走。查找函数根据关键字进行二分搜索通过与当前节点值的比较决定向左子树还是右子树继续查找。查找具体过程如下 1. 从根开始比较查找xx比根的值大则往右边走查找x比根值小则往左边走查找。 2. 最多查找高度次走到到空还没找到这个值不存在。 3. 如果不支持插⼊相等的值找到x即可返回。 4. 如果支持插入相等的值意味着有多个x存在⼀般要求查找中序的第⼀个x。如下图查找到3要找到1的右孩子的那个3返回。 删除函数具体过程如下 首先查找元素是否在二叉搜索树中存在如果不存在则返回false。 如果查找的元素存在则分为下面四种情况进行处理假设要删除的节点值为N 1.要删除的节点N的左右孩子均为nullptr。 2.要删除的节点N的左孩子为nullptr右孩子不为nullptr。 3.要删除的节点N的右孩子为nullptr左孩子不为nullptr。 4.要删除的节点N的左右孩子节点均不为nullptr。 对应上述四种情况作出以下方案 第一种把N节点的父亲节点对应孩子指针指向空直接删除节点。或者我们可以把第一种当做第二或三种情况来处理。 第二种把N节点的父亲指向原删除孩子的指针指向N的右孩子直接删除N节点。 第三种把N节点的父亲指向原删除孩子的指针指向N的左孩子直接删除N节点。 第四种无法直接删除N节点因为N的两个孩子无处安放只能用替换法删除。找N左子树的值的最大节点(最右节点)R或是N右子树的值的最小节点(最左节点)R来代替N因为这两个节点中的任意一个放到N的位置都能满足二叉搜索树的规则。替代N的意思就是N和R的两个节点值交换转而删除R节点R因为符合情况1/2/3所以可以直接删除。中序遍历函数 _Inorder 会递归遍历左子树访问当前节点再递归遍历右子树。这样遍历的结果是按顺序输出树中的所有节点。 二叉搜索树使用场景
key搜索场景 只有key作为关键码结构中只需要存储key即可关键码即为需要搜索的值搜索场景只需要判断key在不在。key的搜索场景实现的二叉搜索树支持增删查但是不支持修改修改key会破坏搜索树的结构。
场景1校区无人值守车库校区车库买了车位的业主才能进小区那么物业会把买了车位的业主的车牌号录入后台系统车辆进入时扫描车牌在不在系统中在就允许进入不再则不能进入。
场景2检查一篇英文文章单词拼写是否正确将词库所有单词放入二叉搜索树读取文章中的单词查找是否在二叉搜索树中不再则波浪线标红提示。
keyvalue搜索场景 每⼀个关键码key都有与之对应的值valuevalue可以任意类型对象。树的结构中(结点)除了需要存储key还要存储对应的value增/删/查还是以key为关键字走二叉搜索树的规则进行比较可以快速查找到key对应的value。key/value的搜索场景实现的⼆叉树搜索树⽀持修改但是不支持修改key修改key破坏搜索树性质了可以修改value。 场景1简单中英互译字典树的结构中(结点)存储key(英文)和vlaue(中文)搜索时输⼊英文则同时查找到了英文对应的中文。 场景2商场无人值守车库入口进场时扫描车牌记录车牌和入场时间出口离场时扫描车牌查找入场时间用当前时间减入场时间计算出停车时长计算出停车费用缴费后抬杆车辆离场。 场景3统计⼀篇文章中单词出现的次数读取⼀个单词查找单词是否存在不存在这个说明第⼀次出现单词1单词存在则单词对应的次数。 keyvalue二叉搜索树
代码演示
namespace key_value
{//BSNode封装类templateclass K, class Vclass BSNode{public:K _key;V _value;BSNodeK, V* _left;BSNodeK, V* _right;BSNode(const K key, const V value):_key(key),_value(value), _left(nullptr), _right(nullptr){}};//BSTree封装类templateclass K, class Vclass BSTree{typedef BSNodeK, V Node;public://默认构造BSTree() default;//拷贝构造BSTree(const BSTreeK, V t){_root Copy(t._root);}//赋值重载BSTreeK, V operator(BSTreeK, V t){swap(_root, t._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* cur _root;Node* Parent nullptr;while (cur) //为空时退出{if (cur-_key key){Parent cur;cur cur-_left;}else if (cur-_key key){Parent cur;cur cur-_right;}else{//相等不插入return false;}}cur new Node(key, value);if (Parent-_key cur-_key)Parent-_left cur;elseParent-_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* cur _root;Node* Parent nullptr;while (cur){if (cur-_key key){Parent cur;cur cur-_left;}else if (cur-_key key){Parent cur;cur cur-_right;}else// 找到了{// 情况1、2、3if (cur-_left nullptr) //左孩子为空{if (Parent nullptr){_root cur-_right;}else{if (Parent-_left cur){Parent-_left cur-_right;}else{Parent-_right cur-_right;}}delete cur;return true;}else if (cur-_right nullptr)//右孩子为空{if (Parent nullptr){_root cur-_left;}else{if (Parent-_left cur){Parent-_left cur-_left;}else{Parent-_right cur-_left;}}delete cur;return true;}else //都不为空 情况4{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;elsereplaceParent-_right replace-_right;//删除替代节点delete replace;return true;}}}return false;}void Inorder(){_Inorder(_root);}private:void _Inorder(Node* root){if (root nullptr){return;}_Inorder(root-_left);cout root-_key :root-_valueendl;_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;Node* newnode new Node(root-_key, root-_value);newnode-_left Copy(root-_left);newnode-_right Copy(root-_right);return newnode;}private:Node* _root nullptr;};
}
BSNode 是一个模板类用于表示树中的每个节点。每个节点保存一个键值对key 和 value以及指向其左子节点和右子节点的指针。 BSTree 是一个模板类表示二叉搜索树。它具有以下成员函数构造函数包括默认构造函数、拷贝构造函数和赋值重载。插入函数Insert将键值对插入到树中。查找函数Find根据键查找节点。删除函数Erase根据键删除节点。遍历函数Inorder中序遍历树并输出节点的键值对。 Insert 函数通过比较键的大小来决定将新节点插入到树中的位置。如果找到一个相同的键则不插入。 Find 函数根据键值进行二分查找返回匹配的节点指针。如果没有找到对应的节点返回 nullptr。 Erase 函数根据节点的子树情况处理左右子树均为空按一个子数为空处理。左子树为空将右子树直接连接到父节点。右子树为空将左子树直接连接到父节点。左右子树都不为空找到右子树的最小节点并替换当前节点。 Inorder 函数是树的中序遍历通过递归打印节点的键值对按升序输出。 Destroy 函数递归销毁树的所有节点而 Copy 函数递归拷贝树的结构生成一棵新的树。
