c++ - 使用二叉树实现字典

Question

我在多个位置读到二叉树应该优先于哈希表，在哈希表中内存有限，因为二叉树会按排序顺序保存数据，而哈希表不会。与哈希表情况下的恒定时间插入和查找相比，二叉树的权衡将具有 O(log n) 查找和插入。

我想知道如果我选择二叉树来实现我的地址簿(总是排序)， key 应该是什么样的？值是名称和数字对吗？

Answer 1

BTree != 二叉树。我假设你指的是后者。

地址簿的外观取决于您要进行的查找。如果您想根据姓名查找某人的地址，则键是姓名，地址/号码是值。

如果你想从地址查找名字，那么你只需颠倒键和值。如果您想要双向查找，则每个地址簿需要两棵树。

请注意，基于二叉树的字典在 C++ 标准库中作为 std::map 可用。在标题中 <map> .除非您想进行编程练习，否则不要自己动手； std::map在性能和功能方面很难被击败。