Binary search tree
In computer science, binary search trees (BST), sometimes called ordered or sorted binary trees, are a particular type of container: data structures that store "items" (such as numbers, names etc.) in memory. By https://en.wikipedia.org/wiki/Binary_search_tree
The library was written in Typescript provides a binary tree data structure for storing or searching data.
NPM: https://www.npmjs.com/package/bst-lib
GIT: https://github.com/edwardconnect/binary-search-tree
Install
npm i bst-lib
Example
Define and instantiate some mock objects.
{ } var mockA = 1 'MockA';var mockB = 2 'MockB';var mockC = 3 'MockC';var mockD = 4 'MockD';var mockE = 5 'MockE';
Instantiate a Bst with type 'Mock'
var bst = new Bst<Mock>()
Insert mock object into bst
bst.insert(mockA.id, mockA);bst.insert(mockC.id, mockC);bst.insert(mockB.id, mockB);bst.insert(mockE.id, mockE);bst.insert(mockD.id, mockD);
Print the bst
bst.print();
/* Print result
5
4
3
2
1
*/
Properties
BstNode
Name | Description |
---|---|
id: string | number |
The id of bst node. The searching relies on comparing the value of id |
data: T |
Store the data with generic type |
left: Bst<T>() |
The left child node of this node |
right: Bst<T>() |
The right child node of this node |
Bst
Name | Description |
---|---|
private root: BstNode<T> = null |
Point to a BstNode if not null |
Methods
Name | Description |
---|---|
isEmpty(): boolean |
Whether the node is Bst point to null |
isContains(id: string | number): boolean |
Whether the bst contain data with target id |
getMaxId(): number | string | null |
Find the largest id |
getMinId(): number | string | null |
Find the smallest id |
getMaxData() :T |
Find the data with largest id |
getMinData() :T |
Find the data with smallest id |
searchDataById(id: number | string): T | null |
Find the data by target id. Return null if not found |
print(depth: number = 0) |
Print the tree in horizontally. (root on left and leafs on right) |
insert(id: string | number, data: T) |
Insert data into bst by inputting id of the data and data itself |
remove(id: string | number) |
Remove the data by id |