tree-multiset-typed
v1.42.4TypeScript
Tree Multiset, AVLTree, BST, Binary Tree. Javascript & Typescript Data Structure.
Tree Multisettree multisettreemultisettree-multisetduplicate elementsduplicatenodenodeselementelements
0/weekUpdated 2 years agoMITUnpacked: 1.6 MB
Published by Tyler Zeng zrwusa@gmail.com
npm install tree-multiset-typed!NPM
!GitHub top language
!npm
!eslint
!npm package minimized gzipped size (select exports)
!npm bundle size
!npm
What
Brief
This is a standalone Tree Multiset data structure from the data-structure-typed collection. If you wish to access more
data structures or advanced features, you can transition to directly installing the
complete data-structure-typed package
How
install
$3
``bash`
npm i tree-multiset-typed --save
$3
`bash`
yarn add tree-multiset-typed
$3
$3
#### TS
`typescript
`
#### JS
`javascript
``
API docs & Examples
Data Structures
| Data Structure | Unit Test | Performance Test | API Documentation | Implemented |
|---|---|---|---|---|
| Binary Tree |  | | Binary Tree | |
| Binary Search Tree (BST) | | | BST | |
| AVL Tree | | | AVLTree | |
| Tree Multiset | | | TreeMultiset | |
| Segment Tree | SegmentTree | | ||
| Binary Indexed Tree | | BinaryIndexedTree | | |
| Graph | | | AbstractGraph | |
| Directed Graph | | | DirectedGraph | |
| Undirected Graph | | | UndirectedGraph | |
| Linked List | | | SinglyLinkedList | |
| Singly Linked List | | | SinglyLinkedList | |
| Doubly Linked List | | | DoublyLinkedList | |
| Queue | | | Queue | |
| Object Deque | | | ObjectDeque | |
| Array Deque | | | ArrayDeque | |
| Stack | | Stack | | |
| Hash | )) | ) | HashTable | ) | )
| Coordinate Set | CoordinateSet | | ||
| Coordinate Map | CoordinateMap | | ||
| Heap | | | Heap | |
| Priority Queue | | | PriorityQueue | |
| Max Priority Queue | | | MaxPriorityQueue | |
| Min Priority Queue | | | MinPriorityQueue | |
| Trie | | Trie | |
Why
Complexities
$3
| Big O Notation | Type | Computations for 10 elements | Computations for 100 elements | Computations for 1000 elements |
|---|---|---|---|---|
| O(1) | Constant | 1 | 1 | 1 |
| O(log N) | Logarithmic | 3 | 6 | 9 |
| O(N) | Linear | 10 | 100 | 1000 |
| O(N log N) | n log(n) | 30 | 600 | 9000 |
| O(N^2) | Quadratic | 100 | 10000 | 1000000 |
| O(2^N) | Exponential | 1024 | 1.26e+29 | 1.07e+301 |
| O(N!) | Factorial | 3628800 | 9.3e+157 | 4.02e+2567 |
$3
| Data Structure | Access | Search | Insertion | Deletion | Comments |
|---|---|---|---|---|---|
| Array | 1 | n | n | n | |
| Stack | n | n | 1 | 1 | |
| Queue | n | n | 1 | 1 | |
| Linked List | n | n | 1 | n | |
| Hash Table | - | n | n | n | In case of perfect hash function costs would be O(1) |
| Binary Search Tree | n | n | n | n | In case of balanced tree costs would be O(log(n)) |
| B-Tree | log(n) | log(n) | log(n) | log(n) | |
| Red-Black Tree | log(n) | log(n) | log(n) | log(n) | |
| AVL Tree | log(n) | log(n) | log(n) | log(n) | |
| Bloom Filter | - | 1 | 1 | - | False positives are possible while searching |
$3
| Name | Best | Average | Worst | Memory | Stable | Comments |
|---|---|---|---|---|---|---|
| Bubble sort | n | n2 | n2 | 1 | Yes | |
| Insertion sort | n | n2 | n2 | 1 | Yes | |
| Selection sort | n2 | n2 | n2 | 1 | No | |
| Heap sort | n log(n) | n log(n) | n log(n) | 1 | No | |
| Merge sort | n log(n) | n log(n) | n log(n) | n | Yes | |
| Quick sort | n log(n) | n log(n) | n2 | log(n) | No | Quicksort is usually done in-place with O(log(n)) stack space |
| Shell sort | n log(n) | depends on gap sequence | n (log(n))2 | 1 | No | |
| Counting sort | n + r | n + r | n + r | n + r | Yes | r - biggest number in array |
| Radix sort | n * k | n * k | n * k | n + k | Yes | k - length of longest key |
!complexities of data structures