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

[longlongint (希佳珈)]

推文中已提示 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: 感謝分享~下午時也用類似的想法解出了，不過有建出BST
→ sunhextfn: http://ideone.com/4WpYMQ
→ longlongint: 該不會是 Cartesian tree
推 suhorng: 排序後用 Cartesian tree 解, O(排序) + O(n)
→ suhorng: 把插入的 index 當 key 就是 cartesian tree
→ longlongint: 哦哦感謝 又學到新招了
※ 編輯: longlongint (114.36.52.199), 02/17/2015 02:51:18
→ sunhextfn: 我不知Cartesian tree，是看到你的提醒才想到的XD
→ suhorng: 重新獨立發現 Cartesian tree XD
→ longlongint: 羨慕  我只有獨立發現過queue