[問題] randomly built binary search tree

看板Prob_Solve作者 (無法顯示)時間15年前 (2011/02/18 22:15), 編輯推噓1(1推 0噓 0→)
留言1則, 1人參與, 最新討論串1/1
用 n 個node 隨機建立二元搜尋樹 這顆樹預期的高度是O(lgn) 請問要怎麼證明呢? 我看cormen是擺在12.4節 可是除了cormen用的方法之外 還有別的方法可以證明嗎? 謝謝 -- ※ 發信站: 批踢踢實業坊(ptt.cc) ◆ From: 61.228.25.34
推
02/19 02:54, , 1F
個人覺得再怎麼變都不脫同一條思路: 遞迴地由兩子樹建立全樹
02/19 02:54, 1F
‣ 更多 mqazz1 的文章
文章代碼(AID): #1DNdxkQi (Prob_Solve)