New Case Study:See how Anthropic automated 95% of dependency reviews with Socket.Learn More →
Socket
Sign inDemoInstall
Socket
Sign inDemoInstall

tree-multiset-typed

Package Overview
Dependencies
Maintainers
1
Versions
80
Alerts
File Explorer

Advanced tools

License
Socket logo

Install Socket

Detect and block malicious and high-risk dependencies

Install

tree-multiset-typed - npm Package Compare versions

Comparing version 1.42.3 to 1.42.4

4

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

@@ -37,3 +37,3 @@ /**

* a new node.
* @param {BTNKey | N | null} keyOrNode - The `keyOrNode` parameter can accept either a
* @param {BTNKey | N | undefined} keyOrNode - The `keyOrNode` parameter can accept either a
* `BTNKey` or a `N` (which represents a node in the binary tree) or `null`.

@@ -44,3 +44,3 @@ * @param [value] - The `value` parameter is the value that you want to assign to the new node that you

*/
add(keyOrNode: BTNKey | N | null, value?: V): N | null | undefined;
add(keyOrNode: BTNKey | N | null | undefined, value?: V): N | undefined;
/**

@@ -47,0 +47,0 @@ * The function overrides the delete method of a binary tree and balances the tree after deleting a

8

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

@@ -44,3 +44,3 @@ "use strict";

* a new node.
* @param {BTNKey | N | null} keyOrNode - The `keyOrNode` parameter can accept either a
* @param {BTNKey | N | undefined} keyOrNode - The `keyOrNode` parameter can accept either a
* `BTNKey` or a `N` (which represents a node in the binary tree) or `null`.

@@ -52,2 +52,4 @@ * @param [value] - The `value` parameter is the value that you want to assign to the new node that you

add(keyOrNode, value) {
if (keyOrNode === null)
return undefined;
const inserted = super.add(keyOrNode, value);

@@ -222,3 +224,3 @@ if (inserted)

const B = A.left;
let C = null;
let C = undefined;
if (B) {

@@ -307,3 +309,3 @@ C = B.right;

const B = A.right;
let C = null;
let C = undefined;
if (B) {

@@ -310,0 +312,0 @@ C = B.left;

108

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

@@ -72,7 +72,7 @@ /**

constructor(options?: BinaryTreeOptions);
protected _root: N | null;
protected _root: N | null | undefined;
/**
* Get the root node of the binary tree.
*/
get root(): N | null;
get root(): N | null | undefined;
protected _size: number;

@@ -105,3 +105,3 @@ /**

*/
add(keyOrNode: BTNKey | N | null, value?: V): N | null | undefined;
add(keyOrNode: BTNKey | N | null | undefined, value?: V): N | null | undefined;
/**

@@ -117,3 +117,3 @@ * The `addMany` function takes an array of binary tree node IDs or nodes, and optionally an array of corresponding data

*/
addMany(keysOrNodes: (BTNKey | null)[] | (N | null)[], values?: V[]): (N | null | undefined)[];
addMany(keysOrNodes: (BTNKey | null | undefined)[] | (N | null | undefined)[], values?: V[]): (N | null | undefined)[];
/**

@@ -128,5 +128,5 @@ * The `refill` function clears the binary tree and adds multiple nodes with the given IDs or nodes and optional data.

*/
refill(keysOrNodes: (BTNKey | null)[] | (N | null)[], data?: Array<V>): boolean;
refill(keysOrNodes: (BTNKey | null | undefined)[] | (N | null | undefined)[], data?: Array<V>): boolean;
delete<C extends BTNCallback<N, BTNKey>>(identifier: BTNKey, callback?: C): BinaryTreeDeletedResult<N>[];
delete<C extends BTNCallback<N, N>>(identifier: N | null, callback?: C): BinaryTreeDeletedResult<N>[];
delete<C extends BTNCallback<N, N>>(identifier: N | null | undefined, callback?: C): BinaryTreeDeletedResult<N>[];
delete<C extends BTNCallback<N>>(identifier: ReturnType<C>, callback: C): BinaryTreeDeletedResult<N>[];

@@ -136,6 +136,6 @@ /**

* specified root node.
* @param {BTNKey | N | null} distNode - The `distNode` parameter represents the node
* @param {BTNKey | N | null | undefined} distNode - The `distNode` parameter represents the node
* whose depth we want to find in the binary tree. It can be either a node object (`N`), a key value
* of the node (`BTNKey`), or `null`.
* @param {BTNKey | N | null} beginRoot - The `beginRoot` parameter represents the
* @param {BTNKey | N | null | undefined} beginRoot - The `beginRoot` parameter represents the
* starting node from which we want to calculate the depth. It can be either a node object or the key

@@ -146,7 +146,7 @@ * of a node in the binary tree. If no value is provided for `beginRoot`, it defaults to the root

*/
getDepth(distNode: BTNKey | N | null, beginRoot?: BTNKey | N | null): number;
getDepth(distNode: BTNKey | N | null | undefined, beginRoot?: BTNKey | N | null | undefined): number;
/**
* The `getHeight` function calculates the maximum height of a binary tree using either recursive or
* iterative approach.
* @param {BTNKey | N | null} beginRoot - The `beginRoot` parameter represents the
* @param {BTNKey | N | null | undefined} beginRoot - The `beginRoot` parameter represents the
* starting node from which the height of the binary tree is calculated. It can be either a node

@@ -160,7 +160,7 @@ * object (`N`), a key value of a node in the tree (`BTNKey`), or `null` if no starting

*/
getHeight(beginRoot?: BTNKey | N | null, iterationType?: IterationType): number;
getHeight(beginRoot?: BTNKey | N | null | undefined, iterationType?: IterationType): number;
/**
* The `getMinHeight` function calculates the minimum height of a binary tree using either a
* recursive or iterative approach.
* @param {N | null} beginRoot - The `beginRoot` parameter is the starting node from which we want to
* @param {N | null | undefined} beginRoot - The `beginRoot` parameter is the starting node from which we want to
* calculate the minimum height of the tree. It is optional and defaults to the root of the tree if

@@ -172,23 +172,23 @@ * not provided.

*/
getMinHeight(beginRoot?: N | null, iterationType?: IterationType): number;
getMinHeight(beginRoot?: N | null | undefined, iterationType?: IterationType): number;
/**
* The function checks if a binary tree is perfectly balanced by comparing the minimum height and the
* height of the tree.
* @param {N | null} beginRoot - The parameter `beginRoot` is of type `N | null`, which means it can
* @param {N | null | undefined} beginRoot - The parameter `beginRoot` is of type `N | null | undefined`, which means it can
* either be of type `N` (representing a node in a tree) or `null` (representing an empty tree).
* @returns The method is returning a boolean value.
*/
isPerfectlyBalanced(beginRoot?: N | null): boolean;
getNodes<C extends BTNCallback<N, BTNKey>>(identifier: BTNKey, callback?: C, onlyOne?: boolean, beginRoot?: N | null, iterationType?: IterationType): N[];
getNodes<C extends BTNCallback<N, N>>(identifier: N | null, callback?: C, onlyOne?: boolean, beginRoot?: N | null, iterationType?: IterationType): N[];
getNodes<C extends BTNCallback<N>>(identifier: ReturnType<C>, callback: C, onlyOne?: boolean, beginRoot?: N | null, iterationType?: IterationType): N[];
has<C extends BTNCallback<N, BTNKey>>(identifier: BTNKey, callback?: C, beginRoot?: N | null, iterationType?: IterationType): boolean;
has<C extends BTNCallback<N, N>>(identifier: N | null, callback?: C, beginRoot?: N | null, iterationType?: IterationType): boolean;
has<C extends BTNCallback<N>>(identifier: ReturnType<C> | null, callback: C, beginRoot?: N | null, iterationType?: IterationType): boolean;
getNode<C extends BTNCallback<N, BTNKey>>(identifier: BTNKey, callback?: C, beginRoot?: N | null, iterationType?: IterationType): N | null;
getNode<C extends BTNCallback<N, N>>(identifier: N | null, callback?: C, beginRoot?: N | null, iterationType?: IterationType): N | null;
getNode<C extends BTNCallback<N>>(identifier: ReturnType<C>, callback: C, beginRoot?: N | null, iterationType?: IterationType): N | null;
get<C extends BTNCallback<N, BTNKey>>(identifier: BTNKey, callback?: C, beginRoot?: N | null, iterationType?: IterationType): V | undefined;
get<C extends BTNCallback<N, N>>(identifier: N | null, callback?: C, beginRoot?: N | null, iterationType?: IterationType): V | undefined;
get<C extends BTNCallback<N>>(identifier: ReturnType<C>, callback: C, beginRoot?: N | null, iterationType?: IterationType): V | undefined;
isPerfectlyBalanced(beginRoot?: N | null | undefined): boolean;
getNodes<C extends BTNCallback<N, BTNKey>>(identifier: BTNKey, callback?: C, onlyOne?: boolean, beginRoot?: N | null | undefined, iterationType?: IterationType): N[];
getNodes<C extends BTNCallback<N, N>>(identifier: N | null | undefined, callback?: C, onlyOne?: boolean, beginRoot?: N | null | undefined, iterationType?: IterationType): N[];
getNodes<C extends BTNCallback<N>>(identifier: ReturnType<C>, callback: C, onlyOne?: boolean, beginRoot?: N | null | undefined, iterationType?: IterationType): N[];
has<C extends BTNCallback<N, BTNKey>>(identifier: BTNKey, callback?: C, beginRoot?: N | null | undefined, iterationType?: IterationType): boolean;
has<C extends BTNCallback<N, N>>(identifier: N | null | undefined, callback?: C, beginRoot?: N | null | undefined, iterationType?: IterationType): boolean;
has<C extends BTNCallback<N>>(identifier: ReturnType<C> | null | undefined, callback: C, beginRoot?: N | null | undefined, iterationType?: IterationType): boolean;
getNode<C extends BTNCallback<N, BTNKey>>(identifier: BTNKey, callback?: C, beginRoot?: N | null | undefined, iterationType?: IterationType): N | null | undefined;
getNode<C extends BTNCallback<N, N>>(identifier: N | null | undefined, callback?: C, beginRoot?: N | null | undefined, iterationType?: IterationType): N | null | undefined;
getNode<C extends BTNCallback<N>>(identifier: ReturnType<C>, callback: C, beginRoot?: N | null | undefined, iterationType?: IterationType): N | null | undefined;
get<C extends BTNCallback<N, BTNKey>>(identifier: BTNKey, callback?: C, beginRoot?: N | null | undefined, iterationType?: IterationType): V | undefined;
get<C extends BTNCallback<N, N>>(identifier: N | null | undefined, callback?: C, beginRoot?: N | null | undefined, iterationType?: IterationType): V | undefined;
get<C extends BTNCallback<N>>(identifier: ReturnType<C>, callback: C, beginRoot?: N | null | undefined, iterationType?: IterationType): V | undefined;
/**

@@ -208,3 +208,3 @@ * The function `getPathToRoot` returns an array of nodes starting from a given node and traversing

* iterative traversal.
* @param {BTNKey | N | null} beginRoot - The `beginRoot` parameter is the starting point
* @param {BTNKey | N | null | undefined} beginRoot - The `beginRoot` parameter is the starting point
* for finding the leftmost node in a binary tree. It can be either a node object (`N`), a key value

@@ -217,8 +217,8 @@ * of a node (`BTNKey`), or `null` if the tree is empty.

*/
getLeftMost(beginRoot?: BTNKey | N | null, iterationType?: IterationType): N | null;
getLeftMost(beginRoot?: BTNKey | N | null | undefined, iterationType?: IterationType): N | null | undefined;
/**
* The function `getRightMost` returns the rightmost node in a binary tree, either recursively or
* iteratively.
* @param {N | null} beginRoot - The `beginRoot` parameter is the starting node from which we want to
* find the rightmost node. It is of type `N | null`, which means it can either be a node of type `N`
* @param {N | null | undefined} beginRoot - The `beginRoot` parameter is the starting node from which we want to
* find the rightmost node. It is of type `N | null | undefined`, which means it can either be a node of type `N`
* or `null`. If it is `null`, it means there is no starting node

@@ -230,3 +230,3 @@ * @param iterationType - The `iterationType` parameter is used to determine the type of iteration to

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

@@ -241,3 +241,3 @@ * The function `isSubtreeBST` checks if a given binary tree is a valid binary search tree.

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

@@ -252,14 +252,17 @@ * The function checks if a binary tree is a binary search tree.

isBST(iterationType?: IterationType): boolean;
subTreeTraverse<C extends BTNCallback<N>>(callback?: C, beginRoot?: BTNKey | N | null, iterationType?: IterationType, includeNull?: false): ReturnType<C>[];
subTreeTraverse<C extends BTNCallback<N>>(callback?: C, beginRoot?: BTNKey | N | null, iterationType?: IterationType, includeNull?: undefined): ReturnType<C>[];
subTreeTraverse<C extends BTNCallback<N | null>>(callback?: C, beginRoot?: BTNKey | N | null, iterationType?: IterationType, includeNull?: true): ReturnType<C>[];
dfs<C extends BTNCallback<N>>(callback?: C, pattern?: DFSOrderPattern, beginRoot?: N | null, iterationType?: IterationType, includeNull?: false): ReturnType<C>[];
dfs<C extends BTNCallback<N>>(callback?: C, pattern?: DFSOrderPattern, beginRoot?: N | null, iterationType?: IterationType, includeNull?: undefined): ReturnType<C>[];
dfs<C extends BTNCallback<N | null>>(callback?: C, pattern?: DFSOrderPattern, beginRoot?: N | null, iterationType?: IterationType, includeNull?: true): ReturnType<C>[];
bfs<C extends BTNCallback<N>>(callback?: C, beginRoot?: N | null, iterationType?: IterationType, includeNull?: false): ReturnType<C>[];
bfs<C extends BTNCallback<N>>(callback?: C, beginRoot?: N | null, iterationType?: IterationType, includeNull?: undefined): ReturnType<C>[];
bfs<C extends BTNCallback<N | null>>(callback?: C, beginRoot?: N | null, iterationType?: IterationType, includeNull?: true): ReturnType<C>[];
listLevels<C extends BTNCallback<N>>(callback?: C, beginRoot?: N | null, iterationType?: IterationType, includeNull?: false): ReturnType<C>[][];
listLevels<C extends BTNCallback<N>>(callback?: C, beginRoot?: N | null, iterationType?: IterationType, includeNull?: undefined): ReturnType<C>[][];
listLevels<C extends BTNCallback<N | null>>(callback?: C, beginRoot?: N | null, iterationType?: IterationType, includeNull?: true): ReturnType<C>[][];
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>[];
isNode(node: any): node is N;
isNIL(node: any): boolean;
isNodeOrNull(node: any): node is (N | null);
dfs<C extends BTNCallback<N>>(callback?: C, pattern?: DFSOrderPattern, beginRoot?: N | null | undefined, iterationType?: IterationType, includeNull?: false): ReturnType<C>[];
dfs<C extends BTNCallback<N>>(callback?: C, pattern?: DFSOrderPattern, beginRoot?: N | null | undefined, iterationType?: IterationType, includeNull?: undefined): ReturnType<C>[];
dfs<C extends BTNCallback<N | null | undefined>>(callback?: C, pattern?: DFSOrderPattern, beginRoot?: N | null | undefined, iterationType?: IterationType, includeNull?: true): ReturnType<C>[];
bfs<C extends BTNCallback<N>>(callback?: C, beginRoot?: N | null | undefined, iterationType?: IterationType, includeNull?: false): ReturnType<C>[];
bfs<C extends BTNCallback<N>>(callback?: C, beginRoot?: N | null | undefined, iterationType?: IterationType, includeNull?: undefined): ReturnType<C>[];
bfs<C extends BTNCallback<N | null | undefined>>(callback?: C, beginRoot?: N | null | undefined, iterationType?: IterationType, includeNull?: true): ReturnType<C>[];
listLevels<C extends BTNCallback<N>>(callback?: C, beginRoot?: N | null | undefined, iterationType?: IterationType, includeNull?: false): ReturnType<C>[][];
listLevels<C extends BTNCallback<N>>(callback?: C, beginRoot?: N | null | undefined, iterationType?: IterationType, includeNull?: undefined): ReturnType<C>[][];
listLevels<C extends BTNCallback<N | null | undefined>>(callback?: C, beginRoot?: N | null | undefined, iterationType?: IterationType, includeNull?: true): ReturnType<C>[][];
/**

@@ -288,3 +291,3 @@ * The function returns the predecessor node of a given node in a binary tree.

* following values:
* @param {N | null} beginRoot - The `beginRoot` parameter is the starting node for the Morris
* @param {N | null | undefined} beginRoot - The `beginRoot` parameter is the starting node for the Morris
* traversal. It specifies the root node of the tree from which the traversal should begin. If

@@ -294,3 +297,3 @@ * `beginRoot` is `null`, an empty array will be returned.

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

@@ -305,3 +308,3 @@ * The above function is an iterator for a binary tree that can be used to traverse the tree in

*/
[Symbol.iterator](node?: N | null): Generator<BTNKey, void, undefined>;
[Symbol.iterator](node?: N | null | undefined): Generator<BTNKey, void, undefined>;
protected defaultOneParamCallback: (node: N) => number;

@@ -317,3 +320,3 @@ /**

* The function `_addTo` adds a new node to a binary tree if there is an available position.
* @param {N | null} newNode - The `newNode` parameter represents the node that you want to add to
* @param {N | null | undefined} newNode - The `newNode` parameter represents the node that you want to add to
* the binary tree. It can be either a node object or `null`.

@@ -327,10 +330,11 @@ * @param {N} parent - The `parent` parameter represents the parent node to which the new node will

*/
protected _addTo(newNode: N | null, parent: N): N | null | undefined;
protected _addTo(newNode: N | null | undefined, parent: N): N | null | undefined;
/**
* The function sets the root property of an object to a given value, and if the value is not null,
* it also sets the parent property of the value to undefined.
* @param {N | null} v - The parameter `v` is of type `N | null`, which means it can either be of
* @param {N | null | undefined} v - The parameter `v` is of type `N | null | undefined`, which means it can either be of
* type `N` or `null`.
*/
protected _setRoot(v: N | null): void;
protected _setRoot(v: N | null | undefined): void;
print(beginRoot?: N | null | undefined): void;
}

