Re: [問題] zerojudge b346 二元搜尋樹快速建造

看板C_and_CPP作者longlongint (希佳珈)時間9年前 (2015/02/16 18:54)推噓2(2推 0噓 7→)

留言9則, 3人參與討論串2/2 (看更多)

推文中已提示 Cartesian Tree 是較好的解。可以直接看推文 -------------- 搞了一陣子之後弄出了解法，讓原PO參考。我覺得我的解法應該不是出題者想要的解法但是我想拋磚引玉想知道別人是怎麼解的簡述: 正常硬幹解法會TLE，因為時間複雜度最糟是O(n^2)。就算用rotate將樹平衡也只會破壞preorder的順序。(可能是我誤會) 所以我改用其他方式，主要想法是排序、RMQ。我發現在一個子樹之中，總是最先輸入的節點當 root 。利用排序可以得到 inorder traversal 所以只要用排序拿到中序尋訪的順序，再抓出 root 將整個陣列切成兩半。需要的"零件"就是在O(logn)時間抓出root。我只要保證總時間大概是O(nlgn)，而且可以解所有case就行了。實作: http://ideone.com/dwEeRp 參考了 topcoder 網站的內容，網址列在註解中。不知道這邊回文能不能直接貼答案。不過我的程式碼不是最佳解所以沒差吧哈哈碎碎念: 這個問題的難處在於只要遇到排序好的序列，就會落入O(N^2)的時間複雜度就算只有一半的數列是排序好的順序，也是令人頭痛。總之只要會變成長鏈狀就會TLE。詳情請翻資料結構課本。原本想用平衡數系列來解決，但是preorder的順序會改變，我想不出來如何用平衡樹解。最後得到的方式是利用排序取得中序尋訪，再利用輸入順序來解出 preorder 。 (根據演算法課本&資料結構課本，我們知道排序就是中序尋訪的順序，不詳細解釋XD) 利用輸入資料 1 4 2 0 3 來說明 0 1 2 3 4 array index 1 4 2 0 3 num 0 1 2 3 4 intput order 排序之後(inorder) 0 1 2 3 4 array index 0 1 2 3 4 num 3 0 2 4 1 input order 在這裡我們先用樹的長相來理解陣列內容格式:Parent(leftTree, rightTree) -號代表null 1(0,4(2(-,3),-)) 我們可以發現最先輸入的 1 是root 分成左右兩半 0 0 3 和 2 3 4 2 3 4 2 4 1 新的 root 是 0 和 4 。依此類推 4的左邊有 2 3 ，右子樹是空。左子樹當中 2 先輸入所以是 root 。利用這個性質，使用任何一套 O(logn) 以內的 Range Minimum Query (RMQ) 就可以快速找到子樹的 root 。我在這裡是使用 segment tree 。有興趣的人可以試試看 Sparse Table (ST) 。不過我覺得我這樣解跟 BST 建置沒甚麼關係啊 OTZ 。跪求神人。 -- ※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 114.36.52.199 ※ 文章網址: https://www.ptt.cc/bbs/C_and_CPP/M.1424084048.A.7F3.html

推

sunhextfn

02/16 22:38, , 1^F

02/16 22:38, 1^F

→

sunhextfn

02/16 23:17, , 2^F

02/16 23:17, 2^F

→

longlongint

02/17 01:05, , 3^F

02/17 01:05, 3^F