用紅黑樹寫一個(gè)字符串集合保存文件名字，每個(gè)文件名字節(jié)點(diǎn)都包含一個(gè)文件夾棧或者說隊(duì)列，遍歷文件夾下所有文件時(shí)每找到一個(gè)文件就把文件的名字插入字符串集合中，如果該名字已經(jīng)存在于字符串集合則遍歷該名字的所有具體路徑，對找到的每一個(gè)文件進(jìn)行比對，看看新插入的文件是否與已經(jīng)存在的文件內(nèi)容重復(fù)了，不重復(fù)就將這個(gè)新的文件夾路徑插入此節(jié)點(diǎn)對應(yīng)的文件夾棧并且文件數(shù)量加一，否則文件數(shù)量不變。

用紅黑樹實(shí)現(xiàn)字符串集合需要知道字典序的概念，也就是用字符串間第一個(gè)不同字符的大小決定字符串的次序，小的在前大的在后，若長短不一致且短字符串與長字符串對應(yīng)區(qū)域的字典序相同，則短字符串的字典序在前，長字符串的字典序在后。紅黑樹是一種從根節(jié)點(diǎn)到葉子結(jié)點(diǎn)的黑色節(jié)點(diǎn)總數(shù)是一個(gè)相同的值的數(shù)據(jù)結(jié)構(gòu)，這里只需要實(shí)現(xiàn)紅黑樹的插入功能就行了，也就是維持黑色節(jié)點(diǎn)總數(shù)相等。

需要的數(shù)據(jù)有：子節(jié)點(diǎn)、父節(jié)點(diǎn)、爺爺節(jié)點(diǎn)、叔叔節(jié)點(diǎn)，曾爺爺節(jié)點(diǎn)，曾曾曾爺爺節(jié)點(diǎn)。

算法步驟如下：

①父子節(jié)點(diǎn)是否都是紅色節(jié)點(diǎn)，是進(jìn)入'②'，否則進(jìn)入'⑥'。

②令父節(jié)點(diǎn)變?yōu)楹谏?jié)點(diǎn)，爺爺節(jié)點(diǎn)變?yōu)榧t色節(jié)點(diǎn)，若叔叔節(jié)點(diǎn)不存在或叔叔節(jié)點(diǎn)為黑色轉(zhuǎn)'③'，叔叔節(jié)點(diǎn)為紅色轉(zhuǎn)'④'。

③進(jìn)行二叉樹旋轉(zhuǎn)，假如父節(jié)點(diǎn)是左節(jié)點(diǎn)令爺爺節(jié)點(diǎn)的左節(jié)點(diǎn)變?yōu)楦腹?jié)點(diǎn)的右節(jié)點(diǎn)，父節(jié)點(diǎn)的右節(jié)點(diǎn)變?yōu)闋敔敼?jié)點(diǎn)，曾爺爺節(jié)點(diǎn)對應(yīng)的爺爺節(jié)點(diǎn)變?yōu)楦腹?jié)點(diǎn)，假如父節(jié)點(diǎn)是右節(jié)點(diǎn)令爺爺節(jié)點(diǎn)的右節(jié)點(diǎn)變?yōu)楦腹?jié)點(diǎn)的左節(jié)點(diǎn)，父節(jié)點(diǎn)的左節(jié)點(diǎn)變?yōu)闋敔敼?jié)點(diǎn)，曾爺爺節(jié)點(diǎn)對應(yīng)的爺爺節(jié)點(diǎn)變?yōu)楦腹?jié)點(diǎn)，旋轉(zhuǎn)后進(jìn)入'⑥'。

④令叔叔節(jié)點(diǎn)變?yōu)楹谏藭r(shí)爺爺節(jié)點(diǎn)是紅色，令子節(jié)點(diǎn)為爺爺節(jié)點(diǎn)，父節(jié)點(diǎn)為曾爺爺節(jié)點(diǎn)爺爺節(jié)點(diǎn)為曾曾爺爺節(jié)點(diǎn)，轉(zhuǎn)'①'。

⑥設(shè)置根節(jié)點(diǎn)為黑色

省略了很多細(xì)節(jié)，以下是代碼實(shí)現(xiàn)

紅黑樹的實(shí)現(xiàn)還是相當(dāng)復(fù)雜的，我也是第一次自己擼出來，對紅黑樹的理解還比較片面，希望有大佬能不吝賜教。