如何在二叉搜索树中找到与给定键值最接近的元素？

Question

给定一个带整数值的bst作为键如何在bst中找到最接近该键的节点？BST使用节点对象(Java)表示.最接近的是例如4,5,9,如果钥匙是6,它将返回5 ..

Answer 1

像找到元素一样遍历树.当您这样做时,记录最接近您的键的值.现在,当您没有找到密钥本身的节点时,返回记录的值.

所以,如果你正在寻找的关键3在下面的树,你最终会在节点上6没有找到一个匹配,但你的入账价值是2因为这是你曾经走过的所有节点(最接近的关键2,7,6).

                 2
              1      7
                   6   8

Answer 2

遍历需要O(n)时间.我们可以在上下进行吗？喜欢这个递归代码:

Tnode * closestBST(Tnode * root, int val){
    if(root->val == val)
        return root;
    if(val < root->val){
        if(!root->left)
            return root;
        Tnode * p = closestBST(root->left, val);
        return abs(p->val-val) > abs(root->val-val) ? root : p;
    }else{
        if(!root->right)
            return root;
        Tnode * p = closestBST(root->right, val);
        return abs(p->val-val) > abs(root->val-val) ? root : p;
    }   
    return null;
}

Answer 3

这是Python中的递归解决方案:

def searchForClosestNodeHelper(root, val, closestNode):
    if root is None:
        return closestNode

    if root.val == val:
        return root

    if closestNode is None or abs(root.val - val) < abs(closestNode.val - val):
        closestNode = root

    if val < root.val:
        return searchForClosestNodeHelper(root.left, val, closestNode)
    else:
        return searchForClosestNodeHelper(root.right, val, closestNode)

def searchForClosestNode(root, val):
    return searchForClosestNodeHelper(root, val, None)

Answer 4

它可以在O(log*n*)时间内解决.

• 如果节点中的值与给定值相同,则它是最近的节点;
• 如果节点中的值大于给定值,则移至左子节点;
• 如果节点中的值小于给定值,请移至右侧子节点.

该算法可以使用以下C++代码实现:

BinaryTreeNode* getClosestNode(BinaryTreeNode* pRoot, int value)
{
    BinaryTreeNode* pClosest = NULL;
    int minDistance = 0x7FFFFFFF;
    BinaryTreeNode* pNode = pRoot;
    while(pNode != NULL){
        int distance = abs(pNode->m_nValue - value);
        if(distance < minDistance){
            minDistance = distance;
            pClosest = pNode;
        }

        if(distance == 0)
            break;

        if(pNode->m_nValue > value)
            pNode = pNode->m_pLeft;
        else if(pNode->m_nValue < value)
            pNode = pNode->m_pRight;
    }

    return pClosest;
}

您可以访问我的博客了解更多详情.