在二叉搜索樹中查找最近的節點

Question

我想擁有一個對象的集合，按某個數值屬性val排序。我希望能夠檢索匹配val與某個值匹配的所有對象，例如x，或者如果沒有對象存在與屬性val匹配x，請找到最接近的val上方和下方的對象x。 （多個對象可能具有相同的值val）

我發現的幾個BST庫之一是dsjslib。它具有它所稱的TreeMultiMap，它爲單個密鑰保存多個值。問題是我看不到如何找到最接近x的節點，如果沒有完全匹配的話。

我該怎麼辦？對ES6的瀏覽器支持似乎要走很長的路了，所以也許我可以使用它的Map這個？

Answer 1

這聽起來像是在二分查找後。我開發了一個數組的二進制findIndex方法，它在排序的數組當中工作。它需要一個回調，並且在它的幫助下，還可以搜索排序的對象數組。由於它是二進制搜索，它比標準的findIndex或indexOf方法快得多。

默認回調是x => x，如果沒有提供回調，默認回調會默認處理已排序的基元。當它處於當前狀態時，如果它找到搜索的對象，它將返回它的索引，但如果不是，它將返回-1。如果搜索到它可以很容易地修改以返回鄰近指數。如果您需要，我可以稍後添加。

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

這裏是一個修改版本，其處理失敗的案例更巧妙。如果找不到搜索的項目，下面的代碼片段將返回它應該存在的索引的否定值。棘手的部分。如果將缺少的項目插入索引0，它將返回一個負的零（-0）。現在應該找到一個不存在的項目的上限和下限的小菜一碟。

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