二叉搜索树更新

Question

我正在开发一个需要将值存储在二进制搜索树中的应用程序。如果删除了一行，则在O(n)中更新后面的行的键。通过将类似于行号(在本例中)的参数作为关键字，我能够在我的应用程序中实现O(n)时间。

有没有办法通过选择其他密钥来达到O(log )时间？

Answer 1

如果您需要从二叉树获得有保证的O(logN)性能，则应该使用自平衡版本，例如Splay Tree或Red black tree

Answer 2

如果您的需求是插入/更新、删除和搜索，那么可以尝试使用具有良好散列函数的Hash Table。许多语言在C++中提供了哈希表实现unordered_map，在python中提供了dict，在javascript中提供了{}……哦，顺便说一句，你可以自己写一个。

你也可以尝试一些O(log(n))的平衡边界条件树，如红黑树，avl树，2-3树。