2
給定二叉查找樹和元素e,使用至多h + 1比較來確定樹是否包含e,其中h是樹的高度並且= =,!=,>,> =,<和< =是比較。有誰知道如何創建這種算法?通過至多h + 1比較查找BST的元素
給定二叉查找樹和元素e,使用至多h + 1比較來確定樹是否包含e,其中h是樹的高度並且= =,!=,>,> =,<和< =是比較。有誰知道如何創建這種算法?通過至多h + 1比較查找BST的元素
首先,編寫一個函數,在樹中查找大於或等於您的值的最小項。
在僞碼:
function find_min_ge(x, node, min_ge) {
if node is nil {
return min_ge
}
if node.x >= x {
return find_min_ge(x, node.left, node.x)
} else {
return find_min_ge(x, node.right, min_ge)
}
}
在此, 「min_ge」 的說法是這是> = X迄今發現的最小值。
然後,與X比較結果:
x_in_tree = find_min_ge(x, root, x + 1) == x
的X + 1是一個虛擬的值,如果有在樹沒有元素> = X那將被返回。 x + 1可以是任何不等於x的表達式。總體而言,find_min_ge至多執行h「> =」比較,然後根據需要在最後完成一個額外的「==」比較,總共最大值爲h + 1。
我不是在談論標準的bst搜索算法 - 最多需要2h-1比較,如果這就是你的意思 – somewhy
是什麼讓你認爲這樣的算法存在? –
這是一個關於使用Elm的編程任務的問題,它已被其他人解決。 – somewhy