在Tree目錄結構中查找歷史操作的算法

我遇到了一個有趣的問題。有一個目錄樹讓呼叫T在Tree目錄結構中查找歷史操作的算法

現在在目錄結構中有3個操作是允許

1. Add a file or another directory under some parent directory 
2. Remove a file or another directory 
3. Modify that is move a file/directory from one parent directory to another.

現在你在任何順序上的目錄T執行上述3個操作。該操作將提供另一個目錄結構，我們稱之爲T'。

的問題是，如果你有T和T'將能夠找到最低順序操作S其轉化T到T'的。

例如

T = 
root/ 
---- a/ 
     --- file1.txt 

T' = 

root/ 
---- a/ 

S = {Delete root/a/file1.txt} 

Another example 

T = 
root/ 
---- a/ 


T' = 

root/ 
---- a/ 
     ---file1.txt 

S = {Add root/a/file1.txt}

來源

2017-09-30 Avishek Bhattacharya

請你詳細說明你的問題.... – krpra

我不知道你想要什麼闡述。在一個目錄中，你可以改變文件，刪除/添加等，之後，以前的目錄從舊狀態轉換爲新狀態。問題是要找到可以更改爲新狀態的最小操作集合 –

@Krpa我已經添加了一個示例 –

我們可以深度上同時兩棵樹，並在文件層面上，我們可以使用校驗和檢查兩個文件是相同的優先搜索。如果所有文件都被重命名，並且n是目錄中文件的數量，那麼文件級別的操作可以是O（n^2），爲了獲得更好的性能，我們可以在每個目錄級別維護一個清單，並對每個捕獲的文件進行校驗和（文件操作需要被修改並且會更加複雜，但如果我們不想經常這樣操作，這不是必需的）。如果一個目錄被移動，這可以產生更多的輸出，在這種情況下，我們可以爲每個目錄計算累積校驗和類似的東西，並保存它以便稍後進行級別遍歷。在稍後進行級別遍歷時，我們可以優化輸出。（只是一個想法）

來源

2017-09-30 13:46:04 user8700406

在Tree目錄結構中查找歷史操作的算法

回答

相關問題