网站建设逻辑组织的几种模型,什么是网络设计方案网络设计的原则有哪些,推广seo主管招聘,中国新闻社四川分社#x1f308;感谢阅读East-sunrise学习分享——[进阶数据结构]二叉搜索树 博主水平有限#xff0c;如有差错#xff0c;欢迎斧正#x1f64f;感谢有你 码字不易#xff0c;若有收获#xff0c;期待你的点赞关注#x1f499;我们一起进步 #x1f308;我们在之前已经学习… 感谢阅读East-sunrise学习分享——[进阶数据结构]二叉搜索树 博主水平有限如有差错欢迎斧正感谢有你 码字不易若有收获期待你的点赞关注我们一起进步 我们在之前已经学习过了二叉树而如今已经掌握C语法的我们比起当初只能通过C语言学习已经稍有精进了 C拥有一些C语言所不具有的优势所以更适合我们对高阶数据结构的学习今天要分享的二叉搜索树是二叉树的进阶类型在做题或实际应用都有着重要地位 目录一、概念二、基本操作2.1 查找2.2 插入2.3 删除三、递归实现3.1 递归查找 - Find3.2 递归插入 - Insert3.3 递归删除 - Erase四、二叉搜索树的应用4.1 K模型4.2 KV模型五、二叉搜索树的性能分析六、二叉树进阶试题一、概念
二叉搜索树又称二叉排序树它或者是一棵空树或者是具有以下性质的二叉树:
若它的左子树不为空则左子树上所有节点的值都小于根节点的值若它的右子树不为空则右子树上所有节点的值都大于根节点的值它的左右子树也分别为二叉搜索树 二、基本操作 int a[] {8, 3, 1, 10, 6, 4, 7, 14, 13};2.1 查找
搜索二叉树的特性结构使得它的查找效率十分快
从根开始比较、查找比根大则往右边走查找比根小则往左边走查找。最多查找高度次走到到空还没找到这个值不存在。
✏️代码实现
//查找
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;}elsereturn true;}return false;
}2.2 插入
插入的具体过程如下
树为空则直接新增节点赋值给root指针树不空按二叉搜索树性质查找插入位置插入新节点 由于要严格遵循二叉搜索树的结构所以在每次遍历或最后的插入时都需要比较新增节点与其父节点的值的大小♨️所以我们可以用一个parent指针随时记录下父节点便于插入时的大小判断 ✏️代码实现
//插入
bool Insert(const K key)
{if (_root nullptr){_root new Node(key);return true;}//插入,小于就插左大于就插右Node* parent nullptr;Node* cur _root;while (cur){parent cur;if (key cur-_key)cur cur-_left;else if (key cur-_key)cur cur-_right;elsereturn false;}//到合适的空了开始插入//要插在左还是右还是需要比较cur new Node(key);if (key parent-_key)parent-_left cur;if (key parent-_key)parent-_right cur;return true;
}2.3 删除
二叉搜索树的删除较为复杂
首先查找元素是否在二叉搜索树中如果不存在则返回false, 否则要删除的结点可能分下面四种情况
要删除的节点无孩子节点要删除的节点只有右孩子节点要删除的节点只有左孩子节点要删除的节点有左、右孩子节点 删除的情况有些许复杂我们可以将其归成两类
直接删除法替换法删除
⭕直接删除法 直接删除法适用于以上的情况1、2、3其具体情况是删除的节点只有一个孩子或没有孩子节点 而当你删除节点后其被删节点的孩子节点不能就任其飘荡呀所以我们就需要对其进行“寄养”而若删除节点没有孩子节点左右孩子节点都为空则删除后被删节点的父节点所对应的孩子节点也需要指向空 综上所述根据搜索二叉树的结构可得 在代码实现时我们可以把情况1和情况2合为一种情况 —— 被删节点的左孩子节点为空 —— 判断被删节点为其父节点的左or右孩子 —— 将被删节点的右孩子与父节点链接起来寄养✅ 情况3 —— 被删节点的右孩子节点为空 —— 判断被删节点为其父节点的左or右孩子 —— 将被删节点的左孩子与父节点链接起来寄养✅
直接删除法有一个bug需要留意 —— 当被删节点为根节点时会出现空指针的问题因此在代码实现时注意判断
⭕替换法删除 ✏️代码实现
//删除
bool Erase(const K key)
{Node* parent nullptr;Node* cur _root;while (cur){if (cur-_key key){parent cur;cur cur-_right;}else if (cur-_key key){parent cur;cur cur-_left;}else//值相等 - 找到了{//1.左为空//2.右为空//3.左右都不为空 - 替换删除if (cur-_left nullptr){if (cur _root) //parent nullptr_root cur-_right;else{if (cur parent-_left)parent-_left cur-_right;elseparent-_right cur-_right;}delete cur;}else if (cur-_right nullptr){if (cur _root) //parent nullptr_root cur-_left;else{if (cur parent-_left)parent-_left cur-_left;elseparent-_right cur-_left;}delete cur;}else{//替换删除Node* parent cur;Node* minRight cur-_right;while (minRight-_left){parent minRight;minRight minRight-_left;}cur-_key minRight-_key;if (minRight parent-_left)parent-_left minRight-_right;elseparent-_right minRight-_right;delete minRight;}return true;}}return false;
}三、递归实现
3.1 递归查找 - Find
bool _FindR(Node* root, const K key)
{if (root nullptr)return false;if (key root-_key)root root-_right;else if (key root-_key)root root-_left;elsereturn true;
}3.2 递归插入 - Insert
在实现递归插入的过程中最后会发现插入时需要调用到父指针但是一步一步传父指针很麻烦于是这里用到了一个很巧妙的方法 ✏️代码实现
bool _InsertR(Node* root, const K key)
{if (root nullptr){root new Node(key);return true;}if (key root-_key)return _InsertR(root-_right, key);else if (key root-_key)return _InsertR(root-_left, key);elsereturn false;
}3.3 递归删除 - Erase
✏️代码实现
bool _EraseR(Node* root, const K key)
{if (root nullptr)return false;if (key root-_key)return _EraseR(root-_left, key);else if (key root-_key)return _EraseR(root-_right, key);else{//1.左右都为空//2.右为空//3.左右都不为空Node* del root;if (root-_left nullptr){root root-_right;}else if (root-_right nullptr){root root-_left;}else{//替换删除Node* minRight root-_right;while (minRight-_left)minRight minRight-_left;swap(root-_key, minRight-_key);// 转换成在子树中去删除节点return _EraseR(root-_right, key);}delete del;return true;}
}此递归实现有两处点睛之笔✨✨ 假如如图我们要删除的是节点14当递归走到节点10这一层时调用函数时传的是节点10- 右 也就意味着下一层函数的root是10-right的别名那我们要删除的就是节点正是10 - right此时是节点14我们再创建一个指针del将其存起来然后直接改变其值 —— root root - _left 如此一来10 - right 就变为13了✔️最后再将del给delete掉就搞定了 当我们需要替换法删除时替换了节点后此树子树不符合搜索二叉树的结构了但是我们能够发现其删除节点的子树是符合的因此要删掉节点只需要转换到子树中删除即可✔️
四、二叉搜索树的应用
4.1 K模型
K模型K模型即只有key作为关键码结构中只需要存储Key即可关键码即为需要搜索到的值。
比如给一个单词word判断该单词是否拼写正确具体方式如下
以词库中所有单词集合中的每个单词作为key构建一棵二叉搜索树在二叉搜索树中检索该单词是否存在存在则拼写正确不存在则拼写错误
4.2 KV模型
KV模型每一个关键码key都有与之对应的value即Key, Value 的键值对。这种方式在现实生活中非常常见
比如英汉词典就是英文与中文的对应关系通过英文可以快速找到与其对应的中文英文单词与其对应的中文word, chinese就构成一种键值对再比如统计单词次数统计成功后给定单词就可快速找到其出现的次数单词与其出现次数就是word, count就构成一种键值对
✏️改造二叉搜索树为KV结构
templateclass K, class V
struct BSTNode
{BSTNode(const K key K(), const V value V()): _pLeft(nullptr) , _pRight(nullptr), _key(key), _Value(value){}BSTNodeT* _pLeft;BSTNodeT* _pRight;K _key;V _value
};templateclass K, class V
class BSTree
{typedef BSTNodeK, V Node;typedef Node* PNode;
public:BSTree(): _pRoot(nullptr){}PNode Find(const K key);bool Insert(const K key, const V value)bool Erase(const K key)
private:PNode _pRoot;
};void TestBSTree3()
{// 输入单词查找单词对应的中文翻译BSTreestring, string dict;dict.Insert(string, 字符串);dict.Insert(tree, 树);dict.Insert(left, 左边、剩余);dict.Insert(right, 右边);dict.Insert(sort, 排序);// 插入词库中所有单词string str;while (cinstr){BSTreeNodestring, string* ret dict.Find(str);if (ret nullptr)cout 单词拼写错误词库中没有这个单词: str endl;elsecout str 中文翻译: ret-_value endl;}
}void TestBSTree4()
{// 统计水果出现的次数string arr[] { 苹果, 西瓜, 苹果, 西瓜, 苹果, 苹果, 西瓜, 苹果, 香蕉, 苹果, 香蕉 };BSTreestring, int countTree;for (const auto str : arr){// 先查找水果在不在搜索树中// 1、不在说明水果第一次出现则插入水果, 1// 2、在则查找到的节点中水果对应的次数//BSTreeNodestring, int* ret countTree.Find(str);auto ret countTree.Find(str);if (ret NULL)countTree.Insert(str, 1);elseret-_value;}
countTree.InOrder();
}五、二叉搜索树的性能分析
插入和删除操作都必须先查找查找效率代表了二叉搜索树中各个操作的性能。
对有n个结点的二叉搜索树若每个元素查找的概率相等则二叉搜索树平均查找长度是结点在二叉搜索树的深度的函数即结点越深则比较次数越多
但对于同一个关键码集合如果各关键码插入的次序不同可能得到不同结构的二叉搜索树 最优情况下二叉搜索树为完全二叉树(或者接近完全二叉树)其平均比较次数为logN
最差情况下二叉搜索树退化为单支树(或者类似单支)其平均比较次数为N/2
问题如果退化成单支树二叉搜索树的性能就失去了。那能否进行改进不论按照什么次序插入关键码二叉搜索树的性能都能达到最优这就需要我们的AVL树和红黑树派上用场了后续分享
✏️附上二叉搜索树源码BST.h
namespace K
{template class Kstruct BSTreeNode{BSTreeNodeK* _left;BSTreeNodeK* _right;K _key;//构造函数BSTreeNode(const K key):_key(key), _left(nullptr), _right(nullptr){}};templateclass Kclass BSTree{typedef BSTreeNodeK Node;public:BSTree():_root(nullptr){}BSTree(const BSTreeK t){_root Copy(t._root);}~BSTree(){Destroy(_root);_root nullptr;}BSTreeK operator(BSTreeK t){swap(_root, t._root);return *this;}//插入bool Insert(const K key){if (_root nullptr){_root new Node(key);return true;}//插入,小于就插左大于就插右Node* parent nullptr;Node* cur _root;while (cur){parent cur;if (key cur-_key)cur cur-_left;else if (key cur-_key)cur cur-_right;elsereturn false;}//到合适的空了开始插入//要插在左还是右还是需要比较cur new Node(key);if (key parent-_key)parent-_left cur;if (key parent-_key)parent-_right cur;return true;}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;}elsereturn true;}return false;}//删除bool Erase(const K key){Node* parent nullptr;Node* cur _root;while (cur){if (cur-_key key){parent cur;cur cur-_right;}else if (cur-_key key){parent cur;cur cur-_left;}else//值相等 - 找到了{//1.左为空//2.右为空//3.左右都不为空 - 替换删除if (cur-_left nullptr){if (cur _root) //parent nullptr_root cur-_right;else{if (cur parent-_left)parent-_left cur-_right;elseparent-_right cur-_right;}delete cur;}else if (cur-_right nullptr){if (cur _root)_root cur-_left;else{if (cur parent-_left)parent-_left cur-_left;elseparent-_right cur-_left;}delete cur;}else{//替换删除Node* parent cur;Node* minRight cur-_right;while (minRight-_left){parent minRight;minRight minRight-_left;}cur-_key minRight-_key;if (minRight parent-_left)parent-_left minRight-_right;elseparent-_right minRight-_right;delete minRight;}return true;}}return false;}//递归bool FindR(const K key){return _FindR(_root, key);}bool InsertR(const K key){return _InsertR(_root, key);}bool EraseR(const K key){return _EraseR(_root, key);}//中序遍历void Inorder(){_Inorder(_root);cout endl;}private:Node* _root nullptr;Node* Copy(Node* root){if (root nullptr)return nullptr;Node* newnode new Node(root-_key);newnode-_left Copy(root-_left);newnode-_right Copy(root-_right);return newnode;}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);}bool _FindR(Node* root, const K key){if (root nullptr)return false;if (key root-_key)root root-_right;else if (key root-_key)root root-_left;elsereturn true;}bool _InsertR(Node* root, const K key){if (root nullptr){root new Node(key);return true;}if (key root-_key)return _InsertR(root-_right, key);else if (key root-_key)return _InsertR(root-_left, key);elsereturn false;}bool _EraseR(Node* root, const K key){if (root nullptr)return false;if (key root-_key)return _EraseR(root-_left, key);else if (key root-_key)return _EraseR(root-_right, key);else{Node* del root;if (root-_left nullptr){root root-_right;}else if (root-_right nullptr){root root-_left;}else{//替换删除Node* minRight root-_right;while (minRight-_left)minRight minRight-_left;swap(root-_key, minRight-_key);// 转换成在子树中去删除节点return _EraseR(root-_right, key);}delete del;return true;}}};
}六、二叉树进阶试题
1️⃣根据二叉树创建字符串
传送门 解题思路此题的难点在于括号的省略我们可以先按照不用省略括号的思路写出前序遍历再去归纳什么时候就需要省略括号 class Solution {
public:string tree2str(TreeNode* root) {//可能是空树if(root nullptr)return string();//不是空树开始前序遍历//首先构造一个stringstring str;//不是空树则先插入根str to_string(root-val);//前序遍历 - 递归 -- 中-左-右//根完毕后就转换为子问题去遍历左树左树完毕就遍历右树//关于括号省略//1.左为空 右为空 - 省略//2.左为空右不为空 - 不能省略//3.左不为空右为空 - 省略if(root-left || root-right){str (;str tree2str(root-left);str );}if(root-right){str (;str tree2str(root-right);str );} return str;}
};2️⃣二叉树的层序遍历
传送门 解题思路对于大部分层序遍历我们都可以利用队列来辅助完成由于先进先出每次元素出队列时就带入其子节点这样我们便能按层顺序入队列以及出队列了。♨️而此题的难点在于不仅要层序遍历而且还需要将每层的元素分开那么我们可以在队列加入一个标记变量livesize来标识每层元素所剩元素个数和是否已经全部出完 class Solution {
public:vectorvectorint levelOrder(TreeNode* root) {vectorvectorint sum;queueTreeNode* q;//有可能是空树if(root nullptr)return sum;//非空q.push(root);int levesize 1;while(!q.empty()){vectorint ret;while(levesize--){TreeNode* front q.front();q.pop();ret.push_back(front-val);if(front-left)q.push(front-left);eif(front-right)q.push(front-right);}//一层遍历结束levesize q.size();sum.push_back(ret);}return sum;}
};3️⃣二叉树的最近公共祖先
传送门 ✏️思路1递归检查 解题思路我们经过分析可以归纳总结以下的情况 1.若有一个根节点并且一个在其左子树一个在其右子树那么此根节点即是最近公共祖先 2.若走到一个节点正是题目中的要求节点之一而另外一个节点在其子树则先走到的那个节点为最近公共祖先 此思路主要需要判断节点是否在根的左右子树中因此变量的命名尤为重要不然就容易乱 class Solution {
public:bool Find(TreeNode* sub, TreeNode* x){if(sub nullptr)return false;if(sub x)return true;return Find(sub-left, x)|| Find(sub-right, x);}TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {if(root nullptr)return nullptr;//根就是if(root q || root p)return root;bool qInLeft, qInRight, pInLeft, pInRight;pInLeft Find(root-left, p);pInRight !pInLeft;qInLeft Find(root-left, q);qInRight !qInLeft;//1、一个在左一个在右root就是最近公共祖先//2、如果都在左就递归去左边//3、如果都在右就递归去右边if((pInLeft qInRight) || (qInLeft pInRight)){return root;}else if (qInLeft pInLeft){return lowestCommonAncestor(root-left, p, q);}else if (qInRight pInRight){return lowestCommonAncestor(root-right, p, q);}else{return nullptr;}}
};✏️思路2路径比较 解题思路从根开始走到每个节点都有其路径而我们可以把2个节点的路径都记录下来然后找出那个最后一样的节点便是公共祖先 而对于路径的记录我们可以通过递归来记录对于最后公共祖先的查找我们可以让大的栈先pop直到两个路径栈的元素个数相同再相比较如果不同则pop class Solution {
public:bool Fpath(TreeNode* root,TreeNode* cur,stackTreeNode* st){if(root nullptr)return false;st.push(root);if(root cur)return true;if(Fpath(root-left,cur,st))return true;if(Fpath(root-right,cur,st))return true;//走到光标处说明此节点的左右子树都falsest.pop();return false;}TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {stackTreeNode* ppath;stackTreeNode* qpath;Fpath(root,p,ppath);Fpath(root,q,qpath);//两个栈的数量不一则要统一//找路径相遇点while(ppath.size()!qpath.size()){if(ppath.size() qpath.size())ppath.pop();elseqpath.pop();}while(ppath.top() ! qpath.top()){ppath.pop();qpath.pop();}return ppath.top();}
};写在最后 我们今天的学习分享之旅就到此结束了 感谢能耐心地阅读到此 码字不易感谢三连 关注博主我们一起学习、一起进步
