表示层次结构的数据结构

Question

我最近有一个采访问题，询问如何用数据结构表示组织结构。查询如列出管理人员下的所有员工应该被有效查询。

我在回答N行树的问题，但我不太清楚应该是什么关键以及如何实现它。很想知道这可以做的最好的方式是什么。

Answer 1

具有adjacency list表示的定向图似乎是最好的解决方案。

Answer 2

你有一个选择 - 对于这个确切的需求稍微高效的自定义容器，或者找出哪些STL容器将做得非常好。在一次采访中，我肯定会开始说 - “让我们来看看STL容器会做什么，然后看看是否存在效率低下（无论是在可伸缩性还是在支持并发性方面）为自定义容器辩护”。

因此，通常您会为每位员工提供一个唯一的employee_id。您希望能够使用该ID搜索员工，并且可能会通过名称搜索并获得相当快的结果。所以，如果你想快速任意地插入/删除，你可以使用员工ID的std :: map或unordered_map（C++ 11）到员工姓名和其他细节，以及从名称到employee_id的另一个地图。如果数据没有变化（通常），其中一个或两个都可以是一个已排序的向量 - 稍好一点的打包和内存/缓存效率，但仍允许O（log2n）查找。考虑到基本模型，我们可以通过让每个员工对象包含其经理的employee_id以及他们的直接报告的employee_id的向量来扩展它以反映员工之间的关系。由于直接报告的数量不可能太大，矢量是相当实用的。这确实意味着要列出所有员工必须“直接报告”直接报告及其直接报告等，但无论如何，这非常有效，并且与冗余记录针对每位员工的所有直接和间接报告相比，节省了大量内存。

上述STL方法很可能适合您的需求。尽管可能不是最佳的表现，但稍加锁定即可保证线程安全。尽管如此，当需要更多的可伸缩性，持久性，跨进程事务语义等时，数据可能会更好地转移到商业数据库中，除非您是内存数据库的专家（例如，当我在彭博的Ticker工厂 - 每秒插入数十万条财务记录 - 我们确实专业化，但很少有人力资源项目需要它）。