资讯中心

从热更新卡顿到毫秒级响应:一文讲透二分搜索树(BST)原理与应用

📅 2026/10/14 5:43:15
从热更新卡顿到毫秒级响应:一文讲透二分搜索树(BST)原理与应用
聊二分搜索树Binary Search TreeBST这个数据结构得从一次真实的调试经历说起。大概一年多前我帮某团队优化一个配置存储模块他们用的方案是把配置项放进一个有序数组每次插入都做一次二分查找定位然后memmove挪数据。配置项少的时候没什么感觉等数量涨到几万条一次热更新直接把服务卡了快两秒。当时我就问了一句为什么不用二分搜索树那个开发者的回答很有意思知道这个名字但一直觉得数据结构是面试题工作里用不上。我就给他写了个三十行的BST插入逻辑替换之后热更新耗时从秒级降到了毫秒级。这让我特别想好好聊一聊这个看起来简单、用起来真香的数据结构。无论你是刚学编程的学生还是写业务代码的工程师这篇文章都值得你花十分钟读完因为二分搜索树是理解后面所有树形结构平衡树、B树、红黑树的基石掌握了它相当于给算法内功打了一层扎实的地基。1. 二分搜索树到底是什么一个类比讲清楚先抛开教科书定义用一个生活场景帮助理解。想象你管理一间图书馆书架上的书需要满足一个铁律书架正中间摆一本基准书左边所有书的编号都比基准书小右边所有书的编号都比基准书大。然后左边这个分区里再找一本次基准书它左边的编号更小、右边的编号更大右边分区同理递归下去。这样一个书架上的书就天然按照编号排好了序而且从顶层书架往下找某本书的过程每一步都能砍掉将近一半的搜索范围。这个图书馆就是二分搜索树。计算机里的定义是这样的二分搜索树是一棵二叉树其中每个节点的值大于其左子树中所有节点的值并且小于其右子树中所有节点的值。注意这里的大于小于是严格定义的一般要求树中不存放重复值或者统一放在一侧。性质上它有这么几个特点中序遍历左子树、根节点、右子树的结果是一个严格递增的序列。这条性质是BST能用来排序的核心。理想情况下查找、插入、删除操作的时间复杂度都是 O(log n)。这个复杂度是建立在树高约等于log n且左右子树相对平衡的前提下。最坏情况下如果按有序序列逐个插入树会退化成一条直链此时复杂度退化为 O(n)退回到了线性表级别。这个数据结构同时解决了两件事一是保持了数据的有序性所以做范围查询很方便二是利用二分思想把检索代价压低到对数级别。数组能做到随机访问但插入删除代价高链表能做到动态插入但查找要遍历BST相当于在两者之间找了一个平衡点。我遇到过不少人一开始会把二分搜索树和二分查找算法混为一谈。区别很简单二分查找是一个算法作用在有序数组上二分搜索树是一个数据结构它自己维护着有序性不需要在插入时移动大量元素。说白了BST就是让动态数据的二分查找成为了可能。2. 为什么说BST是动态有序数据的基础设施2.1 数组和链表的痛点要理解BST的价值最好先感受一下另外两种基础数据结构在动态场景下的无力感。有序数组的查找很痛快O(log n) 的二分查找是谁用谁知道。但一旦涉及插入代价就原形毕露为了保持数组有序我得把插入位置之后的所有元素全部往后挪一格这个操作平均要移动 n/2 个元素时间复杂度 O(n)。删除同理。当数据量大、操作频繁的时候这个代价极其致命。上面的热更新场景就是这么踩坑的。链表呢链表插入和删除确实方便只要修改指针就行O(1)。但查找就尴尬了想在链表中找到一个特定值只能从头部开始逐个遍历最坏情况下要访问 n 个节点O(n)。链表可以有序但有序链表本身并不能支持高效的二分搜索——因为你没法随机跳到中间节点。BST的思路是重构数据的组织形态不是把数据排在一个线性序列里而是根据值的大小关系把数据安排在不同层级让每个节点天然拥有去左边找和去右边找的能力。结果就是插入和查找都只需要沿着树的高度走一次在平衡状态下就是O(log n)。2.2 为什么O(log n)那么重要我经常跟朋友讲O(log n) 和 O(n) 的差距不是快一点和慢一点的区别而是能用和不能用的区别。以一次插入操作为例假设数据集规模 n 100 万。O(n) 的数组插入平均要移动 50 万个元素O(log n) 的BST插入只需要访问约20个节点就是沿着树从根一路往下找到合适位置再挂上去。单次操作看起来无所谓但当操作次数是十万次、百万次的时候差距就是指数级的。服务器承受不住的那些卡顿往往就是这里一点点累积起来的。说实话日常业务开发里数据规模几千条的时候你用数组还是BST可能没区别甚至数组因为缓存友好反而更快。但数据上了量或者操作频率上了量BST这类结构的价值就完全体现出来了。这也是为什么几乎所有标准库——比如某些语言里的TreeMap、TreeSet——底层都用了自平衡的二叉搜索树通常是红黑树。3. 核心操作逐一拆解插入、查找、删除3.1 插入操作递归写法为什么最直观BST插入的思想一句话就能说清从根节点出发如果待插入值比当前节点小就往左走比当前节点大就往右走找到空位NULL就挂上新节点。递归的写法最贴合这个逻辑这里以C风格的伪代码来表示struct Node { int val; Node* left; Node* right; explicit Node(int v) : val(v), left(nullptr), right(nullptr) {} }; Node* insert(Node* root, int value) { if (root nullptr) { return new Node(value); } if (value root-val) { root-left insert(root-left, value); } else if (value root-val) { root-right insert(root-right, value); } // 如果 value root-val根据实现约定可以忽略不插入重复值 return root; }我把这段代码贴出来想重点说明两个容易被忽略的细节。第一个细节为什么递归返回值要赋给root-left因为insert函数最终返回的是以传入节点为根的那棵子树在插入完成后的新根。如果子树为空新节点就是新根如果子树不为空根不变。所以root-left insert(...)这个赋值操作本质上是在维护父节点与子树的连接关系。新手最容易犯的错误就是只调用insert(root-left, value)而不接收返回值结果新节点插进去了但父节点指针没更新树还是断的。第二个细节递归到底深入到哪一层结束当走到一个空节点时插入操作就完成了此时新节点被创建并通过逐层返回被挂到了正确的位置上。这就是递归写法的自然之处你不需要手动维护父节点指针对栈递归的调用栈本身就充当了回溯路径。当然递归在树退化成链表比如按有序序列插入时会有爆栈风险。这个实际工作中很常见后面我会在避坑部分专门讲。如果数据规模大且无序程度低更稳妥的做法是使用迭代版本——循环比较值的大小同时用一个parent指针记录当前节点的父节点直到走到空位然后判断挂到左边还是右边。迭代版不存在递归深度问题是生产环境更推荐的方式。3.2 查找操作三种变体都很实用BST的查找逻辑和插入同构也很适合用循环来写Node* search(Node* root, int key) { while (root ! nullptr root-val ! key) { if (key root-val) { root root-left; } else { root root-right; } } return root; }查找操作不改动树结构所以不涉及指针更新比插入简单不少。但查找在实际工程里有三种变体值得分开捋一捋查找特定值上面这个找不到就返回nullptr。用来判断一个元素是否存在。查找最小值从根一路往左走到黑最左边的节点就是整个树的最小值。为什么因为BST定义里任意节点的左子树所有值都小于它本身那么最左下角一定是全局最小。查找最大值对称一路往右走到黑。我特别喜欢找最小/最大值这个操作因为它在很多场景里都会用到最典型的就是删除节点时需要的后继节点后面删除部分细讲。另外如果是查找前驱、后继比某值小的最大节点、比某值大的最小节点也可以通过从根往下搜索的方式实现带着一个候选答案往下走每次走左子树时更新后继走右子树时更新前驱。这个技巧在很多进阶算法题里很常见但基础版本的BST讲解里往往不讲。补充一个工程中很实用的能力区间查询。给定 [L, R]怎么快速返回所有落在区间内的节点function rangeQuery(node, L, R): if node is null: return if node.val L: rangeQuery(node.left, L, R) if L node.val R: print(node.val) if node.val R: rangeQuery(node.right, L, R)它的巧妙之处在于利用BST的有序性进行剪枝只有节点值大于左边界时才需要往左找只有小于右边界时才需要往右找。这样不会遍历整棵树效率远高于拿到全量数据再过滤。数据库索引在实现范围扫描时也是类似思路。3.3 删除操作最容易写错的环节删除是BST里最考验细节的操作。根据目标节点的孩子情况可以分成三个caseCase 1叶子节点没有左孩子也没有右孩子直接删掉就好把父节点对它的指针设为空。Case 2只有一个孩子让它唯一的孩子顶替它的位置。比如要删除的节点只有右孩子就用右孩子替换它只有左孩子就用左孩子替换它。这个操作本质上是绕过要删除的节点让父亲直接连接孙子。Case 3有两个孩子这个case是难点。如果一个节点既有左孩子又有右孩子直接删除自己后谁来接手这个位置接手者必须同时满足两个条件比它左子树所有节点都大比它右子树所有节点都小。两个候选很自然地跳出来一是它左子树中的最大节点也就是左子树最右边的节点二是它右子树中的最小节点也就是右子树最左边的节点。选哪个都行工程上普遍选右子树的最小节点我习惯叫它后继节点。操作流程是这样的在右子树中找到最小节点一路向左。把这个最小节点的值拷贝到当前要删除的节点上。然后递归去右子树中删除那个最小节点。第二步值拷贝 第三步递归删除这两个步骤分开的意义在于第三步删的一定是满足只有一个孩子或没有孩子的节点因为右子树最小节点必然没有左孩子它已经是最左的了所以它最多只有一个右孩子直接按Case 1或Case 2处理即可。用伪代码表达Node* remove(Node* root, int key) { if (root nullptr) return nullptr; if (key root-val) { root-left remove(root-left, key); } else if (key root-val) { root-right remove(root-right, key); } else { // 找到要删的节点了 if (root-left nullptr) { Node* rightChild root-right; delete root; return rightChild; } if (root-right nullptr) { Node* leftChild root-left; delete root; return leftChild; } // 两个孩子的case Node* successor findMin(root-right); root-val successor-val; root-right remove(root-right, successor-val); } return root; }我教学的时候最喜欢让学员在这个函数上多走几遍因为这里的细节密度很高。几个容易踩的坑findMin(root-right)不能写成findMin(root)那样找出来的是整棵树的最小值不一定是右子树的最小值。值拷贝之后要删的是后继节点的那棵子树里最小值的节点而不是根。用remove(root-right, successor-val)会形成一个递归调用但这次递归进去后会直接命中找到要删的节点然后走Case 1或Case 2。如果删除时不注意返回值赋回给父节点的指针树会断。这和插入一样大量bug的根源都在这里。一个更工程化的trick是如果有大量删除操作可以考虑使用惰性删除给每个节点打一个deleted标记逻辑上删除但物理上保留。这样避免频繁调整树结构摊还下来有时候更划算。Java的TreeMap删除不是惰性的但某些带有TTL的缓存实现会这么干因为缓存场景里删除频率实在太高了每次都动树结构太亏。4. 遍历的四种姿势以及它们各自解决什么问题BST的遍历方式分为深度优先DFS和广度优先BFS两大派系。深度优先又可以根据根节点的访问时机拆成前序、中序、后序三种。理解这四种遍历的意义不能光背口诀得知道每种遍历到底产出了什么实际有什么用。4.1 中序遍历有序序列的生产线中序遍历的顺序是左子树 → 根节点 → 右子树。因为BST的性质保证左子树所有值都小于根、右子树所有值都大于根所以中序遍历天然产出一个升序序列。这是BST五大遍历组合里最美妙的一条性质也是最常被考到的一条。void inorder(Node* root) { if (root nullptr) return; inorder(root-left); std::cout root-val ; inorder(root-right); }利用中序遍历可以做的事情包括把BST转成有序数组、判断一棵二叉树是不是合法的BST只要看中序遍历结果是否严格递增、以及原地把BST转成双向链表等。日常工程里如果你需要从一个BST里输出所有键值对的排序结果直接中序遍历就是最稳的答案。测试的时候我们也经常用中序遍历来检查一棵树的合法性如果中序遍历不是严格递增的那这棵树一定违反了BST定义。4.2 前序与后序遍历序列化和重建的关键前序的顺序是根 → 左 → 右后序是左 → 右 → 根。它们在实际工程中最重要的用途就是树的序列化与反序列化。什么叫序列化把一棵树变成一段字符串或者字节流方便存储和传输之后还能重建出完全一样的树。由于树的结构信息父子关系、兄弟关系在序列化文本里如果没有特殊标记是容易丢失的所以通常需要配合空节点的占位符或者直接利用前序/后序 中序的组合来重建。一个常用的序列化方案是用前序遍历输出所有节点值空节点用特殊符号比如#代替。然后反序列化时按前序顺序重建节点。另一种我不止一次在面试和工作中用到的方案是给定前序序列 中序序列重建整棵二叉树。因为前序序列的第一个元素一定是根节点在中序序列中找到这个根的位置就能划分左右子树递归重建下去。后序遍历的一个典型应用是计算子树信息——因为后序顺序是先处理完左右子树再处理当前节点天然适合做自底向上的统计。比如计算树的高度、判断平衡二叉树AVL、计算整棵树的和等。4.3 层序遍历不需要递归的BFS层序遍历就是按层级从上到下、从左到右扫描树也就是广度优先搜索在树结构上的应用。它不像前中后序那样自然联想到递归而是要用队列来模拟逐层推进。void levelOrder(Node* root) { if (root nullptr) return; std::queueNode* q; q.push(root); while (!q.empty()) { Node* cur q.front(); q.pop(); std::cout cur-val ; if (cur-left) q.push(cur-left); if (cur-right) q.push(cur-right); } }这里有个非常经典的进阶需求按层输出每层一行。实现方式是在while循环里多加一层嵌套先获取当前队列的长度表示这一层有多少节点然后一次性处理完这一层再进入下一层while (!q.empty()) { int levelSize q.size(); for (int i 0; i levelSize; i) { Node* cur q.front(); q.pop(); std::cout cur-val ; if (cur-left) q.push(cur-left); if (cur-right) q.push(cur-right); } std::cout \n; }我实测下来层序遍历在实际工作中很容易和深搜混淆边界但它们的适用场景差别很大层序适合最短路径、最小深度、同层关系分析深搜适合路径累加、子树归并、结构变形。选遍历方式不是看喜欢递归还是循环而是看你需要的信息依赖顺序。5. 复杂度分析BST的天气系统刚开始学复杂度分析的时候我跟许多人一样只背结论BST查找O(log n)、插入O(log n)、删除O(log n)。等实际写了几百行BST代码测试了几万条数据之后我发现这个结论最多只回答了一半问题。另一半是关于平衡的约束条件——BST的性能表现完全取决于树长得是否匀称。一棵满二叉树如果每个内部节点都有两个孩子树高大约是 log2(n)。在这种理想形态下查找一个值就像在电话簿里猜页码每猜一次砍掉一半可能性最多猜log n次。但BST有个与生俱来的天气系统问题如果数据插入的顺序不好比如先插1、2、3、4、5……一路递增那么每个新节点都会插到前一个节点的右孩子位置树就退化成一条单链表。这种情况下查找的时间复杂度直接从O(log n)坍缩到O(n)。碰上这种现象你从根开始找一个尾部节点要一路遍历完整个树这完全可以先用暴力遍历BST的优势瞬间蒸发。所以真实的工程考量是这样的如果你并不控制输入数据的顺序比如用户随意往里塞数据普通BST可能有退化风险这时应该考虑自平衡树比如AVL树或红黑树。如果你掌控了插入顺序比如只从文件按序加载一次可以衍生出一种优化把数据预先打乱再建树或者直接把有序数组转化为中序遍历式的平衡BST就能规避退化。那么怎么把一个有序数组构建成尽量平衡的BST方法很简单每次取中间元素作为根左侧区间递归构造左子树右侧区间递归构造右子树。这样左右子树的大小差最多不超过1树高被压到最小值。这个操作在数据仓库预建索引时是很常见的。还有一点容易混淆BST的O(log n)是平均情况不是最坏情况保证。真正最坏也能O(log n)的是平衡树AVL、红黑树等。普通BST是平均很好、最坏完蛋红黑树是牺牲一点平均换来最稳定的上限。日常用库里的TreeMap/TreeSet为什么用红黑树而不是AVL就是因为红黑树的插入删除重平衡代价比AVL小虽然它不如AVL严格平衡但工程综合效率更高。6. 从BST到工程应用二分搜索树到底用在哪6.1 数据库索引B树和B树的引路人很多第一次学BST的同学都会有这个疑问学了BST到底能干什么直接回答这个问题最常见的答案是数据库索引就是B树B树是BST的亲戚——它是一种多叉平衡搜索树。数据库里最常见的操作是等值查询和范围查询。BST的中序遍历有序性天然支持范围查询BST的O(log n)查询时间天然满足索引的核心需求。但为什么数据库不直接用BST呢因为BST是二叉树每个节点最多两个孩子当数据量以亿计时树的高度只是log2(n)大约30层左右。这个层数看起来不多但考虑到机械硬盘随机访问慢得令人发指30次寻道也够呛。B树的结构让每个节点能存储多个键值和多个孩子指针于是同样的数据量树高通常只有3~4层磁盘IO次数大幅减少。引擎层面无论是InnoDB聚簇索引还是非聚簇索引B树的设计都借鉴了BST的有序 分层 二分查找核心思想。可以理解为BST是内核B树是外包装包装的目的是适配磁盘存储。6.2 语言标准库与排序场景几个主流语言的标准库里都有BST的重要身影Java的TreeMap和TreeSet底层是红黑树。C STL的std::map和std::set底层通常也是红黑树。各种语言的SortedDict/SortedSet实现核心思想往往都是某种平衡搜索树。这类容器最方便的是按键有序遍历、定位前驱后继ceilingEntry/floorEntry、范围操作。比如一个实时订单系统里需要按价格排序并快速查询当前价格区间的订单量TreeMap几乎是随手就能写出来的方案。我第一次在实际项目中用TreeMap就是做限价订单簿的价格聚合那个效果如果用普通哈希表完全做不到有序遍历用数组又扛不住频繁增删。还有一类应用是在线排序数据不是一个批量的数组一次性给你而是像流一样逐个到达。需要每来一个数据就能立刻知道它排第几。BST天然支持这种动态排名节点里额外存一个子树大小字段就能稳定实现这可比全量重排舒服太多。6.3 各种算法题的出题基地不用避讳这一点二分搜索树也是算法面试的重灾区。面试官喜欢用BST来考察对递归的理解、对树结构的理解以及代码细节的把控能力。常见的变体包括验证一棵树是不是合法的BST中序遍历有序或者递归传上下界求BST中第K小的元素中序遍历 计数或者扩展节点记录子树大小给定前序/后序遍历重建BSTBST中两节点的最近公共祖先利用节点值比较大小可以聪明地减少搜索路径把BST调整为累加树把每个节点改成大于等于自己的所有节点值之和判断BST的平衡性左子树高度和右子树高度差不超过1我比较建议的是学BST时不要直接刷题先在一张纸上手画一棵树手动走一遍插入、删除的完整流程再打开IDEA敲代码。只有亲手把删除有两个孩子的节点那步走顺了后面理解红黑树、AVL的重平衡逻辑才会觉得顺理成章。7. 避坑清单我踩过的坑希望你别再踩一遍7.1 递归爆栈问题这是我在生产环境吃过亏的地方。当时要在一棵已经退化成链的BST上反复插入新节点递归版insert直接压爆了调用栈服务进程崩溃。事后排查才发现那批数据是从数据库按主键顺序拉出来的天然有序BST建出来就是一条线。解决方案有两个方向把递归改成循环迭代。迭代版不占用调用栈插入深度再大也不怕但代码读起来比递归稍绕。在数据加载阶段使用分治法建树把有序数组取中位数作根递归构建左右子树直接建成平衡BST然后后续维护时再用普通BST插入逻辑。如果都不想做那干脆用平衡树或者直接用跳表替代不要硬扛。7.2 删除时的指针更新我见过大量初学者以及部分工作两年的朋友在删除节点时只改了新节点的值没有把父节点指向该节点的指针更新成新节点导致整棵树的联接关系断裂。这个问题的核心在于删除的本质不是把那个格子清空而是把父节点与这个位置的连接关系重新指向合适的新节点。在递归写法里答案就在那行root-left remove(root-left, key)和root-right remove(root-right, key)。必须把返回值赋回去不然你删除的子树无法把自己的新根告诉上层。迭代写法里需要额外维护一个parent指针删除时专门比较是parent-left还是parent-right等于目标节点再改对应指针。7.3 重复值的处理策略要提前定BST定义本身要求值不重复但实际上业务数据经常会遇到重复。处理策略需要提前定死否则后续查找和删除都会出现歧义。三种常见方案忽略重复值后插入的不进树。适合存在性判断场景。允许重复值统一插到右子树或者统一插到左子树。逻辑简单但查找时必须持续向右/向左搜到空为止不能再找到相等就返回。每个节点额外保存一个计数count重复时count1删除时count-1count降到0才真正移除节点。这个方案在词频统计类场景里很常用。我个人最推荐第三种因为它对树的平衡性基本无破坏查找和删除都能保持清晰语义。7.4 前驱和后继选择不一致的问题删除有两个孩子的节点时可以用左子树最大值前驱也可以用右子树最小值后继。选谁都行但不要在同一个删除函数里写两个逻辑分支随机切换那会把问题搞复杂。固定用后继右子树最小就够了原因很简单右子树最小节点必然没有左孩子递归删除它时必定走最简单的分支好写也好看。7.5 调试时善用中序遍历和中序遍历序列对比BST的调试相比链表要难一些因为树上的结构是一大片。我在项目里调试BST类的第一个动作永远是打一遍中序遍历。如果中序遍历得到的结果不是有序递增那树一定出bug了。如果是再结合断点输出父节点和子树根的关系去精确定位。这个技巧几乎是免费的只需要写一个几行的递归函数但能省下大量盯着指针发呆的时间。8. 实操案例从零手写一个支持前驱后继的BST理论说了那么多最后给一个可以直接抄的完整实现思路采用C风格包含插入、删除、查找、前驱、后继、中序遍历。为了简洁我把节点定义和公共接口封装在一个类里。#include iostream #include queue #include vector struct Node { int val; Node* left; Node* right; explicit Node(int v) : val(v), left(nullptr), right(nullptr) {} }; Node* insert(Node* root, int value) { if (!root) return new Node(value); if (value root-val) root-left insert(root-left, value); else if (value root-val) root-right insert(root-right, value); return root; } Node* findMin(Node* root) { while (root root-left) root root-left; return root; } Node* findMax(Node* root) { while (root root-right) root root-right; return root; } Node* remove(Node* root, int key) { if (!root) return nullptr; if (key root-val) { root-left remove(root-left, key); } else if (key root-val) { root-right remove(root-right, key); } else { if (!root-left) { Node* rightChild root-right; delete root; return rightChild; } if (!root-right) { Node* leftChild root-left; delete root; return leftChild; } Node* successor findMin(root-right); root-val successor-val; root-right remove(root-right, successor-val); } return root; }前驱和后继的查找迭代版可以这样实现Node* findSuccessor(Node* root, Node* target) { Node* successor nullptr; while (root) { if (target-val root-val) { successor root; root root-left; } else { root root-right; } } return successor; }这段代码的核心思路是把可能的后继候选记下来每次走左子树时更新candidate走右子树时不更新最后返回的就是大于target的最小值。前驱则是镜像逻辑每次走右子树时更新predecessor走左子树时不更新。中序遍历的代码前面已经给了就那三行。层序遍历给过队列实现。把这些拼在一起一个最精简的功能完整的BST就完成了。9. 实战心得与扩展建议最后再分享一点我个人的体会。我其实在BST上吃过一次不小的亏——之前在一家数据平台公司做配置中心我用普通BST存了几十万条带有时间戳的配置记录想着查找快、插入快、还能范围查询结果没想到数据插入顺序是接近递增的树退化成链表线上有一段时间响应特别慢排查了半天才发现是树高退化导致的。后来我把加载逻辑改成先取中间时间戳作根两边递归建树退树问题立刻消失效果立竿见影。从那以后我养成了一个习惯任何用到BST的地方我都会顺便问自己三个问题——插入数据的顺序是什么会不会接近有序最坏情况下树高会不会退化到n如果有一个答案是会我就要么加一层平衡逻辑用AVL或者跳表要么在建树阶段做一次优化。这三个问题我建议所有做工程开发的你也在使用BST前先问一遍自己。如果你已经熟练掌握了普通BST下一步的扩展方向其实很清晰先去看AVL树严格平衡旋转操作再看红黑树应用最广结构最精巧接着摸一摸B树/B树数据库索引基石。有第一条路线打底后面每走一步都会顺很多。甚至有时间的话可以自己动手给节点加一个子树高度字段实现一个简易AVL插入再做一次按中序遍历输出所有节点的校验。这个过程会比你想象的有趣得多。

看完文章,想为自己的企业也做一次专业网站诊断?

尧图顾问免费为您评估现有网站,并给出建站/改版建议与报价方案。

免费获取方案