二叉搜索树更新

Question

我正在开发一个需要将值存储在二叉搜索树中的应用程序。这是一些类似于通过将每行存储为一个键值来实现textpad的应用程序。如果删除一行，则在O（n）中更新之后的行的键。通过考虑类似于行号的参数（在该示例中）作为密钥，我能够在我的应用程序中实现O（n）时间。

有没有办法通过选择其他键来实现O（log n）时间？

Answer 1

如果您需要保证O(logN) peformance从二叉树你应该使用自平衡版本，例如， Splay Tree或Red black tree

Answer 2

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

此外，你可以尝试一些平衡bst O(log(n))像红黑树，avl树，2-3树。