※ 引述《willyhsu (wi)》之銘言：
: 另外想請問，假設集合0 1 2 3是新出現集合，要產生對應的節點建到樹結構之前，我要
: 參考0123子集資料，是不是只能重新將0 1 2 3 再分解成子集{0, 1, 2, 3, 01, 02,
: 03, 012, 013, …} 一一的traverse找對應子集節點的資訊，計算完後再將 0 1 2 3建到
: 樹結構?
雖然還不知道原本樹的構成方式,但根據前面幾篇反覆討論得到的心得,
可以建議使用一種樹結構:
目前已經知道,已經存在集合 S 情況時,如果出現一個新點 N, 會把 N 對 S 個別銜接
產生 S'. 這種對稱的結構剛好可以建立一顆樹為
/--- N ---\
S S'
因為你的系統是處理隨機出現的交易資料,資料順序無法預期也無可定數,最好見招拆招.
處理第一批 {012,123} 時,先用 0123 產生子集樹,然後分別把 012 子集和 123 子集
的統計數登錄到樹中各別位置的資料欄位. 之後處理第二批 {014,145} 時, 要先判斷
0145 對 0123 的差異, 差異為 45, 則接著要把 45 加入樹結構. 舉例來說, 先有 042
建立樹的操作結果為:
--------- 2 ---------
--- 4 --- ---- 42 ----
0 04 02 042
之後加入新元素 1 變成:
------------------------ 1 --------- ... (略)
--------- 2 ---------
--- 4 --- ---- 42 ----
0 04 02 042
我不知道這樹有沒有名字,如果沒有名字,因為樹的構成順序是亂的,可以稱為亂樹. :D
接下來是在樹中搜尋資料的方法:
這種樹有很明顯的特徵,首先是從根一路左走一直線,是到目前收集的集合 {0,4,2,1}.
第二項特徵是,每一子樹的左子樹是不包含樹根的其他子集,右子樹是左子樹加上樹根
的子集,至於樹根的向上回溯要看是左回溯或右回溯,如果向右回溯則可以找得到
本子樹的超集. 尋找超集這個功能,可能用不到吧.
從根往下找特定資料的辦法,例如要找 02 位置,首先一路向左找基本元素,找 02 的 2
在樹中找到 2 的時候, 你會知道三件事,一是左子樹排除在外,因為絕對沒有包含 2;
二是 2 子樹的樹根全都不要考慮,因為絕對不會是以 2 結尾; 三是,所以 02 會存在
於 2 子樹的右子樹中. 下一步在 02 - 42 - 042 這棵子樹中尋找,這次要以十位數
的基數為比對準則, (所以節點的比對要加上一些基數方式的比對法呀,剛才漏想了..)
這次從樹根 42 一路向左找 02 的 0, 找到 02 位置, 而且 2 和 0 都找過了,
所以命中並且可以結束. 按照這個規則,如果要找 34, 會發現最後在某子樹一路向左
搜尋時完全找不到 3,所以判斷為漏失,找不到.
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 218.160.212.16