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

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

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

Answer 5

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

Answer 6

Вот рабочее решение в java, которое использует характеристики BST и дополнительное целое число для хранения минимальной разницы

public class ClosestValueBinaryTree {
        static int closestValue;

        public static void closestValueBST(Node22 node, int target) {
            if (node == null) {
                return;
            }
            if (node.data - target == 0) {
                closestValue = node.data;
                return;
            }
            if (Math.abs(node.data - target) < Math.abs(closestValue - target)) {
                closestValue = node.data;
            }
            if (node.data - target < 0) {
                closestValueBST(node.right, target);
            } else {
                closestValueBST(node.left, target);
            }
        }
    }

Сложность времени выполнения - O (logN) * ​​1004 *

Пространственно-временная сложность - O (1)

Answer 7

Вот полный код Java для поиска ближайшего элемента в BST.

        package binarytree;

        class BSTNode {
            BSTNode left,right;
            int data;

            public BSTNode(int data) {
                this.data = data;
                this.left = this.right = null;
            }
        }

        class BST {
            BSTNode root;

            public static BST createBST() {
                BST bst = new BST();
                bst.root = new BSTNode(9);
                bst.root.left = new BSTNode(4);
                bst.root.right = new BSTNode(17);

                bst.root.left.left = new BSTNode(3);
                bst.root.left.right= new BSTNode(6);

                bst.root.left.right.left= new BSTNode(5);
                bst.root.left.right.right= new BSTNode(7);

                bst.root.right.right = new BSTNode(22);
                bst.root.right.right.left = new BSTNode(20);

                return bst;
            }
        }

        public class ClosestElementInBST {
            public static void main(String[] args) {
                BST bst = BST.createBST();
                int target = 18;
                BSTNode currentClosest = null;
                BSTNode closestNode = findClosestElement(bst.root, target, currentClosest);

                if(closestNode != null) {
                    System.out.println("Found closest node: " + closestNode.data);
                }
                else {
                    System.out.println("Couldn't find closest node.");
                }
            }

            private static BSTNode findClosestElement(BSTNode node, int target, BSTNode currentClosest) {
                if(node == null) return currentClosest;

                if(currentClosest == null || 
                        (currentClosest != null && (Math.abs(currentClosest.data - target) > Math.abs(node.data - target)))) {
                    currentClosest = node;
                }

               if(node.data == target) return node;

                else if(target < node.data) {
                    return findClosestElement(node.left, target, currentClosest);
                }

                else { //target > node.data
                    currentClosest = node;
                    return findClosestElement(node.right, target, currentClosest);
                }
            }

        }

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

Answer 9

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

}

Answer 10

Это можно сделать с помощью 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;
}