《数据结构二叉搜索树Binary Search Tree》**作者的个人gitee**​​作者的算法讲解主页▶️每日一言“人生如逆旅我亦是行人。”一、二叉搜索树的概念二叉搜索树Binary Search TreeBST是一种特殊的二叉树具有以下性质若左子树不为空则左子树上所有结点的值都小于等于根结点的值。若右子树不为空则右子树上所有结点的值都大于等于根结点的值。左右子树也分别为二叉搜索树。二叉搜索树中可以支持插入相等的值也可以不支持具体取决于使用场景的定义。如在C标准模板库中map和set不支持插入相等值而multimap和multiset支持插入相等值。二、二叉搜索树的性能分析二叉搜索树的性能主要取决于其高度。以下是不同情况下的性能分析情况高度增删查改时间复杂度最优logNO(logN)最差NO(N)平均取决于插入顺序取决于插入顺序最优情况当二叉搜索树为完全二叉树或接近完全二叉树时其高度为log2N。此时增删查改的时间复杂度为 O(log2N)。最差情况当二叉搜索树退化为单支树或类似单支时其高度为N。此时增删查改的时间复杂度为O(N)。平均情况在实际应用中二叉搜索树的高度取决于插入数据的顺序。如果插入数据是随机的那么平均情况下二叉搜索树的性能接近最优情况但如果插入数据是有序的那么二叉搜索树可能会退化为单支树性能接近最差情况。三、二叉搜索树的操作一插入插入操作的步骤如下树为空如果二叉搜索树为空则直接创建一个新的结点并将其赋值给根指针。树不为空从根结点开始按照二叉搜索树的性质进行比较如果插入值小于当前结点的值则向左子树移动。如果插入值大于当前结点的值则向右子树移动。如果插入值等于当前结点的值支持插入相等值的情况可以选择向左或向右移动但需要保持逻辑一致性。找到空位置当找到一个空位置时创建一个新的结点并将其插入到该位置。二查找查找操作的步骤如下从根开始从根结点开始将目标值与当前结点的值进行比较。比较并移动如果目标值小于当前结点的值则向左子树移动。如果目标值大于当前结点的值则向右子树移动。查找结果如果在某个结点找到目标值则返回该结点。如果走到空结点仍未找到目标值则说明目标值不存在。三删除删除操作相对复杂需要分情况处理查找目标结点首先查找要删除的结点是否存在。如果不存在则返回false。删除目标结点如果目标结点存在根据其子树情况分以下四种情况处理情况1目标结点左右孩子均为空。直接删除该结点并将其父结点对应的孩子指针置为空。情况2目标结点左孩子为空右孩子不为空。将目标结点的父结点对应的孩子指针指向目标结点的右孩子然后删除目标结点。情况3目标结点右孩子为空左孩子不为空。将目标结点的父结点对应的孩子指针指向目标结点的左孩子然后删除目标结点。情况4目标结点左右孩子均不为空。使用替换法删除。可以找目标结点左子树的最大值结点最右结点或者右子树的最小值结点最左结点替代目标结点。替代后将问题转化为删除替代结点替代结点符合情况2或情况3可以直接删除。四、二叉搜索树的实现代码一结构体BSTNodetemplateclassKstructBSTNode{K _key;BSTNodeK*_left;BSTNodeK*_right;BSTNode(constKkey):_key(key),_left(nullptr),_right(nullptr){}};二类BSTreetemplateclassKclassBSTree{typedefBSTNodeKNode;public:boolInsert(constKkey){if(_rootnullptr){_rootnewNode(key);returntrue;}Node*parentnullptr;Node*cur_root;while(cur){if(cur-_keykey){parentcur;curcur-_right;}elseif(cur-_keykey){parentcur;curcur-_left;}else{returnfalse;// 不允许插入重复值}}curnewNode(key);if(parent-_keykey){parent-_rightcur;}else{parent-_leftcur;}returntrue;}boolFind(constKkey){Node*cur_root;while(cur){if(cur-_keykey){curcur-_right;}elseif(cur-_keykey){curcur-_left;}else{returntrue;// 找到目标值}}returnfalse;// 未找到目标值}boolErase(constKkey){Node*parentnullptr;Node*cur_root;while(cur){if(cur-_keykey){parentcur;curcur-_right;}elseif(cur-_keykey){parentcur;curcur-_left;}else{// 情况1左右孩子均为空if(cur-_leftnullptrcur-_rightnullptr){if(parentnullptr){_rootnullptr;}else{if(parent-_leftcur)parent-_leftnullptr;elseparent-_rightnullptr;}deletecur;returntrue;}// 情况2左孩子为空右孩子不为空elseif(cur-_leftnullptr){if(parentnullptr){_rootcur-_right;}else{if(parent-_leftcur)parent-_leftcur-_right;elseparent-_rightcur-_right;}deletecur;returntrue;}// 情况3右孩子为空左孩子不为空elseif(cur-_rightnullptr){if(parentnullptr){_rootcur-_left;}else{if(parent-_leftcur)parent-_leftcur-_left;elseparent-_rightcur-_left;}deletecur;returntrue;}// 情况4左右孩子均不为空else{Node*rightMinPcur;Node*rightMincur-_right;while(rightMin-_left){rightMinPrightMin;rightMinrightMin-_left;}cur-_keyrightMin-_key;if(rightMinP-_leftrightMin)rightMinP-_leftrightMin-_right;elserightMinP-_rightrightMin-_right;deleterightMin;returntrue;}}}returnfalse;// 未找到目标值}voidInOrder(){_InOrder(_root);coutendl;}private:void_InOrder(Node*root){if(rootnullptr){return;}_InOrder(root-_left);coutroot-_key ;_InOrder(root-_right);}Node*_rootnullptr;};五、二叉搜索树的应用场景一key搜索场景在key搜索场景中二叉搜索树仅存储关键码key用于判断某个值是否存在。小区无人值守车库将买了车位的业主车牌号录入后台系统车辆进入时扫描车牌号判断其是否存在于系统中从而决定是否抬杆。英文单词拼写检查将词库中的所有单词放入二叉搜索树读取文章中的单词查找其是否存在于二叉搜索树中若不存在则提示拼写错误。二key/value搜索场景在key/value搜索场景中二叉搜索树的每个结点不仅存储关键码key还存储与之对应的值value。搜索时以key为关键字进行比较可以快速找到key对应的value。中英互译字典在树的结点中存储英文单词key和对应的中文翻译value搜索时输入英文单词即可找到其对应的中文翻译。商场无人值守车库入口进场时扫描车牌号记录车牌号和入场时间key/value出口离场时扫描车牌号查找入场时间计算停车时长和费用。统计文章中单词出现次数读取一个单词查找其是否存在于二叉搜索树中若不存在则插入该单词并将其出现次数初始化为1若存在则将其对应的出现次数加1。六、总结二叉搜索树是一种重要的数据结构具有插入、查找、删除等操作。其性能在最优情况下接近O(log2N)但在最差情况下会退化为O(N)。为了提高二叉搜索树的性能后续可以学习其进阶如平衡二叉搜索树AVL树、B树和红黑树。车库**入口进场时扫描车牌号记录车牌号和入场时间key/value出口离场时扫描车牌号查找入场时间计算停车时长和费用。统计文章中单词出现次数读取一个单词查找其是否存在于二叉搜索树中若不存在则插入该单词并将其出现次数初始化为1若存在则将其对应的出现次数加1。六、总结二叉搜索树是一种重要的数据结构具有插入、查找、删除等操作。其性能在最优情况下接近O(log2N)但在最差情况下会退化为O(N)。为了提高二叉搜索树的性能后续可以学习其进阶如平衡二叉搜索树AVL树、B树和红黑树。如果有帮助的话麻烦点个赞和关注吧秋梨膏QAQ!