Как найти ближайший элемент к заданному значению ключа в двоичном дереве поиска?

Ответ 1

Поверните дерево так, как вы бы нашли этот элемент. Пока вы делаете эту запись, значение, которое ближе всего к вашему ключу. Теперь, когда вы не нашли node для самого ключа, возвращайте записанное значение.

Итак, если вы искали ключ 3 в следующем дереве, вы попали бы в node 6, не найдя соответствия, но ваше записанное значение было бы 2, поскольку это был самый близкий ключ все узлы, которые вы прошли (2, 7, 6).

                 2
              1      7
                   6   8

Ответ 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;
}

Ответ 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)

Ответ 4

Он может быть решен в O (log * n *) времени.

• Если значение в node такое же, как заданное значение, это ближайший node;
• Если значение в node больше заданного значения, перейдите к левому дочернему элементу,
• Если значение в node меньше заданного значения, перейдите в правый дочерний элемент.

Алгоритм может быть реализован со следующим кодом С++:

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;
}

Вы можете посетить мой блог для более подробной информации.

Ответ 5

Проблема с подходом "левый правый обход и поиск ближайшего" заключается в том, что он зависит от последовательности, в которой элементы были введены для создания BST. Если мы ищем 11 для последовательности BST 22, 15, 16, 6, 14, 3, 1, 90, вышеуказанный метод вернет 15, а правильный ответ - 14. Единственный метод должен использовать рекурсию для перемещения всех узлов, возвращая ближайшую из них в результате рекурсивной функции. Это даст нам самое близкое значение

Ответ 6

Это можно сделать с помощью Queue и ArrayList. Очередь будет использоваться для выполнения первого поиска по дереву. ArrayList будет использоваться для хранения элемента дерева в первом порядке. Вот код для реализации того же

Queue queue = new LinkedList();
ArrayList list = new ArrayList();
int i =0;
public Node findNextRightNode(Node root,int key)
{
    System.out.print("The breadth first search on Tree : \t");      
    if(root == null)
        return null;

    queue.clear();
    queue.add(root);

    while(!queue.isEmpty() )
    {
        Node node = (Node)queue.remove();
        System.out.print(node.data + " ");
        list.add(node);
        if(node.left != null) queue.add(node.left);
        if(node.right !=null) queue.add(node.right);            
    }

    Iterator iter = list.iterator();
    while(iter.hasNext())
        {
            if(((Node)iter.next()).data == key)
            {
                return ((Node)iter.next());
            }               
        }

    return null;
}

Ответ 7

void closestNode(Node root, int k , Node result) {
    if(root == null) 
    {
       return;      //currently result is null , so it  will be the result
    }
    if(result == null || Math.abs(root.data - k) < Math.abs(result.data - k) )
    {
      result == root;
    }
    if(k < root.data)
    {
    closestNode(root.left, k, result)
    } 
    else 
    {
        closestNode(root.right, k, result);
    }

}

Ответ 8

Ниже один работает с разными образцами, которые у меня есть.

public Node findNearest(Node root, int k) {
    if (root == null) {
        return null;
    }
    int minDiff = 0;
    Node minAt = root;
    minDiff = Math.abs(k - root.data);

    while (root != null) {
        if (k == root.data) {
            return root;
        }
        if (k < root.data) {
            minAt = updateMin(root, k, minDiff, minAt);
            root = root.left;
        } else if (k > root.data) {
            minAt = updateMin(root, k, minDiff, minAt);
            root = root.right;
        }

    }
    return minAt;
}

private Node updateMin(Node root, int k, int minDiff, Node minAt) {
    int curDif;
    curDif = Math.abs(k - root.data);
    if (curDif < minDiff) {
        minAt = root;
    }
    return minAt;
}

Ответ 9

Самое простое решение - вернуть свое дерево с тех пор, как

• вы найдете элемент
• вы достигаете листа. В этом случае вы должны сделать пару сравнений, чтобы определить, является ли ближайшее значение листом или родителем листа.

До вас реализация.