JS实现的二叉搜索树插入操作慢于搜索删除的原因问询

你的猜测是正确的，大量Node实例创建确实是BST插入性能远低于另外三种结构的核心原因，同时还有其他几个因素共同导致了该结果：

• 实例化开销：JS中类实例的创建、属性初始化需要额外的内存分配和运行时开销，你每次调用add方法都会执行new Node(key, value)，百万次调用叠加的内存分配、垃圾回收成本非常高。而原生Map、普通对象的插入逻辑由JS引擎底层C++实现，哈希表的键值存储不需要在JS层面创建额外的实例对象，性能远高于用户侧JS实现的类实例创建。
• 测试设计的偏差：你当前的测试用例中，插入操作执行了100万次，而搜索和删除仅各执行了1次，这直接放大了插入操作的耗时差距，无法公平对比BST三种操作的实际性能。如果改为同样执行100万次随机搜索、随机删除，你会看到后两者的耗时也会大幅上升，和插入的差距会明显缩小。
• 时间复杂度的实际差异：理论上平衡BST的三种操作时间复杂度是O(logn)，但原生Map、对象底层基于哈希表实现，插入/查询/删除的平均时间复杂度是O(1)，本身就比O(logn)在大数据量下有性能优势。另外你实现的是普通未平衡的BST，极端情况下（比如插入有序键）会退化为O(n)的时间复杂度，进一步拉低插入性能。
• 实现层面的可优化点：你可以通过对象池优化Node实例的创建开销：预先创建一批空闲的Node实例，插入时从对象池取实例赋值，删除时把实例放回对象池，避免频繁的new和GC，能明显提升插入性能。

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