Alle Schnittpunkte im Interval Binary Search Tree

Question

Also ich versuche, einen Algorithmus zu implementieren, um durch einen Intervall-Suchbaum zu gehen und alle Schnittpunkte zu finden. Ich konnte Knoten ohne Probleme erstellen und einfügen, aber der Algorithmus, den ich durch den Baum gehen muss, sucht derzeit nur nach einem Intervall, das das Abfrageintervall schneidet. Wenn beispielsweise (21, 23) als der Abfrageparameter übergeben wurde, würde der Baum den Knoten 16, 22 als eine Kreuzung finden, aber den Knoten, der sich derzeit rechts von dem Wurzelknoten befindet, außer Acht lassen. Irgendwelche Ideen, wie ich einen Algorithmus machen kann, um JEDEN Knoten zu finden, mit dem sich die Abfrage schneidet?

https://gist.github.com/anonymous/ce4e40e9d9e4af27d66690dcc16245a3

Aktualisierte Version, die für alle Kreuzungen

I-Knoten entfernen entschieden prüft, wenn sie in dem Algorithmus gefunden werden, die für eine Kreuzung überprüft, bis sie null zurück.

https://gist.github.com/DandroidDeveloper/009717551e3785cde48a53ffdeded7d1

function checkIntersection(interval, tree){ 
var currentNode = tree.root; 
var intersection = {}; 
while(currentNode){ 

    console.log("Searching...", currentNode); 
    if (currentNode.list.length > 0){ 
     for (var i = 0; i < currentNode.list.length; i++){ 
      if (interval[0] < currentNode.list[i].interval[1] && currentNode.list[i].interval[0] < interval[1]){ 
       intersection.interval = currentNode.list[i].interval; 
       intersection.id = currentNode.list[i].id; 
       tree.remove(currentNode.list[i].interval, currentNode.list[i].id); 
       return intersection; 
      } 
     } 
    } 
    if (interval[0] < currentNode.interval[1] && currentNode.interval[0] < interval[1]){ 
     console.log("INTERSECTION: "+interval, currentNode.interval); 
     intersection.interval = currentNode.interval; 
     intersection.id = currentNode.id; 
     tree.remove(currentNode.interval, currentNode.id); 
     return intersection; 
    } 
    if (!currentNode.left){ 
     console.log("NO NODE TO LEFT, GO RIGHT"); 
     if (!currentNode.right){ 
      console.log("NO MORE NODES"); 
      return null; 
     } 
     console.log(currentNode.right); 
     currentNode = currentNode.right; 
    } 
    else if (currentNode.left.max < interval[0]){ 
     console.log("LEFT MAX: "+currentNode.left.max+" < "+interval[0]+" GO RIGHT"); 
     currentNode = currentNode.right; 
    } 
    else{ 
     console.log("INTERVAL MAY BE TO LEFT, GO LEFT"); 
     currentNode = currentNode.left; 
    } 
} 
} 

function checkAllIntersections(interval, tree){ 
var intersections = []; 
var flag = true; 
while(flag){ 
    var temp = checkIntersection(interval, tree); 
    if (!temp){ 
     flag = false; 
    } 
    else{ 
     intersections.push(temp); 
    } 
} 
for (var i = 0; i < intersections.length; i++){ 
    tree.add(intersections[i].interval, intersections[i].id); 
} 
return intersections; 

}

Answer 1

Alles, was Sie tun müssen, ist ein Array von Objekten zu konstruieren, während über den Baum gehen und kehren das Array am Ende statt nur von der Rückkehr der ersten Sie finden. Hier ist der Code so verändert:

function checkIntersection(interval, tree){ 
var currentNode = tree.root; 
var intersection = {}; 
var intersections = []; //array to return multiple objects 
while(currentNode){ 

    console.log("Searching...", currentNode); 
    if (currentNode.list.length > 0){ 
     for (var i = 0; i < currentNode.list.length; i++){ 
      if (interval[0] < currentNode.list[i].interval[1] && currentNode.list[i].interval[0] < interval[1]){ 
       intersection.interval = currentNode.list[i].interval; 
       intersection.id = currentNode.list[i].id; 
       //---DELETE---tree.remove(currentNode.list[i].interval, currentNode.list[i].id); no need to remove 
       intersections.push(intersection); //add the newly found intersection to the returned array 
       intersection = {}; //prepare the variable for next find 
      } 
     } 
    } 
    if (interval[0] < currentNode.interval[1] && currentNode.interval[0] < interval[1]){ 
     console.log("INTERSECTION: "+interval, currentNode.interval); 
     intersection.interval = currentNode.interval; 
     intersection.id = currentNode.id; 
     //again no need to remove 
     intersections.push(intersection); 
     intersection = {}; 
    } 
    if (!currentNode.left){ 
     console.log("NO NODE TO LEFT, GO RIGHT"); 
     if (!currentNode.right){ 
      console.log("NO MORE NODES"); 
      return intersections; 
     } 
     console.log(currentNode.right); 
     currentNode = currentNode.right; 
    } 
    else if (currentNode.left.max < interval[0]){ 
     console.log("LEFT MAX: "+currentNode.left.max+" < "+interval[0]+" GO RIGHT"); 
     currentNode = currentNode.right; 
    } 
    else{ 
     console.log("INTERVAL MAY BE TO LEFT, GO LEFT"); 
     currentNode = currentNode.left; 
    } 
} 

Beachten Sie, dass dieser Code den ganzen Baum für jede Suche auch durchqueren, wenn die Schnitte nur in der äußersten linken Blatt des Baumes sind. Um dies zu ändern, können Sie am Ende Prüfungen hinzufügen (ähnlich wie bei der Prüfung, dass Sie jetzt keine Teilbäume mit zu niedrigen Maximalwerten erhalten), um Teilbäume mit zu hohen Mindestwerten für das abgefragte Intervall zu vermeiden:

if (interval[1] < currentNode.right.value){ //no intersections possible in the right subtree 
    return intersections; 
} else { 
    currentNode = currentNode.right; 
} 

gerade diese Schnipsel verwenden, wo immer Sie jetzt haben: currentNode = currentNode.right;