通過至多h + 1比較查找BST的元素

Question

給定二叉查找樹和元素e，使用至多h + 1比較來確定樹是否包含e，其中h是樹的高度並且= =，！=，>，> =，<和< =是比較。有誰知道如何創建這種算法？

Answer 1

首先，編寫一個函數，在樹中查找大於或等於您的值的最小項。

在僞碼：

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。