Finde die nächsten Knoten im binären Suchbaum

Question

Ich möchte eine Sammlung von Objekten haben, sortiert nach einer numerischen Eigenschaft, val. Ich möchte in der Lage sein, alle Objekte abzurufen, die übereinstimmen, wo val mit einem Wert übereinstimmt, zB x, oder wenn keine Objekte mit der Eigenschaft val übereinstimmen x, finden Sie die Objekte mit dem nächsten val über und unter x. (Mehrere Objekte können die gleichen Werte für val haben)

Eine der wenigen BST-Bibliotheken, die ich gefunden habe, ist dsjslib. Es hat, was es eine TreeMultiMap nennt, die mehrere Werte für einen einzelnen Schlüssel hält. Das Problem ist, ich kann nicht sehen, wie ich Knoten am nächsten zu x abrufen könnte, wenn es keine genauen Übereinstimmungen gibt.

Wie kann ich darüber gehen? Browser-Unterstützung für ES6 scheint weit zu kommen, also könnte ich vielleicht seine Map dafür verwenden?

Answer 1

Das klingt, als ob Sie nach binärer Suche sind. Ich hatte eine binäre findIndex Methode für Arrays entwickelt, die natürlich in sortierten Arrays funktioniert. Es erfolgt ein Rückruf und mit Hilfe dessen kann auch ein sortiertes Array von Objekten durchsucht werden. Da es binäre Suche ist, ist es viel schneller als die Standardmethoden findIndex oder indexOf.

Der Standard-Callback ist x => x, wodurch es standardmäßig sortierte Primitive behandelt, wenn kein Callback bereitgestellt wird. Mit dem aktuellen Status, wenn das gesuchte Objekt gefunden wird, gibt es seinen Index zurück, aber wenn nicht, wird -1 zurückgegeben. Wenn es gesucht wird, kann es leicht modifiziert werden, um die Indices der Nähe zurückzugeben. Ich kann das später hinzufügen, wenn Sie es wünschen.

Array.prototype.sortedFindIndex = function(val, cb = x => x) { // default callback for primitive arrays 
 
    var deli = this.length-1,         // delta index 
 
     base = 0;            // base to add the delta index 
 
    while (deli > 0 && cb(this[base + deli]) != val) { 
 
    deli = ~~(deli/2); 
 
    cb(this[base + deli]) < val && (base += deli); 
 
    } 
 
    return cb(this[base + deli]) === val ? base + deli : -1; 
 
}; 
 

 
arr = [{a:0,b:"foo"},{a:1,b:"bar"},{a:2,b:"baz"},{a:3,b:"qux"},{a:4,b:"fox"},{a:5,b:"pun"},{a:6,b:"alf"}], 
 
idx = arr.sortedFindIndex(4, o => o.a); 
 

 
console.log(idx);

Und hier ist eine modifizierte Version, die mehr Fehlerfälle geschickt behandelt. Wenn das gesuchte Objekt nicht gefunden werden kann, gibt das folgende Snippet einen negierten Wert des Index zurück, an dem er hätte existieren sollen. Schwieriger Teil. Es wird eine negative Null (-0) zurückgegeben, wenn der fehlende Gegenstand bei Index 0 eingefügt werden soll. Jetzt sollte es ein Kinderspiel sein, die obere und untere Nähe eines nicht vorhandenen Gegenstandes zu finden.

Array.prototype.sortedFindIndex = function(val, cb = x => x) { // default callback for primitive arrays 
 
    var   deli = this.length-1,       // delta index 
 
       base = 0,          // base to add the delta index 
 
     calculatedValue = cb(this[base + deli]),     // use callback and get the value 
 
      expectedAt = i => { while (this[i] !== void 0 && cb(this[i]) < val) ++i; 
 
           return -i}; 
 
    while (deli > 0 && calculatedValue != val) { 
 
    deli = ~~(deli/2); 
 
    (calculatedValue = cb(this[base + deli])) < val && (base += deli); 
 
    } 
 
    return calculatedValue === val ? base + deli : expectedAt(base + deli); 
 
}; 
 

 
arr = [{a:0,b:"foo"},{a:1,b:"bar"},{a:2,b:"baz"},{a:3,b:"qux"},{a:4,b:"fox"},{a:5,b:"pun"},{a:6,b:"alf"},{a:7,b:"alf"},{a:8,b:"alf"},{a:9,b:"alf"},{a:10,b:"alf"},{a:11,b:"alf"},{a:13,b:"alf"}], 
 
idx = arr.sortedFindIndex(12, o => o.a); 
 

 
console.log(idx);