168

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

@@ -91,3 +91,3 @@ "use strict";

this.iterationType = types_1.IterationType.ITERATIVE;
this._root = null;
this._root = undefined;
this._size = 0;

@@ -125,3 +125,3 @@ this.defaultOneParamCallback = (node) => node.key;

clear() {
this._setRoot(null);
this._setRoot(undefined);
this._size = 0;

@@ -298,6 +298,6 @@ }

* specified root node.
* @param {BTNKey | N | null} distNode - The `distNode` parameter represents the node
* @param {BTNKey | N | null | undefined} distNode - The `distNode` parameter represents the node
* whose depth we want to find in the binary tree. It can be either a node object (`N`), a key value
* of the node (`BTNKey`), or `null`.
* @param {BTNKey | N | null} beginRoot - The `beginRoot` parameter represents the
* @param {BTNKey | N | null | undefined} beginRoot - The `beginRoot` parameter represents the
* starting node from which we want to calculate the depth. It can be either a node object or the key

@@ -326,3 +326,3 @@ * of a node in the binary tree. If no value is provided for `beginRoot`, it defaults to the root

* iterative approach.
* @param {BTNKey | N | null} beginRoot - The `beginRoot` parameter represents the
* @param {BTNKey | N | null | undefined} beginRoot - The `beginRoot` parameter represents the
* starting node from which the height of the binary tree is calculated. It can be either a node

@@ -373,3 +373,3 @@ * object (`N`), a key value of a node in the tree (`BTNKey`), or `null` if no starting

* recursive or iterative approach.
* @param {N | null} beginRoot - The `beginRoot` parameter is the starting node from which we want to
* @param {N | null | undefined} beginRoot - The `beginRoot` parameter is the starting node from which we want to
* calculate the minimum height of the tree. It is optional and defaults to the root of the tree if

@@ -428,3 +428,3 @@ * not provided.

* height of the tree.
* @param {N | null} beginRoot - The parameter `beginRoot` is of type `N | null`, which means it can
* @param {N | null | undefined} beginRoot - The parameter `beginRoot` is of type `N | null | undefined`, which means it can
* either be of type `N` (representing a node in a tree) or `null` (representing an empty tree).

@@ -450,3 +450,3 @@ * @returns The method is returning a boolean value.

* function will continue searching for all
* @param {N | null} beginRoot - The `beginRoot` parameter is the starting node from which the
* @param {N | null | undefined} beginRoot - The `beginRoot` parameter is the starting node from which the
* traversal of the binary tree will begin. It is optional and defaults to the root of the binary

@@ -584,3 +584,3 @@ * tree.

* iterative traversal.
* @param {BTNKey | N | null} beginRoot - The `beginRoot` parameter is the starting point
* @param {BTNKey | N | null | undefined} beginRoot - The `beginRoot` parameter is the starting point
* for finding the leftmost node in a binary tree. It can be either a node object (`N`), a key value

@@ -619,4 +619,4 @@ * of a node (`BTNKey`), or `null` if the tree is empty.

* iteratively.
* @param {N | null} beginRoot - The `beginRoot` parameter is the starting node from which we want to
* find the rightmost node. It is of type `N | null`, which means it can either be a node of type `N`
* @param {N | null | undefined} beginRoot - The `beginRoot` parameter is the starting node from which we want to
* find the rightmost node. It is of type `N | null | undefined`, which means it can either be a node of type `N`
* or `null`. If it is `null`, it means there is no starting node

@@ -710,3 +710,3 @@ * @param iterationType - The `iterationType` parameter is used to determine the type of iteration to

* an array.
* @param {BTNKey | N | null} beginRoot - The `beginRoot` parameter is the starting point
* @param {BTNKey | N | null | undefined} beginRoot - The `beginRoot` parameter is the starting point
* for traversing the subtree. It can be either a node object, a key value of a node, or `null` to

@@ -730,8 +730,8 @@ * start from the root of the tree.

if (includeNull) {
cur !== null && cur.left !== undefined && _traverse(cur.left);
cur !== null && cur.right !== undefined && _traverse(cur.right);
cur && this.isNodeOrNull(cur.left) && _traverse(cur.left);
cur && this.isNodeOrNull(cur.right) && _traverse(cur.right);
}
else {
cur !== null && cur.left && _traverse(cur.left);
cur !== null && cur.right && _traverse(cur.right);
cur && cur.left && _traverse(cur.left);
cur && cur.right && _traverse(cur.right);
}

@@ -749,8 +749,8 @@ }

if (includeNull) {
cur !== null && cur.right !== undefined && stack.push(cur.right);
cur !== null && cur.left !== undefined && stack.push(cur.left);
cur && this.isNodeOrNull(cur.right) && stack.push(cur.right);
cur && this.isNodeOrNull(cur.left) && stack.push(cur.left);
}
else {
cur !== null && cur.right && stack.push(cur.right);
cur !== null && cur.left && stack.push(cur.left);
cur && cur.right && stack.push(cur.right);
cur && cur.left && stack.push(cur.left);
}

@@ -762,2 +762,11 @@ }

}
isNode(node) {
return node instanceof BinaryTreeNode && node.key.toString() !== 'NaN';
}
isNIL(node) {
return node instanceof BinaryTreeNode && node.key.toString() === 'NaN';
}
isNodeOrNull(node) {
return this.isNode(node) || node === null;
}
/**

@@ -771,3 +780,3 @@ * The `dfs` function performs a depth-first search traversal on a binary tree, executing a callback

* nodes are visited during the depth-first search. There are three possible values for `pattern`:
* @param {N | null} beginRoot - The `beginRoot` parameter is the starting node for the depth-first
* @param {N | null | undefined} beginRoot - The `beginRoot` parameter is the starting node for the depth-first
* search. It determines where the search will begin in the tree or graph structure. If `beginRoot`

@@ -789,13 +798,13 @@ * is `null`, an empty array will be returned.

if (includeNull) {
if (node !== null && node.left !== undefined)
if (node && this.isNodeOrNull(node.left))
_traverse(node.left);
ans.push(callback(node));
if (node !== null && node.right !== undefined)
this.isNodeOrNull(node) && ans.push(callback(node));
if (node && this.isNodeOrNull(node.right))
_traverse(node.right);
}
else {
if (node !== null && node.left)
if (node && node.left)
_traverse(node.left);
ans.push(callback(node));
if (node !== null && node.right)
this.isNode(node) && ans.push(callback(node));
if (node && node.right)
_traverse(node.right);

@@ -806,13 +815,13 @@ }

if (includeNull) {
ans.push(callback(node));
if (node !== null && node.left !== undefined)
this.isNodeOrNull(node) && ans.push(callback(node));
if (node && this.isNodeOrNull(node.left))
_traverse(node.left);
if (node !== null && node.right !== undefined)
if (node && this.isNodeOrNull(node.right))
_traverse(node.right);
}
else {
ans.push(callback(node));
if (node !== null && node.left)
this.isNode(node) && ans.push(callback(node));
if (node && node.left)
_traverse(node.left);
if (node !== null && node.right)
if (node && node.right)
_traverse(node.right);

@@ -823,14 +832,14 @@ }

if (includeNull) {
if (node !== null && node.left !== undefined)
if (node && this.isNodeOrNull(node.left))
_traverse(node.left);
if (node !== null && node.right !== undefined)
if (node && this.isNodeOrNull(node.right))
_traverse(node.right);
ans.push(callback(node));
this.isNodeOrNull(node) && ans.push(callback(node));
}
else {
if (node !== null && node.left)
if (node && node.left)
_traverse(node.left);
if (node !== null && node.right)
if (node && node.right)
_traverse(node.right);
ans.push(callback(node));
this.isNode(node) && ans.push(callback(node));
}

@@ -847,3 +856,3 @@ break;

const cur = stack.pop();
if (cur === undefined)
if (cur === undefined || this.isNIL(cur.node))
continue;

@@ -895,3 +904,3 @@ if (includeNull) {

* `ReturnType<BTNCallback<N>>`. The default value for this parameter is `this.defaultOneParamCallback
* @param {N | null} beginRoot - The `beginRoot` parameter is the starting node for the breadth-first
* @param {N | null | undefined} beginRoot - The `beginRoot` parameter is the starting node for the breadth-first
* search. It determines from which node the search will begin. If `beginRoot` is `null`, the search

@@ -916,5 +925,5 @@ * will not be performed and an empty array will be returned.

if (includeNull) {
if (current && current.left !== undefined)
if (current && this.isNodeOrNull(current.left))
queue.push(current.left);
if (current && current.right !== undefined)
if (current && this.isNodeOrNull(current.right))
queue.push(current.right);

@@ -940,5 +949,5 @@ }

if (includeNull) {
if (current !== null && current.left !== undefined)
if (current && this.isNodeOrNull(current.left))
queue.push(current.left);
if (current !== null && current.right !== undefined)
if (current && this.isNodeOrNull(current.right))
queue.push(current.right);

@@ -963,3 +972,3 @@ }

* is determined by the generic type `C`.
* @param {N | null} beginRoot - The `beginRoot` parameter represents the starting node of the binary tree
* @param {N | null | undefined} beginRoot - The `beginRoot` parameter represents the starting node of the binary tree
* traversal. It can be any node in the binary tree. If no node is provided, the traversal will start

@@ -984,5 +993,5 @@ * from the root node of the binary tree.

if (includeNull) {
if (node && node.left !== undefined)
if (node && this.isNodeOrNull(node.left))
_recursive(node.left, level + 1);
if (node && node.right !== undefined)
if (node && this.isNodeOrNull(node.right))
_recursive(node.right, level + 1);

@@ -1008,5 +1017,5 @@ }

if (includeNull) {
if (node && node.right !== undefined)
if (node && this.isNodeOrNull(node.right))
stack.push([node.right, level + 1]);
if (node && node.left !== undefined)
if (node && this.isNodeOrNull(node.left))
stack.push([node.left, level + 1]);

@@ -1070,3 +1079,3 @@ }

* following values:
* @param {N | null} beginRoot - The `beginRoot` parameter is the starting node for the Morris
* @param {N | null | undefined} beginRoot - The `beginRoot` parameter is the starting node for the Morris
* traversal. It specifies the root node of the tree from which the traversal should begin. If

@@ -1220,3 +1229,3 @@ * `beginRoot` is `null`, an empty array will be returned.

* The function `_addTo` adds a new node to a binary tree if there is an available position.
* @param {N | null} newNode - The `newNode` parameter represents the node that you want to add to
* @param {N | null | undefined} newNode - The `newNode` parameter represents the node that you want to add to
* the binary tree. It can be either a node object or `null`.

@@ -1259,3 +1268,3 @@ * @param {N} parent - The `parent` parameter represents the parent node to which the new node will

* it also sets the parent property of the value to undefined.
* @param {N | null} v - The parameter `v` is of type `N | null`, which means it can either be of
* @param {N | null | undefined} v - The parameter `v` is of type `N | null | undefined`, which means it can either be of
* type `N` or `null`.

@@ -1269,3 +1278,56 @@ */

}
print(beginRoot = this.root) {
const display = (root) => {
const [lines, , ,] = _displayAux(root);
for (const line of lines) {
console.log(line);
}
};
const _displayAux = (node) => {
if (node === undefined || node === null) {
return [[], 0, 0, 0];
}
if (node && node.right === undefined && node.left === undefined) {
const line = `${node.key}`;
const width = line.length;
const height = 1;
const middle = Math.floor(width / 2);
return [[line], width, height, middle];
}
if (node && node.right === undefined) {
const [lines, n, p, x] = _displayAux(node.left);
const s = `${node.key}`;
const u = s.length;
const first_line = ' '.repeat(x + 1) + '_'.repeat(n - x - 1) + s;
const second_line = ' '.repeat(x) + '/' + ' '.repeat(n - x - 1 + u);
const shifted_lines = lines.map(line => line + ' '.repeat(u));
return [[first_line, second_line, ...shifted_lines], n + u, p + 2, n + Math.floor(u / 2)];
}
if (node && node.left === undefined) {
const [lines, n, p, u] = _displayAux(node.right);
const s = `${node.key}`;
const x = s.length;
const first_line = s + '_'.repeat(x) + ' '.repeat(n - x);
const second_line = ' '.repeat(u + x) + '\\' + ' '.repeat(n - x - 1);
const shifted_lines = lines.map(line => ' '.repeat(u) + line);
return [[first_line, second_line, ...shifted_lines], n + x, p + 2, Math.floor(u / 2)];
}
const [left, n, p, x] = _displayAux(node.left);
const [right, m, q, y] = _displayAux(node.right);
const s = `${node.key}`;
const u = s.length;
const first_line = ' '.repeat(x + 1) + '_'.repeat(n - x - 1) + s + '_'.repeat(y) + ' '.repeat(m - y);
const second_line = ' '.repeat(x) + '/' + ' '.repeat(n - x - 1 + u + y) + '\\' + ' '.repeat(m - y - 1);
if (p < q) {
left.push(...new Array(q - p).fill(' '.repeat(n)));
}
else if (q < p) {
right.push(...new Array(p - q).fill(' '.repeat(m)));
}
const zipped_lines = left.map((a, i) => a + ' '.repeat(u) + right[i]);
return [[first_line, second_line, ...zipped_lines], n + m + u, Math.max(p, q) + 2, n + Math.floor(u / 2)];
};
display(beginRoot);
}
}
exports.BinaryTree = BinaryTree;

57

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

@@ -13,3 +13,24 @@ /**

export declare class BSTNode<V = any, N extends BSTNode<V, N> = BSTNodeNested<V>> extends BinaryTreeNode<V, N> {
parent: N | undefined;
constructor(key: BTNKey, value?: V);
protected _left: N | undefined;
/**
* Get the left child node.
*/
get left(): N | undefined;
/**
* Set the left child node.
* @param {N | undefined} v - The left child node.
*/
set left(v: N | undefined);
protected _right: N | undefined;
/**
* Get the right child node.
*/
get right(): N | undefined;
/**
* Set the right child node.
* @param {N | undefined} v - The right child node.
*/
set right(v: N | undefined);
}

@@ -24,3 +45,8 @@ export declare class BST<V = any, N extends BSTNode<V, N> = BSTNode<V, BSTNodeNested<V>>> extends BinaryTree<V, N> implements IBinaryTree<V, N> {

constructor(options?: BSTOptions);
protected _root: N | undefined;
/**
* Get the root node of the binary tree.
*/
get root(): N | undefined;
/**
* The function creates a new binary search tree node with the given key and value.

@@ -37,10 +63,10 @@ * @param {BTNKey} key - The key parameter is the key value that will be associated with

* into the tree.
* @param {BTNKey | N | null} keyOrNode - The `keyOrNode` parameter can be either a
* `BTNKey` (which can be a number or a string), a `BSTNode` object, or `null`.
* @param {BTNKey | N | undefined} keyOrNode - The `keyOrNode` parameter can be either a
* `BTNKey` (which can be a number or a string), a `BSTNode` object, or `undefined`.
* @param [value] - The `value` parameter is the value to be assigned to the new node being added to the
* binary search tree.
* @returns the inserted node (N) if it was successfully added to the binary search tree. If the node
* was not added or if the parameters were invalid, it returns null or undefined.
* was not added or if the parameters were invalid, it returns undefined or undefined.
*/
add(keyOrNode: BTNKey | N | null, value?: V): N | null | undefined;
add(keyOrNode: BTNKey | N | null | undefined, value?: V): N | undefined;
/**

@@ -52,3 +78,3 @@ * The `addMany` function is used to efficiently add multiple nodes to a binary search tree while

* array of `BTNKey` or `N` (which represents the node type in the binary search tree) or
* `null
* `undefined
* @param {V[]} data - The values of tree nodes

@@ -58,5 +84,5 @@ * @param {boolean} isBalanceAdd - If true the nodes will be balance inserted in binary search method.

* It can have two possible values:
* @returns The `addMany` function returns an array of `N`, `null`, or `undefined` values.
* @returns The `addMany` function returns an array of `N`, `undefined`, or `undefined` values.
*/
addMany(keysOrNodes: (BTNKey | null)[] | (N | null)[], data?: V[], isBalanceAdd?: boolean, iterationType?: IterationType): (N | null | undefined)[];
addMany(keysOrNodes: (BTNKey | undefined)[] | (N | undefined)[], data?: V[], isBalanceAdd?: boolean, iterationType?: IterationType): (N | undefined)[];
/**

@@ -66,3 +92,3 @@ * The function `lastKey` returns the key of the rightmost node if the comparison result is less

* rightmost node otherwise.
* @param {N | null} beginRoot - The `beginRoot` parameter is the starting point for finding the last
* @param {N | undefined} beginRoot - The `beginRoot` parameter is the starting point for finding the last
* key in a binary tree. It represents the root node of the subtree from which the search for the

@@ -78,3 +104,3 @@ * last key should begin. If no specific `beginRoot` is provided, the search will start from the root

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

@@ -94,5 +120,5 @@ * The function `getNodes` retrieves nodes from a binary tree based on a given node property or key,

* return an array containing all nodes that match the node
* @param {N | null} beginRoot - The `beginRoot` parameter is the starting node for the traversal. It
* @param {N | undefined} beginRoot - The `beginRoot` parameter is the starting node for the traversal. It
* specifies the root node of the binary tree from which the traversal should begin. If `beginRoot`
* is `null`, an empty array will be returned.
* is `undefined`, an empty array will be returned.
* @param iterationType - The `iterationType` parameter determines the type of iteration used to

@@ -102,3 +128,3 @@ * traverse the binary tree. It can have one of the following values:

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

@@ -113,6 +139,6 @@ * The `lesserOrGreaterTraverse` function traverses a binary tree and applies a callback function to

* of the following values:
* @param {BTNKey | N | null} targetNode - The `targetNode` parameter in the
* @param {BTNKey | N | undefined} targetNode - The `targetNode` parameter in the
* `lesserOrGreaterTraverse` function is used to specify the node from which the traversal should
* start. It can be either a reference to a specific node (`N`), the key of a node
* (`BTNKey`), or `null` to
* (`BTNKey`), or `undefined` to
* @param iterationType - The `iterationType` parameter determines whether the traversal should be

@@ -122,3 +148,3 @@ * done recursively or iteratively. It can have two possible values:

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

@@ -150,2 +176,3 @@ * Balancing Adjustment:

protected _comparator: BSTComparator;
protected _setRoot(v: N | undefined): void;
/**

@@ -152,0 +179,0 @@ * The function compares two values using a comparator function and returns whether the first value

98

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

@@ -10,3 +10,38 @@ "use strict";

super(key, value);
this.parent = undefined;
this._left = undefined;
this._right = undefined;
}
/**
* Get the left child node.
*/
get left() {
return this._left;
}
/**
* Set the left child node.
* @param {N | undefined} v - The left child node.
*/
set left(v) {
if (v) {
v.parent = this;
}
this._left = v;
}
/**
* Get the right child node.
*/
get right() {
return this._right;
}
/**
* Set the right child node.
* @param {N | undefined} v - The right child node.
*/
set right(v) {
if (v) {
v.parent = this;
}
this._right = v;
}
}

