表示層次結構的數據結構

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工廠 - 每秒插入數十萬條財務記錄 - 我們確實專業化，但很少有人力資源項目需要它）。