@dstl-js/bst

Download

You can download the source code directly from the CDN and use it:

• https://unpkg.com/@dstl-js/bst/dist/index.js
• https://unpkg.com/@dstl-js/bst/dist/index.min.js

You can also install it directly using the package manager:

npm i @dstl-js/bst

pnpm add @dstl-js/bst

yarn add @dstl-js/bst

Usage

import { BSTree } from '@dstl-js/bst'

const bst = new BSTree<string>([
  [4, '4'],
  [3, '3'],
  [9, '9'],
  [7, '7'],
  [2, '2'],
  [8, '8'],
  [1, '1']
]);

bst.insert(5, '5');
console.log(bst.has(5)); // true
console.log(bst.prev(5)); // [4, '4']
console.log(bst.next(5)); // [7, '7']

for (const [k] of bst) console.log(k); // 1, 2, 3, 4, 5, 7, 8, 9

Iterable

The BSTree container is an iterable, you can use for...of loop, spread syntax, yield* keyword, and array deconstruction operate on container

Example

import { BSTree } from '@dstl-js/bst'

const bst = new BSTree<string>([
  [1, '1'],
  [2, '2'],
  [3, '3'],
  [4, '4'],
  [5, '5']
]);

// for...of
for (const [k, v] of bst) {
  //...
}

/**
 * spread syntax
 * [
     [1, '1'],
     [2, '2'],
     [3, '3'],
     [4, '4'],
     [5, '5']
 * ]
 */
const arr = [...bst];

// yield*
function* fn() {
  yield* bst;
}
const it = fn();
console.log(it.next().value); // [1, '1']

// array deconstruction
const [a, b, c, d, e] = bst;
console.log(a, b, c, d, e); // [1, '1'], [2, '2'], [3, '3'], [4, '4'], [5, '5']

API

Constructor

• new BSTree(iterable?: Iterable<[key: Key, value: T]>, comparer?: BSComparer<Key>, repeatable: boolaen = false) Create a bst container
  • parameters:
    • iterable? Accepts an iterable as the initial value of the container
    • comparer? This parameter is required when the type of key is not number
    • repeatable? Whether to allow duplicate key, overwrite old value if false

Attributes

• size: number Tree size
  
• isEmpty: boolean Whether the tree is empty
  
• depth: number Tree depth

Methods

• insert(value: T): this Insert element

  • parameters:
    • value: T The value to insert
  • return: this
    

• batchInsert(nodes: Iterable<[key: Key, value: T]>): this Batch insert element

  • parameters:
    • nodes: Iterable<[key: Key, value: T] Accepts an iterable containing a key-value pair
  • return: this
    

• find(key: Key): T | undefined Batch insert element

  • parameters:
    • key: Key To find the element key
  • return: Successful search return search results, failed search return undefined
    

• remove(key: Key | Key[]): [key: Key, value: T][] Batch insert element

  • parameters:
    • key: Key | Key[] The keys to delete the element
  • return: Delete the node array successfully
    

• forEach(callback: (value: T, key: Key) => void): void Traverse the tree using an left-root-right traversal, in the form of a callback

  • parameters:
    • callback: (value: T, key: Key) => void
      

• preorder(): Generator<[T, Key]> Returns a generator consisting of all nodes, in the form of root-left-right traversal
  

• inorder(): Generator<[T, Key]> Returns a generator consisting of all nodes, in the form of left-root-right traversal
  

• postorder(): Generator<[T, Key]> Returns a generator consisting of all nodes, in the form of left-right-root traversal
  

• sequence(): Generator<[T, Key]> Returns a generator consisting of all nodes, in the form of sequence traversal
  

• entries(): Generator<[T, Key]> Equivalent to the inorder function
  

• keys(): Generator<[T, Key]> Returns a generator consisting of all keys, in the form of left-root-right traversal
  

• values(): Generator<[T, Key]> Returns a generator consisting of all values, in the form of left-root-right traversal
  

• prev(key: Key): [T, Key] | null Get the precursor node

  • parameters:
    • key: Key
  • return: Return directly if the node has a precursor, or null if it does not.
    

• next(key: Key): [T, Key] | null Get the successor node

  • parameters:
    • key: Key
  • return: Return directly if the node has a successor, or null if it does not.
    

• min(): [T, Key] | null Get the node with the smallest key in the tree
  

• max(): [T, Key] | null Get the node with the largest key value in the tree
  

• has(key: Key): boolean Check whether the key exists

  • parameters:
    • key: Key
      

• clear(): this Clear tree