推 yupog2003: 我的想法是先把三個sorted array merge起來成一個 01/10 18:07
→ yupog2003: 需要O(n)，然後最中間當root，切成左右兩堆 01/10 18:08
→ yupog2003: 再遞迴做下去，每次遞迴就是把中間那個挑出來當root就 01/10 18:08
→ yupog2003: 好，所以T(n)=2T(n/2)+O(1)，T(n)=O(n) 01/10 18:09
→ yupog2003: 有點好奇原po的作法是如何達到O(logn)的 01/10 18:15
→ ken52011219: Merge無誤 01/10 18:18
→ m666666m: 問一下balanced binary search tree是AVL tree嗎? 01/10 18:26
→ m666666m: 因為AVL tree就是O(logn)了 01/10 18:27
→ yupog2003: AVL tree也是一種balanced binary search tree，那麼 01/10 18:33
→ yupog2003: 要如何達到logn呢？ 01/10 18:33
→ kkk22805385: 我想說AVL都是O(log n) 哈哈 01/10 19:00
→ yupog2003: 可是他這邊是要建一個tree，建一個AVL應該不是O(logn)? 01/10 19:06
→ aa06697: 建AVL tree要nlogn 01/10 19:19
推 FRAXIS: 從 sorted array 建 balanced BST 只要 O(n) 01/10 22:42
推 moooner: sorted array用merge建balance tree也是O(nlogn)? 那用 01/11 07:39
→ moooner: insertion或bubble sort 不也可以達到O(n)? 01/11 07:39
→ moooner: 看錯..他是要建tree.. 01/11 07:43
→ aa06697: balanced bst 就是avl的一種... 請忽略我上面的留言XD 01/11 09:40