@abtnode/binary-search-tree 中文文档教程

Question

Binary search trees for Node.js

这是 @louischatriot 的项目的分支，旨在发展项目并添加新功能。

二叉搜索树的两种实现：basic 和 AVL（一种自平衡二叉搜索树）。

Installation and tests

包名称是 binary-search-tree。

npm install @abtnode/binary-search-tree --save

make test

Usage

该API主要提供3个功能：insert、search和delete。 如果不创建唯一类型的二叉搜索树，则可以为同一个键存储多条数据。 使用唯一类型的 BST 这样做会导致抛出错误。 数据始终以数组形式返回，您可以删除与给定键相关的所有数据，或只删除一条数据。

插入的值可以是除 undefined 之外的任何值。

var BinarySearchTree = require('@abtnode/binary-search-tree').BinarySearchTree,
  AVLTree = require('@abtnode/binary-search-tree').AVLTree; // Same API as BinarySearchTree

// Creating a binary search tree
var bst = new BinarySearchTree();

// Inserting some data
bst.insert(15, 'some data for key 15');
bst.insert(12, 'something else');
bst.insert(18, 'hello');

// You can insert multiple pieces of data for the same key
// if your tree doesn't enforce a unique constraint
bst.insert(18, 'world');

// Retrieving data (always returned as an array of all data stored for this key)
bst.search(15); // Equal to ['some data for key 15']
bst.search(18); // Equal to ['hello', 'world']
bst.search(1); // Equal to []

// Search between bounds with a MongoDB-like query
// Data is returned in key order
// Note the difference between $lt (less than) and $gte (less than OR EQUAL)
bst.betweenBounds({ $lt: 18, $gte: 12 }); // Equal to ['something else', 'some data for key 15']

// Deleting all the data relating to a key
bst.delete(15); // bst.search(15) will now give []
bst.delete(18, 'world'); // bst.search(18) will now give ['hello']

您可以向 BST 构造函数传递三个可选参数，允许您强制执行键唯一性约束、使用自定义函数比较键以及使用自定义函数检查值是否相等。 这些参数都是在一个对象中传递的。

Browsing through all keys in the tree

您可以使用 searchAfter 和 searchBefore 浏览树中的所有键，如下所示：

// this assumes that each value in the BST includes 'key' attribute
var node = bst.search(bst.getMinKey());
for (; node.length > 0; node = bst.searchAfter(node[0].key)) {
  // do something with each node here
  // node is now an array of values, as with search()
}

您可以使用 getMinKey 和 getMaxKey 从开头或结尾开始，或者您也可以使用任何其他键值作为起点。

Finding the nearest key to a given key which may or may not be in the tree

您可以使用 searchNearest 查找最接近指定键的键和数据。

// Creating a binary search tree
var bst = new BinarySearchTree();

// Inserting some data
bst.insert(15, 'some data for key 15');
bst.insert(12, 'something else');
bst.insert(18, 'hello');

bst.searchNearest(20); // Equal to ['hello']
bst.searchNearest(13); // Equal to ['something else']

Uniqueness

var bst = new BinarySearchTree({ unique: true });
bst.insert(10, 'hello');
bst.insert(10, 'world'); // Will throw an error

Custom key comparison

// Custom key comparison function
// It needs to return the distance between the keys. Negative if
// a < b and positive if a > b
// If none is provided, the default one can compare numbers, dates and strings
// which are the most common usecases
function compareKeys(a, b) {
  return a.age - b.age;
}

// Now we can use objects with an 'age' property as keys
var bst = new BinarySearchTree({ compareKeys: compareKeys });
bst.insert({ age: 23 }, 'Mark');
bst.insert({ age: 47 }, 'Franck');

Custom value checking

// Custom value equality checking function used when we try to just delete one piece of data
// Returns true if a and b are considered the same, false otherwise
// The default function is able to compare numbers and strings
function checkValueEquality(a, b) {
  return a.length === b.length;
}
var bst = new BinarySearchTree({ checkValueEquality: checkValueEquality });
bst.insert(10, 'hello');
bst.insert(10, 'world');
bst.insert(10, 'howdoyoudo');

bst.delete(10, 'abcde');
bst.search(10); // Returns ['howdoyoudo']

License

（麻省理工学院许可证）

版权所有 (c) 2013 Louis Chatriot;

特此免费授予任何获得许可的人 此软件和相关文档文件的副本（ “软件”），不受限制地处理软件，包括 但不限于使用、复制、修改、合并、发布、 分发、再许可和/或出售软件的副本，以及 允许向其提供软件的人这样做，但须遵守 下列条件：

上述版权声明和本许可声明应 包含在软件的所有副本或重要部分中。

本软件按“原样”提供，不提供任何形式的保证， 明示或暗示的，包括但不限于 适销性、特定用途的适用性和非侵权性。 在任何情况下，作者或版权持有人均不对任何 索赔、损害赔偿或其他责任，无论是在合同行为中， 侵权行为或其他由以下原因引起、由其引起或与之相关的行为 软件或软件的使用或其他交易。