Re: [理工][資結] 搜尋樹 優先佇列

[pttptt2008 (鄉民)]

※ 引述《ting301 ( )》之銘言：
: 由1到1000共1000個整數  組成的BST

二元搜尋樹（Binary Search Tree），或者是一棵空樹，或者是具有下列性質的二元樹：

1.若它的左子樹不空，則左子樹上所有結點的值均小於它的根結點的值；
2.若它的右子樹不空，則右子樹上所有結點的值均大於它的根結點的值；
3.它的左、右子樹也分別為二叉排序樹。

由以上的性質, 我推得 路俓中的數字是 搜尋目標數 的趨近式上下限(...自己亂喊的).

: 若想要搜尋  363  這個數值  下面五種路徑哪一些是不合法的?
: (A) 2  252  401  398  330  344 397  363
: (B) 924  220  911  244  898  258  362  363
: (C) 925  202  911  240  912  245  363
: (D) 2  399  387  219  266  382  381  278  363
: (E) 935  278  347  621  299  392  358  363
: 這個要怎麼判斷啊???

以 (C) 為例

上限 925 911 912(X, 要比911小, 沒有往363趨近)

搜尋目標數 363

下限 202 240 245

所以 (C) (E) 不合法

: ---------------------------------------
: 另外
: 有一問題是指定將{1,2,4,5,6,7,8}排入一定架構的BST  如下:
:         x
:       ／ ＼
:      x     x
:    ／ ＼    ＼
:   x     x     x
:       ／
:      x
: 這種架構是否解不唯一呢??
: 隨便答一種只要合BST性質都OK?

以 BST 的性質來看, 我不知道樹頂除了 6以外, 還有其他種可能

因此我覺得本題應該是唯一解

: -----------------------------------------
: priority queue:
:     Show that or disprove that a priority queue in the comparsion
: sorting model satisfied  both :
: (1) EXTRACT-MIN in O(lglg n)
: (2) BUILD-MAX-HEAP in O(n)
: ------------------------------------------

這題我不會, 請高手解!

: 非常感激指教  尤其第一題我實在不曉得怎麼辨識?


--
※ 發信站: 批踢踢實業坊(ptt.cc) 
◆ From: 125.224.185.234
→ gskman:priority queue 應該1、2都錯吧 delete min感覺像是常數
→ gskman:寫錯 是log n =.=
→ gskman:然後2應該是對的建一個max heap是n沒錯
→ gskman:searching min才是常數-.-"
推 jim055006:heap是製作priority queue的資料結構....
→ jim055006:所以第一題跟樓上想的一樣....
→ jim055006:第二題使用bottom up法建heap...O(n)...就可以了