@@ -23,3 +58,5 @@ exports.BSTNode = BSTNode;

super(options);
this._root = undefined;
this._comparator = (a, b) => a - b;
this._root = undefined;
if (options !== undefined) {

@@ -33,2 +70,8 @@ const { comparator } = options;

/**
* Get the root node of the binary tree.
*/
get root() {
return this._root;
}
/**
* The function creates a new binary search tree node with the given key and value.

@@ -47,13 +90,18 @@ * @param {BTNKey} key - The key parameter is the key value that will be associated with

* into the tree.
* @param {BTNKey | N | null} keyOrNode - The `keyOrNode` parameter can be either a
* `BTNKey` (which can be a number or a string), a `BSTNode` object, or `null`.
* @param {BTNKey | N | undefined} keyOrNode - The `keyOrNode` parameter can be either a
* `BTNKey` (which can be a number or a string), a `BSTNode` object, or `undefined`.
* @param [value] - The `value` parameter is the value to be assigned to the new node being added to the
* binary search tree.
* @returns the inserted node (N) if it was successfully added to the binary search tree. If the node
* was not added or if the parameters were invalid, it returns null or undefined.
* was not added or if the parameters were invalid, it returns undefined or undefined.
*/
add(keyOrNode, value) {
if (keyOrNode === 8) {
debugger;
}
if (keyOrNode === null)
return undefined;
// TODO support node as a parameter
let inserted = null;
let newNode = null;
let inserted;
let newNode;
if (keyOrNode instanceof BSTNode) {

@@ -65,6 +113,6 @@ newNode = keyOrNode;

}
else if (keyOrNode === null) {
newNode = null;
else {
newNode = undefined;
}
if (this.root === null) {
if (this.root === undefined) {
this._setRoot(newNode);

@@ -78,3 +126,3 @@ this._size = this.size + 1;

while (traversing) {
if (cur !== null && newNode !== null) {
if (cur !== undefined && newNode !== undefined) {
if (this._compare(cur.key, newNode.key) === types_1.CP.eq) {

@@ -138,3 +186,3 @@ if (newNode) {

* array of `BTNKey` or `N` (which represents the node type in the binary search tree) or
* `null
* `undefined
* @param {V[]} data - The values of tree nodes

@@ -144,3 +192,3 @@ * @param {boolean} isBalanceAdd - If true the nodes will be balance inserted in binary search method.

* It can have two possible values:
* @returns The `addMany` function returns an array of `N`, `null`, or `undefined` values.
* @returns The `addMany` function returns an array of `N`, `undefined`, or `undefined` values.
*/

@@ -150,6 +198,6 @@ addMany(keysOrNodes, data, isBalanceAdd = true, iterationType = this.iterationType) {

function hasNoNull(arr) {
return arr.indexOf(null) === -1;
return arr.indexOf(undefined) === -1;
}
if (!isBalanceAdd || !hasNoNull(keysOrNodes)) {
return super.addMany(keysOrNodes, data);
return super.addMany(keysOrNodes, data).map(n => n !== null && n !== void 0 ? n : undefined);
}

@@ -221,3 +269,3 @@ const inserted = [];

* rightmost node otherwise.
* @param {N | null} beginRoot - The `beginRoot` parameter is the starting point for finding the last
* @param {N | undefined} beginRoot - The `beginRoot` parameter is the starting point for finding the last
* key in a binary tree. It represents the root node of the subtree from which the search for the

@@ -256,5 +304,5 @@ * last key should begin. If no specific `beginRoot` is provided, the search will start from the root

* return an array containing all nodes that match the node
* @param {N | null} beginRoot - The `beginRoot` parameter is the starting node for the traversal. It
* @param {N | undefined} beginRoot - The `beginRoot` parameter is the starting node for the traversal. It
* specifies the root node of the binary tree from which the traversal should begin. If `beginRoot`
* is `null`, an empty array will be returned.
* is `undefined`, an empty array will be returned.
* @param iterationType - The `iterationType` parameter determines the type of iteration used to

@@ -329,6 +377,6 @@ * traverse the binary tree. It can have one of the following values:

* of the following values:
* @param {BTNKey | N | null} targetNode - The `targetNode` parameter in the
* @param {BTNKey | N | undefined} targetNode - The `targetNode` parameter in the
* `lesserOrGreaterTraverse` function is used to specify the node from which the traversal should
* start. It can be either a reference to a specific node (`N`), the key of a node
* (`BTNKey`), or `null` to
* (`BTNKey`), or `undefined` to
* @param iterationType - The `iterationType` parameter determines whether the traversal should be

@@ -339,4 +387,5 @@ * done recursively or iteratively. It can have two possible values:

lesserOrGreaterTraverse(callback = this.defaultOneParamCallback, lesserOrGreater = types_1.CP.lt, targetNode = this.root, iterationType = this.iterationType) {
var _a;
if (typeof targetNode === 'number')
targetNode = this.getNode(targetNode);
targetNode = (_a = this.getNode(targetNode)) !== null && _a !== void 0 ? _a : undefined;
const ans = [];

@@ -424,2 +473,3 @@ if (!targetNode)

const midNode = sorted[m];
debugger;
this.add(midNode.key, midNode.value);

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

const stack = [];
let node = this.root, last = null;
let node = this.root, last = undefined;
const depths = new Map();

@@ -477,3 +527,3 @@ while (stack.length > 0 || node) {

last = node;
node = null;
node = undefined;
}

@@ -488,2 +538,8 @@ }

}
_setRoot(v) {
if (v) {
v.parent = undefined;
}
this._root = v;
}
/**

@@ -490,0 +546,0 @@ * The function compares two values using a comparator function and returns whether the first value

79

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

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

*/
import { RBTNColor } from '../../types';
export declare class RBTreeNode {
key: number;
parent: RBTreeNode;
left: RBTreeNode;
right: RBTreeNode;
color: number;
constructor(key: number, color?: RBTNColor);
import { BinaryTreeDeletedResult, BTNCallback, BTNKey, IterationType, RBTNColor, RBTreeNodeNested, RBTreeOptions } from '../../types';
import { BST, BSTNode } from "./bst";
import { IBinaryTree } from "../../interfaces";
export declare class RBTreeNode<V = any, N extends RBTreeNode<V, N> = RBTreeNodeNested<V>> extends BSTNode<V, N> {
color: RBTNColor;
constructor(key: BTNKey, value?: V, color?: RBTNColor);
}
export declare const NIL: RBTreeNode;
/**

@@ -26,37 +23,17 @@ * 1. Each node is either red or black.

*/
export declare class RedBlackTree {
constructor();
protected _root: RBTreeNode;
get root(): RBTreeNode;
export declare class RedBlackTree<V = any, N extends RBTreeNode<V, N> = RBTreeNode<V, RBTreeNodeNested<V>>> extends BST<V, N> implements IBinaryTree<V, N> {
constructor(options?: RBTreeOptions);
protected _root: N;
get root(): N;
protected _size: number;
get size(): number;
NIL: N;
add(keyOrNode: BTNKey | N | null | undefined, value?: V): N | undefined;
createNode(key: BTNKey, value?: V, color?: RBTNColor): N;
delete<C extends BTNCallback<N>>(identifier: ReturnType<C> | null | undefined, callback?: C): BinaryTreeDeletedResult<N>[];
isNode(node: N | undefined): node is N;
getNode<C extends BTNCallback<N, BTNKey>>(identifier: BTNKey, callback?: C, beginRoot?: N | undefined, iterationType?: IterationType): N | undefined;
getNode<C extends BTNCallback<N, N>>(identifier: N | undefined, callback?: C, beginRoot?: N | undefined, iterationType?: IterationType): N | undefined;
getNode<C extends BTNCallback<N>>(identifier: ReturnType<C>, callback: C, beginRoot?: N | undefined, iterationType?: IterationType): N | undefined;
/**
* The `insert` function inserts a new node with a given key into a red-black tree and fixes any
* violations of the red-black tree properties.
* @param {number} key - The key parameter is a number that represents the value to be inserted into
* the RBTree.
* @returns The function does not explicitly return anything.
*/
add(key: number): void;
/**
* The `delete` function in TypeScript is used to remove a node with a specific key from a red-black
* tree.
* @param {number} key - The `node` parameter is of type `RBTreeNode` and represents the current
* node being processed in the delete operation.
* @returns The `delete` function does not return anything. It has a return type of `void`.
*/
delete(key: number): void;
isRealNode(node: RBTreeNode | null | undefined): node is RBTreeNode;
/**
* The function `getNode` is a recursive depth-first search algorithm that searches for a node with a
* given key in a red-black tree.
* @param {number} key - The key parameter is a number that represents the value we are searching for
* in the RBTree.
* @param beginRoot - The `beginRoot` parameter is an optional parameter that represents the starting
* point for the search in the binary search tree. If no value is provided for `beginRoot`, it
* defaults to the root of the binary search tree (`this.root`).
* @returns a RBTreeNode.
*/
getNode(key: number, beginRoot?: RBTreeNode): RBTreeNode;
/**
* The function returns the leftmost node in a red-black tree.

@@ -67,3 +44,3 @@ * @param {RBTreeNode} node - The parameter "node" is of type RBTreeNode, which represents a node in

*/
getLeftMost(node?: RBTreeNode): RBTreeNode;
getLeftMost(node?: N): N;
/**

@@ -74,3 +51,3 @@ * The function returns the rightmost node in a red-black tree.

*/
getRightMost(node: RBTreeNode): RBTreeNode;
getRightMost(node: N): N;
/**

@@ -81,3 +58,3 @@ * The function returns the successor of a given node in a red-black tree.

*/
getSuccessor(x: RBTreeNode): RBTreeNode;
getSuccessor(x: N): N | undefined;
/**

@@ -89,5 +66,5 @@ * The function returns the predecessor of a given node in a red-black tree.

*/
getPredecessor(x: RBTreeNode): RBTreeNode;
getPredecessor(x: N): N;
clear(): void;
print(beginRoot?: RBTreeNode): void;
protected _setRoot(v: N): void;
/**

@@ -97,3 +74,3 @@ * The function performs a left rotation on a red-black tree node.

*/
protected _leftRotate(x: RBTreeNode): void;
protected _leftRotate(x: N): void;
/**

@@ -104,3 +81,3 @@ * The function performs a right rotation on a red-black tree node.

*/
protected _rightRotate(x: RBTreeNode): void;
protected _rightRotate(x: N): void;
/**

@@ -111,3 +88,3 @@ * The _fixDelete function is used to rebalance the Red-Black Tree after a node deletion.

*/
protected _fixDelete(x: RBTreeNode): void;
protected _fixDelete(x: N): void;
/**

@@ -118,3 +95,3 @@ * The function `_rbTransplant` replaces one node in a red-black tree with another node.

*/
protected _rbTransplant(u: RBTreeNode, v: RBTreeNode): void;
protected _rbTransplant(u: N, v: N): void;
/**

@@ -125,3 +102,3 @@ * The `_fixInsert` function is used to fix the red-black tree after an insertion operation.

*/
protected _fixInsert(k: RBTreeNode): void;
protected _fixInsert(k: N): void;
}

328

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

@@ -10,16 +10,13 @@ "use strict";

Object.defineProperty(exports, "__esModule", { value: true });
exports.RedBlackTree = exports.NIL = exports.RBTreeNode = void 0;
exports.RedBlackTree = exports.RBTreeNode = void 0;
const types_1 = require("../../types");
class RBTreeNode {
constructor(key, color = types_1.RBTNColor.BLACK) {
this.color = types_1.RBTNColor.BLACK;
this.key = key;
const bst_1 = require("./bst");
const binary_tree_1 = require("./binary-tree");
class RBTreeNode extends bst_1.BSTNode {
constructor(key, value, color = types_1.RBTNColor.BLACK) {
super(key, value);
this.color = color;
this.parent = null;
this.left = null;
this.right = null;
}
}
exports.RBTreeNode = RBTreeNode;
exports.NIL = new RBTreeNode(0);
/**

@@ -32,6 +29,8 @@ * 1. Each node is either red or black.

*/
class RedBlackTree {
constructor() {
class RedBlackTree extends bst_1.BST {
constructor(options) {
super(options);
this._size = 0;
this._root = exports.NIL;
this.NIL = new RBTreeNode(NaN);
this._root = this.NIL;
}

@@ -44,27 +43,35 @@ get root() {

}
/**
* The `insert` function inserts a new node with a given key into a red-black tree and fixes any
* violations of the red-black tree properties.
* @param {number} key - The key parameter is a number that represents the value to be inserted into
* the RBTree.
* @returns The function does not explicitly return anything.
*/
add(key) {
const node = new RBTreeNode(key, types_1.RBTNColor.RED);
node.left = exports.NIL;
node.right = exports.NIL;
let y = null;
add(keyOrNode, value) {
let node;
if (typeof keyOrNode === 'number') {
node = this.createNode(keyOrNode, value, types_1.RBTNColor.RED);
}
else if (keyOrNode instanceof RBTreeNode) {
node = keyOrNode;
}
else if (keyOrNode === null) {
return;
}
else if (keyOrNode === undefined) {
return;
}
else {
return;
}
node.left = this.NIL;
node.right = this.NIL;
let y = undefined;
let x = this.root;
while (x !== exports.NIL) {
while (x !== this.NIL) {
y = x;
if (node.key < x.key) {
if (x && node.key < x.key) {
x = x.left;
}
else {
x = x.right;
x = x === null || x === void 0 ? void 0 : x.right;
}
}
node.parent = y;
if (y === null) {
this._root = node;
if (y === undefined) {
this._setRoot(node);
}

@@ -77,3 +84,3 @@ else if (node.key < y.key) {

}
if (node.parent === null) {
if (node.parent === undefined) {
node.color = types_1.RBTNColor.BLACK;

@@ -83,3 +90,3 @@ this._size++;

}
if (node.parent.parent === null) {
if (node.parent.parent === undefined) {
this._size++;

@@ -91,25 +98,24 @@ return;

}
/**
* The `delete` function in TypeScript is used to remove a node with a specific key from a red-black
* tree.
* @param {number} key - The `node` parameter is of type `RBTreeNode` and represents the current
* node being processed in the delete operation.
* @returns The `delete` function does not return anything. It has a return type of `void`.
*/
delete(key) {
createNode(key, value, color = types_1.RBTNColor.BLACK) {
return new RBTreeNode(key, value, color);
}
delete(identifier, callback = this.defaultOneParamCallback) {
const ans = [];
if (identifier === null)
return ans;
const helper = (node) => {
let z = exports.NIL;
let z = this.NIL;
let x, y;
while (node !== exports.NIL) {
if (node.key === key) {
while (node !== this.NIL) {
if (node && callback(node) === identifier) {
z = node;
}
if (node.key <= key) {
if (node && identifier && callback(node) <= identifier) {
node = node.right;
}
else {
node = node.left;
node = node === null || node === void 0 ? void 0 : node.left;
}
}
if (z === exports.NIL) {
if (z === this.NIL) {
this._size--;

@@ -120,7 +126,7 @@ return;

let yOriginalColor = y.color;
if (z.left === exports.NIL) {
if (z.left === this.NIL) {
x = z.right;
this._rbTransplant(z, z.right);
}
else if (z.right === exports.NIL) {
else if (z.right === this.NIL) {
x = z.left;

@@ -152,31 +158,28 @@ this._rbTransplant(z, z.left);

helper(this.root);
// TODO
return ans;
}
isRealNode(node) {
return node !== exports.NIL && node !== null;
isNode(node) {
return node !== this.NIL && node !== undefined;
}
/**
* The function `getNode` is a recursive depth-first search algorithm that searches for a node with a
* given key in a red-black tree.
* @param {number} key - The key parameter is a number that represents the value we are searching for
* in the RBTree.
* @param beginRoot - The `beginRoot` parameter is an optional parameter that represents the starting
* point for the search in the binary search tree. If no value is provided for `beginRoot`, it
* defaults to the root of the binary search tree (`this.root`).
* @returns a RBTreeNode.
* The function `get` returns the first node in a binary tree that matches the given property or key.
* @param {BTNKey | N} identifier - The `identifier` parameter is the key or value of
* the node that you want to find in the binary tree. It can be either a `BTNKey` or `N`
* type.
* @param callback - The `callback` parameter is a function that is used to determine whether a node
* matches the desired criteria. It takes a node as input and returns a boolean value indicating
* whether the node matches the criteria or not. The default callback function
* (`this.defaultOneParamCallback`) is used if no callback function is
* @param beginRoot - The `beginRoot` parameter is the starting point for the search. It specifies
* the root node from which the search should begin.
* @param iterationType - The `iterationType` parameter specifies the type of iteration to be
* performed when searching for a node in the binary tree. It can have one of the following values:
* @returns either the found node (of type N) or null if no node is found.
*/
getNode(key, beginRoot = this.root) {
const dfs = (node) => {
if (this.isRealNode(node)) {
if (key === node.key) {
return node;
}
if (key < node.key)
return dfs(node.left);
return dfs(node.right);
}
else {
return null;
}
};
return dfs(beginRoot);
getNode(identifier, callback = this.defaultOneParamCallback, beginRoot = this.root, iterationType = this.iterationType) {
var _a;
if (identifier instanceof binary_tree_1.BinaryTreeNode)
callback = (node => node);
return (_a = this.getNodes(identifier, callback, true, beginRoot, iterationType)[0]) !== null && _a !== void 0 ? _a : undefined;
}

@@ -190,3 +193,3 @@ /**

getLeftMost(node = this.root) {
while (node.left !== null && node.left !== exports.NIL) {
while (node.left !== undefined && node.left !== this.NIL) {
node = node.left;

@@ -202,3 +205,3 @@ }

getRightMost(node) {
while (node.right !== null && node.right !== exports.NIL) {
while (node.right !== undefined && node.right !== this.NIL) {
node = node.right;

@@ -214,7 +217,7 @@ }

getSuccessor(x) {
if (x.right !== exports.NIL) {
if (x.right !== this.NIL) {
return this.getLeftMost(x.right);
}
let y = x.parent;
while (y !== exports.NIL && y !== null && x === y.right) {
while (y !== this.NIL && y !== undefined && x === y.right) {
x = y;

@@ -232,7 +235,7 @@ y = y.parent;

getPredecessor(x) {
if (x.left !== exports.NIL) {
if (x.left !== this.NIL) {
return this.getRightMost(x.left);
}
let y = x.parent;
while (y !== exports.NIL && x === y.left) {
while (y !== this.NIL && x === y.left) {
x = y;

@@ -244,57 +247,10 @@ y = y.parent;

clear() {
this._root = exports.NIL;
this._root = this.NIL;
this._size = 0;
}
print(beginRoot = this.root) {
const display = (root) => {
const [lines, , ,] = _displayAux(root);
for (const line of lines) {
console.log(line);
}
};
const _displayAux = (node) => {
if (node === null) {
return [[], 0, 0, 0];
}
if (node.right === null && node.left === null) {
const line = `${node.key}`;
const width = line.length;
const height = 1;
const middle = Math.floor(width / 2);
return [[line], width, height, middle];
}
if (node.right === null) {
const [lines, n, p, x] = _displayAux(node.left);
const s = `${node.key}`;
const u = s.length;
const first_line = ' '.repeat(x + 1) + '_'.repeat(n - x - 1) + s;
const second_line = ' '.repeat(x) + '/' + ' '.repeat(n - x - 1 + u);
const shifted_lines = lines.map(line => line + ' '.repeat(u));
return [[first_line, second_line, ...shifted_lines], n + u, p + 2, n + Math.floor(u / 2)];
}
if (node.left === null) {
const [lines, n, p, u] = _displayAux(node.right);
const s = `${node.key}`;
const x = s.length;
const first_line = s + '_'.repeat(x) + ' '.repeat(n - x);
const second_line = ' '.repeat(u + x) + '\\' + ' '.repeat(n - x - 1);
const shifted_lines = lines.map(line => ' '.repeat(u) + line);
return [[first_line, second_line, ...shifted_lines], n + x, p + 2, Math.floor(u / 2)];
}
const [left, n, p, x] = _displayAux(node.left);
const [right, m, q, y] = _displayAux(node.right);
const s = `${node.key}`;
const u = s.length;
const first_line = ' '.repeat(x + 1) + '_'.repeat(n - x - 1) + s + '_'.repeat(y) + ' '.repeat(m - y);
const second_line = ' '.repeat(x) + '/' + ' '.repeat(n - x - 1 + u + y) + '\\' + ' '.repeat(m - y - 1);
if (p < q) {
left.push(...new Array(q - p).fill(' '.repeat(n)));
}
else if (q < p) {
right.push(...new Array(p - q).fill(' '.repeat(m)));
}
const zipped_lines = left.map((a, i) => a + ' '.repeat(u) + right[i]);
return [[first_line, second_line, ...zipped_lines], n + m + u, Math.max(p, q) + 2, n + Math.floor(u / 2)];
};
display(beginRoot);
_setRoot(v) {
if (v) {
v.parent = undefined;
}
this._root = v;
}

@@ -306,19 +262,22 @@ /**

_leftRotate(x) {
const y = x.right;
x.right = y.left;
if (y.left !== exports.NIL) {
y.left.parent = x;
if (x.right) {
const y = x.right;
x.right = y.left;
if (y.left !== this.NIL) {
if (y.left)
y.left.parent = x;
}
y.parent = x.parent;
if (x.parent === undefined) {
this._setRoot(y);
}
else if (x === x.parent.left) {
x.parent.left = y;
}
else {
x.parent.right = y;
}
y.left = x;
x.parent = y;
}
y.parent = x.parent;
if (x.parent === null) {
this._root = y;
}
else if (x === x.parent.left) {
x.parent.left = y;
}
else {
x.parent.right = y;
}
y.left = x;
x.parent = y;
}

@@ -331,19 +290,22 @@ /**

_rightRotate(x) {
const y = x.left;
x.left = y.right;
if (y.right !== exports.NIL) {
y.right.parent = x;
if (x.left) {
const y = x.left;
x.left = y.right;
if (y.right !== this.NIL) {
if (y.right)
y.right.parent = x;
}
y.parent = x.parent;
if (x.parent === undefined) {
this._setRoot(y);
}
else if (x === x.parent.right) {
x.parent.right = y;
}
else {
x.parent.left = y;
}
y.right = x;
x.parent = y;
}
y.parent = x.parent;
if (x.parent === null) {
this._root = y;
}
else if (x === x.parent.right) {
x.parent.right = y;
}
else {
x.parent.left = y;
}
y.right = x;
x.parent = y;
}

@@ -358,3 +320,3 @@ /**

while (x !== this.root && x.color === types_1.RBTNColor.BLACK) {
if (x === x.parent.left) {
if (x.parent && x === x.parent.left) {
s = x.parent.right;

@@ -367,3 +329,3 @@ if (s.color === 1) {

}
if (s.left !== null && s.left.color === types_1.RBTNColor.BLACK && s.right.color === types_1.RBTNColor.BLACK) {
if (s.left !== undefined && s.left.color === types_1.RBTNColor.BLACK && s.right && s.right.color === types_1.RBTNColor.BLACK) {
s.color = types_1.RBTNColor.RED;

@@ -373,4 +335,5 @@ x = x.parent;

else {
if (s.right.color === types_1.RBTNColor.BLACK) {
s.left.color = types_1.RBTNColor.BLACK;
if (s.right && s.right.color === types_1.RBTNColor.BLACK) {
if (s.left)
s.left.color = types_1.RBTNColor.BLACK;
s.color = types_1.RBTNColor.RED;

@@ -380,5 +343,7 @@ this._rightRotate(s);

}
s.color = x.parent.color;
if (s)
s.color = x.parent.color;
x.parent.color = types_1.RBTNColor.BLACK;
s.right.color = types_1.RBTNColor.BLACK;
if (s && s.right)
s.right.color = types_1.RBTNColor.BLACK;
this._leftRotate(x.parent);

@@ -396,3 +361,3 @@ x = this.root;

}
if (s.right.color === types_1.RBTNColor.BLACK && s.right.color === types_1.RBTNColor.BLACK) {
if (s && s.right && s.right.color === types_1.RBTNColor.BLACK && s.right.color === types_1.RBTNColor.BLACK) {
s.color = types_1.RBTNColor.RED;

@@ -402,4 +367,5 @@ x = x.parent;

else {
if (s.left.color === types_1.RBTNColor.BLACK) {
s.right.color = types_1.RBTNColor.BLACK;
if (s && s.left && s.left.color === types_1.RBTNColor.BLACK) {
if (s.right)
s.right.color = types_1.RBTNColor.BLACK;
s.color = types_1.RBTNColor.RED;

@@ -409,5 +375,7 @@ this._leftRotate(s);

}
s.color = x.parent.color;
if (s)
s.color = x.parent.color;
x.parent.color = types_1.RBTNColor.BLACK;
s.left.color = types_1.RBTNColor.BLACK;
if (s && s.left)
s.left.color = types_1.RBTNColor.BLACK;
this._rightRotate(x.parent);

@@ -426,4 +394,4 @@ x = this.root;

_rbTransplant(u, v) {
if (u.parent === null) {
this._root = v;
if (u.parent === undefined) {
this._setRoot(v);
}

@@ -445,6 +413,6 @@ else if (u === u.parent.left) {

let u;
while (k.parent.color === 1) {
if (k.parent === k.parent.parent.right) {
while (k.parent && k.parent.color === 1) {
if (k.parent.parent && k.parent === k.parent.parent.right) {
u = k.parent.parent.left;
if (u.color === 1) {
if (u && u.color === 1) {
u.color = types_1.RBTNColor.BLACK;

@@ -467,3 +435,3 @@ k.parent.color = types_1.RBTNColor.BLACK;

u = k.parent.parent.right;
if (u.color === 1) {
if (u && u.color === 1) {
u.color = types_1.RBTNColor.BLACK;

@@ -470,0 +438,0 @@ k.parent.color = types_1.RBTNColor.BLACK;

20

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

@@ -52,5 +52,5 @@ /**

* exists, and balancing the tree if necessary.
* @param {BTNKey | N | null} keyOrNode - The `keyOrNode` parameter can be either a
* @param {BTNKey | N | undefined} keyOrNode - The `keyOrNode` parameter can be either a
* `BTNKey` (which represents the key of the node to be added), a `N` (which represents a
* node to be added), or `null` (which represents a null node).
* node to be added), or `undefined` (which represents a undefined node).
* @param [value] - The `value` parameter represents the value associated with the key that is being

@@ -61,9 +61,9 @@ * added to the binary tree.

* count is specified, the default count will be 1.
* @returns The function `add` returns a value of type `N | null | undefined`.
* @returns The function `add` returns a value of type `N | undefined | undefined`.
*/
add(keyOrNode: BTNKey | N | null, value?: V, count?: number): N | null | undefined;
add(keyOrNode: BTNKey | N | null | undefined, value?: V, count?: number): N | undefined;
/**
* The function adds a new node to a binary tree if there is an available slot in the parent node.
* @param {N | null} newNode - The `newNode` parameter represents the node that needs to be added to
* the tree. It can be either a node object (`N`) or `null`.
* @param {N | undefined} newNode - The `newNode` parameter represents the node that needs to be added to
* the tree. It can be either a node object (`N`) or `undefined`.
* @param {N} parent - The `parent` parameter represents the parent node to which the new node will

@@ -73,7 +73,7 @@ * be added as a child.

*/
_addTo(newNode: N | null, parent: N): N | null | undefined;
_addTo(newNode: N | undefined, parent: N): N | undefined;
/**
* The `addMany` function adds multiple keys or nodes to a TreeMultiset and returns an array of the
* inserted nodes.
* @param {(BTNKey | null)[] | (N | null)[]} keysOrNodes - An array of keys or nodes to be
* @param {(BTNKey | undefined)[] | (N | undefined)[]} keysOrNodes - An array of keys or nodes to be
* added to the multiset. Each element can be either a BTNKey or a TreeMultisetNode.

@@ -83,5 +83,5 @@ * @param {V[]} [data] - The `data` parameter is an optional array of values that correspond

* each key or node.
* @returns The function `addMany` returns an array of `N`, `null`, or `undefined` values.
* @returns The function `addMany` returns an array of `N`, `undefined`, or `undefined` values.
*/
addMany(keysOrNodes: (BTNKey | null)[] | (N | null)[], data?: V[]): (N | null | undefined)[];
addMany(keysOrNodes: (BTNKey | undefined)[] | (N | undefined)[], data?: V[]): (N | undefined)[];
/**

@@ -88,0 +88,0 @@ * The `perfectlyBalance` function in TypeScript takes a sorted array of nodes and builds a balanced

37

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

@@ -55,5 +55,5 @@ "use strict";

* exists, and balancing the tree if necessary.
* @param {BTNKey | N | null} keyOrNode - The `keyOrNode` parameter can be either a
* @param {BTNKey | N | undefined} keyOrNode - The `keyOrNode` parameter can be either a
* `BTNKey` (which represents the key of the node to be added), a `N` (which represents a
* node to be added), or `null` (which represents a null node).
* node to be added), or `undefined` (which represents a undefined node).
* @param [value] - The `value` parameter represents the value associated with the key that is being

@@ -64,5 +64,7 @@ * added to the binary tree.

* count is specified, the default count will be 1.
* @returns The function `add` returns a value of type `N | null | undefined`.
* @returns The function `add` returns a value of type `N | undefined | undefined`.
*/
add(keyOrNode, value, count = 1) {
if (keyOrNode === null)
return undefined;
let inserted = undefined, newNode;

@@ -72,4 +74,4 @@ if (keyOrNode instanceof TreeMultisetNode) {

}
else if (keyOrNode === null) {
newNode = null;
else if (keyOrNode === undefined) {
newNode = undefined;
}

@@ -132,3 +134,3 @@ else {

else {
// TODO may need to support null inserted
// TODO may need to support undefined inserted
}

@@ -147,4 +149,4 @@ }

* The function adds a new node to a binary tree if there is an available slot in the parent node.
* @param {N | null} newNode - The `newNode` parameter represents the node that needs to be added to
* the tree. It can be either a node object (`N`) or `null`.
* @param {N | undefined} newNode - The `newNode` parameter represents the node that needs to be added to
* the tree. It can be either a node object (`N`) or `undefined`.
* @param {N} parent - The `parent` parameter represents the parent node to which the new node will

@@ -158,3 +160,3 @@ * be added as a child.

parent.left = newNode;
if (newNode !== null) {
if (newNode !== undefined) {
this._size = this.size + 1;

@@ -167,3 +169,3 @@ this._setCount(this.count + newNode.count);

parent.right = newNode;
if (newNode !== null) {
if (newNode !== undefined) {
this._size = this.size + 1;

@@ -185,3 +187,3 @@ this._setCount(this.count + newNode.count);

* inserted nodes.
* @param {(BTNKey | null)[] | (N | null)[]} keysOrNodes - An array of keys or nodes to be
* @param {(BTNKey | undefined)[] | (N | undefined)[]} keysOrNodes - An array of keys or nodes to be
* added to the multiset. Each element can be either a BTNKey or a TreeMultisetNode.

@@ -191,3 +193,3 @@ * @param {V[]} [data] - The `data` parameter is an optional array of values that correspond

* each key or node.
* @returns The function `addMany` returns an array of `N`, `null`, or `undefined` values.
* @returns The function `addMany` returns an array of `N`, `undefined`, or `undefined` values.
*/

@@ -202,3 +204,3 @@ addMany(keysOrNodes, data) {

}
if (keyOrNode === null) {
if (keyOrNode === undefined) {
inserted.push(this.add(NaN, undefined, 0));

@@ -272,10 +274,11 @@ continue;

delete(identifier, callback = this.defaultOneParamCallback, ignoreCount = false) {
var _a;
const bstDeletedResult = [];
if (!this.root)
return bstDeletedResult;
const curr = this.getNode(identifier, callback);
const curr = (_a = this.getNode(identifier, callback)) !== null && _a !== void 0 ? _a : undefined;
if (!curr)
return bstDeletedResult;
const parent = (curr === null || curr === void 0 ? void 0 : curr.parent) ? curr.parent : null;
let needBalanced = null, orgCurrent = curr;
const parent = (curr === null || curr === void 0 ? void 0 : curr.parent) ? curr.parent : undefined;
let needBalanced = undefined, orgCurrent = curr;
if (curr.count > 1 && !ignoreCount) {

@@ -303,3 +306,3 @@ curr.count--;

else {
const leftSubTreeRightMost = curr.left ? this.getRightMost(curr.left) : null;
const leftSubTreeRightMost = curr.left ? this.getRightMost(curr.left) : undefined;
if (leftSubTreeRightMost) {

@@ -306,0 +309,0 @@ const parentOfLeftSubTreeMax = leftSubTreeRightMost.parent;

2

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

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

deleted: N | null | undefined;
needBalanced: N | null;
needBalanced: N | null | undefined;
};

@@ -27,0 +27,0 @@ export type BinaryTreeNodeNested<T> = BinaryTreeNode<T, BinaryTreeNode<T, BinaryTreeNode<T, BinaryTreeNode<T, BinaryTreeNode<T, BinaryTreeNode<T, BinaryTreeNode<T, BinaryTreeNode<T, BinaryTreeNode<T, BinaryTreeNode<T, BinaryTreeNode<T, BinaryTreeNode<T, BinaryTreeNode<T, BinaryTreeNode<T, BinaryTreeNode<T, BinaryTreeNode<T, BinaryTreeNode<T, BinaryTreeNode<T, BinaryTreeNode<T, BinaryTreeNode<T, BinaryTreeNode<T, BinaryTreeNode<T, BinaryTreeNode<T, BinaryTreeNode<T, BinaryTreeNode<T, BinaryTreeNode<T, BinaryTreeNode<T, BinaryTreeNode<T, BinaryTreeNode<T, BinaryTreeNode<T, BinaryTreeNode<T, BinaryTreeNode<T, BinaryTreeNode<T, BinaryTreeNode<T, BinaryTreeNode<T, BinaryTreeNode<T, BinaryTreeNode<T, BinaryTreeNode<T, BinaryTreeNode<T, BinaryTreeNode<T, BinaryTreeNode<T, BinaryTreeNode<T, BinaryTreeNode<T, BinaryTreeNode<T, BinaryTreeNode<T, BinaryTreeNode<T, BinaryTreeNode<T, BinaryTreeNode<T, BinaryTreeNode<T, BinaryTreeNode<T, any>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>;

4

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

@@ -0,1 +1,3 @@

import { RBTreeNode } from '../../../data-structures';
import { BSTOptions } from "./bst";
export declare enum RBTNColor {

@@ -5,1 +7,3 @@ RED = 1,

}
export type RBTreeNodeNested<T> = RBTreeNode<T, RBTreeNode<T, RBTreeNode<T, RBTreeNode<T, RBTreeNode<T, RBTreeNode<T, RBTreeNode<T, RBTreeNode<T, RBTreeNode<T, RBTreeNode<T, RBTreeNode<T, RBTreeNode<T, RBTreeNode<T, RBTreeNode<T, RBTreeNode<T, RBTreeNode<T, RBTreeNode<T, RBTreeNode<T, RBTreeNode<T, RBTreeNode<T, RBTreeNode<T, RBTreeNode<T, RBTreeNode<T, RBTreeNode<T, RBTreeNode<T, RBTreeNode<T, RBTreeNode<T, RBTreeNode<T, RBTreeNode<T, RBTreeNode<T, RBTreeNode<T, RBTreeNode<T, RBTreeNode<T, RBTreeNode<T, RBTreeNode<T, RBTreeNode<T, RBTreeNode<T, RBTreeNode<T, RBTreeNode<T, RBTreeNode<T, RBTreeNode<T, RBTreeNode<T, RBTreeNode<T, RBTreeNode<T, RBTreeNode<T, RBTreeNode<T, RBTreeNode<T, RBTreeNode<T, RBTreeNode<T, RBTreeNode<T, any>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>;
export type RBTreeOptions = BSTOptions & {};

5

dist/types/data-structures/binary-tree/rb-tree.js
"use strict";
// import {BinaryTreeOptions} from './binary-tree';
// import {RBTreeNode} from '../../../data-structures';
Object.defineProperty(exports, "__esModule", { value: true });

@@ -11,4 +9,1 @@ exports.RBTNColor = void 0;

})(RBTNColor = exports.RBTNColor || (exports.RBTNColor = {}));
// export type RBTreeNodeNested<T> = RBTreeNode<T, RBTreeNode<T, RBTreeNode<T, RBTreeNode<T, RBTreeNode<T, RBTreeNode<T, RBTreeNode<T, RBTreeNode<T, RBTreeNode<T, RBTreeNode<T, RBTreeNode<T, RBTreeNode<T, RBTreeNode<T, RBTreeNode<T, RBTreeNode<T, RBTreeNode<T, RBTreeNode<T, RBTreeNode<T, RBTreeNode<T, RBTreeNode<T, RBTreeNode<T, RBTreeNode<T, RBTreeNode<T, RBTreeNode<T, RBTreeNode<T, RBTreeNode<T, RBTreeNode<T, RBTreeNode<T, RBTreeNode<T, RBTreeNode<T, RBTreeNode<T, RBTreeNode<T, RBTreeNode<T, RBTreeNode<T, RBTreeNode<T, RBTreeNode<T, RBTreeNode<T, RBTreeNode<T, RBTreeNode<T, RBTreeNode<T, RBTreeNode<T, RBTreeNode<T, RBTreeNode<T, RBTreeNode<T, RBTreeNode<T, RBTreeNode<T, RBTreeNode<T, RBTreeNode<T, RBTreeNode<T, RBTreeNode<T, any>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>
//
// export type RBTreeOptions = BinaryTreeOptions & {}

4

package.json
{
"name": "tree-multiset-typed",
"version": "1.42.3",
"version": "1.42.4",
"description": "Tree Multiset, AVLTree, BST, Binary Tree. Javascript & Typescript Data Structure.",

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

"dependencies": {
"data-structure-typed": "^1.42.3"
"data-structure-typed": "^1.42.4"
}
}

9

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

@@ -52,3 +52,3 @@ /**

* a new node.
* @param {BTNKey | N | null} keyOrNode - The `keyOrNode` parameter can accept either a
* @param {BTNKey | N | undefined} keyOrNode - The `keyOrNode` parameter can accept either a
* `BTNKey` or a `N` (which represents a node in the binary tree) or `null`.

@@ -59,3 +59,4 @@ * @param [value] - The `value` parameter is the value that you want to assign to the new node that you

*/
override add(keyOrNode: BTNKey | N | null, value?: V): N | null | undefined {
override add(keyOrNode: BTNKey | N | null | undefined, value?: V): N | undefined {
if (keyOrNode === null) return undefined;
const inserted = super.add(keyOrNode, value);

@@ -231,3 +232,3 @@ if (inserted) this._balancePath(inserted);

const B = A.left;
let C = null;
let C = undefined;
if (B) {

@@ -315,3 +316,3 @@ C = B.right;

const B = A.right;
let C = null;
let C = undefined;
if (B) {

@@ -318,0 +319,0 @@ C = B.left;

332

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

@@ -126,3 +126,3 @@ /**

protected _root: N | null = null;
protected _root: N | null | undefined = undefined;

@@ -132,3 +132,3 @@ /**

*/
get root(): N | null {
get root(): N | null | undefined {
return this._root;

@@ -160,3 +160,3 @@ }

clear() {
this._setRoot(null);
this._setRoot(undefined);
this._size = 0;

@@ -179,3 +179,3 @@ }

*/
add(keyOrNode: BTNKey | N | null, value?: V): N | null | undefined {
add(keyOrNode: BTNKey | N | null | undefined, value?: V): N | null | undefined {
const _bfs = (root: N, newNode: N | null): N | undefined | null => {

@@ -243,3 +243,3 @@ const queue = new Queue<N | null>([root]);

*/
addMany(keysOrNodes: (BTNKey | null)[] | (N | null)[], values?: V[]): (N | null | undefined)[] {
addMany(keysOrNodes: (BTNKey | null | undefined)[] | (N | null | undefined)[], values?: V[]): (N | null | undefined)[] {
// TODO not sure addMany not be run multi times

@@ -269,3 +269,3 @@ return keysOrNodes.map((keyOrNode, i) => {

*/
refill(keysOrNodes: (BTNKey | null)[] | (N | null)[], data?: Array<V>): boolean {
refill(keysOrNodes: (BTNKey | null | undefined)[] | (N | null | undefined)[], data?: Array<V>): boolean {
this.clear();

@@ -277,3 +277,3 @@ return keysOrNodes.length === this.addMany(keysOrNodes, data).length;

delete<C extends BTNCallback<N, N>>(identifier: N | null, callback?: C): BinaryTreeDeletedResult<N>[];
delete<C extends BTNCallback<N, N>>(identifier: N | null | undefined, callback?: C): BinaryTreeDeletedResult<N>[];

@@ -297,3 +297,3 @@ delete<C extends BTNCallback<N>>(identifier: ReturnType<C>, callback: C): BinaryTreeDeletedResult<N>[];

delete<C extends BTNCallback<N>>(
identifier: ReturnType<C> | null,
identifier: ReturnType<C> | null | undefined,
callback: C = this.defaultOneParamCallback as C

@@ -308,4 +308,4 @@ ): BinaryTreeDeletedResult<N>[] {

const parent: N | null = curr?.parent ? curr.parent : null;
let needBalanced: N | null = null,
const parent: N | null | undefined = curr?.parent ? curr.parent : null;
let needBalanced: N | null | undefined = null,
orgCurrent = curr;

@@ -348,6 +348,6 @@

* specified root node.
* @param {BTNKey | N | null} distNode - The `distNode` parameter represents the node
* @param {BTNKey | N | null | undefined} distNode - The `distNode` parameter represents the node
* whose depth we want to find in the binary tree. It can be either a node object (`N`), a key value
* of the node (`BTNKey`), or `null`.
* @param {BTNKey | N | null} beginRoot - The `beginRoot` parameter represents the
* @param {BTNKey | N | null | undefined} beginRoot - The `beginRoot` parameter represents the
* starting node from which we want to calculate the depth. It can be either a node object or the key

@@ -358,3 +358,3 @@ * of a node in the binary tree. If no value is provided for `beginRoot`, it defaults to the root

*/
getDepth(distNode: BTNKey | N | null, beginRoot: BTNKey | N | null = this.root): number {
getDepth(distNode: BTNKey | N | null | undefined, beginRoot: BTNKey | N | null | undefined = this.root): number {
if (typeof distNode === 'number') distNode = this.getNode(distNode);

@@ -376,3 +376,3 @@ if (typeof beginRoot === 'number') beginRoot = this.getNode(beginRoot);

* iterative approach.
* @param {BTNKey | N | null} beginRoot - The `beginRoot` parameter represents the
* @param {BTNKey | N | null | undefined} beginRoot - The `beginRoot` parameter represents the
* starting node from which the height of the binary tree is calculated. It can be either a node

@@ -386,3 +386,3 @@ * object (`N`), a key value of a node in the tree (`BTNKey`), or `null` if no starting

*/
getHeight(beginRoot: BTNKey | N | null = this.root, iterationType = this.iterationType): number {
getHeight(beginRoot: BTNKey | N | null | undefined = this.root, iterationType = this.iterationType): number {
if (typeof beginRoot === 'number') beginRoot = this.getNode(beginRoot);

@@ -429,3 +429,3 @@ if (!beginRoot) return -1;

* recursive or iterative approach.
* @param {N | null} beginRoot - The `beginRoot` parameter is the starting node from which we want to
* @param {N | null | undefined} beginRoot - The `beginRoot` parameter is the starting node from which we want to
* calculate the minimum height of the tree. It is optional and defaults to the root of the tree if

@@ -437,3 +437,3 @@ * not provided.

*/
getMinHeight(beginRoot: N | null = this.root, iterationType = this.iterationType): number {
getMinHeight(beginRoot: N | null | undefined = this.root, iterationType = this.iterationType): number {
if (!beginRoot) return -1;

@@ -454,3 +454,3 @@

let node: N | null | undefined = beginRoot,
last: N | null = null;
last: N | null | undefined = null;
const depths: Map<N, number> = new Map();

@@ -484,7 +484,7 @@

* height of the tree.
* @param {N | null} beginRoot - The parameter `beginRoot` is of type `N | null`, which means it can
* @param {N | null | undefined} beginRoot - The parameter `beginRoot` is of type `N | null | undefined`, which means it can
* either be of type `N` (representing a node in a tree) or `null` (representing an empty tree).
* @returns The method is returning a boolean value.
*/
isPerfectlyBalanced(beginRoot: N | null = this.root): boolean {
isPerfectlyBalanced(beginRoot: N | null | undefined = this.root): boolean {
return this.getMinHeight(beginRoot) + 1 >= this.getHeight(beginRoot);

@@ -497,3 +497,3 @@ }

onlyOne?: boolean,
beginRoot?: N | null,
beginRoot?: N | null | undefined,
iterationType?: IterationType

@@ -503,6 +503,6 @@ ): N[];

getNodes<C extends BTNCallback<N, N>>(
identifier: N | null,
identifier: N | null | undefined,
callback?: C,
onlyOne?: boolean,
beginRoot?: N | null,
beginRoot?: N | null | undefined,
iterationType?: IterationType

@@ -515,3 +515,3 @@ ): N[];

onlyOne?: boolean,
beginRoot?: N | null,
beginRoot?: N | null | undefined,
iterationType?: IterationType

@@ -534,3 +534,3 @@ ): N[];

* function will continue searching for all
* @param {N | null} beginRoot - The `beginRoot` parameter is the starting node from which the
* @param {N | null | undefined} beginRoot - The `beginRoot` parameter is the starting node from which the
* traversal of the binary tree will begin. It is optional and defaults to the root of the binary

@@ -543,6 +543,6 @@ * tree.

getNodes<C extends BTNCallback<N>>(
identifier: ReturnType<C> | null,
identifier: ReturnType<C> | null | undefined,
callback: C = this.defaultOneParamCallback as C,
onlyOne = false,
beginRoot: N | null = this.root,
beginRoot: N | null | undefined = this.root,
iterationType = this.iterationType

@@ -587,3 +587,3 @@ ): N[] {

callback?: C,
beginRoot?: N | null,
beginRoot?: N | null | undefined,
iterationType?: IterationType

@@ -593,5 +593,5 @@ ): boolean;

has<C extends BTNCallback<N, N>>(
identifier: N | null,
identifier: N | null | undefined,
callback?: C,
beginRoot?: N | null,
beginRoot?: N | null | undefined,
iterationType?: IterationType

@@ -601,5 +601,5 @@ ): boolean;

has<C extends BTNCallback<N>>(
identifier: ReturnType<C> | null,
identifier: ReturnType<C> | null | undefined,
callback: C,
beginRoot?: N | null,
beginRoot?: N | null | undefined,
iterationType?: IterationType

@@ -626,3 +626,3 @@ ): boolean;

has<C extends BTNCallback<N>>(
identifier: ReturnType<C> | null,
identifier: ReturnType<C> | null | undefined,
callback: C = this.defaultOneParamCallback as C,

@@ -640,12 +640,12 @@ beginRoot = this.root,

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

@@ -655,5 +655,5 @@ getNode<C extends BTNCallback<N>>(

callback: C,
beginRoot?: N | null,
beginRoot?: N | null | undefined,
iterationType?: IterationType
): N | null;
): N | null | undefined;

@@ -676,7 +676,7 @@ /**

getNode<C extends BTNCallback<N>>(
identifier: ReturnType<C> | null,
identifier: ReturnType<C> | null | undefined,
callback: C = this.defaultOneParamCallback as C,
beginRoot = this.root,
iterationType = this.iterationType
): N | null {
): N | null | undefined {
if ((identifier as any) instanceof BinaryTreeNode) callback = (node => node) as C;

@@ -690,3 +690,3 @@

callback?: C,
beginRoot?: N | null,
beginRoot?: N | null | undefined,
iterationType?: IterationType

@@ -696,5 +696,5 @@ ): V | undefined;

get<C extends BTNCallback<N, N>>(
identifier: N | null,
identifier: N | null | undefined,
callback?: C,
beginRoot?: N | null,
beginRoot?: N | null | undefined,
iterationType?: IterationType

@@ -706,3 +706,3 @@ ): V | undefined;

callback: C,
beginRoot?: N | null,
beginRoot?: N | null | undefined,
iterationType?: IterationType

@@ -727,3 +727,3 @@ ): V | undefined;

get<C extends BTNCallback<N>>(
identifier: ReturnType<C> | null,
identifier: ReturnType<C> | null | undefined,
callback: C = this.defaultOneParamCallback as C,

@@ -764,3 +764,3 @@ beginRoot = this.root,

* iterative traversal.
* @param {BTNKey | N | null} beginRoot - The `beginRoot` parameter is the starting point
* @param {BTNKey | N | null | undefined} beginRoot - The `beginRoot` parameter is the starting point
* for finding the leftmost node in a binary tree. It can be either a node object (`N`), a key value

@@ -773,3 +773,3 @@ * of a node (`BTNKey`), or `null` if the tree is empty.

*/
getLeftMost(beginRoot: BTNKey | N | null = this.root, iterationType = this.iterationType): N | null {
getLeftMost(beginRoot: BTNKey | N | null | undefined = this.root, iterationType = this.iterationType): N | null | undefined {
if (typeof beginRoot === 'number') beginRoot = this.getNode(beginRoot);

@@ -800,4 +800,4 @@

* iteratively.
* @param {N | null} beginRoot - The `beginRoot` parameter is the starting node from which we want to
* find the rightmost node. It is of type `N | null`, which means it can either be a node of type `N`
* @param {N | null | undefined} beginRoot - The `beginRoot` parameter is the starting node from which we want to
* find the rightmost node. It is of type `N | null | undefined`, which means it can either be a node of type `N`
* or `null`. If it is `null`, it means there is no starting node

@@ -809,3 +809,3 @@ * @param iterationType - The `iterationType` parameter is used to determine the type of iteration to

*/
getRightMost(beginRoot: N | null = this.root, iterationType = this.iterationType): N | null {
getRightMost(beginRoot: N | null | undefined = this.root, iterationType = this.iterationType): N | null | undefined {
// TODO support get right most by passing key in

@@ -841,3 +841,3 @@ if (!beginRoot) return beginRoot;

*/
isSubtreeBST(beginRoot: N | null, iterationType = this.iterationType): boolean {
isSubtreeBST(beginRoot: N | null | undefined, iterationType = this.iterationType): boolean {
// TODO there is a bug

@@ -887,3 +887,3 @@ if (!beginRoot) return true;

callback?: C,
beginRoot?: BTNKey | N | null,
beginRoot?: BTNKey | N | null | undefined,
iterationType?: IterationType,

@@ -895,3 +895,3 @@ includeNull?: false

callback?: C,
beginRoot?: BTNKey | N | null,
beginRoot?: BTNKey | N | null | undefined,
iterationType?: IterationType,

@@ -901,5 +901,5 @@ includeNull?: undefined

subTreeTraverse<C extends BTNCallback<N | null>>(
subTreeTraverse<C extends BTNCallback<N | null | undefined>>(
callback?: C,
beginRoot?: BTNKey | N | null,
beginRoot?: BTNKey | N | null | undefined,
iterationType?: IterationType,

@@ -916,3 +916,3 @@ includeNull?: true

* an array.
* @param {BTNKey | N | null} beginRoot - The `beginRoot` parameter is the starting point
* @param {BTNKey | N | null | undefined} beginRoot - The `beginRoot` parameter is the starting point
* for traversing the subtree. It can be either a node object, a key value of a node, or `null` to

@@ -925,5 +925,5 @@ * start from the root of the tree.

*/
subTreeTraverse<C extends BTNCallback<N | null>>(
subTreeTraverse<C extends BTNCallback<N | null | undefined>>(
callback: C = this.defaultOneParamCallback as C,
beginRoot: BTNKey | N | null = this.root,
beginRoot: BTNKey | N | null | undefined = this.root,
iterationType = this.iterationType,

@@ -934,15 +934,15 @@ includeNull = false

const ans: (ReturnType<BTNCallback<N>> | null)[] = [];
const ans: (ReturnType<BTNCallback<N>> | null | undefined)[] = [];
if (!beginRoot) return ans;
if (iterationType === IterationType.RECURSIVE) {
const _traverse = (cur: N | null) => {
const _traverse = (cur: N | null | undefined) => {
if (cur !== undefined) {
ans.push(callback(cur));
if (includeNull) {
cur !== null && cur.left !== undefined && _traverse(cur.left);
cur !== null && cur.right !== undefined && _traverse(cur.right);
cur && this.isNodeOrNull(cur.left) && _traverse(cur.left);
cur && this.isNodeOrNull(cur.right) && _traverse(cur.right);
} else {
cur !== null && cur.left && _traverse(cur.left);
cur !== null && cur.right && _traverse(cur.right);
cur && cur.left && _traverse(cur.left);
cur && cur.right && _traverse(cur.right);
}

@@ -954,3 +954,3 @@ }

} else {
const stack: (N | null)[] = [beginRoot];
const stack: (N | null | undefined)[] = [beginRoot];

@@ -962,7 +962,7 @@ while (stack.length > 0) {

if (includeNull) {
cur !== null && cur.right !== undefined && stack.push(cur.right);
cur !== null && cur.left !== undefined && stack.push(cur.left);
cur && this.isNodeOrNull(cur.right) && stack.push(cur.right);
cur && this.isNodeOrNull(cur.left) && stack.push(cur.left);
} else {
cur !== null && cur.right && stack.push(cur.right);
cur !== null && cur.left && stack.push(cur.left);
cur && cur.right && stack.push(cur.right);
cur && cur.left && stack.push(cur.left);
}

@@ -974,7 +974,19 @@ }

}
isNode(node: any): node is N {
return node instanceof BinaryTreeNode && node.key.toString() !== 'NaN';
}
isNIL(node: any) {
return node instanceof BinaryTreeNode && node.key.toString() === 'NaN';
}
isNodeOrNull(node: any): node is (N | null){
return this.isNode(node) || node === null;
}
dfs<C extends BTNCallback<N>>(
callback?: C,
pattern?: DFSOrderPattern,
beginRoot?: N | null,
beginRoot?: N | null | undefined,
iterationType?: IterationType,

@@ -987,3 +999,3 @@ includeNull?: false

pattern?: DFSOrderPattern,
beginRoot?: N | null,
beginRoot?: N | null | undefined,
iterationType?: IterationType,

@@ -993,6 +1005,6 @@ includeNull?: undefined

dfs<C extends BTNCallback<N | null>>(
dfs<C extends BTNCallback<N | null | undefined>>(
callback?: C,
pattern?: DFSOrderPattern,
beginRoot?: N | null,
beginRoot?: N | null | undefined,
iterationType?: IterationType,

@@ -1010,3 +1022,3 @@ includeNull?: true

* nodes are visited during the depth-first search. There are three possible values for `pattern`:
* @param {N | null} beginRoot - The `beginRoot` parameter is the starting node for the depth-first
* @param {N | null | undefined} beginRoot - The `beginRoot` parameter is the starting node for the depth-first
* search. It determines where the search will begin in the tree or graph structure. If `beginRoot`

@@ -1019,6 +1031,6 @@ * is `null`, an empty array will be returned.

*/
dfs<C extends BTNCallback<N | null>>(
dfs<C extends BTNCallback<N | null | undefined>>(
callback: C = this.defaultOneParamCallback as C,
pattern: DFSOrderPattern = 'in',
beginRoot: N | null = this.root,
beginRoot: N | null | undefined = this.root,
iterationType: IterationType = IterationType.ITERATIVE,

@@ -1030,13 +1042,13 @@ includeNull = false

if (iterationType === IterationType.RECURSIVE) {
const _traverse = (node: N | null) => {
const _traverse = (node: N | null | undefined) => {
switch (pattern) {
case 'in':
if (includeNull) {
if (node !== null && node.left !== undefined) _traverse(node.left);
ans.push(callback(node));
if (node !== null && node.right !== undefined) _traverse(node.right);
if (node && this.isNodeOrNull(node.left)) _traverse(node.left);
this.isNodeOrNull(node) && ans.push(callback(node));
if (node && this.isNodeOrNull(node.right)) _traverse(node.right);
} else {
if (node !== null && node.left) _traverse(node.left);
ans.push(callback(node));
if (node !== null && node.right) _traverse(node.right);
if (node && node.left) _traverse(node.left);
this.isNode(node) && ans.push(callback(node));
if (node && node.right) _traverse(node.right);
}

@@ -1046,9 +1058,9 @@ break;

if (includeNull) {
ans.push(callback(node));
if (node !== null && node.left !== undefined) _traverse(node.left);
if (node !== null && node.right !== undefined) _traverse(node.right);
this.isNodeOrNull(node) && ans.push(callback(node));
if (node && this.isNodeOrNull(node.left)) _traverse(node.left);
if (node && this.isNodeOrNull(node.right)) _traverse(node.right);
} else {
ans.push(callback(node));
if (node !== null && node.left) _traverse(node.left);
if (node !== null && node.right) _traverse(node.right);
this.isNode(node) && ans.push(callback(node));
if (node && node.left) _traverse(node.left);
if (node && node.right) _traverse(node.right);
}

@@ -1058,9 +1070,9 @@ break;

if (includeNull) {
if (node !== null && node.left !== undefined) _traverse(node.left);
if (node !== null && node.right !== undefined) _traverse(node.right);
ans.push(callback(node));
if (node && this.isNodeOrNull(node.left)) _traverse(node.left);
if (node && this.isNodeOrNull(node.right)) _traverse(node.right);
this.isNodeOrNull(node) && ans.push(callback(node));
} else {
if (node !== null && node.left) _traverse(node.left);
if (node !== null && node.right) _traverse(node.right);
ans.push(callback(node));
if (node && node.left) _traverse(node.left);
if (node && node.right) _traverse(node.right);
this.isNode(node) && ans.push(callback(node));
}

@@ -1079,3 +1091,3 @@

const cur = stack.pop();
if (cur === undefined) continue;
if (cur === undefined || this.isNIL(cur.node)) continue;
if (includeNull) {

@@ -1120,3 +1132,3 @@ if (cur.node === undefined) continue;

callback?: C,
beginRoot?: N | null,
beginRoot?: N | null | undefined,
iterationType?: IterationType,

@@ -1128,3 +1140,3 @@ includeNull?: false

callback?: C,
beginRoot?: N | null,
beginRoot?: N | null | undefined,
iterationType?: IterationType,

@@ -1134,5 +1146,5 @@ includeNull?: undefined

bfs<C extends BTNCallback<N | null>>(
bfs<C extends BTNCallback<N | null | undefined>>(
callback?: C,
beginRoot?: N | null,
beginRoot?: N | null | undefined,
iterationType?: IterationType,

@@ -1148,3 +1160,3 @@ includeNull?: true

* `ReturnType<BTNCallback<N>>`. The default value for this parameter is `this.defaultOneParamCallback
* @param {N | null} beginRoot - The `beginRoot` parameter is the starting node for the breadth-first
* @param {N | null | undefined} beginRoot - The `beginRoot` parameter is the starting node for the breadth-first
* search. It determines from which node the search will begin. If `beginRoot` is `null`, the search

@@ -1157,5 +1169,5 @@ * will not be performed and an empty array will be returned.

*/
bfs<C extends BTNCallback<N | null>>(
bfs<C extends BTNCallback<N | null | undefined>>(
callback: C = this.defaultOneParamCallback as C,
beginRoot: N | null = this.root,
beginRoot: N | null | undefined = this.root,
iterationType = this.iterationType,

@@ -1169,3 +1181,3 @@ includeNull = false

if (iterationType === IterationType.RECURSIVE) {
const queue: Queue<N | null> = new Queue<N | null>([beginRoot]);
const queue: Queue<N | null | undefined> = new Queue<N | null | undefined>([beginRoot]);

@@ -1179,4 +1191,4 @@ const traverse = (level: number) => {

if (includeNull) {
if (current && current.left !== undefined) queue.push(current.left);
if (current && current.right !== undefined) queue.push(current.right);
if (current && this.isNodeOrNull(current.left)) queue.push(current.left);
if (current && this.isNodeOrNull(current.right)) queue.push(current.right);
} else {

@@ -1192,3 +1204,3 @@ if (current.left) queue.push(current.left);

} else {
const queue = new Queue<N | null>([beginRoot]);
const queue = new Queue<N | null | undefined>([beginRoot]);
while (queue.size > 0) {

@@ -1202,4 +1214,4 @@ const levelSize = queue.size;

if (includeNull) {
if (current !== null && current.left !== undefined) queue.push(current.left);
if (current !== null && current.right !== undefined) queue.push(current.right);
if (current && this.isNodeOrNull(current.left)) queue.push(current.left);
if (current && this.isNodeOrNull(current.right)) queue.push(current.right);
} else {

@@ -1217,3 +1229,3 @@ if (current.left) queue.push(current.left);

callback?: C,
beginRoot?: N | null,
beginRoot?: N | null | undefined,
iterationType?: IterationType,

@@ -1225,3 +1237,3 @@ includeNull?: false

callback?: C,
beginRoot?: N | null,
beginRoot?: N | null | undefined,
iterationType?: IterationType,

@@ -1231,5 +1243,5 @@ includeNull?: undefined

listLevels<C extends BTNCallback<N | null>>(
listLevels<C extends BTNCallback<N | null | undefined>>(
callback?: C,
beginRoot?: N | null,
beginRoot?: N | null | undefined,
iterationType?: IterationType,

@@ -1245,3 +1257,3 @@ includeNull?: true

* is determined by the generic type `C`.
* @param {N | null} beginRoot - The `beginRoot` parameter represents the starting node of the binary tree
* @param {N | null | undefined} beginRoot - The `beginRoot` parameter represents the starting node of the binary tree
* traversal. It can be any node in the binary tree. If no node is provided, the traversal will start

@@ -1256,5 +1268,5 @@ * from the root node of the binary tree.

*/
listLevels<C extends BTNCallback<N | null>>(
listLevels<C extends BTNCallback<N | null | undefined>>(
callback: C = this.defaultOneParamCallback as C,
beginRoot: N | null = this.root,
beginRoot: N | null | undefined = this.root,
iterationType = this.iterationType,

@@ -1267,8 +1279,8 @@ includeNull = false

if (iterationType === IterationType.RECURSIVE) {
const _recursive = (node: N | null, level: number) => {
const _recursive = (node: N | null | undefined, level: number) => {
if (!levelsNodes[level]) levelsNodes[level] = [];
levelsNodes[level].push(callback(node));
if (includeNull) {
if (node && node.left !== undefined) _recursive(node.left, level + 1);
if (node && node.right !== undefined) _recursive(node.right, level + 1);
if (node && this.isNodeOrNull(node.left)) _recursive(node.left, level + 1);
if (node && this.isNodeOrNull(node.right)) _recursive(node.right, level + 1);
} else {

@@ -1282,3 +1294,3 @@ if (node && node.left) _recursive(node.left, level + 1);

} else {
const stack: [N | null, number][] = [[beginRoot, 0]];
const stack: [N | null | undefined, number][] = [[beginRoot, 0]];

@@ -1293,4 +1305,4 @@ while (stack.length > 0) {

if (includeNull) {
if (node && node.right !== undefined) stack.push([node.right, level + 1]);
if (node && node.left !== undefined) stack.push([node.left, level + 1]);
if (node && this.isNodeOrNull(node.right)) stack.push([node.right, level + 1]);
if (node && this.isNodeOrNull(node.left)) stack.push([node.left, level + 1]);
} else {

@@ -1354,3 +1366,3 @@ if (node && node.right) stack.push([node.right, level + 1]);

* following values:
* @param {N | null} beginRoot - The `beginRoot` parameter is the starting node for the Morris
* @param {N | null | undefined} beginRoot - The `beginRoot` parameter is the starting node for the Morris
* traversal. It specifies the root node of the tree from which the traversal should begin. If

@@ -1363,3 +1375,3 @@ * `beginRoot` is `null`, an empty array will be returned.

pattern: DFSOrderPattern = 'in',
beginRoot: N | null = this.root
beginRoot: N | null | undefined = this.root
): ReturnType<C>[] {

@@ -1381,3 +1393,3 @@ if (beginRoot === null) return [];

};
const _printEdge = (node: N | null) => {
const _printEdge = (node: N | null | undefined) => {
const tail: N | null | undefined = _reverseEdge(node);

@@ -1516,3 +1528,3 @@ let cur: N | null | undefined = tail;

* The function `_addTo` adds a new node to a binary tree if there is an available position.
* @param {N | null} newNode - The `newNode` parameter represents the node that you want to add to
* @param {N | null | undefined} newNode - The `newNode` parameter represents the node that you want to add to
* the binary tree. It can be either a node object or `null`.

@@ -1526,3 +1538,3 @@ * @param {N} parent - The `parent` parameter represents the parent node to which the new node will

*/
protected _addTo(newNode: N | null, parent: N): N | null | undefined {
protected _addTo(newNode: N | null | undefined, parent: N): N | null | undefined {
if (parent) {

@@ -1554,6 +1566,6 @@ // When all leaf nodes are null, it will no longer be possible to add new entity nodes to this binary tree.

* it also sets the parent property of the value to undefined.
* @param {N | null} v - The parameter `v` is of type `N | null`, which means it can either be of
* @param {N | null | undefined} v - The parameter `v` is of type `N | null | undefined`, which means it can either be of
* type `N` or `null`.
*/
protected _setRoot(v: N | null) {
protected _setRoot(v: N | null | undefined) {
if (v) {

@@ -1565,3 +1577,61 @@ v.parent = undefined;

print(beginRoot: N | null | undefined = this.root) {
const display = (root: N | null | undefined): void => {
const [lines, , ,] = _displayAux(root);
for (const line of lines) {
console.log(line);
}
};
const _displayAux = (node: N | null | undefined): [string[], number, number, number] => {
if (node === undefined || node === null) {
return [[], 0, 0, 0];
}
if (node && node.right === undefined && node.left === undefined) {
const line = `${node.key}`;
const width = line.length;
const height = 1;
const middle = Math.floor(width / 2);
return [[line], width, height, middle];
}
if (node && node.right === undefined) {
const [lines, n, p, x] = _displayAux(node.left);
const s = `${node.key}`;
const u = s.length;
const first_line = ' '.repeat(x + 1) + '_'.repeat(n - x - 1) + s;
const second_line = ' '.repeat(x) + '/' + ' '.repeat(n - x - 1 + u);
const shifted_lines = lines.map(line => line + ' '.repeat(u));
return [[first_line, second_line, ...shifted_lines], n + u, p + 2, n + Math.floor(u / 2)];
}
if (node && node.left === undefined) {
const [lines, n, p, u] = _displayAux(node.right);
const s = `${node.key}`;
const x = s.length;
const first_line = s + '_'.repeat(x) + ' '.repeat(n - x);
const second_line = ' '.repeat(u + x) + '\\' + ' '.repeat(n - x - 1);
const shifted_lines = lines.map(line => ' '.repeat(u) + line);
return [[first_line, second_line, ...shifted_lines], n + x, p + 2, Math.floor(u / 2)];
}
const [left, n, p, x] = _displayAux(node.left);
const [right, m, q, y] = _displayAux(node.right);
const s = `${node.key}`;
const u = s.length;
const first_line = ' '.repeat(x + 1) + '_'.repeat(n - x - 1) + s + '_'.repeat(y) + ' '.repeat(m - y);
const second_line = ' '.repeat(x) + '/' + ' '.repeat(n - x - 1 + u + y) + '\\' + ' '.repeat(m - y - 1);
if (p < q) {
left.push(...new Array(q - p).fill(' '.repeat(n)));
} else if (q < p) {
right.push(...new Array(p - q).fill(' '.repeat(m)));
}
const zipped_lines = left.map((a, i) => a + ' '.repeat(u) + right[i]);
return [[first_line, second_line, ...zipped_lines], n + m + u, Math.max(p, q) + 2, n + Math.floor(u / 2)];
};
display(beginRoot);
}
// --- end additional methods ---
}

134

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

@@ -15,5 +15,50 @@ /**

export class BSTNode<V = any, N extends BSTNode<V, N> = BSTNodeNested<V>> extends BinaryTreeNode<V, N> {
override parent: N | undefined;
constructor(key: BTNKey, value?: V) {
super(key, value);
this.parent = undefined;
this._left = undefined;
this._right = undefined;
}
protected override _left: N | undefined;
/**
* Get the left child node.
*/
override get left(): N | undefined {
return this._left;
}
/**
* Set the left child node.
* @param {N | undefined} v - The left child node.
*/
override set left(v: N | undefined) {
if (v) {
v.parent = this as unknown as N;
}
this._left = v;
}
protected override _right: N | undefined;
/**
* Get the right child node.
*/
override get right(): N | undefined {
return this._right;
}
/**
* Set the right child node.
* @param {N | undefined} v - The right child node.
*/
override set right(v: N | undefined) {
if (v) {
v.parent = this as unknown as N;
}
this._right = v;
}
}

@@ -33,2 +78,3 @@

super(options);
this._root = undefined;
if (options !== undefined) {

@@ -41,4 +87,12 @@ const {comparator} = options;

}
protected override _root: N | undefined = undefined;
/**
* Get the root node of the binary tree.
*/
override get root(): N | undefined {
return this._root;
}
/**
* The function creates a new binary search tree node with the given key and value.

@@ -58,13 +112,17 @@ * @param {BTNKey} key - The key parameter is the key value that will be associated with

* into the tree.
* @param {BTNKey | N | null} keyOrNode - The `keyOrNode` parameter can be either a
* `BTNKey` (which can be a number or a string), a `BSTNode` object, or `null`.
* @param {BTNKey | N | undefined} keyOrNode - The `keyOrNode` parameter can be either a
* `BTNKey` (which can be a number or a string), a `BSTNode` object, or `undefined`.
* @param [value] - The `value` parameter is the value to be assigned to the new node being added to the
* binary search tree.
* @returns the inserted node (N) if it was successfully added to the binary search tree. If the node
* was not added or if the parameters were invalid, it returns null or undefined.
* was not added or if the parameters were invalid, it returns undefined or undefined.
*/
override add(keyOrNode: BTNKey | N | null, value?: V): N | null | undefined {
override add(keyOrNode: BTNKey | N | null | undefined, value?: V): N | undefined {
if (keyOrNode === 8) {
debugger
}
if (keyOrNode === null) return undefined;
// TODO support node as a parameter
let inserted: N | null = null;
let newNode: N | null = null;
let inserted:N | undefined;
let newNode:N | undefined;
if (keyOrNode instanceof BSTNode) {

@@ -74,6 +132,6 @@ newNode = keyOrNode;

newNode = this.createNode(keyOrNode, value);
} else if (keyOrNode === null) {
newNode = null;
} else {
newNode = undefined;
}
if (this.root === null) {
if (this.root === undefined) {
this._setRoot(newNode);

@@ -86,3 +144,3 @@ this._size = this.size + 1;

while (traversing) {
if (cur !== null && newNode !== null) {
if (cur !== undefined && newNode !== undefined) {
if (this._compare(cur.key, newNode.key) === CP.eq) {

@@ -140,3 +198,3 @@ if (newNode) {

* array of `BTNKey` or `N` (which represents the node type in the binary search tree) or
* `null
* `undefined
* @param {V[]} data - The values of tree nodes

@@ -146,20 +204,20 @@ * @param {boolean} isBalanceAdd - If true the nodes will be balance inserted in binary search method.

* It can have two possible values:
* @returns The `addMany` function returns an array of `N`, `null`, or `undefined` values.
* @returns The `addMany` function returns an array of `N`, `undefined`, or `undefined` values.
*/
override addMany(
keysOrNodes: (BTNKey | null)[] | (N | null)[],
keysOrNodes: (BTNKey | undefined)[] | (N | undefined)[],
data?: V[],
isBalanceAdd = true,
iterationType = this.iterationType
): (N | null | undefined)[] {
): (N | undefined)[] {
// TODO this addMany function is inefficient, it should be optimized
function hasNoNull(arr: (BTNKey | null)[] | (N | null)[]): arr is BTNKey[] | N[] {
return arr.indexOf(null) === -1;
function hasNoNull(arr: (BTNKey | undefined)[] | (N | undefined)[]): arr is BTNKey[] | N[] {
return arr.indexOf(undefined) === -1;
}
if (!isBalanceAdd || !hasNoNull(keysOrNodes)) {
return super.addMany(keysOrNodes, data);
return super.addMany(keysOrNodes, data).map(n => n ?? undefined);
}
const inserted: (N | null | undefined)[] = [];
const inserted: (N | undefined)[] = [];
const combinedArr: [BTNKey | N, V][] = keysOrNodes.map(

@@ -180,3 +238,3 @@ (value: BTNKey | N, index) => [value, data?.[index]] as [BTNKey | N, V]

let sortedKeysOrNodes: (number | N | null)[] = [],
let sortedKeysOrNodes: (number | N | undefined)[] = [],
sortedData: (V | undefined)[] | undefined = [];

@@ -193,3 +251,3 @@

sortedData = sorted.map(([, value]) => value);
const recursive = (arr: (BTNKey | null | N)[], data?: (V | undefined)[]) => {
const recursive = (arr: (BTNKey | undefined | N)[], data?: (V | undefined)[]) => {
if (arr.length === 0) return;

@@ -233,3 +291,3 @@

* rightmost node otherwise.
* @param {N | null} beginRoot - The `beginRoot` parameter is the starting point for finding the last
* @param {N | undefined} beginRoot - The `beginRoot` parameter is the starting point for finding the last
* key in a binary tree. It represents the root node of the subtree from which the search for the

@@ -245,3 +303,3 @@ * last key should begin. If no specific `beginRoot` is provided, the search will start from the root

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

@@ -266,5 +324,5 @@ else if (this._compare(0, 1) === CP.gt) return this.getLeftMost(beginRoot, iterationType)?.key ?? 0;

* return an array containing all nodes that match the node
* @param {N | null} beginRoot - The `beginRoot` parameter is the starting node for the traversal. It
* @param {N | undefined} beginRoot - The `beginRoot` parameter is the starting node for the traversal. It
* specifies the root node of the binary tree from which the traversal should begin. If `beginRoot`
* is `null`, an empty array will be returned.
* is `undefined`, an empty array will be returned.
* @param iterationType - The `iterationType` parameter determines the type of iteration used to

@@ -275,6 +333,6 @@ * traverse the binary tree. It can have one of the following values:

override getNodes<C extends BTNCallback<N>>(
identifier: ReturnType<C> | null,
identifier: ReturnType<C> | undefined,
callback: C = this.defaultOneParamCallback as C,
onlyOne = false,
beginRoot: N | null = this.root,
beginRoot: N | undefined = this.root,
iterationType = this.iterationType

@@ -341,6 +399,6 @@ ): N[] {

* of the following values:
* @param {BTNKey | N | null} targetNode - The `targetNode` parameter in the
* @param {BTNKey | N | undefined} targetNode - The `targetNode` parameter in the
* `lesserOrGreaterTraverse` function is used to specify the node from which the traversal should
* start. It can be either a reference to a specific node (`N`), the key of a node
* (`BTNKey`), or `null` to
* (`BTNKey`), or `undefined` to
* @param iterationType - The `iterationType` parameter determines whether the traversal should be

@@ -353,6 +411,6 @@ * done recursively or iteratively. It can have two possible values:

lesserOrGreater: CP = CP.lt,
targetNode: BTNKey | N | null = this.root,
targetNode: BTNKey | N | undefined = this.root,
iterationType = this.iterationType
): ReturnType<C>[] {
if (typeof targetNode === 'number') targetNode = this.getNode(targetNode);
if (typeof targetNode === 'number') targetNode = this.getNode(targetNode) ?? undefined;
const ans: ReturnType<BTNCallback<N>>[] = [];

@@ -436,2 +494,3 @@ if (!targetNode) return ans;

const midNode = sorted[m];
debugger
this.add(midNode.key, midNode.value);

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

if (iterationType === IterationType.RECURSIVE) {
const _height = (cur: N | null | undefined): number => {
const _height = (cur: N | undefined): number => {
if (!cur) return 0;

@@ -470,4 +529,4 @@ const leftHeight = _height(cur.left),

const stack: N[] = [];
let node: N | null | undefined = this.root,
last: N | null = null;
let node: N | undefined = this.root,
last:N | undefined = undefined;
const depths: Map<N, number> = new Map();

@@ -489,3 +548,3 @@

last = node;
node = null;
node = undefined;
}

@@ -502,2 +561,9 @@ } else node = node.right;

protected _setRoot(v: N | undefined) {
if (v) {
v.parent = undefined;
}
this._root = v;
}
/**

@@ -504,0 +570,0 @@ * The function compares two values using a comparator function and returns whether the first value

459

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

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

import {RBTNColor} from '../../types';
import {
BinaryTreeDeletedResult,
BTNCallback,
BTNKey,
IterationType,
RBTNColor,
RBTreeNodeNested,
RBTreeOptions
} from '../../types';
import {BST, BSTNode} from "./bst";
import {IBinaryTree} from "../../interfaces";
import {BinaryTreeNode} from "./binary-tree";
export class RBTreeNode {
key: number;
parent: RBTreeNode;
left: RBTreeNode;
right: RBTreeNode;
color: number = RBTNColor.BLACK;
constructor(key: number, color: RBTNColor = RBTNColor.BLACK) {
this.key = key;
export class RBTreeNode<V = any, N extends RBTreeNode<V, N> = RBTreeNodeNested<V>> extends BSTNode<V, N> {
color: RBTNColor;
constructor(key: BTNKey, value?: V, color: RBTNColor = RBTNColor.BLACK) {
super(key, value);
this.color = color;
this.parent = null as unknown as RBTreeNode;
this.left = null as unknown as RBTreeNode;
this.right = null as unknown as RBTreeNode;
}
}
export const NIL = new RBTreeNode(0);
/**

@@ -37,10 +38,15 @@ * 1. Each node is either red or black.

*/
export class RedBlackTree {
constructor() {
this._root = NIL;
export class RedBlackTree<V = any, N extends RBTreeNode<V, N> = RBTreeNode<V, RBTreeNodeNested<V>>>
extends BST<V, N>
implements IBinaryTree<V, N>
{
constructor(options?: RBTreeOptions) {
super(options);
this._root = this.NIL;
}
protected _root: RBTreeNode;
protected _root: N;
get root(): RBTreeNode {
get root(): N {
return this._root;

@@ -55,23 +61,30 @@ }

/**
* The `insert` function inserts a new node with a given key into a red-black tree and fixes any
* violations of the red-black tree properties.
* @param {number} key - The key parameter is a number that represents the value to be inserted into
* the RBTree.
* @returns The function does not explicitly return anything.
*/
add(key: number): void {
const node: RBTreeNode = new RBTreeNode(key, RBTNColor.RED);
node.left = NIL;
node.right = NIL;
NIL: N = new RBTreeNode<V>(NaN) as unknown as N;
let y: RBTreeNode = null as unknown as RBTreeNode;
let x: RBTreeNode = this.root;
override add(keyOrNode: BTNKey | N | null | undefined, value?: V): N | undefined {
let node: N;
if (typeof keyOrNode === 'number') {
node = this.createNode(keyOrNode, value, RBTNColor.RED);
} else if(keyOrNode instanceof RBTreeNode) {
node = keyOrNode;
} else if (keyOrNode === null) {
return;
} else if (keyOrNode === undefined) {
return;
} else {
return;
}
while (x !== NIL) {
node.left = this.NIL;
node.right = this.NIL;
let y: N | undefined = undefined;
let x: N | undefined = this.root;
while (x !== this.NIL) {
y = x;
if (node.key < x.key) {
if (x && node.key < x.key) {
x = x.left;
} else {
x = x.right;
x = x?.right;
}

@@ -81,4 +94,4 @@ }

node.parent = y;
if (y === null) {
this._root = node;
if (y === undefined) {
this._setRoot(node);
} else if (node.key < y.key) {

@@ -90,3 +103,3 @@ y.left = node;

if (node.parent === null) {
if (node.parent === undefined) {
node.color = RBTNColor.BLACK;

@@ -97,3 +110,3 @@ this._size++;

if (node.parent.parent === null) {
if (node.parent.parent === undefined) {
this._size++;

@@ -107,26 +120,29 @@ return;

/**
* The `delete` function in TypeScript is used to remove a node with a specific key from a red-black
* tree.
* @param {number} key - The `node` parameter is of type `RBTreeNode` and represents the current
* node being processed in the delete operation.
* @returns The `delete` function does not return anything. It has a return type of `void`.
*/
delete(key: number): void {
const helper = (node: RBTreeNode): void => {
let z: RBTreeNode = NIL;
let x: RBTreeNode, y: RBTreeNode;
while (node !== NIL) {
if (node.key === key) {
override createNode(key: BTNKey, value?: V, color: RBTNColor = RBTNColor.BLACK): N {
return new RBTreeNode<V, N>(key, value, color) as N;
}
delete<C extends BTNCallback<N>>(
identifier: ReturnType<C> | null | undefined,
callback: C = this.defaultOneParamCallback as C
): BinaryTreeDeletedResult<N>[] {
const ans: BinaryTreeDeletedResult<N>[] = [];
if (identifier === null) return ans;
const helper = (node: N | undefined): void => {
let z: N = this.NIL;
let x: N | undefined, y: N;
while (node !== this.NIL) {
if (node && callback(node) === identifier) {
z = node;
}
if (node.key <= key) {
if (node && identifier && callback(node) <= identifier) {
node = node.right;
} else {
node = node.left;
node = node?.left;
}
}
if (z === NIL) {
if (z === this.NIL) {
this._size--;

@@ -138,8 +154,8 @@ return;

let yOriginalColor: number = y.color;
if (z.left === NIL) {
if (z.left === this.NIL) {
x = z.right;
this._rbTransplant(z, z.right);
} else if (z.right === NIL) {
this._rbTransplant(z, z.right!);
} else if (z.right === this.NIL) {
x = z.left;
this._rbTransplant(z, z.left);
this._rbTransplant(z, z.left!);
} else {

@@ -150,7 +166,7 @@ y = this.getLeftMost(z.right);

if (y.parent === z) {
x.parent = y;
x!.parent = y;
} else {
this._rbTransplant(y, y.right);
this._rbTransplant(y, y.right!);
y.right = z.right;
y.right.parent = y;
y.right!.parent = y;
}

@@ -160,7 +176,7 @@

y.left = z.left;
y.left.parent = y;
y.left!.parent = y;
y.color = z.color;
}
if (yOriginalColor === RBTNColor.BLACK) {
this._fixDelete(x);
this._fixDelete(x!);
}

@@ -170,32 +186,55 @@ this._size--;

helper(this.root);
// TODO
return ans;
}
isRealNode(node: RBTreeNode | null | undefined): node is RBTreeNode {
return node !== NIL && node !== null;
isNode(node: N | undefined): node is N {
return node !== this.NIL && node !== undefined;
}
getNode<C extends BTNCallback<N, BTNKey>>(
identifier: BTNKey,
callback?: C,
beginRoot?: N | undefined,
iterationType?: IterationType
): N | undefined;
getNode<C extends BTNCallback<N, N>>(
identifier: N | undefined,
callback?: C,
beginRoot?: N | undefined,
iterationType?: IterationType
): N | undefined;
getNode<C extends BTNCallback<N>>(
identifier: ReturnType<C>,
callback: C,
beginRoot?: N | undefined,
iterationType?: IterationType
): N | undefined;
/**
* The function `getNode` is a recursive depth-first search algorithm that searches for a node with a
* given key in a red-black tree.
* @param {number} key - The key parameter is a number that represents the value we are searching for
* in the RBTree.
* @param beginRoot - The `beginRoot` parameter is an optional parameter that represents the starting
* point for the search in the binary search tree. If no value is provided for `beginRoot`, it
* defaults to the root of the binary search tree (`this.root`).
* @returns a RBTreeNode.
* The function `get` returns the first node in a binary tree that matches the given property or key.
* @param {BTNKey | N} identifier - The `identifier` parameter is the key or value of
* the node that you want to find in the binary tree. It can be either a `BTNKey` or `N`
* type.
* @param callback - The `callback` parameter is a function that is used to determine whether a node
* matches the desired criteria. It takes a node as input and returns a boolean value indicating
* whether the node matches the criteria or not. The default callback function
* (`this.defaultOneParamCallback`) is used if no callback function is
* @param beginRoot - The `beginRoot` parameter is the starting point for the search. It specifies
* the root node from which the search should begin.
* @param iterationType - The `iterationType` parameter specifies the type of iteration to be
* performed when searching for a node in the binary tree. It can have one of the following values:
* @returns either the found node (of type N) or null if no node is found.
*/
getNode(key: number, beginRoot = this.root): RBTreeNode {
const dfs = (node: RBTreeNode): RBTreeNode => {
if (this.isRealNode(node)) {
if (key === node.key) {
return node;
}
getNode<C extends BTNCallback<N>>(
identifier: ReturnType<C> | undefined,
callback: C = this.defaultOneParamCallback as C,
beginRoot = this.root,
iterationType = this.iterationType
): N | null | undefined {
if ((identifier as any) instanceof BinaryTreeNode) callback = (node => node) as C;
if (key < node.key) return dfs(node.left);
return dfs(node.right);
} else {
return null as unknown as RBTreeNode;
}
};
return dfs(beginRoot);
return this.getNodes(identifier, callback, true, beginRoot, iterationType)[0] ?? undefined;
}

@@ -209,4 +248,4 @@

*/
getLeftMost(node: RBTreeNode = this.root): RBTreeNode {
while (node.left !== null && node.left !== NIL) {
getLeftMost(node: N = this.root): N {
while (node.left !== undefined && node.left !== this.NIL) {
node = node.left;

@@ -222,4 +261,4 @@ }

*/
getRightMost(node: RBTreeNode): RBTreeNode {
while (node.right !== null && node.right !== NIL) {
getRightMost(node: N): N {
while (node.right !== undefined && node.right !== this.NIL) {
node = node.right;

@@ -235,9 +274,9 @@ }

*/
getSuccessor(x: RBTreeNode): RBTreeNode {
if (x.right !== NIL) {
getSuccessor(x: N): N | undefined {
if (x.right !== this.NIL) {
return this.getLeftMost(x.right);
}
let y: RBTreeNode = x.parent;
while (y !== NIL && y !== null && x === y.right) {
let y: N | undefined = x.parent;
while (y !== this.NIL && y !== undefined && x === y.right) {
x = y;

@@ -255,78 +294,26 @@ y = y.parent;

*/
getPredecessor(x: RBTreeNode): RBTreeNode {
if (x.left !== NIL) {
return this.getRightMost(x.left);
getPredecessor(x: N): N {
if (x.left !== this.NIL) {
return this.getRightMost(x.left!);
}
let y: RBTreeNode = x.parent;
while (y !== NIL && x === y.left) {
x = y;
y = y.parent;
let y: N | undefined = x.parent;
while (y !== this.NIL && x === y!.left) {
x = y!;
y = y!.parent;
}
return y;
return y!;
}
clear() {
this._root = NIL;
override clear() {
this._root = this.NIL;
this._size = 0;
}
print(beginRoot: RBTreeNode = this.root) {
const display = (root: RBTreeNode | null): void => {
const [lines, , ,] = _displayAux(root);
for (const line of lines) {
console.log(line);
}
};
const _displayAux = (node: RBTreeNode | null): [string[], number, number, number] => {
if (node === null) {
return [[], 0, 0, 0];
}
if (node.right === null && node.left === null) {
const line = `${node.key}`;
const width = line.length;
const height = 1;
const middle = Math.floor(width / 2);
return [[line], width, height, middle];
}
if (node.right === null) {
const [lines, n, p, x] = _displayAux(node.left);
const s = `${node.key}`;
const u = s.length;
const first_line = ' '.repeat(x + 1) + '_'.repeat(n - x - 1) + s;
const second_line = ' '.repeat(x) + '/' + ' '.repeat(n - x - 1 + u);
const shifted_lines = lines.map(line => line + ' '.repeat(u));
return [[first_line, second_line, ...shifted_lines], n + u, p + 2, n + Math.floor(u / 2)];
}
if (node.left === null) {
const [lines, n, p, u] = _displayAux(node.right);
const s = `${node.key}`;
const x = s.length;
const first_line = s + '_'.repeat(x) + ' '.repeat(n - x);
const second_line = ' '.repeat(u + x) + '\\' + ' '.repeat(n - x - 1);
const shifted_lines = lines.map(line => ' '.repeat(u) + line);
return [[first_line, second_line, ...shifted_lines], n + x, p + 2, Math.floor(u / 2)];
}
const [left, n, p, x] = _displayAux(node.left);
const [right, m, q, y] = _displayAux(node.right);
const s = `${node.key}`;
const u = s.length;
const first_line = ' '.repeat(x + 1) + '_'.repeat(n - x - 1) + s + '_'.repeat(y) + ' '.repeat(m - y);
const second_line = ' '.repeat(x) + '/' + ' '.repeat(n - x - 1 + u + y) + '\\' + ' '.repeat(m - y - 1);
if (p < q) {
left.push(...new Array(q - p).fill(' '.repeat(n)));
} else if (q < p) {
right.push(...new Array(p - q).fill(' '.repeat(m)));
}
const zipped_lines = left.map((a, i) => a + ' '.repeat(u) + right[i]);
return [[first_line, second_line, ...zipped_lines], n + m + u, Math.max(p, q) + 2, n + Math.floor(u / 2)];
};
display(beginRoot);
protected override _setRoot(v: N) {
if (v) {
v.parent = undefined;
}
this._root = v;
}

@@ -338,18 +325,20 @@

*/
protected _leftRotate(x: RBTreeNode): void {
const y: RBTreeNode = x.right;
x.right = y.left;
if (y.left !== NIL) {
y.left.parent = x;
protected _leftRotate(x: N): void {
if (x.right) {
const y: N = x.right;
x.right = y.left;
if (y.left !== this.NIL) {
if (y.left) y.left.parent = x;
}
y.parent = x.parent;
if (x.parent === undefined) {
this._setRoot(y);
} else if (x === x.parent.left) {
x.parent.left = y;
} else {
x.parent.right = y;
}
y.left = x;
x.parent = y;
}
y.parent = x.parent;
if (x.parent === null) {
this._root = y;
} else if (x === x.parent.left) {
x.parent.left = y;
} else {
x.parent.right = y;
}
y.left = x;
x.parent = y;
}

@@ -362,18 +351,20 @@

*/
protected _rightRotate(x: RBTreeNode): void {
const y: RBTreeNode = x.left;
x.left = y.right;
if (y.right !== NIL) {
y.right.parent = x;
protected _rightRotate(x: N): void {
if (x.left) {
const y: N = x.left;
x.left = y.right;
if (y.right !== this.NIL) {
if (y.right) y.right.parent = x;
}
y.parent = x.parent;
if (x.parent === undefined) {
this._setRoot(y);
} else if (x === x.parent.right) {
x.parent.right = y;
} else {
x.parent.left = y;
}
y.right = x;
x.parent = y;
}
y.parent = x.parent;
if (x.parent === null) {
this._root = y;
} else if (x === x.parent.right) {
x.parent.right = y;
} else {
x.parent.left = y;
}
y.right = x;
x.parent = y;
}

@@ -386,7 +377,7 @@

*/
protected _fixDelete(x: RBTreeNode): void {
let s: RBTreeNode;
protected _fixDelete(x: N): void {
let s: N | undefined;
while (x !== this.root && x.color === RBTNColor.BLACK) {
if (x === x.parent.left) {
s = x.parent.right;
if (x.parent && x === x.parent.left) {
s = x.parent.right!;
if (s.color === 1) {

@@ -396,11 +387,11 @@ s.color = RBTNColor.BLACK;

this._leftRotate(x.parent);
s = x.parent.right;
s = x.parent.right!;
}
if (s.left !== null && s.left.color === RBTNColor.BLACK && s.right.color === RBTNColor.BLACK) {
if (s.left !== undefined && s.left.color === RBTNColor.BLACK && s.right && s.right.color === RBTNColor.BLACK) {
s.color = RBTNColor.RED;
x = x.parent;
} else {
if (s.right.color === RBTNColor.BLACK) {
s.left.color = RBTNColor.BLACK;
if (s.right && s.right.color === RBTNColor.BLACK) {
if (s.left) s.left.color = RBTNColor.BLACK;
s.color = RBTNColor.RED;

@@ -411,5 +402,5 @@ this._rightRotate(s);

s.color = x.parent.color;
if (s) s.color = x.parent.color;
x.parent.color = RBTNColor.BLACK;
s.right.color = RBTNColor.BLACK;
if (s && s.right) s.right.color = RBTNColor.BLACK;
this._leftRotate(x.parent);

@@ -419,25 +410,25 @@ x = this.root;

} else {
s = x.parent.left;
s = x.parent!.left!;
if (s.color === 1) {
s.color = RBTNColor.BLACK;
x.parent.color = RBTNColor.RED;
this._rightRotate(x.parent);
s = x.parent.left;
x.parent!.color = RBTNColor.RED;
this._rightRotate(x.parent!);
s = x.parent!.left;
}
if (s.right.color === RBTNColor.BLACK && s.right.color === RBTNColor.BLACK) {
if (s && s.right && s.right.color === RBTNColor.BLACK && s.right.color === RBTNColor.BLACK) {
s.color = RBTNColor.RED;
x = x.parent;
x = x.parent!;
} else {
if (s.left.color === RBTNColor.BLACK) {
s.right.color = RBTNColor.BLACK;
if (s && s.left && s.left.color === RBTNColor.BLACK) {
if (s.right) s.right.color = RBTNColor.BLACK;
s.color = RBTNColor.RED;
this._leftRotate(s);
s = x.parent.left;
s = x.parent!.left;
}
s.color = x.parent.color;
x.parent.color = RBTNColor.BLACK;
s.left.color = RBTNColor.BLACK;
this._rightRotate(x.parent);
if (s) s.color = x.parent!.color;
x.parent!.color = RBTNColor.BLACK;
if (s && s.left) s.left.color = RBTNColor.BLACK;
this._rightRotate(x.parent!);
x = this.root;

@@ -455,5 +446,5 @@ }

*/
protected _rbTransplant(u: RBTreeNode, v: RBTreeNode): void {
if (u.parent === null) {
this._root = v;
protected _rbTransplant(u: N, v: N): void {
if (u.parent === undefined) {
this._setRoot(v);
} else if (u === u.parent.left) {

@@ -472,8 +463,8 @@ u.parent.left = v;

*/
protected _fixInsert(k: RBTreeNode): void {
let u: RBTreeNode;
while (k.parent.color === 1) {
if (k.parent === k.parent.parent.right) {
protected _fixInsert(k: N): void {
let u: N | undefined;
while (k.parent && k.parent.color === 1) {
if (k.parent.parent && k.parent === k.parent.parent.right) {
u = k.parent.parent.left;
if (u.color === 1) {
if (u && u.color === 1) {
u.color = RBTNColor.BLACK;

@@ -489,14 +480,14 @@ k.parent.color = RBTNColor.BLACK;

k.parent.color = RBTNColor.BLACK;
k.parent.parent.color = RBTNColor.RED;
this._leftRotate(k.parent.parent);
k.parent!.color = RBTNColor.BLACK;
k.parent!.parent!.color = RBTNColor.RED;
this._leftRotate(k.parent!.parent!);
}
} else {
u = k.parent.parent.right;
u = k.parent.parent!.right;
if (u.color === 1) {
if (u && u.color === 1) {
u.color = RBTNColor.BLACK;
k.parent.color = RBTNColor.BLACK;
k.parent.parent.color = RBTNColor.RED;
k = k.parent.parent;
k.parent.parent!.color = RBTNColor.RED;
k = k.parent.parent!;
} else {

@@ -508,5 +499,5 @@ if (k === k.parent.right) {

k.parent.color = RBTNColor.BLACK;
k.parent.parent.color = RBTNColor.RED;
this._rightRotate(k.parent.parent);
k.parent!.color = RBTNColor.BLACK;
k.parent!.parent!.color = RBTNColor.RED;
this._rightRotate(k.parent!.parent!);
}

@@ -513,0 +504,0 @@ }

47

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

@@ -74,5 +74,5 @@ /**

* exists, and balancing the tree if necessary.
* @param {BTNKey | N | null} keyOrNode - The `keyOrNode` parameter can be either a
* @param {BTNKey | N | undefined} keyOrNode - The `keyOrNode` parameter can be either a
* `BTNKey` (which represents the key of the node to be added), a `N` (which represents a
* node to be added), or `null` (which represents a null node).
* node to be added), or `undefined` (which represents a undefined node).
* @param [value] - The `value` parameter represents the value associated with the key that is being

@@ -83,11 +83,12 @@ * added to the binary tree.

* count is specified, the default count will be 1.
* @returns The function `add` returns a value of type `N | null | undefined`.
* @returns The function `add` returns a value of type `N | undefined | undefined`.
*/
override add(keyOrNode: BTNKey | N | null, value?: V, count = 1): N | null | undefined {
let inserted: N | null | undefined = undefined,
newNode: N | null;
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 TreeMultisetNode) {
newNode = this.createNode(keyOrNode.key, keyOrNode.value, keyOrNode.count);
} else if (keyOrNode === null) {
newNode = null;
} else if (keyOrNode === undefined) {
newNode = undefined;
} else {

@@ -143,3 +144,3 @@ newNode = this.createNode(keyOrNode, value, count);

} else {
// TODO may need to support null inserted
// TODO may need to support undefined inserted
}

@@ -157,4 +158,4 @@ } else {

* The function adds a new node to a binary tree if there is an available slot in the parent node.
* @param {N | null} newNode - The `newNode` parameter represents the node that needs to be added to
* the tree. It can be either a node object (`N`) or `null`.
* @param {N | undefined} newNode - The `newNode` parameter represents the node that needs to be added to
* the tree. It can be either a node object (`N`) or `undefined`.
* @param {N} parent - The `parent` parameter represents the parent node to which the new node will

@@ -164,7 +165,7 @@ * be added as a child.

*/
override _addTo(newNode: N | null, parent: N): N | null | undefined {
override _addTo(newNode: N | undefined, parent: N): N | undefined {
if (parent) {
if (parent.left === undefined) {
parent.left = newNode;
if (newNode !== null) {
if (newNode !== undefined) {
this._size = this.size + 1;

@@ -177,3 +178,3 @@ this._setCount(this.count + newNode.count);

parent.right = newNode;
if (newNode !== null) {
if (newNode !== undefined) {
this._size = this.size + 1;

@@ -194,3 +195,3 @@ this._setCount(this.count + newNode.count);

* inserted nodes.
* @param {(BTNKey | null)[] | (N | null)[]} keysOrNodes - An array of keys or nodes to be
* @param {(BTNKey | undefined)[] | (N | undefined)[]} keysOrNodes - An array of keys or nodes to be
* added to the multiset. Each element can be either a BTNKey or a TreeMultisetNode.

@@ -200,6 +201,6 @@ * @param {V[]} [data] - The `data` parameter is an optional array of values that correspond

* each key or node.
* @returns The function `addMany` returns an array of `N`, `null`, or `undefined` values.
* @returns The function `addMany` returns an array of `N`, `undefined`, or `undefined` values.
*/
override addMany(keysOrNodes: (BTNKey | null)[] | (N | null)[], data?: V[]): (N | null | undefined)[] {
const inserted: (N | null | undefined)[] = [];
override addMany(keysOrNodes: (BTNKey | undefined)[] | (N | undefined)[], data?: V[]): (N | undefined)[] {
const inserted: (N | undefined | undefined)[] = [];

@@ -214,3 +215,3 @@ for (let i = 0; i < keysOrNodes.length; i++) {

if (keyOrNode === null) {
if (keyOrNode === undefined) {
inserted.push(this.add(NaN, undefined, 0));

@@ -295,7 +296,7 @@ continue;

const curr: N | null = this.getNode(identifier, callback);
const curr: N | undefined = this.getNode(identifier, callback) ?? undefined;
if (!curr) return bstDeletedResult;
const parent: N | null = curr?.parent ? curr.parent : null;
let needBalanced: N | null = null,
const parent: N | undefined = curr?.parent ? curr.parent : undefined;
let needBalanced: N | undefined = undefined,
orgCurrent = curr;

@@ -320,3 +321,3 @@

} else {
const leftSubTreeRightMost = curr.left ? this.getRightMost(curr.left) : null;
const leftSubTreeRightMost = curr.left ? this.getRightMost(curr.left) : undefined;
if (leftSubTreeRightMost) {

@@ -323,0 +324,0 @@ const parentOfLeftSubTreeMax = leftSubTreeRightMost.parent;

2

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

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

export type BinaryTreeDeletedResult<N> = { deleted: N | null | undefined; needBalanced: N | null };
export type BinaryTreeDeletedResult<N> = { deleted: N | null | undefined; needBalanced: N | null | undefined };

@@ -30,0 +30,0 @@ export type BinaryTreeNodeNested<T> = BinaryTreeNode<T, BinaryTreeNode<T, BinaryTreeNode<T, BinaryTreeNode<T, BinaryTreeNode<T, BinaryTreeNode<T, BinaryTreeNode<T, BinaryTreeNode<T, BinaryTreeNode<T, BinaryTreeNode<T, BinaryTreeNode<T, BinaryTreeNode<T, BinaryTreeNode<T, BinaryTreeNode<T, BinaryTreeNode<T, BinaryTreeNode<T, BinaryTreeNode<T, BinaryTreeNode<T, BinaryTreeNode<T, BinaryTreeNode<T, BinaryTreeNode<T, BinaryTreeNode<T, BinaryTreeNode<T, BinaryTreeNode<T, BinaryTreeNode<T, BinaryTreeNode<T, BinaryTreeNode<T, BinaryTreeNode<T, BinaryTreeNode<T, BinaryTreeNode<T, BinaryTreeNode<T, BinaryTreeNode<T, BinaryTreeNode<T, BinaryTreeNode<T, BinaryTreeNode<T, BinaryTreeNode<T, BinaryTreeNode<T, BinaryTreeNode<T, BinaryTreeNode<T, BinaryTreeNode<T, BinaryTreeNode<T, BinaryTreeNode<T, BinaryTreeNode<T, BinaryTreeNode<T, BinaryTreeNode<T, BinaryTreeNode<T, BinaryTreeNode<T, BinaryTreeNode<T, BinaryTreeNode<T, BinaryTreeNode<T, any>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>

10

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

@@ -1,8 +0,8 @@

// import {BinaryTreeOptions} from './binary-tree';
// import {RBTreeNode} from '../../../data-structures';
import {RBTreeNode} from '../../../data-structures';
import {BSTOptions} from "./bst";
export enum RBTNColor { RED = 1, BLACK = 0}
// export type RBTreeNodeNested<T> = RBTreeNode<T, RBTreeNode<T, RBTreeNode<T, RBTreeNode<T, RBTreeNode<T, RBTreeNode<T, RBTreeNode<T, RBTreeNode<T, RBTreeNode<T, RBTreeNode<T, RBTreeNode<T, RBTreeNode<T, RBTreeNode<T, RBTreeNode<T, RBTreeNode<T, RBTreeNode<T, RBTreeNode<T, RBTreeNode<T, RBTreeNode<T, RBTreeNode<T, RBTreeNode<T, RBTreeNode<T, RBTreeNode<T, RBTreeNode<T, RBTreeNode<T, RBTreeNode<T, RBTreeNode<T, RBTreeNode<T, RBTreeNode<T, RBTreeNode<T, RBTreeNode<T, RBTreeNode<T, RBTreeNode<T, RBTreeNode<T, RBTreeNode<T, RBTreeNode<T, RBTreeNode<T, RBTreeNode<T, RBTreeNode<T, RBTreeNode<T, RBTreeNode<T, RBTreeNode<T, RBTreeNode<T, RBTreeNode<T, RBTreeNode<T, RBTreeNode<T, RBTreeNode<T, RBTreeNode<T, RBTreeNode<T, RBTreeNode<T, any>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>
//
// export type RBTreeOptions = BinaryTreeOptions & {}
export type RBTreeNodeNested<T> = RBTreeNode<T, RBTreeNode<T, RBTreeNode<T, RBTreeNode<T, RBTreeNode<T, RBTreeNode<T, RBTreeNode<T, RBTreeNode<T, RBTreeNode<T, RBTreeNode<T, RBTreeNode<T, RBTreeNode<T, RBTreeNode<T, RBTreeNode<T, RBTreeNode<T, RBTreeNode<T, RBTreeNode<T, RBTreeNode<T, RBTreeNode<T, RBTreeNode<T, RBTreeNode<T, RBTreeNode<T, RBTreeNode<T, RBTreeNode<T, RBTreeNode<T, RBTreeNode<T, RBTreeNode<T, RBTreeNode<T, RBTreeNode<T, RBTreeNode<T, RBTreeNode<T, RBTreeNode<T, RBTreeNode<T, RBTreeNode<T, RBTreeNode<T, RBTreeNode<T, RBTreeNode<T, RBTreeNode<T, RBTreeNode<T, RBTreeNode<T, RBTreeNode<T, RBTreeNode<T, RBTreeNode<T, RBTreeNode<T, RBTreeNode<T, RBTreeNode<T, RBTreeNode<T, RBTreeNode<T, RBTreeNode<T, RBTreeNode<T, any>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>
export type RBTreeOptions = BSTOptions & {};
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