import { BinarySearchTree } from "https://dotland.deno.dev/std@0.181.0/collections/binary_search_tree.ts";
An unbalanced binary search tree. The values are in ascending order by default, using JavaScript's built-in comparison operators to sort the values.
For performance, it's recommended that you use a self-balancing binary search tree instead of this one unless you are extending this to create a self-balancing tree. See RedBlackTree for an example of how BinarySearchTree can be extended to create a self-balancing binary search tree.
| Method | Average Case | Worst Case |
|---|---|---|
| find(value) | O(log n) | O(n) |
| insert(value) | O(log n) | O(n) |
| remove(value) | O(log n) | O(n) |
| min() | O(log n) | O(n) |
| max() | O(log n) | O(n) |
Examples
Example 1
Example 1
import {
ascend,
BinarySearchTree,
descend,
} from "https://deno.land/std@0.181.0/collections/binary_search_tree.ts";
import { assertEquals } from "https://deno.land/std@0.181.0/testing/asserts.ts";
const values = [3, 10, 13, 4, 6, 7, 1, 14];
const tree = new BinarySearchTree<number>();
values.forEach((value) => tree.insert(value));
assertEquals([...tree], [1, 3, 4, 6, 7, 10, 13, 14]);
assertEquals(tree.min(), 1);
assertEquals(tree.max(), 14);
assertEquals(tree.find(42), null);
assertEquals(tree.find(7), 7);
assertEquals(tree.remove(42), false);
assertEquals(tree.remove(7), true);
assertEquals([...tree], [1, 3, 4, 6, 10, 13, 14]);
const invertedTree = new BinarySearchTree<number>(descend);
values.forEach((value) => invertedTree.insert(value));
assertEquals([...invertedTree], [14, 13, 10, 7, 6, 4, 3, 1]);
assertEquals(invertedTree.min(), 14);
assertEquals(invertedTree.max(), 1);
assertEquals(invertedTree.find(42), null);
assertEquals(invertedTree.find(7), 7);
assertEquals(invertedTree.remove(42), false);
assertEquals(invertedTree.remove(7), true);
assertEquals([...invertedTree], [14, 13, 10, 6, 4, 3, 1]);
const words = new BinarySearchTree<string>((a, b) =>
ascend(a.length, b.length) || ascend(a, b)
);
["truck", "car", "helicopter", "tank", "train", "suv", "semi", "van"]
.forEach((value) => words.insert(value));
assertEquals([...words], [
"car",
"suv",
"van",
"semi",
"tank",
"train",
"truck",
"helicopter",
]);
assertEquals(words.min(), "car");
assertEquals(words.max(), "helicopter");
assertEquals(words.find("scooter"), null);
assertEquals(words.find("tank"), "tank");
assertEquals(words.remove("scooter"), false);
assertEquals(words.remove("tank"), true);
assertEquals([...words], [
"car",
"suv",
"van",
"semi",
"train",
"truck",
"helicopter",
]);
Properties
Methods
Removes the given node, and returns the node that was physically removed from the tree.
Adds the value to the binary search tree if it does not already exist in it. Returns true if successful.
Returns an iterator that uses in-order (LNR) tree traversal for retrieving values from the binary search tree.
Returns an iterator that uses post-order (LRN) tree traversal for retrieving values from the binary search tree.
Returns an iterator that uses level order tree traversal for retrieving values from the binary search tree.
Returns an iterator that uses pre-order (NLR) tree traversal for retrieving values from the binary search tree.
Returns an iterator that uses reverse in-order (RNL) tree traversal for retrieving values from the binary search tree.
Returns an iterator that uses in-order (LNR) tree traversal for retrieving values from the binary search tree.
Static Methods
Creates a new binary search tree from an array like or iterable object.