看板 [ Grad-ProbAsk ]
討論串[理工] [DS] binary search tree height
共 2 篇文章
內容預覽： 開啟 | 關閉 | 只限未讀
首頁
上一頁
1
下一頁
尾頁
#2
Re: [理工] [DS] binary search tree height
推噓1(1推 0噓 1→)留言2則，0人參與, 最新作者FRAXIS (喔喔)時間11年前 (2014/12/21 23:20), 編輯資訊
0
0
1
內容預覽:
給定 n 個元素為插入 BST 的元素集合。. 假設插入BST的順序是均勻隨機分布。. 此時建出來的樹 T 本身就是一個隨機物件。. 那T的高度 Height(T) 也是一個隨機變數. 所以 Height(T) 的期望值就是期望高度 = E[Height(T)]. 可以證明為O(lg n)。. 但是
(還有449個字)
#1
[理工] [DS] binary search tree height
推噓3(3推 0噓 6→)留言9則，0人參與, 最新作者winnie48 (winnie)時間11年前 (2014/12/21 16:28), 編輯資訊
0
0
1
內容預覽:
想請問 binary search tree 最好的情況下 height = log (n) , 但是 worst case = n，n 是元素個數。那麼要怎麼證明 random 建立的 binary search tree height = log(n) ??. 實在是不太會這種要考慮到機率的情況
首頁
上一頁
1
下一頁
尾頁