BinarySearchTree находит ближайшее значение, которое находится между определенными значениями - PullRequest
Новая
       24

BinarySearchTree находит ближайшее значение, которое находится между определенными значениями

0 голосов
/ 04 октября 2018

У меня есть Binary Search Tree, и мне нужно получить ближайший более высокий и ближайший нижний , а ближайший нижний должен быть между 5 и 9 (то есть либо выше 5, либониже, чем 9).

Допустим, у меня есть Node с идентификатором 125, ближайший более высокий номер к этому узлу равен 127, но он также должен быть между 5 и 9, поэтому«Узел» с идентификатором 130 будет тем, который я ищу.

Вот двоичное дерево, с которым я работаю:

enter image description here

Вот как я нахожу ближайший более высокий уровень в данный момент: 

Node currentNode = null;
int currentNodeID;
double min = Double.MAX_VALUE;    

public Node closestHigherValue(Node root, double target, int low, int high) {
    min = Double.MAX_VALUE;
    closestHigherHelper(root, target, low, high);

    if(currentNodeID < (int) target) return null;
    return currentNode;
}

public void closestHigherHelper(Node root, double target, int low, int high){
    if(root==null)
        return;

    if(Math.abs(root.ID - target) < min && root.ID >target){
        min = Math.abs(root.ID-target);
        currentNodeID = root.ID;
        //If between numbers
        if(root.ID >= low && root.ID <= high) currentNode = root;
    }

    if(target < root.ID){
        closestHigherHelper(root.leftChild, target, low, high);
    } else {
        closestHigherHelper(root.rightChild, target, low, high);
    }
}

Это работает до определенной точки. Здесь я добавляю все узлы, которые можно увидеть на Binary Tree picture, иначать поиск ближайших точек к определенным значениям, а затем, найдя их, удалить их.(Удалить работает нормально). 

BinaryTree binaryTree = new BinaryTree();
binaryTree.add(130);
...

int[] IDArray = new int[]{125, 100, 120, 130};
for (int i = 0; i < IDArray.length; i++) {
    Node closestHigher = binaryTree.closestHigherValue(binaryTree.root, IDArray[i], IDArray[i]+4, IDArray[i]+9);
    System.out.println("Searching for" + IDArray[i] + " and Closest Value = "+ closestHigher.getID());
    binaryTree.deleteNode(binaryTree.root, IDArray[i]);
        }

И это возвращает меня: 

Searching for 125 and Closest value = 130   //Should be 130
Searching for 100 and Closest value = null   //Should be null
Searching for 120 and Closest value = 125   //Should be 125
Searching for 130 and Closest value = 125   //Should be 135 -- This one goes wrong

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

Есть идеи?

1 Ответ

0 голосов
/ 06 октября 2018

Я думаю, что вы должны обновить min только если в пределах "границ", так что: 

 min = Math.abs(root.ID-target);
 currentNodeID = root.ID;
 //If between numbers
 if(root.ID >= low && root.ID <= high) currentNode = root;

должно быть 

 //If between numbers
 if(root.ID >= low && root.ID <= high){
    currentNode = root; 
    min = Math.abs(root.ID-target);
    currentNodeID = root.ID;
 }
...