找到樹數據結構中所有葉節點的最高性能方法

Question

我有一個樹數據結構，其中每個節點可以有任意數量的子節點，樹可以是任何高度。獲得樹中所有葉節點的最佳方式是什麼？在遍歷樹中的每條路徑之前，是否可以做得更好，直到我擊中葉節點？

實際上，樹的最大深度通常爲5左右，樹中的每個節點都會有大約10個孩子。

我接受其他類型的數據結構或特殊樹，這些樹會使葉節點特別優化。

我使用的是JavaScript，但實際上只是在尋找一般建議，任何語言等

謝謝！

Answer 1

內存佈局對於最優檢索是必不可少的，所以子列表應該是連續的而不是鏈表，節點應該按照檢索順序依次放置。

您的樹越靜態，可以完成更好的佈局。

全部在一個佈局

• 所有在一個陣列中的全序

• 臨

  • 存儲器可以爲最大的吞吐量被流傳輸（硬件預取）
  • 沒有不需要的頁面查找
  • 正常查找可以製造
  • 沒有額外的內存來建立鏈表。
  • 內部節點使用偏移上尋找與自己孩子

• 精讀

  • 插入/刪除可能會很麻煩
  • 插入/刪除O（N）
  • 插入可能導致調整陣列的尺寸導致成本高昂的複製

兩個陣列布局爲內部節點

• 一個陣列
• 一個陣列用於葉子

• 內部節點指向葉子

• 臨

  • 葉節點可以是以最大吞吐量進行流式傳輸（如果大多數情況下只有intereste，則可能是最佳佈局d在葉子中）。
  • 沒有不必要的頁查找
  • 間接查找可製成

• 精讀

  • 如果所有的葉子是有序的插入/刪除可能會很麻煩
  • 如果葉子是無序的插入是易於，最後加上。
  • 刪除無序葉子也是一個問題，如果沒有允許任何墓碑，因爲最後一片葉子將不得不被移回並且內部節點需要修復。 （通過進一步的間接方向，這也可以固定參見插槽圖）
  • 調整大小可能會導致大的副本，但小於All-in-one，因爲它們可以獨立完成。使用連續的陣列用於參照每個節點
  • 臨
    • 通過每個子運行的子陣列的

  陣列（矢量的動態尺寸，C++矢量）

  • 列表很快
  • 每個子數組可以獨立調整大小
• 精讀
  • 同時去除大部分的個人名單分散所有其他數據進行查找採取額外的時間中鏈表孩子的額外工作。
  • 插入可能會導致調整大小和數組的副本。

Answer 2

查找樹的葉子是O(n)，這對於樹是最佳的，因爲您必須查看O(n)地點以檢索所有n事物，以及沿途的分支節點。常量開銷是分支節點。

如果我們增加分支因子，例如讓每個分支有32個孩子而不是2個，我們大大減少了開銷節點的數量，這可能使得遍歷速度更快。

如果我們跳過一個分支，我們不包括該分支中的值，所以我們必須查看所有分支。