{
  "name": "binary-search-tree",
  "version": "0.2.3",
  "author": {
    "name": "Louis Chatriot",
    "email": "louis.chatriot@gmail.com"
  },
  "description": "Different binary search tree implementations, including a self-balancing one (AVL)",
  "keywords": [
    "AVL tree",
    "binary search tree",
    "self-balancing",
    "AVL tree"
  ],
  "homepage": "https://github.com/louischatriot/node-binary-search-tree",
  "repository": {
    "type": "git",
    "url": "git@github.com:louischatriot/node-binary-search-tree.git"
  },
  "dependencies": {
    "underscore": "~1.4.4"
  },
  "devDependencies": {
    "chai": "1.0.x",
    "mocha": "1.4.x"
  },
  "scripts": {
    "test": "make test"
  },
  "main": "index",
  "licence": "MIT",
  "readme": "# Binary search trees for Node.js\n\nTwo implementations of binary search tree: <a href=\"http://en.wikipedia.org/wiki/Binary_search_tree\" target=\"_blank\">basic</a> and <a href=\"http://en.wikipedia.org/wiki/AVL_tree\" target=\"_blank\">AVL</a> (a kind of self-balancing binmary search tree). I wrote this module primarily to store indexes for <a href=\"https://github.com/louischatriot/nedb\" target=\"_blank\">NeDB</a> (a javascript dependency-less database).\n\n\n## Installation and tests\nPackage name is `binary-search-tree`.\n\n```bash\nnpm install binary-search-tree --save\n\nmake test\n```\n\n## Usage\nThe API mainly provides 3 functions: `insert`, `search` and `delete`. If you do not create a unique-type binary search tree, you can store multiple pieces of data for the same key. Doing so with a unique-type BST will result in an error being thrown. Data is always returned as an array, and you can delete all data relating to a given key, or just one piece of data.\n\n```javascript\nvar BinarySearchTree = require('binary-search-tree').BinarySearchTree\n  , AVLTree = require('binary-search-tree').AVLTree   // Same API as BinarySearchTree\n\n// Creating a binary search tree\nvar bst = new BinarySearchTree();\n\n// Inserting some data\nbst.insert(15, 'some data for key 15');\nbst.insert(12, 'something else');\nbst.insert(18, 'hello');\n\n// You can insert multiple pieces of data for the same key\n// if your tree doesn't enforce a unique constraint\nbst.insert(18, 'world');\n\n// Retrieving data (always returned as an array of all data stored for this key)\nbst.search(15);   // Equal to ['some data for key 15']\nbst.search(18);   // Equal to ['hello', 'world']\nbst.search(1);    // Equal to []\n\n// Search between bounds with a MongoDB-like query\n// Data is returned in key order\n// Note the difference between $lt (less than) and $gte (less than OR EQUAL)\nbst.betweenBounds({ $lt: 18, $gte: 12});   // Equal to ['something else', 'some data for key 15']\n\n// Deleting all the data relating to a key\nbst.delete(15);   // bst.search(15) will now give []\nbst.delete(18, 'world');   // bst.search(18) will now give ['hello']\n```\n\nThere are three optional parameters you can pass the BST constructor, allowing you to enforce a key-uniqueness constraint, use a custom function to compare keys and use a custom function to check whether values are equal. These parameters are all passed in an object.\n\n### Uniqueness\n\n```javascript\nvar bst = new BinarySearchTree({ unique: true });\nbst.insert(10, 'hello');\nbst.insert(10, 'world');   // Will throw an error\n```\n\n### Custom key comparison\n\n```javascript\n// Custom key comparison function\n// It needs to return a negative number if a is less than b,\n// a positive number if a is greater than b\n// and 0 if they are equal\n// If none is provided, the default one can compare numbers, dates and strings\n// which are the most common usecases\nfunction compareKeys (a, b) {\n  if (a.age < b.age) { return -1; }\n  if (a.age > b.age) { return 1; }\n  \n  return 0;\n}\n\n// Now we can use objects with an 'age' property as keys\nvar bst = new BinarySearchTree({ compareKeys: compareKeys });\nbst.insert({ age: 23 }, 'Mark');\nbst.insert({ age: 47 }, 'Franck');\n```\n\n### Custom value checking\n\n```javascript\n// Custom value equality checking function used when we try to just delete one piece of data\n// Returns true if a and b are considered the same, false otherwise\n// The default function is able to compare numbers and strings\nfunction checkValueEquality (a, b) {\n  return a.length === b.length;\n}\nvar bst = new BinarySearchTree({ checkValueEquality: checkValueEquality });\nbst.insert(10, 'hello');\nbst.insert(10, 'world');\nbst.insert(10, 'howdoyoudo');\n\nbst.delete(10, 'abcde');\nbst.search(10);   // Returns ['howdoyoudo']\n```\n\n\n## License \n\n(The MIT License)\n\nCopyright (c) 2013 Louis Chatriot &lt;louis.chatriot@gmail.com&gt;\n\nPermission is hereby granted, free of charge, to any person obtaining\na copy of this software and associated documentation files (the\n'Software'), to deal in the Software without restriction, including\nwithout limitation the rights to use, copy, modify, merge, publish,\ndistribute, sublicense, and/or sell copies of the Software, and to\npermit persons to whom the Software is furnished to do so, subject to\nthe following conditions:\n\nThe above copyright notice and this permission notice shall be\nincluded in all copies or substantial portions of the Software.\n\nTHE SOFTWARE IS PROVIDED 'AS IS', WITHOUT WARRANTY OF ANY KIND,\nEXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF\nMERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.\nIN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY\nCLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT,\nTORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE\nSOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.\n",
  "readmeFilename": "README.md",
  "bugs": {
    "url": "https://github.com/louischatriot/node-binary-search-tree/issues"
  },
  "_id": "binary-search-tree@0.2.3",
  "_shasum": "b76b362b40df435f6da165f5bd319aee36efdd76",
  "_from": "binary-search-tree@0.2.3",
  "_resolved": "https://registry.npmjs.org/binary-search-tree/-/binary-search-tree-0.2.3.tgz"
}
