我在多个位置读到二叉树应该优先于哈希表,在哈希表中内存有限,因为二叉树会按排序顺序保存数据,而哈希表不会。与哈希表情况下的恒定时间插入和查找相比,二叉树的权衡将具有 O(log n) 查找和插入。
我想知道如果我选择二叉树来实现我的地址簿(总是排序), key 应该是什么样的?值是名称和数字对吗?
最佳答案
BTree != 二叉树。我假设你指的是后者。
地址簿的外观取决于您要进行的查找。如果您想根据姓名查找某人的地址,则键是姓名,地址/号码是值。
如果你想从地址查找名字,那么你只需颠倒键和值。如果您想要双向查找,则每个地址簿需要两棵树。
请注意,基于二叉树的字典在 C++ 标准库中作为 std::map
可用。在标题中 <map>
.除非您想进行编程练习,否则不要自己动手; std::map
在性能和功能方面很难被击败。
关于c++ - 使用二叉树实现字典,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/8142286/