基于.NET的MIDI库：如何高效查找指定时间点的音符（优于O(n)）

核心思路 #

你已经用红黑树按开始时间排序音符，这是很好的基础。要实现优于O(n)的查询，关键是同时利用开始时间和结束时间的有序性，通过剪枝避免遍历所有音符。

具体实现方案 #

1. 基于红黑树的剪枝优化 #

既然已经按开始时间排序，你可以快速定位到所有开始时间 ≤ 查询时间t的音符（红黑树的UpperBound类操作，O(logN)复杂度）。但这些音符里只有结束时间 ≥ t的才符合要求，通过给红黑树节点增加额外信息就能高效筛选：

• 给每个红黑树节点维护一个子树内所有音符的结束时间最大值。
• 查询步骤：
  1. 从根节点开始遍历，若左子树的最大结束时间 < t，直接跳过左子树（里面不可能有符合条件的音符）；否则递归遍历左子树。
  2. 检查当前节点的音符是否包含t（开始≤t且结束≥t），符合则加入结果。
  3. 若当前节点的开始时间 ≤ t，再递归遍历右子树（右子树的开始时间都≥当前节点，仍可能有符合条件的）。

这种方法实际查询复杂度是O(logN + k)，k是符合条件的音符数量，远优于O(n)。

2. 区间树实现 #

如果这类查询是高频场景，直接实现区间树是更专业的选择——它就是专门用来高效查询包含某个点的所有区间的数据结构：

• 按区间的开始时间构建平衡二叉树（比如红黑树结构），每个节点存储区间，同时维护子树内所有区间的结束时间最大值。
• 查询时从根节点出发：
  • 当前区间包含t则加入结果。
  • 左子树的最大结束时间≥t时，递归查左子树。
  • 当前节点的开始时间≤t时，递归查右子树。

区间树的查询复杂度稳定在O(logN + k)，完全满足性能需求。在.NET中，你可以基于平衡二叉树的逻辑自己封装，不用依赖第三方库。

3. 离线预处理（适用于查询时间点固定的场景） #

如果你的查询时间点是提前确定的，可以用扫描线算法做离线优化：

• 把所有音符的开始、结束事件，加上所有查询时间点放在一起排序。
• 从左到右遍历，维护一个当前活跃的音符集合（开始≤当前时间且结束≥当前时间）。
• 遇到查询时间点时，直接记录当前活跃集合即可。

这种方法预处理复杂度O(N logN + Q logQ)，查询时直接取结果，适合查询量极大且时间点固定的场景。

代码思路示例（红黑树剪枝查询） #

假设你用自定义红黑树节点维护子树最大结束时间：

public class Note
{
    public long StartTime { get; set; }
    public long EndTime { get; set; }
    // 其他MIDI属性
}

// 自定义带剪枝信息的红黑树
public class NoteIntervalTree
{
    private class Node
    {
        public Note Value { get; }
        public Node Left { get; set; }
        public Node Right { get; set; }
        public long MaxEndTime { get; set; } // 子树内最大结束时间

        public Node(Note note)
        {
            Value = note;
            MaxEndTime = note.EndTime;
        }
    }

    private Node _root;

    // 插入节点时同步更新路径上的MaxEndTime
    public void Insert(Note note)
    {
        _root = Insert(_root, note);
    }

    private Node Insert(Node node, Note note)
    {
        if (node == null) return new Node(note);
        
        if (note.StartTime < node.Value.StartTime)
            node.Left = Insert(node.Left, note);
        else
            node.Right = Insert(node.Right, note);
        
        // 更新当前节点的MaxEndTime
        node.MaxEndTime = Math.Max(node.Value.EndTime, 
            Math.Max(node.Left?.MaxEndTime ?? long.MinValue, 
                     node.Right?.MaxEndTime ?? long.MinValue));
        return node;
    }

    // 查询包含t的所有音符
    public List<Note> FindNotesAt(long t)
    {
        var result = new List<Note>();
        Traverse(_root, t, result);
        return result;
    }

    private void Traverse(Node node, long t, List<Note> result)
    {
        if (node == null) return;

        // 左子树可能有符合条件的，才遍历
        if (node.Left != null && node.Left.MaxEndTime >= t)
            Traverse(node.Left, t, result);

        // 当前音符是否包含t
        if (node.Value.StartTime <= t && node.Value.EndTime >= t)
            result.Add(node.Value);

        // 右子树的开始时间<=t，才可能有符合条件的
        if (node.Value.StartTime <= t)
            Traverse(node.Right, t, result);
    }
}

关键注意事项 #

• 插入、删除音符时必须同步更新路径上节点的MaxEndTime，这一步的时间复杂度是O(logN)，不会影响整体性能。
• 剪枝是核心：通过子树的最大结束时间直接跳过不可能包含t的分支，避免无效遍历。

内容的提问来源于stack exchange，提问作者Maxim