內存連續性和搜索樹

我試圖在我的結果之上構建搜索樹。某種類型的k-ary樹，最後有n個葉子。我正在尋找一個C++解決方案並嘗試使用std::vector，但無法完成，因爲我需要內存一致性。它可以通過嵌套向量來完成，但我不能那樣做。內存連續性和搜索樹

讓我舉例說明的細節：

一個未排序的結果可能是

Result R = { 4, 7, 8, 3, 1, 9, 0, 2, 2, 9, 6 }

最重要的是我需要一個樹節點至極的我的具體問題是重心上方。但爲了保持簡單，我會在這裏使用人工值。

我定義了搜索樹尺寸

Height H = 2 
Branch B = 3

樹在第一

4 7 8 3 1 9 0 2 2 9 6

第二步

layer_0   1.6 5  8.2 
        | |  | 
     +-+-+-+-+-+ +-+ +-+-+-+ 
     | | | | | | | | | | | | 
layer_1 3 1 0 2 2 3 4 6 7 8 9 9

最後一步

layer_0     1.6   5   8.2 
          |   |    | 
        +---+---+ +-+---+ +---+----+ 
layer_1   0.8 1.6 2.4 4.2 5 5.8 6.4 8.2 8.4 
        |  | |  | | | | 
       +-+ +-+-+ |  | | | +-+ 
layer_2   1 0 2 2 3 4  6 7 8 9 9

這最後樹不是k元樹作爲最終葉子尺寸0 <= size <= |R|。

在這一刻，我有兩個載體試驗。

std::vector<size_t> layer_2; 

std::vector<float> leafs; 

std::size_t width, height;

隨着width和height幫助有可能通過leafs導航。但我在質疑自己如何優雅地連接leafs和layer_2？

一個很好的解決方案將如何模樣？

來源

2017-03-14 user1587451

_結束「...因爲我需要存儲的一致性。」 _這是什麼意思？你需要**連續**內存？還有別的嗎？爲什麼你的樹木裏充滿了不在你的原始集合中的價值？爲什麼你的葉子沒有排序？ – Useless

是的，連續記憶是正確的方式。對不起我的英語不好。樹葉被分類。樹使用上部葉子的平均值。最後的葉子（4,7,8,3，...）被分組，其值最接近父級。 – user1587451

好的，所以你有固定深度的3-ary樹，和一個單獨的1級部分3-ary樹...這似乎不必要的複雜。啊，我知道，出於某種原因你需要子樹質心值。你究竟在努力實現什麼？ – Useless

注意：此方法是，它使用一個連續的數據結構（向量或矩陣），而不是一個節點指針樣式樹感連續的，而是必須具有根據應用的數據結構內未使用的空間的可能性。

其中這種做法浪費了大量的空間，一個案例：分支機構的每個節點的最大數量很大，但大多數節點實際上已遠遠少生孩子。這對於找到葉子需要多長時間沒有影響。事實上，讓這一點變得相當快是一種折衷。

考慮3支樹與4個級別的連續內存： R,a,b,c,aa,ab,ac,ba,bb,bc,ca,cb,cc,aaa,aab,aac,aba,abb,abc,baa....其中一個節點的子指數從（parent_index * 3）爲+1（parent_index * 3）+3

重要的告誡我暗示的是每個節點必須始終在矢量，數組等任何位置具有三個子空間。如果一個節點只說2個孩子，只需用一個null_child值填充該額外空間來容納該空間。（這是浪費的空間來自於）

的優點是，現在，發現所有的葉子很容易。

first_leaf_index = 0 
for(i=0;i<(4-1);i++)//in this example 4 is the depth 
    first_leaf_index += 3^(i) //three is max branches per node

在這一點上只是重複的數據結構

來源

2017-03-17 19:47:23

內存連續性和搜索樹

回答

相關問題