Google Search Box

自訂搜尋

Wednesday, May 26, 2010

[課業] 資料結構/BST 

作者: skyw830 (.....) 看板: Examination
標題: [課業] 資料結構/BST
時間: Wed May 26 22:30:13 2010

1.考試科目：資料結構


2.章節名稱or篇名(單元關鍵字)：BST


3.目前參考用書or考古題出處：95警察二等第四題


4.想問的內容：
請設計一 O(log n)時間演算法在一數字相異之二元搜尋樹（binary search tree）找出
第k 個最小之元素（the kth smallest element）。

5.想法：
(1)BST如用中序追蹤列入陣列中====>O(n)
(2)再去找第k個最小值============>O(1)
(3)加起來還是O(n)

不知道如何可以O(logn)作法呢?
向各位先進請教，謝謝。
Posted by at

1 comment:

  1. PTT國考RSS閱讀器May 26, 2010 at 11:01 AM

    → JACKIAM:這題覺得有點奇怪 我也不會解 如果假設是complete BST 05/26 23:06
    → JACKIAM:那還有辦法解.. 05/26 23:06
    → skyw830:不太懂J大的意思耶..如何解呢? 05/26 23:17
    推 JACKIAM:complete BST 樹根一定是中間值 k如果n/2往右 05/26 23:23
    → JACKIAM:同樣的方法往下找就只需樹的高度的次數就好 05/26 23:24
    推 audio8862:每個node多個size欄位紀錄子樹節點個數 05/26 23:29
    → audio8862:root就可由左兒子+1 可算出root是第幾小的 05/26 23:34
    → audio8862:k如果小於rootRank 往左遞迴 反之往右 不然就是找到了 05/26 23:36
    → JACKIAM:可是它的worst case好像還是O(n)耶 05/26 23:39
    推 audio8862:-.-這樣會O(n)? 05/26 23:43
    → audio8862:再怎樣 也只有O(height) 05/26 23:44
    → JACKIAM:我的意思是 height也可能是n 05/26 23:45
    推 audio8862:應該都要用avg.case去看吧 05/26 23:53
    推 JACKIAM:喔喔~了解 謝謝a大 05/26 23:56
    → skyw830:懂了懂了，謝謝a大 05/27 00:07

    ReplyDelete

Subscribe to: Post Comments (Atom)