尧图网站建设 
1. 二叉搜索树到底解决了什么问题1.1 定义和核心性质以及一个反直觉的点我第一次接触二叉搜索树Binary Search Tree通常直接叫BST的时候心里想的是这不就是在每个节点上做二分吗左孩子比我小右孩子比我大插入、查找、删除都是顺着路径往下走复杂度O(logn)。听起来很简单真正动手写代码才发现丢人的地方全在细节里。先帮新手把定义理清楚。一棵二叉树如果对于每一个节点都满足左子树中所有节点的值都小于这个节点的值右子树中所有节点的值都大于这个节点的值并且左右子树本身也满足同样条件那它就是一棵二叉搜索树。注意是所有节点不是说直接左孩子比你小就行而是左子树里的每一个节点都比你小。这里有一个很多人会反直觉的点BST保证的是全局有序不是局部有序。举个例子根节点是50左孩子是3030的右孩子是45。45虽然大于30但它依然是左子树的一部分所以它必须小于50。如果你只拿左孩子小于父亲、右孩子大于父亲这种相邻关系去理解BST后面写验证代码的时候一定会翻车。我记得在LeetCode上有一道验证二叉搜索树的题目很多人用递归传最小值、最大值区间的方式去验证结果挂在类似上面这种用例上。原因就是没有理解全局约束这四个字。BST的每个节点其实隐含了一个取值区间根节点是负无穷到正无穷往左走区间的右边界变成当前节点值往右走区间的左边界变成当前节点值。这个区间概念理解了BST的很多操作你都能推导出来。1.2 中序遍历是BST的灵魂不只是一个遍历方式BST最容易被低估的性质是中序遍历结果一定是升序序列。这个性质我为什么单独拿出来说因为它在实际工程里几乎是BST最常用的功能来源。C的std::map和std::set底层的红黑树也是一种平衡BST你迭代遍历std::map的时候拿到的是按键升序排列的数据这个有序性就来自BST的中序遍历性质。如果不做平衡处理底层结构退化成链表中序迭代就退化成链表的顺序遍历。这个性质还有一个很实际的用途验证BST是否合法。我后面写删除操作的时候就是靠中序遍历结果来判断树有没有被写坏。你不需要去画图也不需要去人脑模拟指针指向直接打一个vector出来看是不是严格递增。简单粗暴但特别好用。严格递增还有一个隐藏细节如果树里有相等值节点中序就会有非递增的相邻元素因此相等值到底放在左边还是右边取决于你的定义常规BST要求左边小右边大相等值就不该出现或者说需要特别的约定。我建议所有学BST的人第一件事不是去写插入删除而是先把中序遍历的递归和迭代都写熟。递归版几行就写完迭代版要自己用一个栈模拟这个模拟过程其实就是后面很多平衡树操作的雏形。你连中序迭代都写不明白后面看红黑树的左旋右旋会非常痛苦。1.3 平均复杂度与最坏复杂度的真实差距BST的理论复杂度是查找、插入、删除平均O(logn)。但这个平均是有前提条件的——插入序列的随机性。如果数据是接近有序的比如你依次插入1, 2, 3, 4, 5, ...BST会退化成一个只有右子树的链表这时候查找复杂度直接变成O(n)跟线性表没区别。这不是理论上的恐吓是实际会踩的坑。我曾经为了图方便在某个模块里用BST来维护一份按时间戳排序的缓存结果生产环境的数据真就基本按时间递增到达树的形状歪得没法看查找性能从毫秒级涨到秒级。后来换成std::map底层红黑树自带平衡才解决问题。所以如果你只是想用一个有序容器直接用C标准库的std::map、std::set、std::multimap就行自己写BST更多是为了学原理、应对面试或者在某些特殊场景下自定义行为。操作平均复杂度最坏复杂度退化成链表查找O(log n)O(n)插入O(log n)O(n)删除O(log n)O(n)中序遍历O(n)O(n)这张表值得贴在电脑前面。BST的所有优点都建立在树高接近logn的基础上一旦树高变成n它就没有任何优势了。2. C实现的基础骨架节点设计、插入、查找2.1 节点结构用struct、用模板还是用智能指针写C的BST第一步是设计节点结构。我见过很多新手纠结用struct还是class其实在C里struct和class唯一的区别就是默认访问权限struct默认publicclass默认private。做这种纯粹的数据结构节点用struct最省事struct TreeNode { int val; TreeNode* left; TreeNode* right; explicit TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} };构造函数写explicit是个好习惯防止隐式转换。这个节点结构够用但不通用如果你想存string、double或者其他自定义类型就得改类型。更好的做法是改成模板template typename T struct TreeNode { T val; TreeNode* left; TreeNode* right; explicit TreeNode(const T x) : val(x), left(nullptr), right(nullptr) {} };模板版本的写法和普通版本几乎没差但通用性一下就上来了。还有一点需要注意如果T是一个字符串或者复杂对象构造函数参数最好是const T而不是T少一次拷贝。再来说智能指针。用std::shared_ptr管理节点有一个实际好处删除节点的时候不用手动delete不会因为忘释放内存而泄漏。但代价是shared_ptr的引用计数有额外开销而且如果树里出现环shared_ptr还会导致内存泄漏。BST本身没有环但父节点指回子节点、子节点指向父节点这种双向结构用shared_ptr就要非常小心很容易出现循环引用。我自己的建议是学习阶段老老实实用裸指针把内存管理的意识练出来工程上用std::unique_ptr或者干脆用vector下标管理节点除非有特别需求不建议用shared_ptr。2.2 插入操作的递归写法以及return root的妙处插入操作是我认为BST代码里最有教学价值的一个函数。它短小精悍但把递归的核心思想体现得淋漓尽致template typename T TreeNodeT* insertNode(TreeNodeT* root, const T val) { if (root nullptr) { return new TreeNodeT(val); } if (val root-val) { root-left insertNode(root-left, val); } else if (val root-val) { root-right insertNode(root-right, val); } else { // 值已存在按需求决定忽略、计数或者更新 return root; } return root; }我第一次看到这个写法觉得很奇怪为什么递归调用之后要赋值给root-left直接调用不行吗后来想明白了insertNode的返回值是新插入节点在递归返回后、整条路径上需要挂接的子树根。你只调用不接收返回值父节点的left指针就不会更新新节点就丢了。这个返回并接收的模式在链表的递归操作里也很常见。比如递归反转链表函数返回新头节点上一层调用接收并挂接。理解了这一个模式很多递归数据结构的操作你都能举一反三。值已经存在的情况怎么处理这取决于你的应用场景。如果是要实现multiset就用一个计数器字段记录出现次数如果要实现set就忽略。我习惯在注释里写清楚否则三个月后回来看代码会疑惑为什么相等值不处理。2.3 查找递归能写但迭代更实用查找的递归版本很好理解template typename T TreeNodeT* searchNode(TreeNodeT* root, const T target) { if (root nullptr || root-val target) { return root; } if (target root-val) { return searchNode(root-left, target); } return searchNode(root-right, target); }但实际工程里我会更推荐迭代版本。原因很简单递归每次调用都压栈查找频繁的时候这个开销不可忽略而且如果树高很大递归深度可能把栈打爆。迭代版本就是手动把递归的状态用一个循环接住template typename T TreeNodeT* searchNode(TreeNodeT* root, const T target) { while (root ! nullptr root-val ! target) { if (target root-val) { root root-left; } else { root root-right; } } return root; }这个代码一行多余的东西都没有。你发现了没查找不需要回溯因为BST的性质帮你把路径唯一确定了。每次比较后你至少排除掉一半的子树严格说是所有不可能包含目标值的分支这就是BST查找效率的根源。如果查找中出现了需要回溯的想法说明你的树结构已经不符合BST定义或者你的目标值可能在两个方向那就要停下来检查下了。3. 删除节点与中序遍历验证BST最容易翻车的两个环节3.1 删除节点的三种情况删除是BST里面bug率最高的操作没有之一。原因在于删除一个节点后你不仅要处理这个节点本身还要保证剩下的树仍然满足BST性质。按照被删除节点的子节点数量可以分成三种情况情况处理方式复杂度叶子节点直接删除父节点对应指针置空简单只有一个子节点让子节点顶替被删除节点位置中等有两个子节点用左子树最大节点或右子树最小节点替换删除节点复杂前两种情况边界比较简单。叶子节点直接delete父节点的指针要置空。只有一个子节点时把那个子节点提上来顶替被删节点的位置。这些都是断链操作注意处理好父节点的指向。第三种情况是真正的分水岭。被删除节点有两个孩子你不能简单地把其中一个孩子提上来因为提上来之后另一个孩子没地方放而且还会破坏排序。标准做法是在右子树里找到最小的节点或者在左子树里找到最大的节点用这个节点的值覆盖要删除节点的值然后去删除那个用来替换的节点。这样树的结构没有被破坏只是把值搬了个家被替换节点一定最多只有一个子节点为什么因为它是最小节点不可能有左子节点最大节点则不可能有右子节点问题就回归到第二种情况的处理容易很多。3.2 删除代码完整实现与两个容易踩的坑我的删除实现长这样template typename T TreeNodeT* findMin(TreeNodeT* root) { while (root ! nullptr root-left ! nullptr) { root root-left; } return root; } template typename T TreeNodeT* deleteNode(TreeNodeT* root, const T target) { if (root nullptr) { return nullptr; } if (target root-val) { root-left deleteNode(root-left, target); } else if (target root-val) { root-right deleteNode(root-right, target); } else { // 找到目标节点 if (root-left nullptr root-right nullptr) { delete root; return nullptr; } if (root-left nullptr) { TreeNodeT* rightChild root-right; delete root; return rightChild; } if (root-right nullptr) { TreeNodeT* leftChild root-left; delete root; return leftChild; } // 两个子节点都存在用右子树最小节点替换 TreeNodeT* minNode findMin(root-right); root-val minNode-val; root-right deleteNode(root-right, minNode-val); } return root; }这段代码我调试过很多次有两点特别想提醒大家。第一个坑是只delete节点不处理指针。如果你在一个节点的父节点结构里直接delete了它但是没有把父节点的left或right置空这个指针就成了野指针。我的代码里是通过返回值来处理的删除后返回nullptr或者子节点地址上一层调用接收并赋值给root-left或root-right这样指针更新就统一收口了。这个模式很优雅但前提是你别漏掉任何一条return分支。第二个坑是用右子树最小节点替换后忘了删除那个被替换的节点或者删除时写成了对整个root调用deleteNode。上面的代码在替换值之后对root-right递归调用deleteNode传入的是minNode-val这样就能精准地把那个节点删除不会误伤其他节点。提示跟踪递归调用时有一个技巧通过打印args和返回值的方式在函数入口和出口各打一行日志马上能看到递归的调用链。我自己调试的时候用这个方法比用眼睛硬盯代码快得多。3.3 用中序遍历自检BST的正确性写完了插入、删除怎么确认代码是对的我习惯写一个自检函数用中序遍历生成序列然后判断序列是否严格递增。template typename T void inOrderTraversal(TreeNodeT* root, std::vectorT result) { if (root nullptr) return; inOrderTraversal(root-left, result); result.push_back(root-val); inOrderTraversal(root-right, result); } template typename T bool isValidBST(TreeNodeT* root) { std::vectorT result; inOrderTraversal(root, result); for (size_t i 1; i result.size(); i) { if (result[i] result[i - 1]) { return false; } } return true; }这个自检函数特别有用。我在写BST的练习中每执行完一组插入和删除就调用这个函数验证一下。如果返回false就说明树被写坏了再结合具体操作步骤从出错的那个节点开始排查。它不能告诉你是哪一步写错了但能告诉你已经出错了在练习阶段配合二分查找定位效率很高。还有个更严苛的验证方法把操作序列和对应的预期结果记下来做模糊验证。比如随机插入n个数再随机删除m个数每步之后都检查三件事——树是否满足BST性质、中序序列是否和实际存的值集合一致、树中节点数量是否等于存的值集合大小。这一套组合拳打下来你的插入删除实现基本可以放心。4. 从不同的二叉搜索树题目理解卡特兰数4.1 题目要求与直觉突破LeetCode上有一道经典题目叫不同的二叉搜索树输入一个整数n要求计算由1到n这n个节点一共能组成多少种不同形态的二叉搜索树。我第一次看到这道题第一反应是用回溯枚举后来发现n做到19的时候结果已经很大枚举到天荒地老都算不完。这题考查的是组合数学里的卡特兰数。先想一个关键问题如果1到n构成BST根节点是i那么左子树由1到i-1构成右子树由i1到n构成。左子树的形态数和右子树的形态数是独立的所以以i为根的BST总数 左子树形态数 × 右子树形态数。注意这里左子树和右子树的节点个数决定了形态数而不是具体数值。因为节点是从1到i-1还是从5到9只要节点个数相同能组成的BST形态数就相同。这个个数决定形态的认知是整个题目推导的突破口。4.2 动态规划推导dp[n] Σ dp[i] × dp[n-1-i]设dp[n]表示n个节点能组成的BST数量。dp[0]等于多少空树也算一种形态所以dp[0] 1这个约定是为了递推方便。dp[1] 1只有一个节点没得选。考虑n个节点根节点选i左子树有i-1个节点右子树有n-i个节点总的形态数是dp[i-1] × dp[n-i]。因为i可以取1到n任意值所以把所有情况加起来dp[n] Σ(i1到n) dp[i-1] × dp[n-i]换种写法令j i-1则dp[n] Σ(j0到n-1) dp[j] × dp[n-1-j]。这就是卡特兰数的递推形式。这个递推式用动态规划很容易实现而且每一步的计算都依赖前面已经算好的值天然适合自底向上。这个递推的核心其实是独立子问题相乘然后枚举求和的套路。以后你遇到类似的树上计数问题比如统计所有可能的二叉树、所有可能的括号组合都可以往这个思路上靠。4.3 C实现与边界处理int numTrees(int n) { std::vectorlong long dp(n 1, 0); dp[0] 1; for (int i 1; i n; i) { for (int j 0; j i; j) { dp[i] dp[j] * dp[i - 1 - j]; } } return static_castint(dp[n]); }两点提醒。第一dp的类型我用了long long。卡特兰数增长很快n19时结果是1767263190已经接近int的极限n20就直接溢出int了。如果你要算更大的n用long long都不够得用大数或者取模。第二内层循环j i还是j i-1就是个数问题。总节点数为i左子树j个右子树i-1-j个j的取值范围是0到i-1所以写j i正好。这道题虽然只是个计数问题但它让我真正理解了BST的递归结构。你甚至可以从这个DP推导过程反推出给定一组有序值我们不光能数出有多少种BST还能通过回溯DP数组把所有具体的树的形态都构造出来。比如要求输出所有形态那就是在计算过程中记录每种根的选择再用递归的方式拼装出树的结构。这就是计数和构造的区别前者只算数量后者要生成所有解。5. 退化风险与递归深度总要面对的薄弱环节5.1 有序插入导致退化成链表前面说过BST的平均复杂度是O(logn)但前提是插入序列足够随机。如果数据本身有序BST会退化。具体来说依次插入1, 2, 3, 4, 5你会得到一条向右延伸的链每个节点只有右孩子没有左孩子。这时候BST就是一个加了包装的链表查找一个节点的时间是O(n)跟数组顺序查找没有区别。这个退化的根因在于普通BST没有维护平衡这个约束。插入和删除只会改变局部路径上的节点不会在全局范围做结构调整。长此以往树高就可能偏离logn。我教你一个简单的观测方法插入一组数据后用中序遍历和层次遍历对比一下树的深度。如果深度远大于logn比如n10深度接近10那你基本可以断定树已经歪了。我实际做过一个实验把0到999按顺序插入BST树高是999但把这1000个数随机打乱再插入树高大概是20多。这个差距直观得吓人。5.2 递归深度逼近系统栈上限怎么办递归实现的BST操作最怕的就是树特别高。系统栈大小一般默认8MB递归调用每次大概占几十到上百字节的栈帧。如果树高是10000递归深度上万次很可能直接爆栈。我在项目里遇到过这个问题。当时维护一棵非常大的BST树高一度到了好几万插入操作递归调用导致程序直接崩溃。后来做了两个改造第一把插入和查找改成了迭代写法消除递归调用第二对树做了一次重构把不平衡的节点重新整理成平衡BST。所以我的建议很直接学习阶段用递归理解原理没问题但要在心里时刻记得递归深度等于树高这个限制。真到了生产环境或者处理大规模数据优先考虑迭代版本或者直接上自带平衡的容器。5.3 从BST到AVL树旋转在解决什么问题BST退化的终极解决方案是平衡树。最经典的是AVL树它要求任何节点的左右子树高度差不超过1。插入、删除之后如果某个节点不满足这个约束就要通过旋转来恢复平衡。旋转操作一共有四种LL、RR、LR、RL。LL就是left-left失衡某个节点的左子树的左子树太高了需要右旋一次来恢复RR就是镜像的情况左旋一次LR则是左子树的右子树太高需要先左旋再右旋RL是右子树的左子树太高需要先右旋再左旋。旋转的本质是什么是把一棵歪的树重新捋直同时保持BST的中序有序性不变。我最初看旋转代码时一头雾水后来在纸上画了好几遍才明白旋转改变了节点的父子关系但不改变中序序列。中序序列的稳定性是BST所有操作必须遵守的底线旋转也是围绕这个底线设计的。红黑树是AVL的一种工程化改良它不追求严格的高度差不超过1而是用颜色约束来保证最长路径不超过最短路径的两倍。C标准库的std::map用的就是红黑树因为它插入删除时需要的旋转次数比AVL少综合性能更好。理解了BST和AVL再看红黑树就不会那么懵因为红黑树本质上就是加了颜色约束的BST配合旋转和变色来平衡。6. 动手实验时的调试心得和VSCode环境建议6.1 我踩过的三个典型bug学BST这段时间我踩过不少坑挑三个印象最深的分享出来。第一个是递归插入时忘了接收返回值。我在insertNode里写了递归调用但没有写root-left insertNode(...)直接写insertNode(root-left, val)编译不报错、运行也没异常但树根本没有变化。查了大半天才发现递归修改的是形参出了函数就没了必须通过返回值把更新后的子树带回来。C是按值传递指针的你想在函数里修改指针本身得传二级指针或者用引用不然就得靠返回值。这个教训让我记住了数据结构的递归更新模式。第二个是删除叶子节点之后野指针。我最初写的删除代码在叶子节点时直接delete root然后返回但父节点的left指针没有被更新还指向已经被释放的内存。后来在树中查找一个不存在的值逻辑没走错但内存越界。这个问题用中序遍历自检函数能很快发现因为野指针会让程序在遍历时崩溃或者产生随机值。解决方法是严格按照删除函数返回新子树根上层调用接住并赋值的模式来写。第三个是相等值节点的处理。如果插入序列里有两个相同的元素BST的性质没有统一标准规定放左边还是放右边。如果你的实现里相等值既可能往左走也可能往右走删除的时候就可能找不到目标节点。我的建议是在设计节点结构时就要明确相等值是忽略、计数还是放某一侧。我倾向于用忽略来保持树中元素唯一如果确实要支持重复元素就给节点加一个count字段而不是在树里复制出两个相同值的节点。6.2 用断言和中序序列做回归验证我自己练习BST时喜欢在代码里加一个自检函数并在每次插入删除之后调用。这个自检函数做三件事检查节点数量是否符合预期、中序遍历序列是否严格递增、树的深度是否不超过一个合理范围。如果这三者都通过基本就可以认为当前操作没把树写坏。比如插入10个随机数删除其中3个我期望的序列是排序后的7个数。自检函数会实际跑一遍中序遍历把结果和预期对比不一致就打印日志。void debugBST(TreeNodeint* root) { std::vectorint seq; inOrderTraversal(root, seq); for (size_t i 1; i seq.size(); i) { assert(seq[i] seq[i - 1]); } std::cout 节点数: seq.size() , 深度: treeDepth(root) std::endl; }在Debug模式下assert会触发Release模式下会被剥离。调试阶段这东西的价值非常大一旦你写完一个函数就能立刻验证正确性不用等到整个程序都写完才发现问题藏在哪个角落。6.3 VSCode调试C的几个关键配置很多人学C数据结构卡在环境配置上我在VSCode里配置C环境走了不少弯路把最关键的两点拎出来说下。tasks.json负责编译核心是告诉编译器你要编译哪个文件、输出到哪里、用什么标准。我建议把C标准至少设成C17这样可以用很多现代特性。编译命令类似{ type: cppbuild, command: g, args: [ -fdiagnostics-coloralways, -g, -stdc17, ${file}, -o, ${fileDirname}/${fileBasenameNoExtension}.exe ] }-g参数特别重要它生成调试信息没有这一项断点基本是摆设。-stdc17避免一些老标准下的坑。launch.json负责调试关键配置是program要指向你编译出来的exe文件路径和tasks.json的输出路径保持一致。配置好之后就可以在VSCode里打断点了。我写BST时常用的调试方式是在insertNode的递归调用前后各打一个断点配合Watch窗口观察root-val、root-left和root-right的值。因为树的指针结构非常复杂你光靠print不一定能看出问题所在但单步执行加Watch就能看到一个节点的左右子树是不是按预期更新。还有一个排查递归问题的小技巧在Watch窗口里添加root的地址和对应的val再添加递归返回值的临时变量。这样你能看到每一层递归返回后父节点的结构变化很多人写递归调用的bug就是这么一步步盯出来的。如果你用的是Windows记得安装MinGW-w64或者Visual Studio的C工具链之后在VSCode里指定编译器路径。Linux/macOS用户直接用系统自带的g或者clang就行tasks.json里的command改成g或clang就好。环境本身不复杂但网上很多教程配的版本比较老导致编译老报错。核心就一句话tasks.json管编译launch.json管调试两者配合好你的C学习之旅会顺畅很多。BST这份笔记写到这里我最有感触的还不是这些代码本身而是学习数据结构的方法。别光盯着别人的代码看一定要自己动手写写完用中序序列去验证用随机插入和删除去折腾它用有序插入去观察退化。你对树结构的理解就是在这一次次写坏、定位、修复的过程中建立起来的。后面再去看红黑树、B树你会发现自己已经能很快抓住它们的核心思路了。 二叉搜索树从原理到实战：C++实现、删除与退化分析
1. 二叉搜索树到底解决了什么问题1.1 定义和核心性质以及一个反直觉的点我第一次接触二叉搜索树Binary Search Tree通常直接叫BST的时候心里想的是这不就是在每个节点上做二分吗左孩子比我小右孩子比我大插入、查找、删除都是顺着路径往下走复杂度O(logn)。听起来很简单真正动手写代码才发现丢人的地方全在细节里。先帮新手把定义理清楚。一棵二叉树如果对于每一个节点都满足左子树中所有节点的值都小于这个节点的值右子树中所有节点的值都大于这个节点的值并且左右子树本身也满足同样条件那它就是一棵二叉搜索树。注意是所有节点不是说直接左孩子比你小就行而是左子树里的每一个节点都比你小。这里有一个很多人会反直觉的点BST保证的是全局有序不是局部有序。举个例子根节点是50左孩子是3030的右孩子是45。45虽然大于30但它依然是左子树的一部分所以它必须小于50。如果你只拿左孩子小于父亲、右孩子大于父亲这种相邻关系去理解BST后面写验证代码的时候一定会翻车。我记得在LeetCode上有一道验证二叉搜索树的题目很多人用递归传最小值、最大值区间的方式去验证结果挂在类似上面这种用例上。原因就是没有理解全局约束这四个字。BST的每个节点其实隐含了一个取值区间根节点是负无穷到正无穷往左走区间的右边界变成当前节点值往右走区间的左边界变成当前节点值。这个区间概念理解了BST的很多操作你都能推导出来。1.2 中序遍历是BST的灵魂不只是一个遍历方式BST最容易被低估的性质是中序遍历结果一定是升序序列。这个性质我为什么单独拿出来说因为它在实际工程里几乎是BST最常用的功能来源。C的std::map和std::set底层的红黑树也是一种平衡BST你迭代遍历std::map的时候拿到的是按键升序排列的数据这个有序性就来自BST的中序遍历性质。如果不做平衡处理底层结构退化成链表中序迭代就退化成链表的顺序遍历。这个性质还有一个很实际的用途验证BST是否合法。我后面写删除操作的时候就是靠中序遍历结果来判断树有没有被写坏。你不需要去画图也不需要去人脑模拟指针指向直接打一个vector出来看是不是严格递增。简单粗暴但特别好用。严格递增还有一个隐藏细节如果树里有相等值节点中序就会有非递增的相邻元素因此相等值到底放在左边还是右边取决于你的定义常规BST要求左边小右边大相等值就不该出现或者说需要特别的约定。我建议所有学BST的人第一件事不是去写插入删除而是先把中序遍历的递归和迭代都写熟。递归版几行就写完迭代版要自己用一个栈模拟这个模拟过程其实就是后面很多平衡树操作的雏形。你连中序迭代都写不明白后面看红黑树的左旋右旋会非常痛苦。1.3 平均复杂度与最坏复杂度的真实差距BST的理论复杂度是查找、插入、删除平均O(logn)。但这个平均是有前提条件的——插入序列的随机性。如果数据是接近有序的比如你依次插入1, 2, 3, 4, 5, ...BST会退化成一个只有右子树的链表这时候查找复杂度直接变成O(n)跟线性表没区别。这不是理论上的恐吓是实际会踩的坑。我曾经为了图方便在某个模块里用BST来维护一份按时间戳排序的缓存结果生产环境的数据真就基本按时间递增到达树的形状歪得没法看查找性能从毫秒级涨到秒级。后来换成std::map底层红黑树自带平衡才解决问题。所以如果你只是想用一个有序容器直接用C标准库的std::map、std::set、std::multimap就行自己写BST更多是为了学原理、应对面试或者在某些特殊场景下自定义行为。操作平均复杂度最坏复杂度退化成链表查找O(log n)O(n)插入O(log n)O(n)删除O(log n)O(n)中序遍历O(n)O(n)这张表值得贴在电脑前面。BST的所有优点都建立在树高接近logn的基础上一旦树高变成n它就没有任何优势了。2. C实现的基础骨架节点设计、插入、查找2.1 节点结构用struct、用模板还是用智能指针写C的BST第一步是设计节点结构。我见过很多新手纠结用struct还是class其实在C里struct和class唯一的区别就是默认访问权限struct默认publicclass默认private。做这种纯粹的数据结构节点用struct最省事struct TreeNode { int val; TreeNode* left; TreeNode* right; explicit TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} };构造函数写explicit是个好习惯防止隐式转换。这个节点结构够用但不通用如果你想存string、double或者其他自定义类型就得改类型。更好的做法是改成模板template typename T struct TreeNode { T val; TreeNode* left; TreeNode* right; explicit TreeNode(const T x) : val(x), left(nullptr), right(nullptr) {} };模板版本的写法和普通版本几乎没差但通用性一下就上来了。还有一点需要注意如果T是一个字符串或者复杂对象构造函数参数最好是const T而不是T少一次拷贝。再来说智能指针。用std::shared_ptr管理节点有一个实际好处删除节点的时候不用手动delete不会因为忘释放内存而泄漏。但代价是shared_ptr的引用计数有额外开销而且如果树里出现环shared_ptr还会导致内存泄漏。BST本身没有环但父节点指回子节点、子节点指向父节点这种双向结构用shared_ptr就要非常小心很容易出现循环引用。我自己的建议是学习阶段老老实实用裸指针把内存管理的意识练出来工程上用std::unique_ptr或者干脆用vector下标管理节点除非有特别需求不建议用shared_ptr。2.2 插入操作的递归写法以及return root的妙处插入操作是我认为BST代码里最有教学价值的一个函数。它短小精悍但把递归的核心思想体现得淋漓尽致template typename T TreeNodeT* insertNode(TreeNodeT* root, const T val) { if (root nullptr) { return new TreeNodeT(val); } if (val root-val) { root-left insertNode(root-left, val); } else if (val root-val) { root-right insertNode(root-right, val); } else { // 值已存在按需求决定忽略、计数或者更新 return root; } return root; }我第一次看到这个写法觉得很奇怪为什么递归调用之后要赋值给root-left直接调用不行吗后来想明白了insertNode的返回值是新插入节点在递归返回后、整条路径上需要挂接的子树根。你只调用不接收返回值父节点的left指针就不会更新新节点就丢了。这个返回并接收的模式在链表的递归操作里也很常见。比如递归反转链表函数返回新头节点上一层调用接收并挂接。理解了这一个模式很多递归数据结构的操作你都能举一反三。值已经存在的情况怎么处理这取决于你的应用场景。如果是要实现multiset就用一个计数器字段记录出现次数如果要实现set就忽略。我习惯在注释里写清楚否则三个月后回来看代码会疑惑为什么相等值不处理。2.3 查找递归能写但迭代更实用查找的递归版本很好理解template typename T TreeNodeT* searchNode(TreeNodeT* root, const T target) { if (root nullptr || root-val target) { return root; } if (target root-val) { return searchNode(root-left, target); } return searchNode(root-right, target); }但实际工程里我会更推荐迭代版本。原因很简单递归每次调用都压栈查找频繁的时候这个开销不可忽略而且如果树高很大递归深度可能把栈打爆。迭代版本就是手动把递归的状态用一个循环接住template typename T TreeNodeT* searchNode(TreeNodeT* root, const T target) { while (root ! nullptr root-val ! target) { if (target root-val) { root root-left; } else { root root-right; } } return root; }这个代码一行多余的东西都没有。你发现了没查找不需要回溯因为BST的性质帮你把路径唯一确定了。每次比较后你至少排除掉一半的子树严格说是所有不可能包含目标值的分支这就是BST查找效率的根源。如果查找中出现了需要回溯的想法说明你的树结构已经不符合BST定义或者你的目标值可能在两个方向那就要停下来检查下了。3. 删除节点与中序遍历验证BST最容易翻车的两个环节3.1 删除节点的三种情况删除是BST里面bug率最高的操作没有之一。原因在于删除一个节点后你不仅要处理这个节点本身还要保证剩下的树仍然满足BST性质。按照被删除节点的子节点数量可以分成三种情况情况处理方式复杂度叶子节点直接删除父节点对应指针置空简单只有一个子节点让子节点顶替被删除节点位置中等有两个子节点用左子树最大节点或右子树最小节点替换删除节点复杂前两种情况边界比较简单。叶子节点直接delete父节点的指针要置空。只有一个子节点时把那个子节点提上来顶替被删节点的位置。这些都是断链操作注意处理好父节点的指向。第三种情况是真正的分水岭。被删除节点有两个孩子你不能简单地把其中一个孩子提上来因为提上来之后另一个孩子没地方放而且还会破坏排序。标准做法是在右子树里找到最小的节点或者在左子树里找到最大的节点用这个节点的值覆盖要删除节点的值然后去删除那个用来替换的节点。这样树的结构没有被破坏只是把值搬了个家被替换节点一定最多只有一个子节点为什么因为它是最小节点不可能有左子节点最大节点则不可能有右子节点问题就回归到第二种情况的处理容易很多。3.2 删除代码完整实现与两个容易踩的坑我的删除实现长这样template typename T TreeNodeT* findMin(TreeNodeT* root) { while (root ! nullptr root-left ! nullptr) { root root-left; } return root; } template typename T TreeNodeT* deleteNode(TreeNodeT* root, const T target) { if (root nullptr) { return nullptr; } if (target root-val) { root-left deleteNode(root-left, target); } else if (target root-val) { root-right deleteNode(root-right, target); } else { // 找到目标节点 if (root-left nullptr root-right nullptr) { delete root; return nullptr; } if (root-left nullptr) { TreeNodeT* rightChild root-right; delete root; return rightChild; } if (root-right nullptr) { TreeNodeT* leftChild root-left; delete root; return leftChild; } // 两个子节点都存在用右子树最小节点替换 TreeNodeT* minNode findMin(root-right); root-val minNode-val; root-right deleteNode(root-right, minNode-val); } return root; }这段代码我调试过很多次有两点特别想提醒大家。第一个坑是只delete节点不处理指针。如果你在一个节点的父节点结构里直接delete了它但是没有把父节点的left或right置空这个指针就成了野指针。我的代码里是通过返回值来处理的删除后返回nullptr或者子节点地址上一层调用接收并赋值给root-left或root-right这样指针更新就统一收口了。这个模式很优雅但前提是你别漏掉任何一条return分支。第二个坑是用右子树最小节点替换后忘了删除那个被替换的节点或者删除时写成了对整个root调用deleteNode。上面的代码在替换值之后对root-right递归调用deleteNode传入的是minNode-val这样就能精准地把那个节点删除不会误伤其他节点。提示跟踪递归调用时有一个技巧通过打印args和返回值的方式在函数入口和出口各打一行日志马上能看到递归的调用链。我自己调试的时候用这个方法比用眼睛硬盯代码快得多。3.3 用中序遍历自检BST的正确性写完了插入、删除怎么确认代码是对的我习惯写一个自检函数用中序遍历生成序列然后判断序列是否严格递增。template typename T void inOrderTraversal(TreeNodeT* root, std::vectorT result) { if (root nullptr) return; inOrderTraversal(root-left, result); result.push_back(root-val); inOrderTraversal(root-right, result); } template typename T bool isValidBST(TreeNodeT* root) { std::vectorT result; inOrderTraversal(root, result); for (size_t i 1; i result.size(); i) { if (result[i] result[i - 1]) { return false; } } return true; }这个自检函数特别有用。我在写BST的练习中每执行完一组插入和删除就调用这个函数验证一下。如果返回false就说明树被写坏了再结合具体操作步骤从出错的那个节点开始排查。它不能告诉你是哪一步写错了但能告诉你已经出错了在练习阶段配合二分查找定位效率很高。还有个更严苛的验证方法把操作序列和对应的预期结果记下来做模糊验证。比如随机插入n个数再随机删除m个数每步之后都检查三件事——树是否满足BST性质、中序序列是否和实际存的值集合一致、树中节点数量是否等于存的值集合大小。这一套组合拳打下来你的插入删除实现基本可以放心。4. 从不同的二叉搜索树题目理解卡特兰数4.1 题目要求与直觉突破LeetCode上有一道经典题目叫不同的二叉搜索树输入一个整数n要求计算由1到n这n个节点一共能组成多少种不同形态的二叉搜索树。我第一次看到这道题第一反应是用回溯枚举后来发现n做到19的时候结果已经很大枚举到天荒地老都算不完。这题考查的是组合数学里的卡特兰数。先想一个关键问题如果1到n构成BST根节点是i那么左子树由1到i-1构成右子树由i1到n构成。左子树的形态数和右子树的形态数是独立的所以以i为根的BST总数 左子树形态数 × 右子树形态数。注意这里左子树和右子树的节点个数决定了形态数而不是具体数值。因为节点是从1到i-1还是从5到9只要节点个数相同能组成的BST形态数就相同。这个个数决定形态的认知是整个题目推导的突破口。4.2 动态规划推导dp[n] Σ dp[i] × dp[n-1-i]设dp[n]表示n个节点能组成的BST数量。dp[0]等于多少空树也算一种形态所以dp[0] 1这个约定是为了递推方便。dp[1] 1只有一个节点没得选。考虑n个节点根节点选i左子树有i-1个节点右子树有n-i个节点总的形态数是dp[i-1] × dp[n-i]。因为i可以取1到n任意值所以把所有情况加起来dp[n] Σ(i1到n) dp[i-1] × dp[n-i]换种写法令j i-1则dp[n] Σ(j0到n-1) dp[j] × dp[n-1-j]。这就是卡特兰数的递推形式。这个递推式用动态规划很容易实现而且每一步的计算都依赖前面已经算好的值天然适合自底向上。这个递推的核心其实是独立子问题相乘然后枚举求和的套路。以后你遇到类似的树上计数问题比如统计所有可能的二叉树、所有可能的括号组合都可以往这个思路上靠。4.3 C实现与边界处理int numTrees(int n) { std::vectorlong long dp(n 1, 0); dp[0] 1; for (int i 1; i n; i) { for (int j 0; j i; j) { dp[i] dp[j] * dp[i - 1 - j]; } } return static_castint(dp[n]); }两点提醒。第一dp的类型我用了long long。卡特兰数增长很快n19时结果是1767263190已经接近int的极限n20就直接溢出int了。如果你要算更大的n用long long都不够得用大数或者取模。第二内层循环j i还是j i-1就是个数问题。总节点数为i左子树j个右子树i-1-j个j的取值范围是0到i-1所以写j i正好。这道题虽然只是个计数问题但它让我真正理解了BST的递归结构。你甚至可以从这个DP推导过程反推出给定一组有序值我们不光能数出有多少种BST还能通过回溯DP数组把所有具体的树的形态都构造出来。比如要求输出所有形态那就是在计算过程中记录每种根的选择再用递归的方式拼装出树的结构。这就是计数和构造的区别前者只算数量后者要生成所有解。5. 退化风险与递归深度总要面对的薄弱环节5.1 有序插入导致退化成链表前面说过BST的平均复杂度是O(logn)但前提是插入序列足够随机。如果数据本身有序BST会退化。具体来说依次插入1, 2, 3, 4, 5你会得到一条向右延伸的链每个节点只有右孩子没有左孩子。这时候BST就是一个加了包装的链表查找一个节点的时间是O(n)跟数组顺序查找没有区别。这个退化的根因在于普通BST没有维护平衡这个约束。插入和删除只会改变局部路径上的节点不会在全局范围做结构调整。长此以往树高就可能偏离logn。我教你一个简单的观测方法插入一组数据后用中序遍历和层次遍历对比一下树的深度。如果深度远大于logn比如n10深度接近10那你基本可以断定树已经歪了。我实际做过一个实验把0到999按顺序插入BST树高是999但把这1000个数随机打乱再插入树高大概是20多。这个差距直观得吓人。5.2 递归深度逼近系统栈上限怎么办递归实现的BST操作最怕的就是树特别高。系统栈大小一般默认8MB递归调用每次大概占几十到上百字节的栈帧。如果树高是10000递归深度上万次很可能直接爆栈。我在项目里遇到过这个问题。当时维护一棵非常大的BST树高一度到了好几万插入操作递归调用导致程序直接崩溃。后来做了两个改造第一把插入和查找改成了迭代写法消除递归调用第二对树做了一次重构把不平衡的节点重新整理成平衡BST。所以我的建议很直接学习阶段用递归理解原理没问题但要在心里时刻记得递归深度等于树高这个限制。真到了生产环境或者处理大规模数据优先考虑迭代版本或者直接上自带平衡的容器。5.3 从BST到AVL树旋转在解决什么问题BST退化的终极解决方案是平衡树。最经典的是AVL树它要求任何节点的左右子树高度差不超过1。插入、删除之后如果某个节点不满足这个约束就要通过旋转来恢复平衡。旋转操作一共有四种LL、RR、LR、RL。LL就是left-left失衡某个节点的左子树的左子树太高了需要右旋一次来恢复RR就是镜像的情况左旋一次LR则是左子树的右子树太高需要先左旋再右旋RL是右子树的左子树太高需要先右旋再左旋。旋转的本质是什么是把一棵歪的树重新捋直同时保持BST的中序有序性不变。我最初看旋转代码时一头雾水后来在纸上画了好几遍才明白旋转改变了节点的父子关系但不改变中序序列。中序序列的稳定性是BST所有操作必须遵守的底线旋转也是围绕这个底线设计的。红黑树是AVL的一种工程化改良它不追求严格的高度差不超过1而是用颜色约束来保证最长路径不超过最短路径的两倍。C标准库的std::map用的就是红黑树因为它插入删除时需要的旋转次数比AVL少综合性能更好。理解了BST和AVL再看红黑树就不会那么懵因为红黑树本质上就是加了颜色约束的BST配合旋转和变色来平衡。6. 动手实验时的调试心得和VSCode环境建议6.1 我踩过的三个典型bug学BST这段时间我踩过不少坑挑三个印象最深的分享出来。第一个是递归插入时忘了接收返回值。我在insertNode里写了递归调用但没有写root-left insertNode(...)直接写insertNode(root-left, val)编译不报错、运行也没异常但树根本没有变化。查了大半天才发现递归修改的是形参出了函数就没了必须通过返回值把更新后的子树带回来。C是按值传递指针的你想在函数里修改指针本身得传二级指针或者用引用不然就得靠返回值。这个教训让我记住了数据结构的递归更新模式。第二个是删除叶子节点之后野指针。我最初写的删除代码在叶子节点时直接delete root然后返回但父节点的left指针没有被更新还指向已经被释放的内存。后来在树中查找一个不存在的值逻辑没走错但内存越界。这个问题用中序遍历自检函数能很快发现因为野指针会让程序在遍历时崩溃或者产生随机值。解决方法是严格按照删除函数返回新子树根上层调用接住并赋值的模式来写。第三个是相等值节点的处理。如果插入序列里有两个相同的元素BST的性质没有统一标准规定放左边还是放右边。如果你的实现里相等值既可能往左走也可能往右走删除的时候就可能找不到目标节点。我的建议是在设计节点结构时就要明确相等值是忽略、计数还是放某一侧。我倾向于用忽略来保持树中元素唯一如果确实要支持重复元素就给节点加一个count字段而不是在树里复制出两个相同值的节点。6.2 用断言和中序序列做回归验证我自己练习BST时喜欢在代码里加一个自检函数并在每次插入删除之后调用。这个自检函数做三件事检查节点数量是否符合预期、中序遍历序列是否严格递增、树的深度是否不超过一个合理范围。如果这三者都通过基本就可以认为当前操作没把树写坏。比如插入10个随机数删除其中3个我期望的序列是排序后的7个数。自检函数会实际跑一遍中序遍历把结果和预期对比不一致就打印日志。void debugBST(TreeNodeint* root) { std::vectorint seq; inOrderTraversal(root, seq); for (size_t i 1; i seq.size(); i) { assert(seq[i] seq[i - 1]); } std::cout 节点数: seq.size() , 深度: treeDepth(root) std::endl; }在Debug模式下assert会触发Release模式下会被剥离。调试阶段这东西的价值非常大一旦你写完一个函数就能立刻验证正确性不用等到整个程序都写完才发现问题藏在哪个角落。6.3 VSCode调试C的几个关键配置很多人学C数据结构卡在环境配置上我在VSCode里配置C环境走了不少弯路把最关键的两点拎出来说下。tasks.json负责编译核心是告诉编译器你要编译哪个文件、输出到哪里、用什么标准。我建议把C标准至少设成C17这样可以用很多现代特性。编译命令类似{ type: cppbuild, command: g, args: [ -fdiagnostics-coloralways, -g, -stdc17, ${file}, -o, ${fileDirname}/${fileBasenameNoExtension}.exe ] }-g参数特别重要它生成调试信息没有这一项断点基本是摆设。-stdc17避免一些老标准下的坑。launch.json负责调试关键配置是program要指向你编译出来的exe文件路径和tasks.json的输出路径保持一致。配置好之后就可以在VSCode里打断点了。我写BST时常用的调试方式是在insertNode的递归调用前后各打一个断点配合Watch窗口观察root-val、root-left和root-right的值。因为树的指针结构非常复杂你光靠print不一定能看出问题所在但单步执行加Watch就能看到一个节点的左右子树是不是按预期更新。还有一个排查递归问题的小技巧在Watch窗口里添加root的地址和对应的val再添加递归返回值的临时变量。这样你能看到每一层递归返回后父节点的结构变化很多人写递归调用的bug就是这么一步步盯出来的。如果你用的是Windows记得安装MinGW-w64或者Visual Studio的C工具链之后在VSCode里指定编译器路径。Linux/macOS用户直接用系统自带的g或者clang就行tasks.json里的command改成g或clang就好。环境本身不复杂但网上很多教程配的版本比较老导致编译老报错。核心就一句话tasks.json管编译launch.json管调试两者配合好你的C学习之旅会顺畅很多。BST这份笔记写到这里我最有感触的还不是这些代码本身而是学习数据结构的方法。别光盯着别人的代码看一定要自己动手写写完用中序序列去验证用随机插入和删除去折腾它用有序插入去观察退化。你对树结构的理解就是在这一次次写坏、定位、修复的过程中建立起来的。后面再去看红黑树、B树你会发现自己已经能很快抓住它们的核心思路了。