算法合集之樹(shù)的枚舉(參考版)
2024-10-19 20:32本頁(yè)面
【正文】 下表可以作為算法時(shí)間復(fù)雜度的直觀參考。算法中涉及的樹(shù)的復(fù)制，以及遍歷等，復(fù)雜度均為 O（ n），并且在樹(shù)的生成過(guò)程中完全沒(méi)有重復(fù)生成，所以整個(gè)算法的耗時(shí)主要與不同形態(tài)樹(shù)的總數(shù)有關(guān)。 比如說(shuō)：為了使 2021成為比它小，但又與它相差最少的自然數(shù)： 2021 1999 1000 ? 類(lèi)似地 , 再看一個(gè)有向樹(shù)變換的例子 : 刪除結(jié)點(diǎn) ， 使子樹(shù)變小 將后面的子樹(shù)重組 （ 最大化 ） 變換完成 ? 我們先從后向前找到一個(gè)待刪除結(jié)點(diǎn)，刪除它之后，然后對(duì)其它子樹(shù)進(jìn)行了一定的變換（類(lèi)似于上面把 0變成為 9的過(guò)程），確保了整棵樹(shù)變小的程度最小，從而得到了序列中的下一棵有向樹(shù)。 {包括上面的兩種情況 : 子樹(shù)深度改變 , 以及深度未改變 } 7 end of while 小結(jié) ? 雖然上面變換過(guò)程看似十分復(fù)雜，實(shí)質(zhì)上它是以一種簡(jiǎn)潔和嚴(yán)謹(jǐn)?shù)囊?guī)律為基礎(chǔ)的。 5 刪除 target。得到新的樹(shù)。 將 F刪去，處理 E極其兄弟（此處為空），連同刪去的F，以 C為根進(jìn)行重組。 C E： 深度將會(huì)變小。 過(guò)程 II 算法 刪除結(jié)點(diǎn)后子樹(shù)深度不變 ? 接下來(lái)，對(duì)排列在被改動(dòng)的這棵子樹(shù)以后的其它子樹(shù)進(jìn)行重新組合，使它們?cè)跐M足不大于當(dāng)前這棵子樹(shù)的情況下變得最大（同時(shí)將被刪除的那個(gè)結(jié)點(diǎn)加入）。 刪除一個(gè)結(jié)點(diǎn)之后，會(huì)出現(xiàn)兩種情況： ? 當(dāng)前子樹(shù)深度不變，結(jié)點(diǎn)數(shù)
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號(hào)-1