我正在开发一个需要将值存储在二叉搜索树中的应用程序。它有点类似于通过将每一行存储为带有某个键的值来实现文本板的应用程序。如果删除了一行，则在 O(n) 中更新之后行的键。通过考虑类似于行号（在示例中）的参数作为键，我能够在我的应用程序中实现 O(n) 时间。
有没有办法通过选择其他键来实现 O(log n) 时间？
问问题
2427 次
2 回答
1
如果您需要O(logN)二叉树的性能保证，您应该使用自平衡版本，例如Splay Tree或Red black tree
于 2012-09-16T22:09:10.457 回答
1
如果您的要求是插入/更新、删除和搜索，请尝试Hash Table使用良好的哈希函数。unordered_map许多语言在 C++、dictpython、 javascript 中提供哈希表实现{}......哦，顺便说一句，您可以自己编写一个。
您也可以尝试一些平衡的 bst，O(log(n))例如红黑树、avl 树、2-3 棵树。
于 2012-09-16T22:23:45.850 回答