吉林省城乡建设部网站网站 搜索 关键字 description

当前位置： 首页 > news >正文

吉林省城乡建设部网站,网站 搜索 关键字 description,做网站用的小图标,怎么做繁体字网站1、二叉搜索树概念

1. ⼆叉搜索树的概念 ⼆叉搜索树⼜称⼆叉排序树#xff0c;它或者是⼀棵空树#xff0c;或者是具有以下性质的⼆叉树: • 若它的左⼦树不为空#xff0c;则左⼦树上所有结点的值都⼩于等于根结点的值 • 若它的右⼦树不为空#xff0c;则右⼦树上所有结… 1、二叉搜索树概念
2. ⼆叉搜索树的概念 ⼆叉搜索树⼜称⼆叉排序树它或者是⼀棵空树或者是具有以下性质的⼆叉树: • 若它的左⼦树不为空则左⼦树上所有结点的值都⼩于等于根结点的值 • 若它的右⼦树不为空则右⼦树上所有结点的值都⼤于等于根结点的值 • 它的左右⼦树也分别为⼆叉搜索树 • ⼆叉搜索树中可以⽀持插⼊相等的值也可以不⽀持插⼊相等的值具体看使⽤场景定义map/set/multimap/multiset系列容器底层就是⼆叉搜索树其中map/set不⽀持插⼊相等 值multimap/multiset⽀持插⼊相等值 以下就是两颗二叉搜索树 2. ⼆叉搜索树的性能分析 最优情况下⼆叉搜索树为完全⼆叉树(或者接近完全⼆叉树)其⾼度为O(log2 N)  最差情况下⼆叉搜索树退化为单⽀树(或者类似单⽀)其⾼度为O( N/2 )  所以综合⽽⾔⼆叉搜索树增删查改时间复杂度为O(N) 这样的效率显然是⽆法满⾜我们需求的后续会讲解⼆叉搜索树的变形平衡⼆ 叉搜索树AVL树和红⿊树才能适⽤于我们在内存中存储和搜索数据。 ⼆分查找也可以实现O( logN ) 级别的查找效率但是⼆分查找有两⼤缺陷 1. 需要存储在⽀持下标随机访问的结构中并且有序。 2. 插⼊和删除数据效率很低因为存储在下标随机访问的结构中插⼊和删除数据⼀般需要挪动数据。 这⾥也就体现出了⼆叉搜索树的价值。 3. 二叉搜索树的实现 需要明确的一点是我们此处实现的是不可插入相同值的二叉搜索树。 而搜索二叉树的本质还是使用递归来完成因此与我们之前博客实现的二叉树逻辑大体相似因此一些类似的操作我们简略描述。 3.1 定义二叉搜索树 3.1.2 定义二叉搜索树节点 这与之前实现的二叉树类似只不过用上了模板跟构造函数因为构造函数我们在后面需要用来生成节点。 templateclass K struct BSTNode {K _key;BSTNodeK* _left;BSTNodeK* _right;BSTNode(const K key):_key(key),_left(nullptr),_right(nullptr){} };3.1.2 定义二叉搜索树结构  templateclass K class BSTree {//这里也能体现封装思想不管我们如何实现的类此处我们只需定义成Node即可typedef BSTNodeK Node; private:Node* _root nullptr;//头节点 } 3.2 中序遍历 根据二叉搜索树的性质中序遍历得到的应该是一个有序的升序列表。 中序搜索的逻辑与之前大差不差我们只需记住先遍历左子树在打印当前根节点的值而后遍历右子树这就是“ 左 根 右”。 不要忘记了返回条件遍历到空需要返回到上一级。 最后需要注意的一点是我们遍历时需要传入头节点root但是root是我们类的私有成员变量在类外无法访问那我们怎么办呢对于这种问题有个统一的办法我们可以将这个函数定义成类的私有成员在写一个类的公有成员函数去调用类的私有成员函数即可。 pubilcvoid InOder(){_InOder(_root);cout endl;} privatevoid _InOder(Node* root){if (root nullptr){return;}_InOder(root-_left);cout root-_key ;_InOder(root-_right);} 3.3 插入 我们根据搜索二叉树的特点可以得出我们的插入逻辑 1.若当前的树是一颗空树那么我们只需新增节点赋给root节点即可。 2.若树不为空我们只需根据二叉搜索树的性质定义一个指针cur遍历二叉搜索树若cur指向的节点值大于我们要插入的值va则cur往右子树走反之则往左子树走知道cur的下一节点为空时用val初始化一个节点并根据cur和val的值比较判断插入到左子树还是右子树 bool Insert(const K val){if (_root nullptr){_root new Node(val);return true;}Node* parent _root;Node* cur _root;while (cur){if ( val cur-_key ){parent cur;cur cur-_left;}else if ( val cur-_key ){parent cur;cur cur-_right;}else{return false;}}cur new Node(val);if (val parent-_key){parent-_right cur;}else{parent-_left cur ;}return true;} 3.4 查找 从根开始⽐较查找xx⽐根的值⼤则往右边⾛查找x⽐根值⼩则往左边⾛查找。⾛到到空还没找到这个值不存在返回false。找到则返回true。 bool Find(const K val){Node* cur _root;while (cur){if (val cur-_key){cur cur-_right;}else if (val cur-_key){cur cur-_left;}else{return true;}}return false;} 3.5 删除 二叉搜索树的插入时整个步骤中最复杂的因为在插入数据时我们需要对二叉搜索树的部分结构进行适当的调整使其保持原有的性质。 我们以下图的删除二叉数为例 在删除之前我们还需要明确一点我们删除节点释放完资源之后还需使其对应的父亲节点指向nullptr避免产生野指针的问题因此我们我们要一个指针cur来搜寻要删除的节点还需要一个指针parent来记录cur的前一节点。 在删除的过程中分为了好几种情况。我们需要分别讨论 1. 删除的位置为叶子节点            这时候只需要cur搜索到对应的节点再删除即可。 2. 删除的位置只有一个孩子节点。            若cur为parent的左节点则使 parent-left 指向cur的非空节点            反之则使 parent-right 指向cur的非空节点 3.删除位置有两个孩子节点            这是最后一种也是最复杂的一种情况。有两个孩子意味着删除了该节点后我们需要对搜索二叉树部分结构进行适当的调整。 这里我没有两种方法我们定义一个指针MaxLeft使其找到要删除节点cur左子树的最大值或者定义一个指针MinRight使其找到cur右子树的最小节点将其与cur的值进行交换在删除LeftMax或者MinRight指向的节点即可            为什么可以选择这两个节点的其中一个呢因为只有选择这两个节点才会保证二叉搜索树的性质不变。            我们以交换右子树最小节点为例下列图我们可以看出MidRight指针与cur交换完之后二叉搜索树的性质依然符合。 但是我们还需要注意的是和前面的两点一样我们删除掉MidRight节点之后不要文件将其父节点对应的指针指向nullptr因此我们还需要定义一个指针PMidRight防止释放完MidRight之后找不到其对应父节点。 以下是实现的代码 bool Erase(const K val){if (_root nullptr){_root new Node(val);return true;}Node* parent nullptr;Node* cur _root;while (cur){if (val cur-_key){parent cur;cur cur-_left;}else if (val cur-_key){parent cur;cur cur-_right;}else{if (cur-_left nullptr){//让父亲指向我的右if (curparent-_right){parent-_rightcur-_right;}else{parent-_left cur-_right;}delete cur;return true;}else if (cur-_right nullptr){if (cur parent-_right){parent-_right cur-_left;}else{parent-_left cur-_left;}delete cur;return true;}else{Node* rightMin cur-_right;Node* rightMinP cur;while (rightMin-_left){rightMinP rightMin;rightMin rightMin-_left;}cur-_key rightMin-_key;if (rightMinP-_left rightMin)rightMinP-_left rightMin-_right;elserightMinP-_right rightMin-_right;delete rightMin;return true;}}}return false;} 4.源代码 #pragma once #includeiostream #includevector using namespace std;templateclass K struct BSTNode {K _key;BSTNodeK* _left;BSTNodeK* _right;BSTNode(const K key):_key(key),_left(nullptr),_right(nullptr){} };templateclass K class BSTree {typedef BSTNodeK Node;public:bool Insert(const K val){if (_root nullptr){_root new Node(val);return true;}Node* parent _root;Node* cur _root;while (cur){if ( val cur-_key ){parent cur;cur cur-_left;}else if ( val cur-_key ){parent cur;cur cur-_right;}else{return false;}}cur new Node(val);if (val parent-_key){parent-_right cur;}else{parent-_left cur ;}return true;}bool Find(const K val){Node* cur _root;while (cur){if (val cur-_key){cur cur-_right;}else if (val cur-_key){cur cur-_left;}else{return true;}}return false;}void InOder(){_InOder(_root);cout endl;}bool Erase(const K val){if (_root nullptr){_root new Node(val);return true;}Node* parent nullptr;Node* cur _root;while (cur){if (val cur-_key){parent cur;cur cur-_left;}else if (val cur-_key){parent cur;cur cur-_right;}else{if (cur-_left nullptr){//让父亲指向我的右if (curparent-_right){parent-_rightcur-_right;}else{parent-_left cur-_right;}delete cur;return true;}else if (cur-_right nullptr){if (cur parent-_right){parent-_right cur-_left;}else{parent-_left cur-_left;}delete cur;return true;}else{Node* rightMin cur-_right;Node* rightMinP cur;while (rightMin-_left){rightMinP rightMin;rightMin rightMin-_left;}cur-_key rightMin-_key;if (rightMinP-_left rightMin)rightMinP-_left rightMin-_right;elserightMinP-_right rightMin-_right;delete rightMin;return true;}}}return false;}private:Node* _root nullptr;void _InOder(Node* root){if (root nullptr){return;}_InOder(root-_left);cout root-_key ;_InOder(root-_right);} };