Lua二叉搜索树：左小右大的有序插入

【语法算法】

线上事故引入：早上线上出了个事故——排行榜查找接口在数据过万之后明显卡顿，排查发现查找逻辑是数组从头扫到尾，数据越多扫得越久。二叉搜索树的思路是不扫——左子全小于父节点、右子全大于父节点，每比一次就砍掉一半候选。这篇把二叉搜索树整套写法拆开：节点结构、递归插入、最小值删除、调试按钮，一段一段照抄能跑。

一、效果演示

演示场一棵实时生长的二叉树。点「插入随机数」：一个随机数从根节点出发——比当前节点小走左边、大走右边，一路走到空位落地成新叶，插入路径逐帧高亮。点「删除最小值」：最左侧的节点被摘掉，连线实时重画。点「清空」推倒重来，节点数实时显示在顶部。

flowchart TD
A[新数到来] --> B{树为空}
B -- 是 --> C[成为根节点]
B -- 否 --> D{比当前节点小}
D -- 是 --> E[走左子树]
D -- 否 --> F[走右子树]
E --> G{子节点为空}
F --> G
G -- 是 --> H[落地成新叶]
G -- 否 --> D

 fx-bst

二、底层原理

二叉搜索树的机关是一句不变式——任何节点左子树的所有值都小于它、右子树的所有值都大于它。插入就是把这句不变式走一遍：和当前节点比大小，小往左大往右，走到空位落地。查找同理，每次比较排除一半候选，一千个节点最多十次就能锁定目标。删除分三种情况：叶子直接摘、单子节点由孩子顶上、双子节点用右子树最小值补位再原路摘除。这套结构对有序数据天然友好——中序遍历一次就得到升序序列，排序是免费的赠品。
代价是不变式要靠插入次序维护——有序数据依次插入会把树打成一条链，查找退化成线性扫。工程上的补救是打乱插入次序，或者直接上自平衡树。演示里用随机数插入，就是为了避开退化路径。

这套机制的代码量不到一百行，难的不是写而是把不变式记牢——每一处改动都不许破坏左小右大，破坏一次整棵树就废了。

再看删除的细节——摘最小值只需要一路向左走到头，因为最小值必然待在最左端；摘掉之后右孩子原地顶上，整棵树的不变式毫发无伤。递归写法的好处是回溯免费——每一层递归返回时顺手把子指针接牢，调用方完全不用管内部怎么接。演示里的树形绘制按深度分层、按中序位置排横，树长歪一点画布也装得下。

三、核心代码：完整模块（上·骨架）

-- @file BST.lua
-- 二叉搜索树 —— 插入删除查找

local BST = {}

local _root = nil
local _count = 0

local function ShowTip(msg)
    if msg and msg ~= "" then SL:ShowSystemTips(msg) end
end

function BST.Insert(v)
    _root = BST._insert(_root, v)
    _count = _count + 1
end

function BST._insert(node, v)
    if not node then return { v = v, l = nil, r = nil } end
    if v < node.v then
        node.l = BST._insert(node.l, v)
    else
        node.r = BST._insert(node.r, v)
    end
    return node
end

function BST.Count() return _count end

四、核心代码：完整模块（下·推进与卸载）

-- 删除最小值：一路向左走到头
function BST.DeleteMin()
    if not _root then return nil end
    local node = _root
    while node.l do node = node.l end
    local v = node.v
    _root = BST._delMin(_root)
    _count = _count - 1
    return v
end

function BST._delMin(node)
    if not node.l then return node.r end
    node.l = BST._delMin(node.l)
    return node
end

SL:ScheduleOnce(function()
    SL:BindDebugButton("插入随机", function()
        BST.Insert(math.random(1, 99))
    end)
    SL:BindDebugButton("删最小", function()
        BST.DeleteMin()
    end)
    ShowTip("技能已加载: 二叉搜索树")
end, 1.0)

function BST.Unload()
    _root = nil
    _count = 0
end

return BST

五、机制问答

问：插入次序对树形影响大吗？
答：很大——有序插入退化成一条链，随机插入才接近平衡，平衡时查找只要对数次比较。

问：删除带两个子树的节点怎么处理？
答：拿右子树的最小值补位——它比右子树其余都小、比左子树都大，补位之后不变式依然成立。

问：中序遍历输出什么？
答：升序序列——左根右的次序天然有序，排序不用额外花钱。

问：相同大小的值往哪边放？
答：约定一边即可——比如相等一律走右子树，全模块保持同一规则就不会乱。

问：和哈希表怎么选？
答：要有序遍历、范围查询选树；只要单点查得快选哈希——两者服务的问法不同。

六、调参与实战怎么用

参数层面值得调的只有一个量——插入数据的分布。分布越随机树形越匀称，查找越接近对数次；分布越有序退化越狠。实战里这类结构适合排行榜区间查询、背包按品质分段、技能按等级归档——一切"按大小找一段"的问法都是它的主场。常见坑两个：递归忘了写终止条件直接栈溢出；删除双子节点时补位之后忘了原路摘除第二次。

补充一个设计层面的思考——这类机制的核心难点不在于代码怎么写，而在于"什么时候触发、触发后做什么、做完了怎么收场"这三个问题的答案。答案清楚了，代码只是把答案翻译成脚本的过程；答案含糊，写出来的东西改来改去都在原地打转。动手前先把这三个问题各用一句话答出来，答不出的那个就是设计缺口，先补设计再动手。

补充一个维护层面的思考——所有的状态变量都收在模块的闭包里，不摆到全局表。全局表的变量在热重载时会残留旧值，闭包的变量每次加载都是新的，这层隔离是热重载环境里防事故的第一道墙。卸载入口要把定时器、连接、标记一揽子清干净，清不干净的下场就是旧事故原样重演。这篇的模块照抄能跑，改的就是参数表。

补充一个工程层面的思考——模块的可测试性和耦合度成反比。耦合越低越能单独验证，越高越要整套环境才能跑起来。降耦合的通用手法是依赖注入：框架接口通过参数传进来，而不是在模块里直接调死，验证的时候传一组假接口就能脱离框架独立运行。平时多花一分钟做注入，排查的时候省下的是一整晚。

写完留一句给做查找系的同学：左小右大四个字就是整棵树——不变式守住了，千军万马十步必中。