data-structures - BST 时间复杂度：float 值和 int 值有什么区别吗？

Question

给定浮点数的 BST 和 int 数的 BST。我只是想知道基于不同数据类型的 BST 之间是否存在插入、删除等的时间复杂度差异？

Answer 1

二叉搜索树的时间复杂度通常用比较次数来表示。例如，说插入的运行时间是 O(log n) 意味着只进行 O(log n) 比较。如果比较本身需要一些额外的时间（例如，如果您正在比较字符串），那么运行时可能会更改以反映这一点。

比较floats 确实比比较 s 需要更多的时间int，但它仍然是一个恒定的工作量（即 O(1)）。因此，运行时间仍应为 O(log n)，尽管由于进行浮点比较涉及额外的硬件，它可能会慢一些。

希望这可以帮助！

Answer 2

不。时间复杂度源自算法本身的结构和特征（例如有多少嵌套循环，或多少递归），而不是它所操作的数据类型。

搜索、插入和删除在 BST 中平均为 O(log n)，最坏情况下为 O(n)。

有关 BST 的更多信息，请参见Wikipedia。