Socket
Socket
Sign inDemoInstall

directed-graph-typed

Package Overview
Dependencies
Maintainers
1
Versions
147
Alerts
File Explorer

Advanced tools

License
Socket logo

Install Socket

Detect and block malicious and high-risk dependencies

Install

directed-graph-typed - npm Package Compare versions

Comparing version 1.47.6 to 1.47.7

62

dist/data-structures/binary-tree/avl-tree.d.ts

@@ -9,4 +9,4 @@ /**

import { BST, BSTNode } from './bst';
import type { AVLTreeNested, AVLTreeNodeNested, AVLTreeOptions, BiTreeDeleteResult, BTNKey } from '../../types';
import { BTNCallback, IterableEntriesOrKeys } from '../../types';
import type { AVLTreeNested, AVLTreeNodeNested, AVLTreeOptions, BiTreeDeleteResult, BSTNodeKeyOrNode, BTNKey, BTNodeExemplar } from '../../types';
import { BTNCallback } from '../../types';
import { IBinaryTree } from '../../interfaces';

@@ -17,10 +17,23 @@ export declare class AVLTreeNode<V = any, N extends AVLTreeNode<V, N> = AVLTreeNodeNested<V>> extends BSTNode<V, N> {

}
/**
* 1. Height-Balanced: Each node's left and right subtrees differ in height by no more than one.
* 2. Automatic Rebalancing: AVL trees rebalance themselves automatically during insertions and deletions.
* 3. Rotations for Balancing: Utilizes rotations (single or double) to maintain balance after updates.
* 4. Order Preservation: Maintains the binary search tree property where left child values are less than the parent, and right child values are greater.
* 5. Efficient Lookups: Offers O(log n) search time, where 'n' is the number of nodes, due to its balanced nature.
* 6. Complex Insertions and Deletions: Due to rebalancing, these operations are more complex than in a regular BST.
* 7. Path Length: The path length from the root to any leaf is longer compared to an unbalanced BST, but shorter than a linear chain of nodes.
* 8. Memory Overhead: Stores balance factors (or heights) at each node, leading to slightly higher memory usage compared to a regular BST.
*/
export declare class AVLTree<V = any, N extends AVLTreeNode<V, N> = AVLTreeNode<V, AVLTreeNodeNested<V>>, TREE extends AVLTree<V, N, TREE> = AVLTree<V, N, AVLTreeNested<V, N>>> extends BST<V, N, TREE> implements IBinaryTree<V, N, TREE> {
/**
* This is a constructor function for an AVL tree data structure in TypeScript.
* @param {AVLTreeOptions} [options] - The `options` parameter is an optional object that can be passed to the
* constructor of the AVLTree class. It allows you to customize the behavior of the AVL tree by providing different
* options.
* The constructor function initializes an AVLTree object with optional elements and options.
* @param [elements] - The `elements` parameter is an optional iterable of `BTNodeExemplar<V, N>`
* objects. It represents a collection of elements that will be added to the AVL tree during
* initialization.
* @param [options] - The `options` parameter is an optional object that allows you to customize the
* behavior of the AVL tree. It is of type `Partial<AVLTreeOptions>`, which means that you can
* provide only a subset of the properties defined in the `AVLTreeOptions` interface.
*/
constructor(elements?: IterableEntriesOrKeys<V>, options?: Partial<AVLTreeOptions>);
constructor(elements?: Iterable<BTNodeExemplar<V, N>>, options?: Partial<AVLTreeOptions>);
/**

@@ -36,2 +49,9 @@ * The function creates a new AVL tree node with the specified key and value.

createNode(key: BTNKey, value?: V): N;
/**
* The function creates a new AVL tree with the specified options and returns it.
* @param {AVLTreeOptions} [options] - The `options` parameter is an optional object that can be
* passed to the `createTree` function. It is used to customize the behavior of the AVL tree that is
* being created.
* @returns a new AVLTree object.
*/
createTree(options?: AVLTreeOptions): TREE;

@@ -41,12 +61,14 @@ /**

* Space Complexity: O(1) - constant space, as it doesn't use additional data structures that scale with input size.
*/
/**
* Time Complexity: O(log n) - logarithmic time, where "n" is the number of nodes in the tree. The add method of the superclass (BST) has logarithmic time complexity.
* Space Complexity: O(1) - constant space, as it doesn't use additional data structures that scale with input size.
*
* The function overrides the add method of a class, adds a key-value pair to a data structure, and
* balances the structure if necessary.
* @param {BTNKey | N | null | undefined} keyOrNode - The `keyOrNode` parameter can be of type
* `BTNKey`, `N`, `null`, or `undefined`.
* @param {V} [value] - The `value` parameter is the value associated with the key that is being
* added to the binary search tree.
* @returns The method is returning either a node (N) or undefined.
* The function overrides the add method of a binary tree node and balances the tree after inserting
* a new node.
* @param keyOrNodeOrEntry - The parameter `keyOrNodeOrEntry` can be either a key, a node, or an
* entry.
* @returns The method is returning either the inserted node or `undefined`.
*/
add(keyOrNode: BTNKey | N | null | undefined, value?: V): N | undefined;
add(keyOrNodeOrEntry: BTNodeExemplar<V, N>): N | undefined;
/**

@@ -73,8 +95,3 @@ * Time Complexity: O(log n) - logarithmic time, where "n" is the number of nodes in the tree. The add method of the superclass (BST) has logarithmic time complexity.

/**
* Time Complexity: O(log n) - logarithmic time, where "n" is the number of nodes in the tree. The delete method of the superclass (BST) has logarithmic time complexity.
* Space Complexity: O(1) - constant space, as it doesn't use additional data structures that scale with input size.
*/
init(elements: IterableEntriesOrKeys<V>): void;
/**
* The `_swap` function swaps the key, value, and height properties between two nodes in a binary
* The `_swapProperties` function swaps the key, value, and height properties between two nodes in a binary
* tree.

@@ -88,3 +105,3 @@ * @param {BTNKey | N | undefined} srcNode - The `srcNode` parameter represents the source node that

*/
protected _swap(srcNode: BTNKey | N | undefined, destNode: BTNKey | N | undefined): N | undefined;
protected _swapProperties(srcNode: BSTNodeKeyOrNode<N>, destNode: BSTNodeKeyOrNode<N>): N | undefined;
/**

@@ -179,2 +196,3 @@ * Time Complexity: O(1) - constant time, as it performs a fixed number of operations.

protected _balanceRL(A: N): void;
protected _replaceNode(oldNode: N, newNode: N): N;
}

81

dist/data-structures/binary-tree/avl-tree.js

@@ -19,8 +19,21 @@ "use strict";

exports.AVLTreeNode = AVLTreeNode;
/**
* 1. Height-Balanced: Each node's left and right subtrees differ in height by no more than one.
* 2. Automatic Rebalancing: AVL trees rebalance themselves automatically during insertions and deletions.
* 3. Rotations for Balancing: Utilizes rotations (single or double) to maintain balance after updates.
* 4. Order Preservation: Maintains the binary search tree property where left child values are less than the parent, and right child values are greater.
* 5. Efficient Lookups: Offers O(log n) search time, where 'n' is the number of nodes, due to its balanced nature.
* 6. Complex Insertions and Deletions: Due to rebalancing, these operations are more complex than in a regular BST.
* 7. Path Length: The path length from the root to any leaf is longer compared to an unbalanced BST, but shorter than a linear chain of nodes.
* 8. Memory Overhead: Stores balance factors (or heights) at each node, leading to slightly higher memory usage compared to a regular BST.
*/
class AVLTree extends bst_1.BST {
/**
* This is a constructor function for an AVL tree data structure in TypeScript.
* @param {AVLTreeOptions} [options] - The `options` parameter is an optional object that can be passed to the
* constructor of the AVLTree class. It allows you to customize the behavior of the AVL tree by providing different
* options.
* The constructor function initializes an AVLTree object with optional elements and options.
* @param [elements] - The `elements` parameter is an optional iterable of `BTNodeExemplar<V, N>`
* objects. It represents a collection of elements that will be added to the AVL tree during
* initialization.
* @param [options] - The `options` parameter is an optional object that allows you to customize the
* behavior of the AVL tree. It is of type `Partial<AVLTreeOptions>`, which means that you can
* provide only a subset of the properties defined in the `AVLTreeOptions` interface.
*/

@@ -30,3 +43,3 @@ constructor(elements, options) {

if (elements)
this.init(elements);
super.addMany(elements);
}

@@ -45,2 +58,9 @@ /**

}
/**
* The function creates a new AVL tree with the specified options and returns it.
* @param {AVLTreeOptions} [options] - The `options` parameter is an optional object that can be
* passed to the `createTree` function. It is used to customize the behavior of the AVL tree that is
* being created.
* @returns a new AVLTree object.
*/
createTree(options) {

@@ -52,15 +72,17 @@ return new AVLTree([], Object.assign({ iterationType: this.iterationType, comparator: this.comparator }, options));

* Space Complexity: O(1) - constant space, as it doesn't use additional data structures that scale with input size.
*/
/**
* Time Complexity: O(log n) - logarithmic time, where "n" is the number of nodes in the tree. The add method of the superclass (BST) has logarithmic time complexity.
* Space Complexity: O(1) - constant space, as it doesn't use additional data structures that scale with input size.
*
* The function overrides the add method of a class, adds a key-value pair to a data structure, and
* balances the structure if necessary.
* @param {BTNKey | N | null | undefined} keyOrNode - The `keyOrNode` parameter can be of type
* `BTNKey`, `N`, `null`, or `undefined`.
* @param {V} [value] - The `value` parameter is the value associated with the key that is being
* added to the binary search tree.
* @returns The method is returning either a node (N) or undefined.
* The function overrides the add method of a binary tree node and balances the tree after inserting
* a new node.
* @param keyOrNodeOrEntry - The parameter `keyOrNodeOrEntry` can be either a key, a node, or an
* entry.
* @returns The method is returning either the inserted node or `undefined`.
*/
add(keyOrNode, value) {
if (keyOrNode === null)
add(keyOrNodeOrEntry) {
if (keyOrNodeOrEntry === null)
return undefined;
const inserted = super.add(keyOrNode, value);
const inserted = super.add(keyOrNodeOrEntry);
if (inserted)

@@ -101,20 +123,3 @@ this._balancePath(inserted);

/**
* Time Complexity: O(log n) - logarithmic time, where "n" is the number of nodes in the tree. The delete method of the superclass (BST) has logarithmic time complexity.
* Space Complexity: O(1) - constant space, as it doesn't use additional data structures that scale with input size.
*/
init(elements) {
if (elements) {
for (const entryOrKey of elements) {
if (Array.isArray(entryOrKey)) {
const [key, value] = entryOrKey;
this.add(key, value);
}
else {
this.add(entryOrKey);
}
}
}
}
/**
* The `_swap` function swaps the key, value, and height properties between two nodes in a binary
* The `_swapProperties` function swaps the key, value, and height properties between two nodes in a binary
* tree.

@@ -128,5 +133,5 @@ * @param {BTNKey | N | undefined} srcNode - The `srcNode` parameter represents the source node that

*/
_swap(srcNode, destNode) {
srcNode = this.ensureNotKey(srcNode);
destNode = this.ensureNotKey(destNode);
_swapProperties(srcNode, destNode) {
srcNode = this.ensureNode(srcNode);
destNode = this.ensureNode(destNode);
if (srcNode && destNode) {

@@ -442,3 +447,7 @@ const { key, value, height } = destNode;

}
_replaceNode(oldNode, newNode) {
newNode.height = oldNode.height;
return super._replaceNode(oldNode, newNode);
}
}
exports.AVLTree = AVLTree;

216

dist/data-structures/binary-tree/binary-tree.d.ts

@@ -8,4 +8,4 @@ /**

*/
import type { BinaryTreeNodeNested, BinaryTreeOptions, BTNCallback, BTNKey } from '../../types';
import { BinaryTreeNested, BinaryTreePrintOptions, BiTreeDeleteResult, DFSOrderPattern, FamilyPosition, IterableEntriesOrKeys, IterationType, NodeDisplayLayout } from '../../types';
import type { BinaryTreeNodeNested, BinaryTreeOptions, BTNCallback, BTNKey, BTNodeEntry, BTNodeExemplar, BTNodeKeyOrNode } from '../../types';
import { BinaryTreeNested, BinaryTreePrintOptions, BiTreeDeleteResult, DFSOrderPattern, FamilyPosition, IterationType, NodeDisplayLayout } from '../../types';
import { IBinaryTree } from '../../interfaces';

@@ -18,39 +18,11 @@ /**

export declare class BinaryTreeNode<V = any, N extends BinaryTreeNode<V, N> = BinaryTreeNode<V, BinaryTreeNodeNested<V>>> {
/**
* The key associated with the node.
*/
key: BTNKey;
/**
* The value stored in the node.
*/
value?: V;
/**
* The parent node of the current node.
*/
parent?: N | null;
/**
* Creates a new instance of BinaryTreeNode.
* @param {BTNKey} key - The key associated with the node.
* @param {V} value - The value stored in the node.
*/
parent?: N;
constructor(key: BTNKey, value?: V);
protected _left?: N | null;
/**
* Get the left child node.
*/
get left(): N | null | undefined;
/**
* Set the left child node.
* @param {N | null | undefined} v - The left child node.
*/
set left(v: N | null | undefined);
protected _right?: N | null;
/**
* Get the right child node.
*/
get right(): N | null | undefined;
/**
* Set the right child node.
* @param {N | null | undefined} v - The right child node.
*/
set right(v: N | null | undefined);

@@ -64,4 +36,11 @@ /**

/**
* Represents a binary tree data structure.
* @template N - The type of the binary tree's nodes.
* 1. Two Children Maximum: Each node has at most two children.
* 2. Left and Right Children: Nodes have distinct left and right children.
* 3. Depth and Height: Depth is the number of edges from the root to a node; height is the maximum depth in the tree.
* 4. Subtrees: Each child of a node forms the root of a subtree.
* 5. Leaf Nodes: Nodes without children are leaves.
* 6. Internal Nodes: Nodes with at least one child are internal.
* 7. Balanced Trees: The heights of the left and right subtrees of any node differ by no more than one.
* 8. Full Trees: Every node has either 0 or 2 children.
* 9. Complete Trees: All levels are fully filled except possibly the last, filled from left to right.
*/

@@ -71,15 +50,14 @@ export declare class BinaryTree<V = any, N extends BinaryTreeNode<V, N> = BinaryTreeNode<V, BinaryTreeNodeNested<V>>, TREE extends BinaryTree<V, N, TREE> = BinaryTree<V, N, BinaryTreeNested<V, N>>> implements IBinaryTree<V, N, TREE> {

/**
* Creates a new instance of BinaryTree.
* @param {BinaryTreeOptions} [options] - The options for the binary tree.
* The constructor function initializes a binary tree object with optional elements and options.
* @param [elements] - An optional iterable of BTNodeExemplar objects. These objects represent the
* elements to be added to the binary tree.
* @param [options] - The `options` parameter is an optional object that can contain additional
* configuration options for the binary tree. In this case, it is of type
* `Partial<BinaryTreeOptions>`, which means that not all properties of `BinaryTreeOptions` are
* required.
*/
constructor(elements?: IterableEntriesOrKeys<V>, options?: Partial<BinaryTreeOptions>);
constructor(elements?: Iterable<BTNodeExemplar<V, N>>, options?: Partial<BinaryTreeOptions>);
protected _root?: N | null;
/**
* Get the root node of the binary tree.
*/
get root(): N | null | undefined;
protected _size: number;
/**
* Get the number of nodes in the binary tree.
*/
get size(): number;

@@ -93,19 +71,32 @@ /**

createNode(key: BTNKey, value?: V): N;
/**
* The function creates a binary tree with the given options.
* @param [options] - The `options` parameter is an optional object that allows you to customize the
* behavior of the `BinaryTree` class. It is of type `Partial<BinaryTreeOptions>`, which means that
* you can provide only a subset of the properties defined in the `BinaryTreeOptions` interface.
* @returns a new instance of a binary tree.
*/
createTree(options?: Partial<BinaryTreeOptions>): TREE;
/**
* Time Complexity: O(n)
* Space Complexity: O(1)
* The function checks if a given value is an entry in a binary tree node.
* @param kne - BTNodeExemplar<V, N> - A generic type representing a node in a binary tree. It has
* two type parameters V and N, representing the value and node type respectively.
* @returns a boolean value.
*/
isEntry(kne: BTNodeExemplar<V, N>): kne is BTNodeEntry<V>;
/**
* Time Complexity O(log n) - O(n)
* Space Complexity O(1)
*/
/**
* Time Complexity O(log n) - O(n)
* Space Complexity O(1)
*
* The `add` function adds a new node with a key and value to a binary tree, or updates the value of
* an existing node with the same key.
* @param {BTNKey | N | null | undefined} keyOrNode - The `keyOrNode` parameter can be one of the
* following types:
* @param {V} [value] - The value to be associated with the key or node being added to the binary
* tree.
* @returns The function `add` returns a node (`N`) if it was successfully inserted into the binary
* tree, or `null` or `undefined` if the insertion was not successful.
* The `add` function adds a new node to a binary tree, either by key or by providing a node object.
* @param keyOrNodeOrEntry - The parameter `keyOrNodeOrEntry` can be one of the following:
* @returns The function `add` returns the inserted node (`N`), `null`, or `undefined`.
*/
add(keyOrNode: BTNKey | N | null | undefined, value?: V): N | null | undefined;
add(keyOrNodeOrEntry: BTNodeExemplar<V, N>): N | null | undefined;
/**
* Time Complexity: O(n)
* Time Complexity: O(k log n) - O(k * n)
* Space Complexity: O(1)

@@ -115,16 +106,13 @@ * Comments: The time complexity for adding a node depends on the depth of the tree. In the best case (when the tree is empty), it's O(1). In the worst case (when the tree is a degenerate tree), it's O(n). The space complexity is constant.

/**
* Time Complexity: O(k * n) "n" is the number of nodes in the tree, and "k" is the number of keys to be inserted.
* Time Complexity: O(k log n) - O(k * n)
* Space Complexity: O(1)
*
* The `addMany` function takes an array of keys or nodes and an optional array of values, and adds
* each key-value pair to a data structure.
* @param {(BTNKey | N |null | undefined)[]} keysOrNodes - An array of keys or nodes to be added to
* the binary search tree. Each element can be of type `BTNKey` (a key value), `N` (a node), `null`,
* or `undefined`.
* @param {(V | undefined)[]} [values] - The `values` parameter is an optional array of values that
* correspond to the keys or nodes being added. If provided, the values will be associated with the
* keys or nodes during the add operation.
* @returns The function `addMany` returns an array of `N`, `null`, or `undefined` values.
* The function `addMany` takes in an iterable of `BTNodeExemplar` objects, adds each object to the
* current instance, and returns an array of the inserted nodes.
* @param nodes - The `nodes` parameter is an iterable (such as an array or a set) of
* `BTNodeExemplar<V, N>` objects.
* @returns The function `addMany` returns an array of values, where each value is either of type
* `N`, `null`, or `undefined`.
*/
addMany(keysOrNodes: (BTNKey | N | null | undefined)[], values?: (V | undefined)[]): (N | null | undefined)[];
addMany(nodes: Iterable<BTNodeExemplar<V, N>>): (N | null | undefined)[];
/**

@@ -138,11 +126,7 @@ * Time Complexity: O(k * n) "n" is the number of nodes in the tree, and "k" is the number of keys to be inserted.

*
* The `refill` function clears the binary tree and adds multiple nodes with the given IDs or nodes and optional data.
* @param {(BTNKey | N)[]} keysOrNodes - The `keysOrNodes` parameter is an array that can contain either
* `BTNKey` or `N` values.
* @param {N[] | Array<V>} [values] - The `data` parameter is an optional array of values that will be assigned to
* the nodes being added. If provided, the length of the `data` array should be equal to the length of the `keysOrNodes`
* array. Each value in the `data` array will be assigned to the
* @returns The method is returning a boolean value.
* The `refill` function clears the current collection and adds new nodes, keys, or entries to it.
* @param nodesOrKeysOrEntries - The parameter `nodesOrKeysOrEntries` is an iterable object that can
* contain either `BTNodeExemplar` objects, keys, or entries.
*/
refill(keysOrNodes: (BTNKey | N | null | undefined)[], values?: (V | undefined)[]): boolean;
refill(nodesOrKeysOrEntries: Iterable<BTNodeExemplar<V, N>>): void;
/**

@@ -172,3 +156,3 @@ * Time Complexity: O(k * n) "n" is the number of nodes in the tree, and "k" is the number of keys to be inserted.

*/
getDepth(distNode: BTNKey | N | null | undefined, beginRoot?: BTNKey | N | null | undefined): number;
getDepth(distNode: BTNodeKeyOrNode<N>, beginRoot?: BTNodeKeyOrNode<N>): number;
/**

@@ -192,3 +176,3 @@ * Time Complexity: O(n)

*/
getHeight(beginRoot?: BTNKey | N | null | undefined, iterationType?: IterationType): number;
getHeight(beginRoot?: BTNodeKeyOrNode<N>, iterationType?: IterationType): number;
/**

@@ -212,3 +196,3 @@ * Time Complexity: O(n)

*/
getMinHeight(beginRoot?: BTNKey | N | null | undefined, iterationType?: IterationType): number;
getMinHeight(beginRoot?: BTNodeKeyOrNode<N>, iterationType?: IterationType): number;
/**

@@ -230,3 +214,3 @@ * Time Complexity: O(n)

*/
isPerfectlyBalanced(beginRoot?: BTNKey | N | null | undefined): boolean;
isPerfectlyBalanced(beginRoot?: BTNodeKeyOrNode<N>): boolean;
/**

@@ -236,5 +220,5 @@ * Time Complexity: O(n)

*/
getNodes<C extends BTNCallback<N, BTNKey>>(identifier: BTNKey, callback?: C, onlyOne?: boolean, beginRoot?: BTNKey | N | null | undefined, iterationType?: IterationType): N[];
getNodes<C extends BTNCallback<N, N>>(identifier: N | null | undefined, callback?: C, onlyOne?: boolean, beginRoot?: BTNKey | N | null | undefined, iterationType?: IterationType): N[];
getNodes<C extends BTNCallback<N>>(identifier: ReturnType<C>, callback: C, onlyOne?: boolean, beginRoot?: BTNKey | N | null | undefined, iterationType?: IterationType): N[];
getNodes<C extends BTNCallback<N, BTNKey>>(identifier: BTNKey, callback?: C, onlyOne?: boolean, beginRoot?: BTNodeKeyOrNode<N>, iterationType?: IterationType): N[];
getNodes<C extends BTNCallback<N, N>>(identifier: N | null | undefined, callback?: C, onlyOne?: boolean, beginRoot?: BTNodeKeyOrNode<N>, iterationType?: IterationType): N[];
getNodes<C extends BTNCallback<N>>(identifier: ReturnType<C>, callback: C, onlyOne?: boolean, beginRoot?: BTNodeKeyOrNode<N>, iterationType?: IterationType): N[];
/**

@@ -244,5 +228,5 @@ * Time Complexity: O(n)

*/
has<C extends BTNCallback<N, BTNKey>>(identifier: BTNKey, callback?: C, beginRoot?: BTNKey | N | null | undefined, iterationType?: IterationType): boolean;
has<C extends BTNCallback<N, N>>(identifier: N | null | undefined, callback?: C, beginRoot?: BTNKey | N | null | undefined, iterationType?: IterationType): boolean;
has<C extends BTNCallback<N>>(identifier: ReturnType<C> | null | undefined, callback: C, beginRoot?: BTNKey | N | null | undefined, iterationType?: IterationType): boolean;
has<C extends BTNCallback<N, BTNKey>>(identifier: BTNKey, callback?: C, beginRoot?: BTNodeKeyOrNode<N>, iterationType?: IterationType): boolean;
has<C extends BTNCallback<N, N>>(identifier: N | null | undefined, callback?: C, beginRoot?: BTNodeKeyOrNode<N>, iterationType?: IterationType): boolean;
has<C extends BTNCallback<N>>(identifier: ReturnType<C> | null | undefined, callback: C, beginRoot?: BTNodeKeyOrNode<N>, iterationType?: IterationType): boolean;
/**

@@ -252,5 +236,5 @@ * Time Complexity: O(n)

*/
getNode<C extends BTNCallback<N, BTNKey>>(identifier: BTNKey, callback?: C, beginRoot?: BTNKey | N | null | undefined, iterationType?: IterationType): N | null | undefined;
getNode<C extends BTNCallback<N, N>>(identifier: N | null | undefined, callback?: C, beginRoot?: BTNKey | N | null | undefined, iterationType?: IterationType): N | null | undefined;
getNode<C extends BTNCallback<N>>(identifier: ReturnType<C>, callback: C, beginRoot?: BTNKey | N | null | undefined, iterationType?: IterationType): N | null | undefined;
getNode<C extends BTNCallback<N, BTNKey>>(identifier: BTNKey, callback?: C, beginRoot?: BTNodeKeyOrNode<N>, iterationType?: IterationType): N | null | undefined;
getNode<C extends BTNCallback<N, N>>(identifier: N | null | undefined, callback?: C, beginRoot?: BTNodeKeyOrNode<N>, iterationType?: IterationType): N | null | undefined;
getNode<C extends BTNCallback<N>>(identifier: ReturnType<C>, callback: C, beginRoot?: BTNodeKeyOrNode<N>, iterationType?: IterationType): N | null | undefined;
/**

@@ -280,3 +264,3 @@ * Time Complexity: O(n)

/**
* The function `ensureNotKey` returns the node corresponding to the given key if it is a valid node
* The function `ensureNode` returns the node corresponding to the given key if it is a valid node
* key, otherwise it returns the key itself.

@@ -291,6 +275,6 @@ * @param {BTNKey | N | null | undefined} key - The `key` parameter can be of type `BTNKey`, `N`,

*/
ensureNotKey(key: BTNKey | N | null | undefined, iterationType?: IterationType): N | null | undefined;
get<C extends BTNCallback<N, BTNKey>>(identifier: BTNKey, callback?: C, beginRoot?: BTNKey | N | null | undefined, iterationType?: IterationType): V | undefined;
get<C extends BTNCallback<N, N>>(identifier: N | null | undefined, callback?: C, beginRoot?: BTNKey | N | null | undefined, iterationType?: IterationType): V | undefined;
get<C extends BTNCallback<N>>(identifier: ReturnType<C>, callback: C, beginRoot?: BTNKey | N | null | undefined, iterationType?: IterationType): V | undefined;
ensureNode(key: BTNodeKeyOrNode<N>, iterationType?: IterationType): N | null | undefined;
get<C extends BTNCallback<N, BTNKey>>(identifier: BTNKey, callback?: C, beginRoot?: BTNodeKeyOrNode<N>, iterationType?: IterationType): V | undefined;
get<C extends BTNCallback<N, N>>(identifier: N | null | undefined, callback?: C, beginRoot?: BTNodeKeyOrNode<N>, iterationType?: IterationType): V | undefined;
get<C extends BTNCallback<N>>(identifier: ReturnType<C>, callback: C, beginRoot?: BTNodeKeyOrNode<N>, iterationType?: IterationType): V | undefined;
/**

@@ -323,3 +307,3 @@ * Time Complexity: O(n)

*/
getPathToRoot(beginRoot: BTNKey | N | null | undefined, isReverse?: boolean): N[];
getPathToRoot(beginRoot: BTNodeKeyOrNode<N>, isReverse?: boolean): N[];
/**

@@ -343,3 +327,3 @@ * Time Complexity: O(log n)

*/
getLeftMost(beginRoot?: BTNKey | N | null | undefined, iterationType?: IterationType): N | null | undefined;
getLeftMost(beginRoot?: BTNodeKeyOrNode<N>, iterationType?: IterationType): N | null | undefined;
/**

@@ -364,3 +348,3 @@ * Time Complexity: O(log n)

*/
getRightMost(beginRoot?: BTNKey | N | null | undefined, iterationType?: IterationType): N | null | undefined;
getRightMost(beginRoot?: BTNodeKeyOrNode<N>, iterationType?: IterationType): N | null | undefined;
/**

@@ -382,3 +366,3 @@ * Time Complexity: O(log n)

*/
isSubtreeBST(beginRoot: BTNKey | N | null | undefined, iterationType?: IterationType): boolean;
isSubtreeBST(beginRoot: BTNodeKeyOrNode<N>, iterationType?: IterationType): boolean;
/**

@@ -404,5 +388,5 @@ * Time Complexity: O(n)

*/
subTreeTraverse<C extends BTNCallback<N>>(callback?: C, beginRoot?: BTNKey | N | null | undefined, iterationType?: IterationType, includeNull?: false): ReturnType<C>[];
subTreeTraverse<C extends BTNCallback<N>>(callback?: C, beginRoot?: BTNKey | N | null | undefined, iterationType?: IterationType, includeNull?: undefined): ReturnType<C>[];
subTreeTraverse<C extends BTNCallback<N | null | undefined>>(callback?: C, beginRoot?: BTNKey | N | null | undefined, iterationType?: IterationType, includeNull?: true): ReturnType<C>[];
subTreeTraverse<C extends BTNCallback<N>>(callback?: C, beginRoot?: BTNodeKeyOrNode<N>, iterationType?: IterationType, includeNull?: false): ReturnType<C>[];
subTreeTraverse<C extends BTNCallback<N>>(callback?: C, beginRoot?: BTNodeKeyOrNode<N>, iterationType?: IterationType, includeNull?: undefined): ReturnType<C>[];
subTreeTraverse<C extends BTNCallback<N | null | undefined>>(callback?: C, beginRoot?: BTNodeKeyOrNode<N>, iterationType?: IterationType, includeNull?: true): ReturnType<C>[];
/**

@@ -438,5 +422,5 @@ * Time complexity: O(n)

isNodeKey(potentialKey: any): potentialKey is number;
dfs<C extends BTNCallback<N>>(callback?: C, pattern?: DFSOrderPattern, beginRoot?: BTNKey | N | null | undefined, iterationType?: IterationType, includeNull?: false): ReturnType<C>[];
dfs<C extends BTNCallback<N>>(callback?: C, pattern?: DFSOrderPattern, beginRoot?: BTNKey | N | null | undefined, iterationType?: IterationType, includeNull?: undefined): ReturnType<C>[];
dfs<C extends BTNCallback<N | null | undefined>>(callback?: C, pattern?: DFSOrderPattern, beginRoot?: BTNKey | N | null | undefined, iterationType?: IterationType, includeNull?: true): ReturnType<C>[];
dfs<C extends BTNCallback<N>>(callback?: C, pattern?: DFSOrderPattern, beginRoot?: BTNodeKeyOrNode<N>, iterationType?: IterationType, includeNull?: false): ReturnType<C>[];
dfs<C extends BTNCallback<N>>(callback?: C, pattern?: DFSOrderPattern, beginRoot?: BTNodeKeyOrNode<N>, iterationType?: IterationType, includeNull?: undefined): ReturnType<C>[];
dfs<C extends BTNCallback<N | null | undefined>>(callback?: C, pattern?: DFSOrderPattern, beginRoot?: BTNodeKeyOrNode<N>, iterationType?: IterationType, includeNull?: true): ReturnType<C>[];
/**

@@ -446,5 +430,5 @@ * Time complexity: O(n)

*/
bfs<C extends BTNCallback<N>>(callback?: C, beginRoot?: BTNKey | N | null | undefined, iterationType?: IterationType, includeNull?: false): ReturnType<C>[];
bfs<C extends BTNCallback<N>>(callback?: C, beginRoot?: BTNKey | N | null | undefined, iterationType?: IterationType, includeNull?: undefined): ReturnType<C>[];
bfs<C extends BTNCallback<N | null | undefined>>(callback?: C, beginRoot?: BTNKey | N | null | undefined, iterationType?: IterationType, includeNull?: true): ReturnType<C>[];
bfs<C extends BTNCallback<N>>(callback?: C, beginRoot?: BTNodeKeyOrNode<N>, iterationType?: IterationType, includeNull?: false): ReturnType<C>[];
bfs<C extends BTNCallback<N>>(callback?: C, beginRoot?: BTNodeKeyOrNode<N>, iterationType?: IterationType, includeNull?: undefined): ReturnType<C>[];
bfs<C extends BTNCallback<N | null | undefined>>(callback?: C, beginRoot?: BTNodeKeyOrNode<N>, iterationType?: IterationType, includeNull?: true): ReturnType<C>[];
/**

@@ -454,5 +438,5 @@ * Time complexity: O(n)

*/
listLevels<C extends BTNCallback<N>>(callback?: C, beginRoot?: BTNKey | N | null | undefined, iterationType?: IterationType, includeNull?: false): ReturnType<C>[][];
listLevels<C extends BTNCallback<N>>(callback?: C, beginRoot?: BTNKey | N | null | undefined, iterationType?: IterationType, includeNull?: undefined): ReturnType<C>[][];
listLevels<C extends BTNCallback<N | null | undefined>>(callback?: C, beginRoot?: BTNKey | N | null | undefined, iterationType?: IterationType, includeNull?: true): ReturnType<C>[][];
listLevels<C extends BTNCallback<N>>(callback?: C, beginRoot?: BTNodeKeyOrNode<N>, iterationType?: IterationType, includeNull?: false): ReturnType<C>[][];
listLevels<C extends BTNCallback<N>>(callback?: C, beginRoot?: BTNodeKeyOrNode<N>, iterationType?: IterationType, includeNull?: undefined): ReturnType<C>[][];
listLevels<C extends BTNCallback<N | null | undefined>>(callback?: C, beginRoot?: BTNodeKeyOrNode<N>, iterationType?: IterationType, includeNull?: true): ReturnType<C>[][];
/**

@@ -488,3 +472,3 @@ * Time complexity: O(n)

*/
morris<C extends BTNCallback<N>>(callback?: C, pattern?: DFSOrderPattern, beginRoot?: BTNKey | N | null | undefined): ReturnType<C>[];
morris<C extends BTNCallback<N>>(callback?: C, pattern?: DFSOrderPattern, beginRoot?: BTNodeKeyOrNode<N>): ReturnType<C>[];
/**

@@ -547,4 +531,3 @@ * Time complexity: O(n)

*/
print(beginRoot?: BTNKey | N | null | undefined, options?: BinaryTreePrintOptions): void;
init(elements: IterableEntriesOrKeys<V>): void;
print(beginRoot?: BTNodeKeyOrNode<N>, options?: BinaryTreePrintOptions): void;
protected _displayAux(node: N | null | undefined, options: BinaryTreePrintOptions): NodeDisplayLayout;

@@ -558,4 +541,13 @@ protected _defaultOneParamCallback: (node: N) => number;

*/
protected _swap(srcNode: BTNKey | N | null | undefined, destNode: BTNKey | N | null | undefined): N | undefined;
protected _swapProperties(srcNode: BTNodeKeyOrNode<N>, destNode: BTNodeKeyOrNode<N>): N | undefined;
/**
* The function replaces an old node with a new node in a binary tree.
* @param {N} oldNode - The oldNode parameter represents the node that needs to be replaced in the
* tree.
* @param {N} newNode - The `newNode` parameter is the node that will replace the `oldNode` in the
* tree.
* @returns The method is returning the newNode.
*/
protected _replaceNode(oldNode: N, newNode: N): N;
/**
* The function `_addTo` adds a new node to a binary tree if there is an available position.

@@ -571,3 +563,3 @@ * @param {N | null | undefined} newNode - The `newNode` parameter represents the node that you want to add to

*/
protected _addTo(newNode: N | null | undefined, parent: BTNKey | N | null | undefined): N | null | undefined;
protected _addTo(newNode: N | null | undefined, parent: BTNodeKeyOrNode<N>): N | null | undefined;
/**

@@ -574,0 +566,0 @@ * The function sets the root property of an object to a given value, and if the value is not null,

97

dist/data-structures/binary-tree/bst.d.ts

@@ -8,4 +8,4 @@ /**

*/
import type { BSTNested, BSTNodeNested, BSTOptions, BTNCallback, BTNKey, Comparator } from '../../types';
import { CP, IterableEntriesOrKeys, IterationType } from '../../types';
import type { BSTNested, BSTNodeKeyOrNode, BSTNodeNested, BSTOptions, BTNCallback, BTNKey, BTNodeExemplar, Comparator } from '../../types';
import { CP, IterationType } from '../../types';
import { BinaryTree, BinaryTreeNode } from './binary-tree';

@@ -37,13 +37,22 @@ import { IBinaryTree } from '../../interfaces';

}
/**
* 1. Node Order: Each node's left child has a lesser value, and the right child has a greater value.
* 2. Unique Keys: No duplicate keys in a standard BST.
* 3. Efficient Search: Enables quick search, minimum, and maximum operations.
* 4. Inorder Traversal: Yields nodes in ascending order.
* 5. Logarithmic Operations: Ideal operations like insertion, deletion, and searching are O(log n) time-efficient.
* 6. Balance Variability: Can become unbalanced; special types maintain balance.
* 7. No Auto-Balancing: Standard BSTs don't automatically balance themselves.
*/
export declare class BST<V = any, N extends BSTNode<V, N> = BSTNode<V, BSTNodeNested<V>>, TREE extends BST<V, N, TREE> = BST<V, N, BSTNested<V, N>>> extends BinaryTree<V, N, TREE> implements IBinaryTree<V, N, TREE> {
/**
* The constructor function initializes a binary search tree with an optional comparator function.
* @param {BSTOptions} [options] - An optional object that contains additional configuration options
* for the binary search tree.
* This is the constructor function for a binary search tree class in TypeScript, which initializes
* the tree with optional elements and options.
* @param [elements] - An optional iterable of BTNodeExemplar objects that will be added to the
* binary search tree.
* @param [options] - The `options` parameter is an optional object that can contain additional
* configuration options for the binary search tree. It can have the following properties:
*/
constructor(elements?: IterableEntriesOrKeys<V>, options?: Partial<BSTOptions>);
constructor(elements?: Iterable<BTNodeExemplar<V, N>>, options?: Partial<BSTOptions>);
protected _root?: N;
/**
* Get the root node of the binary tree.
*/
get root(): N | undefined;

@@ -60,2 +69,9 @@ comparator: Comparator<BTNKey>;

createNode(key: BTNKey, value?: V): N;
/**
* The function creates a new binary search tree with the specified options.
* @param [options] - The `options` parameter is an optional object that allows you to customize the
* behavior of the `createTree` method. It accepts a partial `BSTOptions` object, which is a type
* that defines various options for creating a binary search tree.
* @returns a new instance of the BST class with the specified options.
*/
createTree(options?: Partial<BSTOptions>): TREE;

@@ -65,37 +81,35 @@ /**

* Space Complexity: O(1) - Constant space is used.
*
* The `add` function adds a new node to a binary search tree based on the provided key and value.
* @param {BTNKey | N | null | undefined} keyOrNode - The `keyOrNode` parameter can be one of the
* following types:
* @param {V} [value] - The `value` parameter is an optional value that can be associated with the
* key or node being added to the binary search tree.
* @returns The method `add` returns a node (`N`) that was inserted into the binary search tree. If
* no node was inserted, it returns `undefined`.
*/
add(keyOrNode: BTNKey | N | null | undefined, value?: V): N | undefined;
/**
* Time Complexity: O(log n) - Average case for a balanced tree. In the worst case (unbalanced tree), it can be O(n).
* Space Complexity: O(1) - Constant space is used.
*
* The `add` function adds a new node to a binary search tree, either by key or by providing a node
* object.
* @param keyOrNodeOrEntry - The `keyOrNodeOrEntry` parameter can be one of the following:
* @returns The method returns either the newly added node (`newNode`) or `undefined` if the input
* (`keyOrNodeOrEntry`) is null, undefined, or does not match any of the expected types.
*/
add(keyOrNodeOrEntry: BTNodeExemplar<V, N>): N | undefined;
/**
* Time Complexity: O(n log n) - Adding each element individually in a balanced tree.
* Space Complexity: O(n) - Additional space is required for the sorted array.
* Time Complexity: O(k log n) - Adding each element individually in a balanced tree.
* Space Complexity: O(k) - Additional space is required for the sorted array.
*/
/**
* Time Complexity: O(k log n) - Adding each element individually in a balanced tree.
* Space Complexity: O(k) - Additional space is required for the sorted array.
*
* The `addMany` function is used to efficiently add multiple keys or nodes with corresponding data
* to a binary search tree.
* @param {(BTNKey | N | undefined)[]} keysOrNodes - An array of keys or nodes to be added to the
* binary search tree. Each element can be of type `BTNKey` (binary tree node key), `N` (binary tree
* node), or `undefined`.
* @param {(V | undefined)[]} [data] - An optional array of values to associate with the keys or
* nodes being added. If provided, the length of the `data` array must be the same as the length of
* the `keysOrNodes` array.
* The `addMany` function in TypeScript adds multiple nodes to a binary tree, either in a balanced or
* unbalanced manner, and returns an array of the inserted nodes.
* @param keysOrNodesOrEntries - An iterable containing keys, nodes, or entries to be added to the
* binary tree.
* @param [isBalanceAdd=true] - A boolean flag indicating whether the tree should be balanced after
* adding the nodes. The default value is `true`.
* adding the nodes. The default value is true.
* @param iterationType - The `iterationType` parameter is an optional parameter that specifies the
* type of iteration to use when adding multiple keys or nodes to the binary search tree. It has a
* default value of `this.iterationType`, which means it will use the iteration type specified in the
* current instance of the binary search tree
* @returns The function `addMany` returns an array of nodes (`N`) or `undefined` values.
* type of iteration to use when adding multiple keys or nodes to the binary tree. It has a default
* value of `this.iterationType`, which means it will use the iteration type specified by the binary
* tree instance.
* @returns The `addMany` function returns an array of `N` or `undefined` values.
*/
addMany(keysOrNodes: (BTNKey | N | undefined)[], data?: (V | undefined)[], isBalanceAdd?: boolean, iterationType?: IterationType): (N | undefined)[];
addMany(keysOrNodesOrEntries: Iterable<BTNodeExemplar<V, N>>, isBalanceAdd?: boolean, iterationType?: IterationType): (N | undefined)[];
/**

@@ -120,3 +134,3 @@ * Time Complexity: O(n log n) - Adding each element individually in a balanced tree.

*/
lastKey(beginRoot?: BTNKey | N | undefined, iterationType?: IterationType): BTNKey;
lastKey(beginRoot?: BSTNodeKeyOrNode<N>, iterationType?: IterationType): BTNKey;
/**

@@ -146,3 +160,3 @@ * Time Complexity: O(log n) - Average case for a balanced tree.

/**
* The function `ensureNotKey` returns the node corresponding to the given key if it is a node key,
* The function `ensureNode` returns the node corresponding to the given key if it is a node key,
* otherwise it returns the key itself.

@@ -155,3 +169,3 @@ * @param {BTNKey | N | undefined} key - The `key` parameter can be of type `BTNKey`, `N`, or

*/
ensureNotKey(key: BTNKey | N | undefined, iterationType?: IterationType): N | undefined;
ensureNode(key: BSTNodeKeyOrNode<N>, iterationType?: IterationType): N | undefined;
/**

@@ -180,3 +194,3 @@ * Time Complexity: O(log n) - Average case for a balanced tree. O(n) - Visiting each node once when identifier is not node's key.

*/
getNodes<C extends BTNCallback<N>>(identifier: ReturnType<C> | undefined, callback?: C, onlyOne?: boolean, beginRoot?: BTNKey | N | undefined, iterationType?: IterationType): N[];
getNodes<C extends BTNCallback<N>>(identifier: ReturnType<C> | undefined, callback?: C, onlyOne?: boolean, beginRoot?: BSTNodeKeyOrNode<N>, iterationType?: IterationType): N[];
/**

@@ -207,3 +221,3 @@ * Time Complexity: O(log n) - Average case for a balanced tree. O(n) - Visiting each node once when identifier is not node's key.

*/
lesserOrGreaterTraverse<C extends BTNCallback<N>>(callback?: C, lesserOrGreater?: CP, targetNode?: BTNKey | N | undefined, iterationType?: IterationType): ReturnType<C>[];
lesserOrGreaterTraverse<C extends BTNCallback<N>>(callback?: C, lesserOrGreater?: CP, targetNode?: BSTNodeKeyOrNode<N>, iterationType?: IterationType): ReturnType<C>[];
/**

@@ -248,7 +262,2 @@ * Time Complexity: O(log n) - Average case for a balanced tree. O(n) - Visiting each node once when identifier is not node's key.

isAVLBalanced(iterationType?: IterationType): boolean;
/**
* Time Complexity: O(n) - Visiting each node once.
* Space Complexity: O(log n) - Space for the recursive call stack in the worst case.
*/
init(elements: IterableEntriesOrKeys<V>): void;
protected _setRoot(v: N | undefined): void;

@@ -255,0 +264,0 @@ /**

291

dist/data-structures/binary-tree/bst.js

@@ -48,7 +48,19 @@ "use strict";

exports.BSTNode = BSTNode;
/**
* 1. Node Order: Each node's left child has a lesser value, and the right child has a greater value.
* 2. Unique Keys: No duplicate keys in a standard BST.
* 3. Efficient Search: Enables quick search, minimum, and maximum operations.
* 4. Inorder Traversal: Yields nodes in ascending order.
* 5. Logarithmic Operations: Ideal operations like insertion, deletion, and searching are O(log n) time-efficient.
* 6. Balance Variability: Can become unbalanced; special types maintain balance.
* 7. No Auto-Balancing: Standard BSTs don't automatically balance themselves.
*/
class BST extends binary_tree_1.BinaryTree {
/**
* The constructor function initializes a binary search tree with an optional comparator function.
* @param {BSTOptions} [options] - An optional object that contains additional configuration options
* for the binary search tree.
* This is the constructor function for a binary search tree class in TypeScript, which initializes
* the tree with optional elements and options.
* @param [elements] - An optional iterable of BTNodeExemplar objects that will be added to the
* binary search tree.
* @param [options] - The `options` parameter is an optional object that can contain additional
* configuration options for the binary search tree. It can have the following properties:
*/

@@ -66,7 +78,4 @@ constructor(elements, options) {

if (elements)
this.init(elements);
this.addMany(elements);
}
/**
* Get the root node of the binary tree.
*/
get root() {

@@ -86,2 +95,9 @@ return this._root;

}
/**
* The function creates a new binary search tree with the specified options.
* @param [options] - The `options` parameter is an optional object that allows you to customize the
* behavior of the `createTree` method. It accepts a partial `BSTOptions` object, which is a type
* that defines various options for creating a binary search tree.
* @returns a new instance of the BST class with the specified options.
*/
createTree(options) {

@@ -93,155 +109,139 @@ return new BST([], Object.assign({ iterationType: this.iterationType, comparator: this.comparator }, options));

* Space Complexity: O(1) - Constant space is used.
*/
/**
* Time Complexity: O(log n) - Average case for a balanced tree. In the worst case (unbalanced tree), it can be O(n).
* Space Complexity: O(1) - Constant space is used.
*
* The `add` function adds a new node to a binary search tree based on the provided key and value.
* @param {BTNKey | N | null | undefined} keyOrNode - The `keyOrNode` parameter can be one of the
* following types:
* @param {V} [value] - The `value` parameter is an optional value that can be associated with the
* key or node being added to the binary search tree.
* @returns The method `add` returns a node (`N`) that was inserted into the binary search tree. If
* no node was inserted, it returns `undefined`.
* The `add` function adds a new node to a binary search tree, either by key or by providing a node
* object.
* @param keyOrNodeOrEntry - The `keyOrNodeOrEntry` parameter can be one of the following:
* @returns The method returns either the newly added node (`newNode`) or `undefined` if the input
* (`keyOrNodeOrEntry`) is null, undefined, or does not match any of the expected types.
*/
add(keyOrNode, value) {
if (keyOrNode === null)
add(keyOrNodeOrEntry) {
if (keyOrNodeOrEntry === null || keyOrNodeOrEntry === undefined) {
return undefined;
// TODO support node as a parameter
let inserted;
}
let newNode;
if (keyOrNode instanceof BSTNode) {
newNode = keyOrNode;
if (keyOrNodeOrEntry instanceof BSTNode) {
newNode = keyOrNodeOrEntry;
}
else if (this.isNodeKey(keyOrNode)) {
newNode = this.createNode(keyOrNode, value);
else if (this.isNodeKey(keyOrNodeOrEntry)) {
newNode = this.createNode(keyOrNodeOrEntry);
}
else if (this.isEntry(keyOrNodeOrEntry)) {
const [key, value] = keyOrNodeOrEntry;
if (key === undefined || key === null) {
return;
}
else {
newNode = this.createNode(key, value);
}
}
else {
newNode = undefined;
return;
}
if (this.root === undefined) {
this._setRoot(newNode);
this._size = this.size + 1;
inserted = this.root;
this._size++;
return this.root;
}
else {
let cur = this.root;
let traversing = true;
while (traversing) {
if (cur !== undefined && newNode !== undefined) {
if (this._compare(cur.key, newNode.key) === types_1.CP.eq) {
if (newNode) {
cur.value = newNode.value;
}
//Duplicates are not accepted.
traversing = false;
inserted = cur;
}
else if (this._compare(cur.key, newNode.key) === types_1.CP.gt) {
// Traverse left of the node
if (cur.left === undefined) {
if (newNode) {
newNode.parent = cur;
}
//Add to the left of the current node
cur.left = newNode;
this._size = this.size + 1;
traversing = false;
inserted = cur.left;
}
else {
//Traverse the left of the current node
if (cur.left)
cur = cur.left;
}
}
else if (this._compare(cur.key, newNode.key) === types_1.CP.lt) {
// Traverse right of the node
if (cur.right === undefined) {
if (newNode) {
newNode.parent = cur;
}
//Add to the right of the current node
cur.right = newNode;
this._size = this.size + 1;
traversing = false;
inserted = cur.right;
}
else {
//Traverse the left of the current node
if (cur.right)
cur = cur.right;
}
}
let current = this.root;
while (current !== undefined) {
if (this._compare(current.key, newNode.key) === types_1.CP.eq) {
// if (current !== newNode) {
// The key value is the same but the reference is different, update the value of the existing node
this._replaceNode(current, newNode);
return newNode;
// } else {
// The key value is the same and the reference is the same, replace the entire node
// this._replaceNode(current, newNode);
// return;
// }
}
else if (this._compare(current.key, newNode.key) === types_1.CP.gt) {
if (current.left === undefined) {
current.left = newNode;
newNode.parent = current;
this._size++;
return newNode;
}
else {
traversing = false;
current = current.left;
}
else {
if (current.right === undefined) {
current.right = newNode;
newNode.parent = current;
this._size++;
return newNode;
}
current = current.right;
}
}
return inserted;
return undefined;
}
/**
* Time Complexity: O(log n) - Average case for a balanced tree. In the worst case (unbalanced tree), it can be O(n).
* Space Complexity: O(1) - Constant space is used.
* Time Complexity: O(k log n) - Adding each element individually in a balanced tree.
* Space Complexity: O(k) - Additional space is required for the sorted array.
*/
/**
* Time Complexity: O(n log n) - Adding each element individually in a balanced tree.
* Space Complexity: O(n) - Additional space is required for the sorted array.
* Time Complexity: O(k log n) - Adding each element individually in a balanced tree.
* Space Complexity: O(k) - Additional space is required for the sorted array.
*
* The `addMany` function is used to efficiently add multiple keys or nodes with corresponding data
* to a binary search tree.
* @param {(BTNKey | N | undefined)[]} keysOrNodes - An array of keys or nodes to be added to the
* binary search tree. Each element can be of type `BTNKey` (binary tree node key), `N` (binary tree
* node), or `undefined`.
* @param {(V | undefined)[]} [data] - An optional array of values to associate with the keys or
* nodes being added. If provided, the length of the `data` array must be the same as the length of
* the `keysOrNodes` array.
* The `addMany` function in TypeScript adds multiple nodes to a binary tree, either in a balanced or
* unbalanced manner, and returns an array of the inserted nodes.
* @param keysOrNodesOrEntries - An iterable containing keys, nodes, or entries to be added to the
* binary tree.
* @param [isBalanceAdd=true] - A boolean flag indicating whether the tree should be balanced after
* adding the nodes. The default value is `true`.
* adding the nodes. The default value is true.
* @param iterationType - The `iterationType` parameter is an optional parameter that specifies the
* type of iteration to use when adding multiple keys or nodes to the binary search tree. It has a
* default value of `this.iterationType`, which means it will use the iteration type specified in the
* current instance of the binary search tree
* @returns The function `addMany` returns an array of nodes (`N`) or `undefined` values.
* type of iteration to use when adding multiple keys or nodes to the binary tree. It has a default
* value of `this.iterationType`, which means it will use the iteration type specified by the binary
* tree instance.
* @returns The `addMany` function returns an array of `N` or `undefined` values.
*/
addMany(keysOrNodes, data, isBalanceAdd = true, iterationType = this.iterationType) {
// TODO this addMany function is inefficient, it should be optimized
function hasNoUndefined(arr) {
return arr.indexOf(undefined) === -1;
}
if (!isBalanceAdd || !hasNoUndefined(keysOrNodes)) {
return super.addMany(keysOrNodes, data).map(n => n !== null && n !== void 0 ? n : undefined);
}
addMany(keysOrNodesOrEntries, isBalanceAdd = true, iterationType = this.iterationType) {
const inserted = [];
const combinedArr = keysOrNodes.map((value, index) => [value, data === null || data === void 0 ? void 0 : data[index]]);
let sorted = [];
function _isNodeOrUndefinedTuple(arr) {
for (const [keyOrNode] of arr)
if (keyOrNode instanceof BSTNode)
return true;
return false;
if (!isBalanceAdd) {
for (const kve of keysOrNodesOrEntries) {
const nn = this.add(kve);
inserted.push(nn);
}
return inserted;
}
const _isBinaryTreeKeyOrNullTuple = (arr) => {
for (const [keyOrNode] of arr)
if (this.isNodeKey(keyOrNode))
return true;
return false;
const realBTNExemplars = [];
const isRealBTNExemplar = (kve) => {
if (kve === undefined || kve === null)
return false;
return !(this.isEntry(kve) && (kve[0] === undefined || kve[0] === null));
};
let sortedKeysOrNodes = [], sortedData = [];
if (_isNodeOrUndefinedTuple(combinedArr)) {
sorted = combinedArr.sort((a, b) => a[0].key - b[0].key);
for (const kve of keysOrNodesOrEntries) {
isRealBTNExemplar(kve) && realBTNExemplars.push(kve);
}
else if (_isBinaryTreeKeyOrNullTuple(combinedArr)) {
sorted = combinedArr.sort((a, b) => a[0] - b[0]);
}
else {
throw new Error('Invalid input keysOrNodes');
}
sortedKeysOrNodes = sorted.map(([keyOrNode]) => keyOrNode);
sortedData = sorted.map(([, value]) => value);
const _dfs = (arr, data) => {
// TODO this addMany function is inefficient, it should be optimized
let sorted = [];
sorted = realBTNExemplars.sort((a, b) => {
let aR, bR;
if (this.isEntry(a))
aR = a[0];
else if (this.isRealNode(a))
aR = a.key;
else
aR = a;
if (this.isEntry(b))
bR = b[0];
else if (this.isRealNode(b))
bR = b.key;
else
bR = b;
return aR - bR;
});
const _dfs = (arr) => {
if (arr.length === 0)
return;
const mid = Math.floor((arr.length - 1) / 2);
const newNode = this.add(arr[mid], data === null || data === void 0 ? void 0 : data[mid]);
const newNode = this.add(arr[mid]);
inserted.push(newNode);
_dfs(arr.slice(0, mid), data === null || data === void 0 ? void 0 : data.slice(0, mid));
_dfs(arr.slice(mid + 1), data === null || data === void 0 ? void 0 : data.slice(mid + 1));
_dfs(arr.slice(0, mid));
_dfs(arr.slice(mid + 1));
};

@@ -257,3 +257,3 @@ const _iterate = () => {

const m = l + Math.floor((r - l) / 2);
const newNode = this.add(sortedKeysOrNodes[m], sortedData === null || sortedData === void 0 ? void 0 : sortedData[m]);
const newNode = this.add(sorted[m]);
inserted.push(newNode);

@@ -267,3 +267,3 @@ stack.push([m + 1, r]);

if (iterationType === types_1.IterationType.RECURSIVE) {
_dfs(sortedKeysOrNodes, sortedData);
_dfs(sorted);
}

@@ -357,3 +357,3 @@ else {

/**
* The function `ensureNotKey` returns the node corresponding to the given key if it is a node key,
* The function `ensureNode` returns the node corresponding to the given key if it is a node key,
* otherwise it returns the key itself.

@@ -366,3 +366,3 @@ * @param {BTNKey | N | undefined} key - The `key` parameter can be of type `BTNKey`, `N`, or

*/
ensureNotKey(key, iterationType = types_1.IterationType.ITERATIVE) {
ensureNode(key, iterationType = types_1.IterationType.ITERATIVE) {
return this.isNodeKey(key) ? this.getNodeByKey(key, iterationType) : key;

@@ -394,3 +394,3 @@ }

getNodes(identifier, callback = this._defaultOneParamCallback, onlyOne = false, beginRoot = this.root, iterationType = this.iterationType) {
beginRoot = this.ensureNotKey(beginRoot);
beginRoot = this.ensureNode(beginRoot);
if (!beginRoot)

@@ -476,3 +476,3 @@ return [];

lesserOrGreaterTraverse(callback = this._defaultOneParamCallback, lesserOrGreater = types_1.CP.lt, targetNode = this.root, iterationType = this.iterationType) {
targetNode = this.ensureNotKey(targetNode);
targetNode = this.ensureNode(targetNode);
const ans = [];

@@ -542,3 +542,3 @@ if (!targetNode)

const midNode = sorted[m];
this.add(midNode.key, midNode.value);
this.add([midNode.key, midNode.value]);
buildBalanceBST(l, m - 1);

@@ -560,3 +560,3 @@ buildBalanceBST(m + 1, r);

debugger;
this.add(midNode.key, midNode.value);
this.add([midNode.key, midNode.value]);
stack.push([m + 1, r]);

@@ -638,19 +638,2 @@ stack.push([l, m - 1]);

}
/**
* Time Complexity: O(n) - Visiting each node once.
* Space Complexity: O(log n) - Space for the recursive call stack in the worst case.
*/
init(elements) {
if (elements) {
for (const entryOrKey of elements) {
if (Array.isArray(entryOrKey)) {
const [key, value] = entryOrKey;
this.add(key, value);
}
else {
this.add(entryOrKey);
}
}
}
}
_setRoot(v) {

@@ -657,0 +640,0 @@ if (v) {

61

dist/data-structures/binary-tree/rb-tree.d.ts

@@ -8,3 +8,3 @@ /**

*/
import { BiTreeDeleteResult, BTNCallback, BTNKey, IterableEntriesOrKeys, IterationType, RBTNColor, RBTreeOptions, RedBlackTreeNested, RedBlackTreeNodeNested } from '../../types';
import { BiTreeDeleteResult, BTNCallback, BTNKey, BTNodeExemplar, IterationType, RBTNColor, RBTreeOptions, RedBlackTreeNested, RedBlackTreeNodeNested } from '../../types';
import { BST, BSTNode } from './bst';

@@ -26,7 +26,13 @@ import { IBinaryTree } from '../../interfaces';

/**
* The constructor function initializes a Red-Black Tree with an optional set of options.
* @param {RBTreeOptions} [options] - The `options` parameter is an optional object that can be
* passed to the constructor. It is used to configure the RBTree object with specific options.
* This is the constructor function for a Red-Black Tree data structure in TypeScript, which
* initializes the tree with optional elements and options.
* @param [elements] - The `elements` parameter is an optional iterable of `BTNodeExemplar<V, N>`
* objects. It represents the initial elements that will be added to the RBTree during its
* construction. If this parameter is provided, the `addMany` method is called to add all the
* elements to the
* @param [options] - The `options` parameter is an optional object that allows you to customize the
* behavior of the RBTree. It is of type `Partial<RBTreeOptions>`, which means that you can provide
* only a subset of the properties defined in the `RBTreeOptions` interface.
*/
constructor(elements?: IterableEntriesOrKeys<V>, options?: Partial<RBTreeOptions>);
constructor(elements?: Iterable<BTNodeExemplar<V, N>>, options?: Partial<RBTreeOptions>);
protected _root: N;

@@ -36,3 +42,22 @@ get root(): N;

get size(): number;
/**
* The function creates a new Red-Black Tree node with the specified key, value, and color.
* @param {BTNKey} key - The key parameter is the key value associated with the node. It is used to
* identify and compare nodes in the Red-Black Tree.
* @param {V} [value] - The `value` parameter is an optional parameter that represents the value
* associated with the node. It is of type `V`, which is a generic type that can be replaced with any
* specific type when using the `createNode` method.
* @param {RBTNColor} color - The "color" parameter is used to specify the color of the node in a
* Red-Black Tree. It can be either "RED" or "BLACK". By default, the color is set to "BLACK".
* @returns The method is returning a new instance of a RedBlackTreeNode with the specified key,
* value, and color.
*/
createNode(key: BTNKey, value?: V, color?: RBTNColor): N;
/**
* The function creates a Red-Black Tree with the specified options and returns it.
* @param {RBTreeOptions} [options] - The `options` parameter is an optional object that can be
* passed to the `createTree` function. It is used to customize the behavior of the `RedBlackTree`
* class.
* @returns a new instance of a RedBlackTree object.
*/
createTree(options?: RBTreeOptions): TREE;

@@ -42,12 +67,11 @@ /**

* Space Complexity: O(1)
*
* The `add` function adds a new node to a Red-Black Tree data structure.
* @param {BTNKey | N | null | undefined} keyOrNode - The `keyOrNode` parameter can be one of the
* following types:
* @param {V} [value] - The `value` parameter is an optional value that can be associated with the
* key in the node being added to the Red-Black Tree.
* @returns The method returns either a node (`N`) or `undefined`.
*/
add(keyOrNode: BTNKey | N | null | undefined, value?: V): N | undefined;
/**
* The function adds a node to a Red-Black Tree data structure.
* @param keyOrNodeOrEntry - The `keyOrNodeOrEntry` parameter can be one of the following:
* @returns The method `add` returns either an instance of `N` (the node that was added) or
* `undefined`.
*/
add(keyOrNodeOrEntry: BTNodeExemplar<V, N>): N | undefined;
/**
* Time Complexity: O(log n) on average (where n is the number of nodes in the tree)

@@ -112,3 +136,2 @@ * Space Complexity: O(1)

clear(): void;
init(elements: IterableEntriesOrKeys<V>): void;
protected _setRoot(v: N): void;

@@ -178,2 +201,12 @@ /**

protected _fixInsert(k: N): void;
/**
* The function replaces an old node with a new node while preserving the color of the old node.
* @param {N} oldNode - The `oldNode` parameter represents the node that needs to be replaced in a
* data structure. It is of type `N`, which is the type of the nodes in the data structure.
* @param {N} newNode - The `newNode` parameter is the node that will replace the `oldNode` in the
* data structure.
* @returns The method is returning the result of calling the `_replaceNode` method from the
* superclass, passing in the `oldNode` and `newNode` as arguments.
*/
protected _replaceNode(oldNode: N, newNode: N): N;
}

103

dist/data-structures/binary-tree/rb-tree.js

@@ -30,5 +30,11 @@ "use strict";

/**
* The constructor function initializes a Red-Black Tree with an optional set of options.
* @param {RBTreeOptions} [options] - The `options` parameter is an optional object that can be
* passed to the constructor. It is used to configure the RBTree object with specific options.
* This is the constructor function for a Red-Black Tree data structure in TypeScript, which
* initializes the tree with optional elements and options.
* @param [elements] - The `elements` parameter is an optional iterable of `BTNodeExemplar<V, N>`
* objects. It represents the initial elements that will be added to the RBTree during its
* construction. If this parameter is provided, the `addMany` method is called to add all the
* elements to the
* @param [options] - The `options` parameter is an optional object that allows you to customize the
* behavior of the RBTree. It is of type `Partial<RBTreeOptions>`, which means that you can provide
* only a subset of the properties defined in the `RBTreeOptions` interface.
*/

@@ -41,3 +47,3 @@ constructor(elements, options) {

if (elements)
this.init(elements);
super.addMany(elements);
}

@@ -50,5 +56,24 @@ get root() {

}
/**
* The function creates a new Red-Black Tree node with the specified key, value, and color.
* @param {BTNKey} key - The key parameter is the key value associated with the node. It is used to
* identify and compare nodes in the Red-Black Tree.
* @param {V} [value] - The `value` parameter is an optional parameter that represents the value
* associated with the node. It is of type `V`, which is a generic type that can be replaced with any
* specific type when using the `createNode` method.
* @param {RBTNColor} color - The "color" parameter is used to specify the color of the node in a
* Red-Black Tree. It can be either "RED" or "BLACK". By default, the color is set to "BLACK".
* @returns The method is returning a new instance of a RedBlackTreeNode with the specified key,
* value, and color.
*/
createNode(key, value, color = types_1.RBTNColor.BLACK) {
return new RedBlackTreeNode(key, value, color);
}
/**
* The function creates a Red-Black Tree with the specified options and returns it.
* @param {RBTreeOptions} [options] - The `options` parameter is an optional object that can be
* passed to the `createTree` function. It is used to customize the behavior of the `RedBlackTree`
* class.
* @returns a new instance of a RedBlackTree object.
*/
createTree(options) {

@@ -60,23 +85,28 @@ return new RedBlackTree([], Object.assign({ iterationType: this.iterationType, comparator: this.comparator }, options));

* Space Complexity: O(1)
*
* The `add` function adds a new node to a Red-Black Tree data structure.
* @param {BTNKey | N | null | undefined} keyOrNode - The `keyOrNode` parameter can be one of the
* following types:
* @param {V} [value] - The `value` parameter is an optional value that can be associated with the
* key in the node being added to the Red-Black Tree.
* @returns The method returns either a node (`N`) or `undefined`.
*/
add(keyOrNode, value) {
/**
* The function adds a node to a Red-Black Tree data structure.
* @param keyOrNodeOrEntry - The `keyOrNodeOrEntry` parameter can be one of the following:
* @returns The method `add` returns either an instance of `N` (the node that was added) or
* `undefined`.
*/
add(keyOrNodeOrEntry) {
let node;
if (this.isNodeKey(keyOrNode)) {
node = this.createNode(keyOrNode, value, types_1.RBTNColor.RED);
if (this.isNodeKey(keyOrNodeOrEntry)) {
node = this.createNode(keyOrNodeOrEntry, undefined, types_1.RBTNColor.RED);
}
else if (keyOrNode instanceof RedBlackTreeNode) {
node = keyOrNode;
else if (keyOrNodeOrEntry instanceof RedBlackTreeNode) {
node = keyOrNodeOrEntry;
}
else if (keyOrNode === null) {
else if (keyOrNodeOrEntry === null || keyOrNodeOrEntry === undefined) {
return;
}
else if (keyOrNode === undefined) {
return;
else if (this.isEntry(keyOrNodeOrEntry)) {
const [key, value] = keyOrNodeOrEntry;
if (key === undefined || key === null) {
return;
}
else {
node = this.createNode(key, value, types_1.RBTNColor.RED);
}
}

@@ -100,2 +130,5 @@ else {

else {
if (node !== x) {
this._replaceNode(x, node);
}
return;

@@ -214,2 +247,6 @@ }

* Space Complexity: O(1)
*/
/**
* Time Complexity: O(log n) on average (where n is the number of nodes in the tree)
* Space Complexity: O(1)
*

@@ -237,3 +274,3 @@ * The function `getNode` retrieves a single node from a binary tree based on a given identifier and

callback = (node => node);
beginRoot = this.ensureNotKey(beginRoot);
beginRoot = this.ensureNode(beginRoot);
return (_a = this.getNodes(identifier, callback, true, beginRoot, iterationType)[0]) !== null && _a !== void 0 ? _a : undefined;

@@ -297,15 +334,2 @@ }

}
init(elements) {
if (elements) {
for (const entryOrKey of elements) {
if (Array.isArray(entryOrKey)) {
const [key, value] = entryOrKey;
this.add(key, value);
}
else {
this.add(entryOrKey);
}
}
}
}
_setRoot(v) {

@@ -540,3 +564,16 @@ if (v) {

}
/**
* The function replaces an old node with a new node while preserving the color of the old node.
* @param {N} oldNode - The `oldNode` parameter represents the node that needs to be replaced in a
* data structure. It is of type `N`, which is the type of the nodes in the data structure.
* @param {N} newNode - The `newNode` parameter is the node that will replace the `oldNode` in the
* data structure.
* @returns The method is returning the result of calling the `_replaceNode` method from the
* superclass, passing in the `oldNode` and `newNode` as arguments.
*/
_replaceNode(oldNode, newNode) {
newNode.color = oldNode.color;
return super._replaceNode(oldNode, newNode);
}
}
exports.RedBlackTree = RedBlackTree;

63

dist/data-structures/binary-tree/tree-multimap.d.ts

@@ -8,4 +8,4 @@ /**

*/
import type { BTNKey, TreeMultimapNodeNested, TreeMultimapOptions } from '../../types';
import { BiTreeDeleteResult, BTNCallback, IterableEntriesOrKeys, IterationType, TreeMultimapNested } from '../../types';
import type { BSTNodeKeyOrNode, BTNKey, BTNodeExemplar, TreeMultimapNodeNested, TreeMultimapOptions } from '../../types';
import { BiTreeDeleteResult, BTNCallback, IterationType, TreeMultimapNested } from '../../types';
import { IBinaryTree } from '../../interfaces';

@@ -31,9 +31,3 @@ import { AVLTree, AVLTreeNode } from './avl-tree';

export declare class TreeMultimap<V = any, N extends TreeMultimapNode<V, N> = TreeMultimapNode<V, TreeMultimapNodeNested<V>>, TREE extends TreeMultimap<V, N, TREE> = TreeMultimap<V, N, TreeMultimapNested<V, N>>> extends AVLTree<V, N, TREE> implements IBinaryTree<V, N, TREE> {
/**
* The constructor function for a TreeMultimap class in TypeScript, which extends another class and sets an option to
* merge duplicated values.
* @param {TreeMultimapOptions} [options] - An optional object that contains additional configuration options for the
* TreeMultimap.
*/
constructor(elements?: IterableEntriesOrKeys<V>, options?: Partial<TreeMultimapOptions>);
constructor(elements?: Iterable<BTNodeExemplar<V, N>>, options?: Partial<TreeMultimapOptions>);
private _count;

@@ -55,32 +49,31 @@ get count(): number;

* Space Complexity: O(1) - constant space, as it doesn't use additional data structures that scale with input size.
*/
/**
* Time Complexity: O(log n) - logarithmic time, where "n" is the number of nodes in the tree. The add method of the superclass (AVLTree) has logarithmic time complexity.
* Space Complexity: O(1) - constant space, as it doesn't use additional data structures that scale with input size.
*
* The `add` function adds a new node to the tree multimap, updating the count if the key already
* exists, and balances the tree if necessary.
* @param {BTNKey | N | null | undefined} keyOrNode - The `keyOrNode` parameter can be one of the
* following types:
* @param {V} [value] - The `value` parameter represents the value associated with the key that is
* being added to the tree. It is an optional parameter, so it can be omitted if not needed.
* The `add` function overrides the base class `add` function to add a new node to the tree multimap
* and update the count.
* @param keyOrNodeOrEntry - The `keyOrNodeOrEntry` parameter can be one of the following:
* @param [count=1] - The `count` parameter is an optional parameter that specifies the number of
* times the key-value pair should be added to the multimap. If not provided, the default value is 1.
* @returns a node (`N`) or `undefined`.
* times the key or node or entry should be added to the multimap. If not provided, the default value
* is 1.
* @returns either a node (`N`) or `undefined`.
*/
add(keyOrNode: BTNKey | N | null | undefined, value?: V, count?: number): N | undefined;
add(keyOrNodeOrEntry: BTNodeExemplar<V, N>, count?: number): N | undefined;
/**
* Time Complexity: O(log n) - logarithmic time, where "n" is the number of nodes in the tree. The add method of the superclass (AVLTree) has logarithmic time complexity.
* Time Complexity: O(k log n) - logarithmic time, where "n" is the number of nodes in the tree. The add method of the superclass (AVLTree) has logarithmic time complexity.
* Space Complexity: O(1) - constant space, as it doesn't use additional data structures that scale with input size.
*/
/**
* Time Complexity: O(k log n) - logarithmic time for each insertion, where "n" is the number of nodes in the tree, and "k" is the number of keys to be inserted. This is because the method iterates through the keys and calls the add method for each.
* Time Complexity: O(k log n) - logarithmic time, where "n" is the number of nodes in the tree. The add method of the superclass (AVLTree) has logarithmic time complexity.
* Space Complexity: O(1) - constant space, as it doesn't use additional data structures that scale with input size.
*
* The function `addMany` takes an array of keys or nodes and adds them to the TreeMultimap,
* returning an array of the inserted nodes.
* @param {(BTNKey | N | undefined)[]} keysOrNodes - An array of keys or nodes. Each element can be
* of type BTNKey, N, or undefined.
* @param {V[]} [data] - The `data` parameter is an optional array of values that correspond to the
* keys or nodes being added. It is used to associate data with each key or node being added to the
* TreeMultimap. If provided, the length of the `data` array should be the same as the length of the
* @returns The function `addMany` returns an array of nodes (`N`) or `undefined` values.
* The function overrides the addMany method to add multiple keys, nodes, or entries to a data
* structure.
* @param keysOrNodesOrEntries - The parameter `keysOrNodesOrEntries` is an iterable that can contain
* either keys, nodes, or entries.
* @returns The method is returning an array of type `N | undefined`.
*/
addMany(keysOrNodes: (BTNKey | N | undefined)[], data?: V[]): (N | undefined)[];
addMany(keysOrNodesOrEntries: Iterable<BTNodeExemplar<V, N>>): (N | undefined)[];
/**

@@ -135,7 +128,2 @@ * Time Complexity: O(1) - constant time, as it performs basic pointer assignments.

/**
* Time Complexity: O(log n) - logarithmic time, where "n" is the number of nodes in the tree. The delete method of the superclass (AVLTree) has logarithmic time complexity.
* Space Complexity: O(1) - constant space, as it doesn't use additional data structures that scale with input size.
*/
init(elements: IterableEntriesOrKeys<V>): void;
/**
* Time Complexity: O(1) - constant time, as it performs basic pointer assignments.

@@ -155,5 +143,5 @@ * Space Complexity: O(1) - constant space, as it only uses a constant amount of memory.

*/
protected _addTo(newNode: N | undefined, parent: BTNKey | N | undefined): N | undefined;
protected _addTo(newNode: N | undefined, parent: BSTNodeKeyOrNode<N>): N | undefined;
/**
* The `_swap` function swaps the key, value, count, and height properties between two nodes.
* The `_swapProperties` function swaps the key, value, count, and height properties between two nodes.
* @param {BTNKey | N | undefined} srcNode - The `srcNode` parameter represents the source node from

@@ -166,3 +154,4 @@ * which the values will be swapped. It can be of type `BTNKey`, `N`, or `undefined`.

*/
protected _swap(srcNode: BTNKey | N | undefined, destNode: BTNKey | N | undefined): N | undefined;
protected _swapProperties(srcNode: BSTNodeKeyOrNode<N>, destNode: BSTNodeKeyOrNode<N>): N | undefined;
protected _replaceNode(oldNode: N, newNode: N): N;
}

195

dist/data-structures/binary-tree/tree-multimap.js

@@ -27,8 +27,2 @@ "use strict";

class TreeMultimap extends avl_tree_1.AVLTree {
/**
* The constructor function for a TreeMultimap class in TypeScript, which extends another class and sets an option to
* merge duplicated values.
* @param {TreeMultimapOptions} [options] - An optional object that contains additional configuration options for the
* TreeMultimap.
*/
constructor(elements, options) {

@@ -38,6 +32,9 @@ super([], options);

if (elements)
this.init(elements);
this.addMany(elements);
}
// TODO the _count is not accurate after nodes count modified
get count() {
return this._count;
let sum = 0;
this.subTreeTraverse(node => sum += node.count);
return sum;
}

@@ -62,124 +59,61 @@ /**

* Space Complexity: O(1) - constant space, as it doesn't use additional data structures that scale with input size.
*/
/**
* Time Complexity: O(log n) - logarithmic time, where "n" is the number of nodes in the tree. The add method of the superclass (AVLTree) has logarithmic time complexity.
* Space Complexity: O(1) - constant space, as it doesn't use additional data structures that scale with input size.
*
* The `add` function adds a new node to the tree multimap, updating the count if the key already
* exists, and balances the tree if necessary.
* @param {BTNKey | N | null | undefined} keyOrNode - The `keyOrNode` parameter can be one of the
* following types:
* @param {V} [value] - The `value` parameter represents the value associated with the key that is
* being added to the tree. It is an optional parameter, so it can be omitted if not needed.
* The `add` function overrides the base class `add` function to add a new node to the tree multimap
* and update the count.
* @param keyOrNodeOrEntry - The `keyOrNodeOrEntry` parameter can be one of the following:
* @param [count=1] - The `count` parameter is an optional parameter that specifies the number of
* times the key-value pair should be added to the multimap. If not provided, the default value is 1.
* @returns a node (`N`) or `undefined`.
* times the key or node or entry should be added to the multimap. If not provided, the default value
* is 1.
* @returns either a node (`N`) or `undefined`.
*/
add(keyOrNode, value, count = 1) {
if (keyOrNode === null)
return undefined;
let inserted = undefined, newNode;
if (keyOrNode instanceof TreeMultimapNode) {
newNode = this.createNode(keyOrNode.key, keyOrNode.value, keyOrNode.count);
add(keyOrNodeOrEntry, count = 1) {
let newNode;
if (keyOrNodeOrEntry === undefined || keyOrNodeOrEntry === null) {
return;
}
else if (keyOrNode === undefined) {
newNode = undefined;
else if (keyOrNodeOrEntry instanceof TreeMultimapNode) {
newNode = keyOrNodeOrEntry;
}
else {
newNode = this.createNode(keyOrNode, value, count);
else if (this.isNodeKey(keyOrNodeOrEntry)) {
newNode = this.createNode(keyOrNodeOrEntry, undefined, count);
}
if (!this.root) {
this._setRoot(newNode);
this._size = this.size + 1;
if (newNode)
this._count += newNode.count;
inserted = this.root;
else if (this.isEntry(keyOrNodeOrEntry)) {
const [key, value] = keyOrNodeOrEntry;
if (key === undefined || key === null) {
return;
}
else {
newNode = this.createNode(key, value, count);
}
}
else {
let cur = this.root;
let traversing = true;
while (traversing) {
if (cur) {
if (newNode) {
if (this._compare(cur.key, newNode.key) === types_1.CP.eq) {
cur.value = newNode.value;
cur.count += newNode.count;
this._count += newNode.count;
traversing = false;
inserted = cur;
}
else if (this._compare(cur.key, newNode.key) === types_1.CP.gt) {
// Traverse left of the node
if (cur.left === undefined) {
//Add to the left of the current node
cur.left = newNode;
this._size = this.size + 1;
this._count += newNode.count;
traversing = false;
inserted = cur.left;
}
else {
//Traverse the left of the current node
if (cur.left)
cur = cur.left;
}
}
else if (this._compare(cur.key, newNode.key) === types_1.CP.lt) {
// Traverse right of the node
if (cur.right === undefined) {
//Add to the right of the current node
cur.right = newNode;
this._size = this.size + 1;
this._count += newNode.count;
traversing = false;
inserted = cur.right;
}
else {
//Traverse the left of the current node
if (cur.right)
cur = cur.right;
}
}
}
else {
// TODO may need to support undefined inserted
}
}
else {
traversing = false;
}
}
return;
}
if (inserted)
this._balancePath(inserted);
const orgNodeCount = (newNode === null || newNode === void 0 ? void 0 : newNode.count) || 0;
const inserted = super.add(newNode);
if (inserted) {
this._count += orgNodeCount;
}
return inserted;
}
/**
* Time Complexity: O(log n) - logarithmic time, where "n" is the number of nodes in the tree. The add method of the superclass (AVLTree) has logarithmic time complexity.
* Time Complexity: O(k log n) - logarithmic time, where "n" is the number of nodes in the tree. The add method of the superclass (AVLTree) has logarithmic time complexity.
* Space Complexity: O(1) - constant space, as it doesn't use additional data structures that scale with input size.
*/
/**
* Time Complexity: O(k log n) - logarithmic time for each insertion, where "n" is the number of nodes in the tree, and "k" is the number of keys to be inserted. This is because the method iterates through the keys and calls the add method for each.
* Time Complexity: O(k log n) - logarithmic time, where "n" is the number of nodes in the tree. The add method of the superclass (AVLTree) has logarithmic time complexity.
* Space Complexity: O(1) - constant space, as it doesn't use additional data structures that scale with input size.
*
* The function `addMany` takes an array of keys or nodes and adds them to the TreeMultimap,
* returning an array of the inserted nodes.
* @param {(BTNKey | N | undefined)[]} keysOrNodes - An array of keys or nodes. Each element can be
* of type BTNKey, N, or undefined.
* @param {V[]} [data] - The `data` parameter is an optional array of values that correspond to the
* keys or nodes being added. It is used to associate data with each key or node being added to the
* TreeMultimap. If provided, the length of the `data` array should be the same as the length of the
* @returns The function `addMany` returns an array of nodes (`N`) or `undefined` values.
* The function overrides the addMany method to add multiple keys, nodes, or entries to a data
* structure.
* @param keysOrNodesOrEntries - The parameter `keysOrNodesOrEntries` is an iterable that can contain
* either keys, nodes, or entries.
* @returns The method is returning an array of type `N | undefined`.
*/
addMany(keysOrNodes, data) {
const inserted = [];
for (let i = 0; i < keysOrNodes.length; i++) {
const keyOrNode = keysOrNodes[i];
if (keyOrNode instanceof TreeMultimapNode) {
inserted.push(this.add(keyOrNode.key, keyOrNode.value, keyOrNode.count));
continue;
}
if (keyOrNode === undefined) {
inserted.push(this.add(NaN, undefined, 0));
continue;
}
inserted.push(this.add(keyOrNode, data === null || data === void 0 ? void 0 : data[i], 1));
}
return inserted;
addMany(keysOrNodesOrEntries) {
return super.addMany(keysOrNodesOrEntries);
}

@@ -212,3 +146,3 @@ /**

const midNode = sorted[m];
this.add(midNode.key, midNode.value, midNode.count);
this.add([midNode.key, midNode.value], midNode.count);
buildBalanceBST(l, m - 1);

@@ -229,3 +163,3 @@ buildBalanceBST(m + 1, r);

const midNode = sorted[m];
this.add(midNode.key, midNode.value, midNode.count);
this.add([midNode.key, midNode.value], midNode.count);
stack.push([m + 1, r]);

@@ -297,3 +231,3 @@ stack.push([l, m - 1]);

const parentOfLeftSubTreeMax = leftSubTreeRightMost.parent;
orgCurrent = this._swap(curr, leftSubTreeRightMost);
orgCurrent = this._swapProperties(curr, leftSubTreeRightMost);
if (parentOfLeftSubTreeMax) {

@@ -333,19 +267,2 @@ if (parentOfLeftSubTreeMax.right === leftSubTreeRightMost) {

/**
* Time Complexity: O(log n) - logarithmic time, where "n" is the number of nodes in the tree. The delete method of the superclass (AVLTree) has logarithmic time complexity.
* Space Complexity: O(1) - constant space, as it doesn't use additional data structures that scale with input size.
*/
init(elements) {
if (elements) {
for (const entryOrKey of elements) {
if (Array.isArray(entryOrKey)) {
const [key, value] = entryOrKey;
this.add(key, value);
}
else {
this.add(entryOrKey);
}
}
}
}
/**
* Time Complexity: O(1) - constant time, as it performs basic pointer assignments.

@@ -366,3 +283,3 @@ * Space Complexity: O(1) - constant space, as it only uses a constant amount of memory.

_addTo(newNode, parent) {
parent = this.ensureNotKey(parent);
parent = this.ensureNode(parent);
if (parent) {

@@ -394,3 +311,3 @@ if (parent.left === undefined) {

/**
* The `_swap` function swaps the key, value, count, and height properties between two nodes.
* The `_swapProperties` function swaps the key, value, count, and height properties between two nodes.
* @param {BTNKey | N | undefined} srcNode - The `srcNode` parameter represents the source node from

@@ -403,5 +320,5 @@ * which the values will be swapped. It can be of type `BTNKey`, `N`, or `undefined`.

*/
_swap(srcNode, destNode) {
srcNode = this.ensureNotKey(srcNode);
destNode = this.ensureNotKey(destNode);
_swapProperties(srcNode, destNode) {
srcNode = this.ensureNode(srcNode);
destNode = this.ensureNode(destNode);
if (srcNode && destNode) {

@@ -425,3 +342,7 @@ const { key, value, count, height } = destNode;

}
_replaceNode(oldNode, newNode) {
newNode.count = oldNode.count + newNode.count;
return super._replaceNode(oldNode, newNode);
}
}
exports.TreeMultimap = TreeMultimap;

8

dist/data-structures/hash/hash-map.d.ts

@@ -17,8 +17,3 @@ /**

protected _objHashFn: (key: K) => object;
/**
* The constructor initializes a HashMapLinkedNode with an optional iterable of key-value pairs.
* @param options - The `options` parameter is an object that contains the `elements` property. The
* `elements` property is an iterable that contains key-value pairs represented as arrays `[K, V]`.
*/
constructor(options?: HashMapOptions<K, V>);
constructor(elements?: Iterable<[K, V]>, options?: HashMapOptions<K>);
protected _size: number;

@@ -176,2 +171,3 @@ get size(): number;

[Symbol.iterator](): Generator<[K, V], void, unknown>;
print(): void;
/**

@@ -178,0 +174,0 @@ * Time Complexity: O(1)

13

dist/data-structures/hash/hash-map.js

@@ -13,9 +13,3 @@ "use strict";

class HashMap {
/**
* The constructor initializes a HashMapLinkedNode with an optional iterable of key-value pairs.
* @param options - The `options` parameter is an object that contains the `elements` property. The
* `elements` property is an iterable that contains key-value pairs represented as arrays `[K, V]`.
*/
constructor(options = {
elements: [],
constructor(elements, options = {
hashFn: (key) => String(key),

@@ -29,3 +23,3 @@ objHashFn: (key) => key

this._sentinel.prev = this._sentinel.next = this._head = this._tail = this._sentinel;
const { elements, hashFn, objHashFn } = options;
const { hashFn, objHashFn } = options;
this._hashFn = hashFn;

@@ -352,2 +346,5 @@ this._objHashFn = objHashFn;

}
print() {
console.log([...this]);
}
/**

@@ -354,0 +351,0 @@ * Time Complexity: O(1)

3

dist/data-structures/trie/trie.d.ts

@@ -23,2 +23,4 @@ /**

constructor(words?: string[], caseSensitive?: boolean);
protected _size: number;
get size(): number;
protected _caseSensitive: boolean;

@@ -149,2 +151,3 @@ get caseSensitive(): boolean;

reduce<T>(callback: (accumulator: T, word: string, index: number, trie: this) => T, initialValue: T): T;
print(): void;
/**

@@ -151,0 +154,0 @@ * Time Complexity: O(M), where M is the length of the input string.

23

dist/data-structures/trie/trie.js

@@ -30,8 +30,12 @@ "use strict";

this._caseSensitive = caseSensitive;
this._size = 0;
if (words) {
for (const i of words) {
this.add(i);
for (const word of words) {
this.add(word);
}
}
}
get size() {
return this._size;
}
get caseSensitive() {

@@ -58,2 +62,3 @@ return this._caseSensitive;

let cur = this.root;
let isNewWord = false;
for (const c of word) {

@@ -67,4 +72,8 @@ let nodeC = cur.children.get(c);

}
cur.isEnd = true;
return true;
if (!cur.isEnd) {
isNewWord = true;
cur.isEnd = true;
this._size++;
}
return isNewWord;
}

@@ -136,2 +145,5 @@ /**

dfs(this.root, 0);
if (isDeleted) {
this._size--;
}
return isDeleted;

@@ -359,2 +371,5 @@ }

}
print() {
console.log([...this]);
}
/**

@@ -361,0 +376,0 @@ * Time Complexity: O(M), where M is the length of the input string.

6

dist/interfaces/binary-tree.d.ts
import { BinaryTree, BinaryTreeNode } from '../data-structures';
import { BinaryTreeNested, BinaryTreeNodeNested, BinaryTreeOptions, BiTreeDeleteResult, BTNCallback, BTNKey, IterableEntriesOrKeys } from '../types';
import { BinaryTreeNested, BinaryTreeNodeNested, BinaryTreeOptions, BiTreeDeleteResult, BTNCallback, BTNKey, BTNodeExemplar } from '../types';
export interface IBinaryTree<V = any, N extends BinaryTreeNode<V, N> = BinaryTreeNodeNested<V>, TREE extends BinaryTree<V, N, TREE> = BinaryTreeNested<V, N>> {
createNode(key: BTNKey, value?: N['value']): N;
createTree(options?: Partial<BinaryTreeOptions>): TREE;
init(elements: IterableEntriesOrKeys<V>): void;
add(keyOrNode: BTNKey | N | null, value?: N['value']): N | null | undefined;
add(keyOrNodeOrEntry: BTNodeExemplar<V, N>, count?: number): N | null | undefined;
addMany(nodes: Iterable<BTNodeExemplar<V, N>>): (N | null | undefined)[];
delete<C extends BTNCallback<N>>(identifier: ReturnType<C> | null, callback: C): BiTreeDeleteResult<N>[];
}

7

dist/types/common.d.ts

@@ -22,2 +22,7 @@ import { BTNKey } from "./data-structures";

};
export type IterableEntriesOrKeys<T> = Iterable<[BTNKey, T | undefined] | BTNKey>;
export type BTNodeEntry<T> = [BTNKey | null | undefined, T | undefined];
export type BTNodeKeyOrNode<N> = BTNKey | null | undefined | N;
export type BTNodeExemplar<T, N> = BTNodeEntry<T> | BTNodeKeyOrNode<N>;
export type BTNodePureExemplar<T, N> = [BTNKey, T | undefined] | BTNodePureKeyOrNode<N>;
export type BTNodePureKeyOrNode<N> = BTNKey | N;
export type BSTNodeKeyOrNode<N> = BTNKey | undefined | N;

3

dist/types/data-structures/hash/hash-map.d.ts

@@ -7,6 +7,5 @@ export type HashMapLinkedNode<K, V> = {

};
export type HashMapOptions<K, V> = {
elements: Iterable<[K, V]>;
export type HashMapOptions<K> = {
hashFn: (key: K) => string;
objHashFn: (key: K) => object;
};

4

package.json
{
"name": "directed-graph-typed",
"version": "1.47.6",
"version": "1.47.7",
"description": "Directed Graph. Javascript & Typescript Data Structure.",

@@ -150,4 +150,4 @@ "main": "dist/index.js",

"dependencies": {
"data-structure-typed": "^1.47.6"
"data-structure-typed": "^1.47.7"
}
}

98

src/data-structures/binary-tree/avl-tree.ts

@@ -9,4 +9,12 @@ /**

import { BST, BSTNode } from './bst';
import type { AVLTreeNested, AVLTreeNodeNested, AVLTreeOptions, BiTreeDeleteResult, BTNKey } from '../../types';
import { BTNCallback, IterableEntriesOrKeys } from '../../types';
import type {
AVLTreeNested,
AVLTreeNodeNested,
AVLTreeOptions,
BiTreeDeleteResult,
BSTNodeKeyOrNode,
BTNKey,
BTNodeExemplar
} from '../../types';
import { BTNCallback } from '../../types';
import { IBinaryTree } from '../../interfaces';

@@ -23,2 +31,12 @@

/**
* 1. Height-Balanced: Each node's left and right subtrees differ in height by no more than one.
* 2. Automatic Rebalancing: AVL trees rebalance themselves automatically during insertions and deletions.
* 3. Rotations for Balancing: Utilizes rotations (single or double) to maintain balance after updates.
* 4. Order Preservation: Maintains the binary search tree property where left child values are less than the parent, and right child values are greater.
* 5. Efficient Lookups: Offers O(log n) search time, where 'n' is the number of nodes, due to its balanced nature.
* 6. Complex Insertions and Deletions: Due to rebalancing, these operations are more complex than in a regular BST.
* 7. Path Length: The path length from the root to any leaf is longer compared to an unbalanced BST, but shorter than a linear chain of nodes.
* 8. Memory Overhead: Stores balance factors (or heights) at each node, leading to slightly higher memory usage compared to a regular BST.
*/
export class AVLTree<V = any, N extends AVLTreeNode<V, N> = AVLTreeNode<V, AVLTreeNodeNested<V>>, TREE extends AVLTree<V, N, TREE> = AVLTree<V, N, AVLTreeNested<V, N>>>

@@ -29,10 +47,13 @@ extends BST<V, N, TREE>

/**
* This is a constructor function for an AVL tree data structure in TypeScript.
* @param {AVLTreeOptions} [options] - The `options` parameter is an optional object that can be passed to the
* constructor of the AVLTree class. It allows you to customize the behavior of the AVL tree by providing different
* options.
* The constructor function initializes an AVLTree object with optional elements and options.
* @param [elements] - The `elements` parameter is an optional iterable of `BTNodeExemplar<V, N>`
* objects. It represents a collection of elements that will be added to the AVL tree during
* initialization.
* @param [options] - The `options` parameter is an optional object that allows you to customize the
* behavior of the AVL tree. It is of type `Partial<AVLTreeOptions>`, which means that you can
* provide only a subset of the properties defined in the `AVLTreeOptions` interface.
*/
constructor(elements?: IterableEntriesOrKeys<V>, options?: Partial<AVLTreeOptions>) {
constructor(elements?: Iterable<BTNodeExemplar<V, N>>, options?: Partial<AVLTreeOptions>) {
super([], options);
if (elements) this.init(elements);
if (elements) super.addMany(elements);
}

@@ -53,2 +74,9 @@

/**
* The function creates a new AVL tree with the specified options and returns it.
* @param {AVLTreeOptions} [options] - The `options` parameter is an optional object that can be
* passed to the `createTree` function. It is used to customize the behavior of the AVL tree that is
* being created.
* @returns a new AVLTree object.
*/
override createTree(options?: AVLTreeOptions): TREE {

@@ -64,14 +92,17 @@ return new AVLTree<V, N, TREE>([], {

* Space Complexity: O(1) - constant space, as it doesn't use additional data structures that scale with input size.
*/
/**
* Time Complexity: O(log n) - logarithmic time, where "n" is the number of nodes in the tree. The add method of the superclass (BST) has logarithmic time complexity.
* Space Complexity: O(1) - constant space, as it doesn't use additional data structures that scale with input size.
*
* The function overrides the add method of a class, adds a key-value pair to a data structure, and
* balances the structure if necessary.
* @param {BTNKey | N | null | undefined} keyOrNode - The `keyOrNode` parameter can be of type
* `BTNKey`, `N`, `null`, or `undefined`.
* @param {V} [value] - The `value` parameter is the value associated with the key that is being
* added to the binary search tree.
* @returns The method is returning either a node (N) or undefined.
* The function overrides the add method of a binary tree node and balances the tree after inserting
* a new node.
* @param keyOrNodeOrEntry - The parameter `keyOrNodeOrEntry` can be either a key, a node, or an
* entry.
* @returns The method is returning either the inserted node or `undefined`.
*/
override add(keyOrNode: BTNKey | N | null | undefined, value?: V): N | undefined {
if (keyOrNode === null) return undefined;
const inserted = super.add(keyOrNode, value);
override add(keyOrNodeOrEntry: BTNodeExemplar<V, N>): N | undefined {
if (keyOrNodeOrEntry === null) return undefined;
const inserted = super.add(keyOrNodeOrEntry);
if (inserted) this._balancePath(inserted);

@@ -115,22 +146,5 @@ return inserted;

/**
* Time Complexity: O(log n) - logarithmic time, where "n" is the number of nodes in the tree. The delete method of the superclass (BST) has logarithmic time complexity.
* Space Complexity: O(1) - constant space, as it doesn't use additional data structures that scale with input size.
*/
init(elements: IterableEntriesOrKeys<V>): void {
if (elements) {
for (const entryOrKey of elements) {
if (Array.isArray(entryOrKey)) {
const [key, value] = entryOrKey;
this.add(key, value);
} else {
this.add(entryOrKey);
}
}
}
}
/**
* The `_swap` function swaps the key, value, and height properties between two nodes in a binary
* The `_swapProperties` function swaps the key, value, and height properties between two nodes in a binary
* tree.

@@ -144,5 +158,5 @@ * @param {BTNKey | N | undefined} srcNode - The `srcNode` parameter represents the source node that

*/
protected override _swap(srcNode: BTNKey | N | undefined, destNode: BTNKey | N | undefined): N | undefined {
srcNode = this.ensureNotKey(srcNode);
destNode = this.ensureNotKey(destNode);
protected override _swapProperties(srcNode: BSTNodeKeyOrNode<N>, destNode: BSTNodeKeyOrNode<N>): N | undefined {
srcNode = this.ensureNode(srcNode);
destNode = this.ensureNode(destNode);

@@ -460,2 +474,8 @@ if (srcNode && destNode) {

}
protected _replaceNode(oldNode: N, newNode: N): N {
newNode.height = oldNode.height;
return super._replaceNode(oldNode, newNode)
}
}

311

src/data-structures/binary-tree/bst.ts

@@ -8,4 +8,14 @@ /**

*/
import type { BSTNested, BSTNodeNested, BSTOptions, BTNCallback, BTNKey, Comparator } from '../../types';
import { CP, IterableEntriesOrKeys, IterationType } from '../../types';
import type {
BSTNested,
BSTNodeKeyOrNode,
BSTNodeNested,
BSTOptions,
BTNCallback,
BTNKey,
BTNodeExemplar,
BTNodePureExemplar,
Comparator
} from '../../types';
import { CP, IterationType } from '../../types';
import { BinaryTree, BinaryTreeNode } from './binary-tree';

@@ -66,2 +76,11 @@ import { IBinaryTree } from '../../interfaces';

/**
* 1. Node Order: Each node's left child has a lesser value, and the right child has a greater value.
* 2. Unique Keys: No duplicate keys in a standard BST.
* 3. Efficient Search: Enables quick search, minimum, and maximum operations.
* 4. Inorder Traversal: Yields nodes in ascending order.
* 5. Logarithmic Operations: Ideal operations like insertion, deletion, and searching are O(log n) time-efficient.
* 6. Balance Variability: Can become unbalanced; special types maintain balance.
* 7. No Auto-Balancing: Standard BSTs don't automatically balance themselves.
*/
export class BST<V = any, N extends BSTNode<V, N> = BSTNode<V, BSTNodeNested<V>>, TREE extends BST<V, N, TREE> = BST<V, N, BSTNested<V, N>>>

@@ -71,8 +90,12 @@ extends BinaryTree<V, N, TREE>

/**
* The constructor function initializes a binary search tree with an optional comparator function.
* @param {BSTOptions} [options] - An optional object that contains additional configuration options
* for the binary search tree.
* This is the constructor function for a binary search tree class in TypeScript, which initializes
* the tree with optional elements and options.
* @param [elements] - An optional iterable of BTNodeExemplar objects that will be added to the
* binary search tree.
* @param [options] - The `options` parameter is an optional object that can contain additional
* configuration options for the binary search tree. It can have the following properties:
*/
constructor(elements?: IterableEntriesOrKeys<V>, options?: Partial<BSTOptions>) {
constructor(elements?: Iterable<BTNodeExemplar<V, N>>, options?: Partial<BSTOptions>) {
super([], options);

@@ -88,3 +111,4 @@

this._root = undefined;
if (elements) this.init(elements);
if (elements) this.addMany(elements);
}

@@ -94,5 +118,2 @@

/**
* Get the root node of the binary tree.
*/
override get root(): N | undefined {

@@ -116,2 +137,9 @@ return this._root;

/**
* The function creates a new binary search tree with the specified options.
* @param [options] - The `options` parameter is an optional object that allows you to customize the
* behavior of the `createTree` method. It accepts a partial `BSTOptions` object, which is a type
* that defines various options for creating a binary search tree.
* @returns a new instance of the BST class with the specified options.
*/
override createTree(options?: Partial<BSTOptions>): TREE {

@@ -127,155 +155,147 @@ return new BST<V, N, TREE>([], {

* Space Complexity: O(1) - Constant space is used.
*/
/**
* Time Complexity: O(log n) - Average case for a balanced tree. In the worst case (unbalanced tree), it can be O(n).
* Space Complexity: O(1) - Constant space is used.
*
* The `add` function adds a new node to a binary search tree based on the provided key and value.
* @param {BTNKey | N | null | undefined} keyOrNode - The `keyOrNode` parameter can be one of the
* following types:
* @param {V} [value] - The `value` parameter is an optional value that can be associated with the
* key or node being added to the binary search tree.
* @returns The method `add` returns a node (`N`) that was inserted into the binary search tree. If
* no node was inserted, it returns `undefined`.
* The `add` function adds a new node to a binary search tree, either by key or by providing a node
* object.
* @param keyOrNodeOrEntry - The `keyOrNodeOrEntry` parameter can be one of the following:
* @returns The method returns either the newly added node (`newNode`) or `undefined` if the input
* (`keyOrNodeOrEntry`) is null, undefined, or does not match any of the expected types.
*/
override add(keyOrNode: BTNKey | N | null | undefined, value?: V): N | undefined {
if (keyOrNode === null) return undefined;
// TODO support node as a parameter
let inserted: N | undefined;
override add(keyOrNodeOrEntry: BTNodeExemplar<V, N>): N | undefined {
if (keyOrNodeOrEntry === null || keyOrNodeOrEntry === undefined) {
return undefined;
}
let newNode: N | undefined;
if (keyOrNode instanceof BSTNode) {
newNode = keyOrNode;
} else if (this.isNodeKey(keyOrNode)) {
newNode = this.createNode(keyOrNode, value);
if (keyOrNodeOrEntry instanceof BSTNode) {
newNode = keyOrNodeOrEntry;
} else if (this.isNodeKey(keyOrNodeOrEntry)) {
newNode = this.createNode(keyOrNodeOrEntry);
} else if (this.isEntry(keyOrNodeOrEntry)) {
const [key, value] = keyOrNodeOrEntry;
if (key === undefined || key === null) {
return;
} else {
newNode = this.createNode(key, value);
}
} else {
newNode = undefined;
return;
}
if (this.root === undefined) {
this._setRoot(newNode);
this._size = this.size + 1;
inserted = this.root;
} else {
let cur = this.root;
let traversing = true;
while (traversing) {
if (cur !== undefined && newNode !== undefined) {
if (this._compare(cur.key, newNode.key) === CP.eq) {
if (newNode) {
cur.value = newNode.value;
}
//Duplicates are not accepted.
traversing = false;
inserted = cur;
} else if (this._compare(cur.key, newNode.key) === CP.gt) {
// Traverse left of the node
if (cur.left === undefined) {
if (newNode) {
newNode.parent = cur;
}
//Add to the left of the current node
cur.left = newNode;
this._size = this.size + 1;
traversing = false;
inserted = cur.left;
} else {
//Traverse the left of the current node
if (cur.left) cur = cur.left;
}
} else if (this._compare(cur.key, newNode.key) === CP.lt) {
// Traverse right of the node
if (cur.right === undefined) {
if (newNode) {
newNode.parent = cur;
}
//Add to the right of the current node
cur.right = newNode;
this._size = this.size + 1;
traversing = false;
inserted = cur.right;
} else {
//Traverse the left of the current node
if (cur.right) cur = cur.right;
}
}
} else {
traversing = false;
this._size++;
return this.root;
}
let current = this.root;
while (current !== undefined) {
if (this._compare(current.key, newNode.key) === CP.eq) {
// if (current !== newNode) {
// The key value is the same but the reference is different, update the value of the existing node
this._replaceNode(current, newNode);
return newNode;
// } else {
// The key value is the same and the reference is the same, replace the entire node
// this._replaceNode(current, newNode);
// return;
// }
} else if (this._compare(current.key, newNode.key) === CP.gt) {
if (current.left === undefined) {
current.left = newNode;
newNode.parent = current;
this._size++;
return newNode;
}
current = current.left;
} else {
if (current.right === undefined) {
current.right = newNode;
newNode.parent = current;
this._size++;
return newNode;
}
current = current.right;
}
}
return inserted;
return undefined;
}
/**
* Time Complexity: O(log n) - Average case for a balanced tree. In the worst case (unbalanced tree), it can be O(n).
* Space Complexity: O(1) - Constant space is used.
* Time Complexity: O(k log n) - Adding each element individually in a balanced tree.
* Space Complexity: O(k) - Additional space is required for the sorted array.
*/
/**
* Time Complexity: O(n log n) - Adding each element individually in a balanced tree.
* Space Complexity: O(n) - Additional space is required for the sorted array.
* Time Complexity: O(k log n) - Adding each element individually in a balanced tree.
* Space Complexity: O(k) - Additional space is required for the sorted array.
*
* The `addMany` function is used to efficiently add multiple keys or nodes with corresponding data
* to a binary search tree.
* @param {(BTNKey | N | undefined)[]} keysOrNodes - An array of keys or nodes to be added to the
* binary search tree. Each element can be of type `BTNKey` (binary tree node key), `N` (binary tree
* node), or `undefined`.
* @param {(V | undefined)[]} [data] - An optional array of values to associate with the keys or
* nodes being added. If provided, the length of the `data` array must be the same as the length of
* the `keysOrNodes` array.
* The `addMany` function in TypeScript adds multiple nodes to a binary tree, either in a balanced or
* unbalanced manner, and returns an array of the inserted nodes.
* @param keysOrNodesOrEntries - An iterable containing keys, nodes, or entries to be added to the
* binary tree.
* @param [isBalanceAdd=true] - A boolean flag indicating whether the tree should be balanced after
* adding the nodes. The default value is `true`.
* adding the nodes. The default value is true.
* @param iterationType - The `iterationType` parameter is an optional parameter that specifies the
* type of iteration to use when adding multiple keys or nodes to the binary search tree. It has a
* default value of `this.iterationType`, which means it will use the iteration type specified in the
* current instance of the binary search tree
* @returns The function `addMany` returns an array of nodes (`N`) or `undefined` values.
* type of iteration to use when adding multiple keys or nodes to the binary tree. It has a default
* value of `this.iterationType`, which means it will use the iteration type specified by the binary
* tree instance.
* @returns The `addMany` function returns an array of `N` or `undefined` values.
*/
override addMany(
keysOrNodes: (BTNKey | N | undefined)[],
data?: (V | undefined)[],
keysOrNodesOrEntries: Iterable<BTNodeExemplar<V, N>>,
isBalanceAdd = true,
iterationType = this.iterationType
): (N | undefined)[] {
// TODO this addMany function is inefficient, it should be optimized
function hasNoUndefined(arr: (BTNKey | N | undefined)[]): arr is (BTNKey | N)[] {
return arr.indexOf(undefined) === -1;
const inserted: (N | undefined)[] = []
if (!isBalanceAdd) {
for (const kve of keysOrNodesOrEntries) {
const nn = this.add(kve)
inserted.push(nn);
}
return inserted;
}
const realBTNExemplars: BTNodePureExemplar<V, N>[] = [];
if (!isBalanceAdd || !hasNoUndefined(keysOrNodes)) {
return super.addMany(keysOrNodes, data).map(n => n ?? undefined);
const isRealBTNExemplar = (kve: BTNodeExemplar<V, N>): kve is BTNodePureExemplar<V, N> => {
if (kve === undefined || kve === null) return false;
return !(this.isEntry(kve) && (kve[0] === undefined || kve[0] === null));
}
const inserted: (N | undefined)[] = [];
const combinedArr: [BTNKey | N, V][] = keysOrNodes.map(
(value: BTNKey | N, index) => [value, data?.[index]] as [BTNKey | N, V]
);
for (const kve of keysOrNodesOrEntries) {
isRealBTNExemplar(kve) && realBTNExemplars.push(kve);
}
let sorted = [];
// TODO this addMany function is inefficient, it should be optimized
let sorted: BTNodePureExemplar<V, N>[] = [];
function _isNodeOrUndefinedTuple(arr: [BTNKey | N, V][]): arr is [N, V][] {
for (const [keyOrNode] of arr) if (keyOrNode instanceof BSTNode) return true;
return false;
}
sorted = realBTNExemplars.sort((a, b) => {
let aR: number, bR: number;
if (this.isEntry(a)) aR = a[0]
else if (this.isRealNode(a)) aR = a.key
else aR = a;
const _isBinaryTreeKeyOrNullTuple = (arr: [BTNKey | N, V][]): arr is [BTNKey, V][] => {
for (const [keyOrNode] of arr) if (this.isNodeKey(keyOrNode)) return true;
return false;
};
if (this.isEntry(b)) bR = b[0]
else if (this.isRealNode(b)) bR = b.key
else bR = b;
let sortedKeysOrNodes: (number | N | undefined)[] = [],
sortedData: (V | undefined)[] | undefined = [];
return aR - bR;
})
if (_isNodeOrUndefinedTuple(combinedArr)) {
sorted = combinedArr.sort((a, b) => a[0].key - b[0].key);
} else if (_isBinaryTreeKeyOrNullTuple(combinedArr)) {
sorted = combinedArr.sort((a, b) => a[0] - b[0]);
} else {
throw new Error('Invalid input keysOrNodes');
}
sortedKeysOrNodes = sorted.map(([keyOrNode]) => keyOrNode);
sortedData = sorted.map(([, value]) => value);
const _dfs = (arr: (BTNKey | undefined | N)[], data?: (V | undefined)[]) => {
const _dfs = (arr: BTNodePureExemplar<V, N>[]) => {
if (arr.length === 0) return;
const mid = Math.floor((arr.length - 1) / 2);
const newNode = this.add(arr[mid], data?.[mid]);
const newNode = this.add(arr[mid]);
inserted.push(newNode);
_dfs(arr.slice(0, mid), data?.slice(0, mid));
_dfs(arr.slice(mid + 1), data?.slice(mid + 1));
_dfs(arr.slice(0, mid));
_dfs(arr.slice(mid + 1));
};

@@ -291,3 +311,3 @@ const _iterate = () => {

const m = l + Math.floor((r - l) / 2);
const newNode = this.add(sortedKeysOrNodes[m], sortedData?.[m]);
const newNode = this.add(sorted[m]);
inserted.push(newNode);

@@ -301,3 +321,3 @@ stack.push([m + 1, r]);

if (iterationType === IterationType.RECURSIVE) {
_dfs(sortedKeysOrNodes, sortedData);
_dfs(sorted);
} else {

@@ -330,3 +350,3 @@ _iterate();

*/
lastKey(beginRoot: BTNKey | N | undefined = this.root, iterationType = this.iterationType): BTNKey {
lastKey(beginRoot: BSTNodeKeyOrNode<N> = this.root, iterationType = this.iterationType): BTNKey {
if (this._compare(0, 1) === CP.lt) return this.getRightMost(beginRoot, iterationType)?.key ?? 0;

@@ -387,3 +407,3 @@ else if (this._compare(0, 1) === CP.gt) return this.getLeftMost(beginRoot, iterationType)?.key ?? 0;

/**
* The function `ensureNotKey` returns the node corresponding to the given key if it is a node key,
* The function `ensureNode` returns the node corresponding to the given key if it is a node key,
* otherwise it returns the key itself.

@@ -396,3 +416,3 @@ * @param {BTNKey | N | undefined} key - The `key` parameter can be of type `BTNKey`, `N`, or

*/
override ensureNotKey(key: BTNKey | N | undefined, iterationType = IterationType.ITERATIVE): N | undefined {
override ensureNode(key: BSTNodeKeyOrNode<N>, iterationType = IterationType.ITERATIVE): N | undefined {
return this.isNodeKey(key) ? this.getNodeByKey(key, iterationType) : key;

@@ -428,6 +448,6 @@ }

onlyOne = false,
beginRoot: BTNKey | N | undefined = this.root,
beginRoot: BSTNodeKeyOrNode<N> = this.root,
iterationType = this.iterationType
): N[] {
beginRoot = this.ensureNotKey(beginRoot);
beginRoot = this.ensureNode(beginRoot);
if (!beginRoot) return [];

@@ -510,6 +530,6 @@ const ans: N[] = [];

lesserOrGreater: CP = CP.lt,
targetNode: BTNKey | N | undefined = this.root,
targetNode: BSTNodeKeyOrNode<N> = this.root,
iterationType = this.iterationType
): ReturnType<C>[] {
targetNode = this.ensureNotKey(targetNode);
targetNode = this.ensureNode(targetNode);
const ans: ReturnType<BTNCallback<N>>[] = [];

@@ -576,3 +596,3 @@ if (!targetNode) return ans;

const midNode = sorted[m];
this.add(midNode.key, midNode.value);
this.add([midNode.key, midNode.value]);
buildBalanceBST(l, m - 1);

@@ -594,3 +614,3 @@ buildBalanceBST(m + 1, r);

debugger;
this.add(midNode.key, midNode.value);
this.add([midNode.key, midNode.value]);
stack.push([m + 1, r]);

@@ -673,20 +693,3 @@ stack.push([l, m - 1]);

/**
* Time Complexity: O(n) - Visiting each node once.
* Space Complexity: O(log n) - Space for the recursive call stack in the worst case.
*/
init(elements: IterableEntriesOrKeys<V>): void {
if (elements) {
for (const entryOrKey of elements) {
if (Array.isArray(entryOrKey)) {
const [key, value] = entryOrKey;
this.add(key, value);
} else {
this.add(entryOrKey);
}
}
}
}
protected _setRoot(v: N | undefined) {

@@ -693,0 +696,0 @@ if (v) {

115

src/data-structures/binary-tree/rb-tree.ts

@@ -11,5 +11,6 @@ /**

BiTreeDeleteResult,
BSTNodeKeyOrNode,
BTNCallback,
BTNKey,
IterableEntriesOrKeys,
BTNodeExemplar,
IterationType,

@@ -49,13 +50,18 @@ RBTNColor,

/**
* The constructor function initializes a Red-Black Tree with an optional set of options.
* @param {RBTreeOptions} [options] - The `options` parameter is an optional object that can be
* passed to the constructor. It is used to configure the RBTree object with specific options.
* This is the constructor function for a Red-Black Tree data structure in TypeScript, which
* initializes the tree with optional elements and options.
* @param [elements] - The `elements` parameter is an optional iterable of `BTNodeExemplar<V, N>`
* objects. It represents the initial elements that will be added to the RBTree during its
* construction. If this parameter is provided, the `addMany` method is called to add all the
* elements to the
* @param [options] - The `options` parameter is an optional object that allows you to customize the
* behavior of the RBTree. It is of type `Partial<RBTreeOptions>`, which means that you can provide
* only a subset of the properties defined in the `RBTreeOptions` interface.
*/
constructor(elements?: IterableEntriesOrKeys<V>, options?: Partial<RBTreeOptions>) {
constructor(elements?: Iterable<BTNodeExemplar<V, N>>, options?: Partial<RBTreeOptions>) {
super([], options);
this._root = this.Sentinel;
if (elements) this.init(elements);
if (elements) super.addMany(elements);
}

@@ -75,2 +81,14 @@

/**
* The function creates a new Red-Black Tree node with the specified key, value, and color.
* @param {BTNKey} key - The key parameter is the key value associated with the node. It is used to
* identify and compare nodes in the Red-Black Tree.
* @param {V} [value] - The `value` parameter is an optional parameter that represents the value
* associated with the node. It is of type `V`, which is a generic type that can be replaced with any
* specific type when using the `createNode` method.
* @param {RBTNColor} color - The "color" parameter is used to specify the color of the node in a
* Red-Black Tree. It can be either "RED" or "BLACK". By default, the color is set to "BLACK".
* @returns The method is returning a new instance of a RedBlackTreeNode with the specified key,
* value, and color.
*/
override createNode(key: BTNKey, value?: V, color: RBTNColor = RBTNColor.BLACK): N {

@@ -80,2 +98,9 @@ return new RedBlackTreeNode<V, N>(key, value, color) as N;

/**
* The function creates a Red-Black Tree with the specified options and returns it.
* @param {RBTreeOptions} [options] - The `options` parameter is an optional object that can be
* passed to the `createTree` function. It is used to customize the behavior of the `RedBlackTree`
* class.
* @returns a new instance of a RedBlackTree object.
*/
override createTree(options?: RBTreeOptions): TREE {

@@ -91,20 +116,26 @@ return new RedBlackTree<V, N, TREE>([], {

* Space Complexity: O(1)
*
* The `add` function adds a new node to a Red-Black Tree data structure.
* @param {BTNKey | N | null | undefined} keyOrNode - The `keyOrNode` parameter can be one of the
* following types:
* @param {V} [value] - The `value` parameter is an optional value that can be associated with the
* key in the node being added to the Red-Black Tree.
* @returns The method returns either a node (`N`) or `undefined`.
*/
override add(keyOrNode: BTNKey | N | null | undefined, value?: V): N | undefined {
/**
* The function adds a node to a Red-Black Tree data structure.
* @param keyOrNodeOrEntry - The `keyOrNodeOrEntry` parameter can be one of the following:
* @returns The method `add` returns either an instance of `N` (the node that was added) or
* `undefined`.
*/
override add(keyOrNodeOrEntry: BTNodeExemplar<V, N>): N | undefined {
let node: N;
if (this.isNodeKey(keyOrNode)) {
node = this.createNode(keyOrNode, value, RBTNColor.RED);
} else if (keyOrNode instanceof RedBlackTreeNode) {
node = keyOrNode;
} else if (keyOrNode === null) {
if (this.isNodeKey(keyOrNodeOrEntry)) {
node = this.createNode(keyOrNodeOrEntry, undefined, RBTNColor.RED);
} else if (keyOrNodeOrEntry instanceof RedBlackTreeNode) {
node = keyOrNodeOrEntry;
} else if (keyOrNodeOrEntry === null || keyOrNodeOrEntry === undefined) {
return;
} else if (keyOrNode === undefined) {
return;
} else if (this.isEntry(keyOrNodeOrEntry)) {
const [key, value] = keyOrNodeOrEntry;
if (key === undefined || key === null) {
return;
} else {
node = this.createNode(key, value, RBTNColor.RED);
}
} else {

@@ -128,2 +159,5 @@ return;

} else {
if (node !== x) {
this._replaceNode(x, node)
}
return;

@@ -273,2 +307,7 @@ }

* Space Complexity: O(1)
*/
/**
* Time Complexity: O(log n) on average (where n is the number of nodes in the tree)
* Space Complexity: O(1)
*

@@ -295,7 +334,7 @@ * The function `getNode` retrieves a single node from a binary tree based on a given identifier and

callback: C = this._defaultOneParamCallback as C,
beginRoot: BTNKey | N | undefined = this.root,
beginRoot: BSTNodeKeyOrNode<N> = this.root,
iterationType = this.iterationType
): N | null | undefined {
if ((identifier as any) instanceof BinaryTreeNode) callback = (node => node) as C;
beginRoot = this.ensureNotKey(beginRoot);
beginRoot = this.ensureNode(beginRoot);
return this.getNodes(identifier, callback, true, beginRoot, iterationType)[0] ?? undefined;

@@ -368,15 +407,2 @@ }

init(elements: IterableEntriesOrKeys<V>): void {
if (elements) {
for (const entryOrKey of elements) {
if (Array.isArray(entryOrKey)) {
const [key, value] = entryOrKey;
this.add(key, value);
} else {
this.add(entryOrKey);
}
}
}
}
protected override _setRoot(v: N) {

@@ -608,2 +634,17 @@ if (v) {

}
/**
* The function replaces an old node with a new node while preserving the color of the old node.
* @param {N} oldNode - The `oldNode` parameter represents the node that needs to be replaced in a
* data structure. It is of type `N`, which is the type of the nodes in the data structure.
* @param {N} newNode - The `newNode` parameter is the node that will replace the `oldNode` in the
* data structure.
* @returns The method is returning the result of calling the `_replaceNode` method from the
* superclass, passing in the `oldNode` and `newNode` as arguments.
*/
protected _replaceNode(oldNode: N, newNode: N): N {
newNode.color = oldNode.color;
return super._replaceNode(oldNode, newNode)
}
}

212

src/data-structures/binary-tree/tree-multimap.ts

@@ -8,12 +8,10 @@ /**

*/
import type { BTNKey, TreeMultimapNodeNested, TreeMultimapOptions } from '../../types';
import {
BiTreeDeleteResult,
BTNCallback,
CP,
FamilyPosition,
IterableEntriesOrKeys,
IterationType,
TreeMultimapNested
import type {
BSTNodeKeyOrNode,
BTNKey,
BTNodeExemplar,
TreeMultimapNodeNested,
TreeMultimapOptions
} from '../../types';
import { BiTreeDeleteResult, BTNCallback, FamilyPosition, IterationType, TreeMultimapNested } from '../../types';
import { IBinaryTree } from '../../interfaces';

@@ -52,11 +50,5 @@ import { AVLTree, AVLTreeNode } from './avl-tree';

/**
* The constructor function for a TreeMultimap class in TypeScript, which extends another class and sets an option to
* merge duplicated values.
* @param {TreeMultimapOptions} [options] - An optional object that contains additional configuration options for the
* TreeMultimap.
*/
constructor(elements?: IterableEntriesOrKeys<V>, options?: Partial<TreeMultimapOptions>) {
constructor(elements?: Iterable<BTNodeExemplar<V, N>>, options?: Partial<TreeMultimapOptions>) {
super([], options);
if (elements) this.init(elements);
if (elements) this.addMany(elements);
}

@@ -66,4 +58,7 @@

// TODO the _count is not accurate after nodes count modified
get count(): number {
return this._count;
let sum = 0;
this.subTreeTraverse(node => sum += node.count);
return sum;
}

@@ -94,79 +89,39 @@

* Space Complexity: O(1) - constant space, as it doesn't use additional data structures that scale with input size.
*/
/**
* Time Complexity: O(log n) - logarithmic time, where "n" is the number of nodes in the tree. The add method of the superclass (AVLTree) has logarithmic time complexity.
* Space Complexity: O(1) - constant space, as it doesn't use additional data structures that scale with input size.
*
* The `add` function adds a new node to the tree multimap, updating the count if the key already
* exists, and balances the tree if necessary.
* @param {BTNKey | N | null | undefined} keyOrNode - The `keyOrNode` parameter can be one of the
* following types:
* @param {V} [value] - The `value` parameter represents the value associated with the key that is
* being added to the tree. It is an optional parameter, so it can be omitted if not needed.
* The `add` function overrides the base class `add` function to add a new node to the tree multimap
* and update the count.
* @param keyOrNodeOrEntry - The `keyOrNodeOrEntry` parameter can be one of the following:
* @param [count=1] - The `count` parameter is an optional parameter that specifies the number of
* times the key-value pair should be added to the multimap. If not provided, the default value is 1.
* @returns a node (`N`) or `undefined`.
* times the key or node or entry should be added to the multimap. If not provided, the default value
* is 1.
* @returns either a node (`N`) or `undefined`.
*/
override add(keyOrNode: BTNKey | N | null | undefined, value?: V, count = 1): N | undefined {
if (keyOrNode === null) return undefined;
let inserted: N | undefined = undefined,
newNode: N | undefined;
if (keyOrNode instanceof TreeMultimapNode) {
newNode = this.createNode(keyOrNode.key, keyOrNode.value, keyOrNode.count);
} else if (keyOrNode === undefined) {
newNode = undefined;
override add(keyOrNodeOrEntry: BTNodeExemplar<V, N>, count = 1): N | undefined {
let newNode: N | undefined;
if (keyOrNodeOrEntry === undefined || keyOrNodeOrEntry === null) {
return;
} else if (keyOrNodeOrEntry instanceof TreeMultimapNode) {
newNode = keyOrNodeOrEntry;
} else if (this.isNodeKey(keyOrNodeOrEntry)) {
newNode = this.createNode(keyOrNodeOrEntry, undefined, count);
} else if (this.isEntry(keyOrNodeOrEntry)) {
const [key, value] = keyOrNodeOrEntry;
if (key === undefined || key === null) {
return;
} else {
newNode = this.createNode(key, value, count);
}
} else {
newNode = this.createNode(keyOrNode, value, count);
return;
}
if (!this.root) {
this._setRoot(newNode);
this._size = this.size + 1;
if (newNode) this._count += newNode.count;
inserted = this.root;
} else {
let cur = this.root;
let traversing = true;
while (traversing) {
if (cur) {
if (newNode) {
if (this._compare(cur.key, newNode.key) === CP.eq) {
cur.value = newNode.value;
cur.count += newNode.count;
this._count += newNode.count;
traversing = false;
inserted = cur;
} else if (this._compare(cur.key, newNode.key) === CP.gt) {
// Traverse left of the node
if (cur.left === undefined) {
//Add to the left of the current node
cur.left = newNode;
this._size = this.size + 1;
this._count += newNode.count;
traversing = false;
inserted = cur.left;
} else {
//Traverse the left of the current node
if (cur.left) cur = cur.left;
}
} else if (this._compare(cur.key, newNode.key) === CP.lt) {
// Traverse right of the node
if (cur.right === undefined) {
//Add to the right of the current node
cur.right = newNode;
this._size = this.size + 1;
this._count += newNode.count;
traversing = false;
inserted = cur.right;
} else {
//Traverse the left of the current node
if (cur.right) cur = cur.right;
}
}
} else {
// TODO may need to support undefined inserted
}
} else {
traversing = false;
}
}
const orgNodeCount = newNode?.count || 0;
const inserted = super.add(newNode);
if (inserted) {
this._count += orgNodeCount;
}
if (inserted) this._balancePath(inserted);
return inserted;

@@ -176,3 +131,3 @@ }

/**
* Time Complexity: O(log n) - logarithmic time, where "n" is the number of nodes in the tree. The add method of the superclass (AVLTree) has logarithmic time complexity.
* Time Complexity: O(k log n) - logarithmic time, where "n" is the number of nodes in the tree. The add method of the superclass (AVLTree) has logarithmic time complexity.
* Space Complexity: O(1) - constant space, as it doesn't use additional data structures that scale with input size.

@@ -182,33 +137,13 @@ */

/**
* Time Complexity: O(k log n) - logarithmic time for each insertion, where "n" is the number of nodes in the tree, and "k" is the number of keys to be inserted. This is because the method iterates through the keys and calls the add method for each.
* Time Complexity: O(k log n) - logarithmic time, where "n" is the number of nodes in the tree. The add method of the superclass (AVLTree) has logarithmic time complexity.
* Space Complexity: O(1) - constant space, as it doesn't use additional data structures that scale with input size.
*
* The function `addMany` takes an array of keys or nodes and adds them to the TreeMultimap,
* returning an array of the inserted nodes.
* @param {(BTNKey | N | undefined)[]} keysOrNodes - An array of keys or nodes. Each element can be
* of type BTNKey, N, or undefined.
* @param {V[]} [data] - The `data` parameter is an optional array of values that correspond to the
* keys or nodes being added. It is used to associate data with each key or node being added to the
* TreeMultimap. If provided, the length of the `data` array should be the same as the length of the
* @returns The function `addMany` returns an array of nodes (`N`) or `undefined` values.
* The function overrides the addMany method to add multiple keys, nodes, or entries to a data
* structure.
* @param keysOrNodesOrEntries - The parameter `keysOrNodesOrEntries` is an iterable that can contain
* either keys, nodes, or entries.
* @returns The method is returning an array of type `N | undefined`.
*/
override addMany(keysOrNodes: (BTNKey | N | undefined)[], data?: V[]): (N | undefined)[] {
const inserted: (N | undefined)[] = [];
for (let i = 0; i < keysOrNodes.length; i++) {
const keyOrNode = keysOrNodes[i];
if (keyOrNode instanceof TreeMultimapNode) {
inserted.push(this.add(keyOrNode.key, keyOrNode.value, keyOrNode.count));
continue;
}
if (keyOrNode === undefined) {
inserted.push(this.add(NaN, undefined, 0));
continue;
}
inserted.push(this.add(keyOrNode, data?.[i], 1));
}
return inserted;
override addMany(keysOrNodesOrEntries: Iterable<BTNodeExemplar<V, N>>): (N | undefined)[] {
return super.addMany(keysOrNodesOrEntries);
}

@@ -244,3 +179,3 @@

const midNode = sorted[m];
this.add(midNode.key, midNode.value, midNode.count);
this.add([midNode.key, midNode.value], midNode.count);
buildBalanceBST(l, m - 1);

@@ -261,3 +196,3 @@ buildBalanceBST(m + 1, r);

const midNode = sorted[m];
this.add(midNode.key, midNode.value, midNode.count);
this.add([midNode.key, midNode.value], midNode.count);
stack.push([m + 1, r]);

@@ -331,3 +266,3 @@ stack.push([l, m - 1]);

const parentOfLeftSubTreeMax = leftSubTreeRightMost.parent;
orgCurrent = this._swap(curr, leftSubTreeRightMost);
orgCurrent = this._swapProperties(curr, leftSubTreeRightMost);
if (parentOfLeftSubTreeMax) {

@@ -371,20 +306,2 @@ if (parentOfLeftSubTreeMax.right === leftSubTreeRightMost) {

/**
* Time Complexity: O(log n) - logarithmic time, where "n" is the number of nodes in the tree. The delete method of the superclass (AVLTree) has logarithmic time complexity.
* Space Complexity: O(1) - constant space, as it doesn't use additional data structures that scale with input size.
*/
init(elements: IterableEntriesOrKeys<V>): void {
if (elements) {
for (const entryOrKey of elements) {
if (Array.isArray(entryOrKey)) {
const [key, value] = entryOrKey;
this.add(key, value);
} else {
this.add(entryOrKey);
}
}
}
}
/**
* Time Complexity: O(1) - constant time, as it performs basic pointer assignments.

@@ -404,4 +321,4 @@ * Space Complexity: O(1) - constant space, as it only uses a constant amount of memory.

*/
protected override _addTo(newNode: N | undefined, parent: BTNKey | N | undefined): N | undefined {
parent = this.ensureNotKey(parent);
protected override _addTo(newNode: N | undefined, parent: BSTNodeKeyOrNode<N>): N | undefined {
parent = this.ensureNode(parent);
if (parent) {

@@ -432,3 +349,3 @@ if (parent.left === undefined) {

/**
* The `_swap` function swaps the key, value, count, and height properties between two nodes.
* The `_swapProperties` function swaps the key, value, count, and height properties between two nodes.
* @param {BTNKey | N | undefined} srcNode - The `srcNode` parameter represents the source node from

@@ -441,5 +358,5 @@ * which the values will be swapped. It can be of type `BTNKey`, `N`, or `undefined`.

*/
protected _swap(srcNode: BTNKey | N | undefined, destNode: BTNKey | N | undefined): N | undefined {
srcNode = this.ensureNotKey(srcNode);
destNode = this.ensureNotKey(destNode);
protected override _swapProperties(srcNode: BSTNodeKeyOrNode<N>, destNode: BSTNodeKeyOrNode<N>): N | undefined {
srcNode = this.ensureNode(srcNode);
destNode = this.ensureNode(destNode);
if (srcNode && destNode) {

@@ -466,2 +383,7 @@ const { key, value, count, height } = destNode;

}
protected _replaceNode(oldNode: N, newNode: N): N {
newNode.count = oldNode.count + newNode.count
return super._replaceNode(oldNode, newNode);
}
}

16

src/data-structures/hash/hash-map.ts

@@ -22,9 +22,5 @@ /**

/**
* The constructor initializes a HashMapLinkedNode with an optional iterable of key-value pairs.
* @param options - The `options` parameter is an object that contains the `elements` property. The
* `elements` property is an iterable that contains key-value pairs represented as arrays `[K, V]`.
*/
constructor(options: HashMapOptions<K, V> = {
elements: [],
constructor(elements?: Iterable<[K, V]>, options: HashMapOptions<K> = {
hashFn: (key: K) => String(key),

@@ -36,3 +32,3 @@ objHashFn: (key: K) => (<object>key)

const { elements, hashFn, objHashFn } = options;
const { hashFn, objHashFn } = options;
this._hashFn = hashFn;

@@ -384,2 +380,6 @@ this._objHashFn = objHashFn;

print() {
console.log([...this]);
}
/**

@@ -386,0 +386,0 @@ * Time Complexity: O(1)

27

src/data-structures/trie/trie.ts

@@ -32,5 +32,6 @@ /**

this._caseSensitive = caseSensitive;
this._size = 0;
if (words) {
for (const i of words) {
this.add(i);
for (const word of words) {
this.add(word);
}

@@ -40,2 +41,8 @@ }

protected _size: number;
get size(): number {
return this._size;
}
protected _caseSensitive: boolean;

@@ -69,2 +76,3 @@

let cur = this.root;
let isNewWord = false;
for (const c of word) {

@@ -78,4 +86,8 @@ let nodeC = cur.children.get(c);

}
cur.isEnd = true;
return true;
if (!cur.isEnd) {
isNewWord = true;
cur.isEnd = true;
this._size++;
}
return isNewWord;
}

@@ -150,2 +162,5 @@

dfs(this.root, 0);
if (isDeleted) {
this._size--;
}
return isDeleted;

@@ -385,2 +400,6 @@ }

print() {
console.log([...this]);
}
/**

@@ -387,0 +406,0 @@ * Time Complexity: O(M), where M is the length of the input string.

6

src/interfaces/binary-tree.ts

@@ -9,3 +9,3 @@ import { BinaryTree, BinaryTreeNode } from '../data-structures';

BTNKey,
IterableEntriesOrKeys
BTNodeExemplar,
} from '../types';

@@ -18,7 +18,7 @@

init(elements: IterableEntriesOrKeys<V>): void;
add(keyOrNodeOrEntry: BTNodeExemplar<V, N>, count?: number): N | null | undefined;
add(keyOrNode: BTNKey | N | null, value?: N['value']): N | null | undefined;
addMany(nodes: Iterable<BTNodeExemplar<V, N>>): (N | null | undefined)[];
delete<C extends BTNCallback<N>>(identifier: ReturnType<C> | null, callback: C): BiTreeDeleteResult<N>[];
}

12

src/types/common.ts

@@ -27,2 +27,12 @@ import { BTNKey } from "./data-structures";

export type IterableEntriesOrKeys<T> = Iterable<[BTNKey, T | undefined] | BTNKey>
export type BTNodeEntry<T> = [BTNKey | null | undefined, T | undefined];
export type BTNodeKeyOrNode<N> = BTNKey | null | undefined | N;
export type BTNodeExemplar<T, N> = BTNodeEntry<T> | BTNodeKeyOrNode<N>
export type BTNodePureExemplar<T, N> = [BTNKey, T | undefined] | BTNodePureKeyOrNode<N>
export type BTNodePureKeyOrNode<N> = BTNKey | N;
export type BSTNodeKeyOrNode<N> = BTNKey | undefined | N;

3

src/types/data-structures/hash/hash-map.ts

@@ -8,6 +8,5 @@ export type HashMapLinkedNode<K, V> = {

export type HashMapOptions<K, V> = {
elements: Iterable<[K, V]>;
export type HashMapOptions<K> = {
hashFn: (key: K) => string;
objHashFn: (key: K) => object
}
dist/data-structures/binary-tree/binary-tree.js

Sorry, the diff of this file is too big to display

src/data-structures/binary-tree/binary-tree.ts

Sorry, the diff of this file is too big to display

SocketSocket SOC 2 Logo

Product

  • Package Alerts
  • Integrations
  • Docs
  • Pricing
  • FAQ
  • Roadmap
  • Changelog

About

Packages

npm

Go

Maven

PyPI

Rubygems

Stay in touch

Get open source security insights delivered straight into your inbox.

  • Terms
  • Privacy
  • Security

Made with ⚡️ by Socket Inc