Huge News!Announcing our $40M Series B led by Abstract Ventures.Learn More →
Socket
Sign inDemoInstall
Socket
Sign inDemoInstall

red-black-tree-typed

Package Overview
Dependencies
Maintainers
1
Versions
62
Alerts
File Explorer

Advanced tools

License
Socket logo

Install Socket

Detect and block malicious and high-risk dependencies

Install

red-black-tree-typed - npm Package Compare versions

Comparing version 1.50.8 to 1.50.9

18

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

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

*/
import type { AVLTreeMultiMapNested, AVLTreeMultiMapNodeNested, AVLTreeMultiMapOptions, BinaryTreeDeleteResult, BSTNKeyOrNode, BTNCallback, KeyOrNodeOrEntry } from '../../types';
import type { AVLTreeMultiMapNested, AVLTreeMultiMapNodeNested, AVLTreeMultiMapOptions, BinaryTreeDeleteResult, BSTNKeyOrNode, BTNCallback, IterationType, KeyOrNodeOrEntry } from '../../types';
import { IBinaryTree } from '../../interfaces';

@@ -49,4 +49,16 @@ import { AVLTree, AVLTreeNode } from './avl-tree';

get count(): number;
getMutableCount(): number;
/**
* Time Complexity: O(n)
* Space Complexity: O(1)
*/
/**
* Time Complexity: O(n)
* Space Complexity: O(1)
*
* The function calculates the sum of the count property of all nodes in a tree using depth-first
* search.
* @returns the sum of the count property of all nodes in the tree.
*/
getComputedCount(): number;
/**
* The function creates a new BSTNode with the given key, value, and count.

@@ -161,3 +173,3 @@ * @param {K} key - The key parameter is the unique identifier for the binary tree node. It is used to

*/
perfectlyBalance(iterationType?: import("../../types").IterationType): boolean;
perfectlyBalance(iterationType?: IterationType): boolean;
/**

@@ -164,0 +176,0 @@ * Time complexity: O(n)

16

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

@@ -57,3 +57,15 @@ "use strict";

}
getMutableCount() {
/**
* Time Complexity: O(n)
* Space Complexity: O(1)
*/
/**
* Time Complexity: O(n)
* Space Complexity: O(1)
*
* The function calculates the sum of the count property of all nodes in a tree using depth-first
* search.
* @returns the sum of the count property of all nodes in the tree.
*/
getComputedCount() {
let sum = 0;

@@ -274,3 +286,3 @@ this.dfs(node => (sum += node.count));

perfectlyBalance(iterationType = this.iterationType) {
const sorted = this.dfs(node => node, 'in'), n = sorted.length;
const sorted = this.dfs(node => node, 'IN'), n = sorted.length;
if (sorted.length < 1)

@@ -277,0 +289,0 @@ return false;

4

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

@@ -142,3 +142,3 @@ /**

*/
ensureNode(keyOrNodeOrEntry: KeyOrNodeOrEntry<K, V, NODE>, iterationType?: string): NODE | null | undefined;
ensureNode(keyOrNodeOrEntry: KeyOrNodeOrEntry<K, V, NODE>, iterationType?: IterationType): NODE | null | undefined;
/**

@@ -252,3 +252,3 @@ * The function "isNode" checks if an keyOrNodeOrEntry is an instance of the BinaryTreeNode class.

*/
getNodeByKey(key: K, iterationType?: string): NODE | undefined;
getNodeByKey(key: K, iterationType?: IterationType): NODE | undefined;
get<C extends BTNCallback<NODE, K>>(identifier: K, callback?: C, beginRoot?: KeyOrNodeOrEntry<K, V, NODE>, iterationType?: IterationType): V | undefined;

@@ -255,0 +255,0 @@ get<C extends BTNCallback<NODE, NODE>>(identifier: NODE | null | undefined, callback?: C, beginRoot?: KeyOrNodeOrEntry<K, V, NODE>, iterationType?: IterationType): V | undefined;

21

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

@@ -115,3 +115,3 @@ /**

*/
ensureNode(keyOrNodeOrEntry: KeyOrNodeOrEntry<K, V, NODE>, iterationType?: string): NODE | undefined;
ensureNode(keyOrNodeOrEntry: KeyOrNodeOrEntry<K, V, NODE>, iterationType?: IterationType): NODE | undefined;
/**

@@ -183,3 +183,3 @@ * The function checks if an keyOrNodeOrEntry is an instance of BSTNode.

*/
getNodeByKey(key: K, iterationType?: string): NODE | undefined;
getNodeByKey(key: K, iterationType?: IterationType): NODE | undefined;
/**

@@ -381,4 +381,21 @@ * Time Complexity: O(log n)

protected _compare(a: K, b: K): CP;
/**
* The function `_lt` compares two values `a` and `b` using an extractor function and returns true if
* `a` is less than `b` based on the specified variant.
* @param {K} a - The parameter "a" is of type "K", which means it can be any type. It represents the
* first value to be compared in the function.
* @param {K} b - The parameter `b` is of type `K`, which means it can be any type. It is used as one
* of the arguments for the comparison in the `_lt` function.
* @returns a boolean value.
*/
protected _lt(a: K, b: K): boolean;
/**
* The function compares two values using a custom extractor function and returns true if the first
* value is greater than the second value.
* @param {K} a - The parameter "a" is of type K, which means it can be any type.
* @param {K} b - The parameter "b" is of type K, which means it can be any type. It is used as one
* of the arguments for the comparison in the function.
* @returns a boolean value.
*/
protected _gt(a: K, b: K): boolean;
}

22

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

@@ -364,2 +364,3 @@ "use strict";

getNodeByKey(key, iterationType = 'ITERATIVE') {
// return this.getNodes(key, this._defaultOneParamCallback, true, this.root, iterationType)[0];
if (!this.isRealNode(this.root))

@@ -508,3 +509,3 @@ return undefined;

*/
dfs(callback = this._defaultOneParamCallback, pattern = 'in', beginRoot = this.root, iterationType = 'ITERATIVE') {
dfs(callback = this._defaultOneParamCallback, pattern = 'IN', beginRoot = this.root, iterationType = 'ITERATIVE') {
return super.dfs(callback, pattern, beginRoot, iterationType, false);

@@ -675,3 +676,3 @@ }

perfectlyBalance(iterationType = this.iterationType) {
const sorted = this.dfs(node => node, 'in'), n = sorted.length;
const sorted = this.dfs(node => node, 'IN'), n = sorted.length;
this.clear();

@@ -804,2 +805,11 @@ if (sorted.length < 1)

}
/**
* The function `_lt` compares two values `a` and `b` using an extractor function and returns true if
* `a` is less than `b` based on the specified variant.
* @param {K} a - The parameter "a" is of type "K", which means it can be any type. It represents the
* first value to be compared in the function.
* @param {K} b - The parameter `b` is of type `K`, which means it can be any type. It is used as one
* of the arguments for the comparison in the `_lt` function.
* @returns a boolean value.
*/
_lt(a, b) {

@@ -813,2 +823,10 @@ const extractedA = this.extractor(a);

}
/**
* The function compares two values using a custom extractor function and returns true if the first
* value is greater than the second value.
* @param {K} a - The parameter "a" is of type K, which means it can be any type.
* @param {K} b - The parameter "b" is of type K, which means it can be any type. It is used as one
* of the arguments for the comparison in the function.
* @returns a boolean value.
*/
_gt(a, b) {

@@ -815,0 +833,0 @@ const extractedA = this.extractor(a);

10

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

@@ -1,2 +0,2 @@

import type { BinaryTreeDeleteResult, BSTNKeyOrNode, BTNCallback, KeyOrNodeOrEntry, RBTreeOptions, RedBlackTreeNested, RedBlackTreeNodeNested } from '../../types';
import type { BinaryTreeDeleteResult, BSTNKeyOrNode, BTNCallback, IterationType, KeyOrNodeOrEntry, RBTreeOptions, RedBlackTreeNested, RedBlackTreeNodeNested } from '../../types';
import { CRUD, RBTNColor } from '../../types';

@@ -15,3 +15,3 @@ import { BST, BSTNode } from './bst';

* @param {RBTNColor} color - The `color` parameter is used to specify the color of the Red-Black
* Tree Node. It is an optional parameter with a default value of `RBTNColor.BLACK`.
* Tree Node. It is an optional parameter with a default value of `'BLACK'`.
*/

@@ -62,4 +62,4 @@ constructor(key: K, value?: V, color?: RBTNColor);

* @param {RBTNColor} color - The "color" parameter is used to specify the color of the node in a
* Red-Black Tree. It is an optional parameter with a default value of "RBTNColor.BLACK". The color
* can be either "RBTNColor.RED" or "RBTNColor.BLACK".
* Red-Black Tree. It is an optional parameter with a default value of "'BLACK'". The color
* can be either "'RED'" or "'BLACK'".
* @returns The method is returning a new instance of a RedBlackTreeNode with the specified key,

@@ -145,3 +145,3 @@ * value, and color.

*/
getNode<C extends BTNCallback<NODE>>(identifier: ReturnType<C> | undefined, callback?: C, beginRoot?: BSTNKeyOrNode<K, NODE>, iterationType?: import("../../types").IterationType): NODE | null | undefined;
getNode<C extends BTNCallback<NODE>>(identifier: ReturnType<C> | undefined, callback?: C, beginRoot?: BSTNKeyOrNode<K, NODE>, iterationType?: IterationType): NODE | null | undefined;
/**

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

86

dist/data-structures/binary-tree/rb-tree.js
"use strict";
Object.defineProperty(exports, "__esModule", { value: true });
exports.RedBlackTree = exports.RedBlackTreeNode = void 0;
const types_1 = require("../../types");
const bst_1 = require("./bst");

@@ -16,5 +15,5 @@ class RedBlackTreeNode extends bst_1.BSTNode {

* @param {RBTNColor} color - The `color` parameter is used to specify the color of the Red-Black
* Tree Node. It is an optional parameter with a default value of `RBTNColor.BLACK`.
* Tree Node. It is an optional parameter with a default value of `'BLACK'`.
*/
constructor(key, value, color = types_1.RBTNColor.BLACK) {
constructor(key, value, color = 'BLACK') {
super(key, value);

@@ -79,8 +78,8 @@ this._color = color;

* @param {RBTNColor} color - The "color" parameter is used to specify the color of the node in a
* Red-Black Tree. It is an optional parameter with a default value of "RBTNColor.BLACK". The color
* can be either "RBTNColor.RED" or "RBTNColor.BLACK".
* Red-Black Tree. It is an optional parameter with a default value of "'BLACK'". The color
* can be either "'RED'" or "'BLACK'".
* @returns The method is returning a new instance of a RedBlackTreeNode with the specified key,
* value, and color.
*/
createNode(key, value, color = types_1.RBTNColor.BLACK) {
createNode(key, value, color = 'BLACK') {
return new RedBlackTreeNode(key, value, color);

@@ -126,7 +125,7 @@ }

else {
node = this.createNode(key, value, types_1.RBTNColor.RED);
node = this.createNode(key, value, 'RED');
}
}
else if (!this.isNode(keyOrNodeOrEntry)) {
node = this.createNode(keyOrNodeOrEntry, value, types_1.RBTNColor.RED);
node = this.createNode(keyOrNodeOrEntry, value, 'RED');
}

@@ -199,3 +198,2 @@ else {

var _a;
// if ((identifier as any) instanceof RedBlackTreeNode) callback = (node => node) as C;
return (_a = this.getNodes(identifier, callback, true, beginRoot, iterationType)[0]) !== null && _a !== void 0 ? _a : undefined;

@@ -243,3 +241,3 @@ }

if (this.isRealNode(this._root)) {
this._root.color = types_1.RBTNColor.BLACK;
this._root.color = 'BLACK';
}

@@ -320,3 +318,3 @@ else {

// If the original color was black, fix the tree
if (originalColor === types_1.RBTNColor.BLACK) {
if (originalColor === 'BLACK') {
this._deleteFixup(replacementNode);

@@ -402,3 +400,3 @@ }

node.right = this.SENTINEL;
node.color = types_1.RBTNColor.RED;
node.color = 'RED';
this._insertFixup(node);

@@ -449,3 +447,3 @@ return 'CREATED';

// Continue fixing the tree as long as the parent of z is red
while (((_a = z === null || z === void 0 ? void 0 : z.parent) === null || _a === void 0 ? void 0 : _a.color) === types_1.RBTNColor.RED) {
while (((_a = z === null || z === void 0 ? void 0 : z.parent) === null || _a === void 0 ? void 0 : _a.color) === 'RED') {
// Check if the parent of z is the left child of its parent

@@ -455,7 +453,7 @@ if (z.parent === ((_b = z.parent.parent) === null || _b === void 0 ? void 0 : _b.left)) {

const y = z.parent.parent.right;
if ((y === null || y === void 0 ? void 0 : y.color) === types_1.RBTNColor.RED) {
if ((y === null || y === void 0 ? void 0 : y.color) === 'RED') {
// Set colors to restore properties of Red-Black Tree
z.parent.color = types_1.RBTNColor.BLACK;
y.color = types_1.RBTNColor.BLACK;
z.parent.parent.color = types_1.RBTNColor.RED;
z.parent.color = 'BLACK';
y.color = 'BLACK';
z.parent.parent.color = 'RED';
// Move up the tree to continue fixing

@@ -474,4 +472,4 @@ z = z.parent.parent;

if (z && this.isRealNode(z.parent) && this.isRealNode(z.parent.parent)) {
z.parent.color = types_1.RBTNColor.BLACK;
z.parent.parent.color = types_1.RBTNColor.RED;
z.parent.color = 'BLACK';
z.parent.parent.color = 'RED';
this._rightRotate(z.parent.parent);

@@ -485,6 +483,6 @@ }

const y = (_d = (_c = z === null || z === void 0 ? void 0 : z.parent) === null || _c === void 0 ? void 0 : _c.parent) === null || _d === void 0 ? void 0 : _d.left;
if ((y === null || y === void 0 ? void 0 : y.color) === types_1.RBTNColor.RED) {
z.parent.color = types_1.RBTNColor.BLACK;
y.color = types_1.RBTNColor.BLACK;
z.parent.parent.color = types_1.RBTNColor.RED;
if ((y === null || y === void 0 ? void 0 : y.color) === 'RED') {
z.parent.color = 'BLACK';
y.color = 'BLACK';
z.parent.parent.color = 'RED';
z = z.parent.parent;

@@ -498,4 +496,4 @@ }

if (z && this.isRealNode(z.parent) && this.isRealNode(z.parent.parent)) {
z.parent.color = types_1.RBTNColor.BLACK;
z.parent.parent.color = types_1.RBTNColor.RED;
z.parent.color = 'BLACK';
z.parent.parent.color = 'RED';
this._leftRotate(z.parent.parent);

@@ -508,3 +506,3 @@ }

if (this.isRealNode(this._root))
this._root.color = types_1.RBTNColor.BLACK;
this._root.color = 'BLACK';
}

@@ -528,9 +526,9 @@ /**

// Early exit condition
if (!node || node === this.root || node.color === types_1.RBTNColor.BLACK) {
if (!node || node === this.root || node.color === 'BLACK') {
if (node) {
node.color = types_1.RBTNColor.BLACK; // Ensure the final node is black
node.color = 'BLACK'; // Ensure the final node is black
}
return;
}
while (node && node !== this.root && node.color === types_1.RBTNColor.BLACK) {
while (node && node !== this.root && node.color === 'BLACK') {
const parent = node.parent;

@@ -543,5 +541,5 @@ if (!parent) {

// Cases 1 and 2: Sibling is red or both children of sibling are black
if ((sibling === null || sibling === void 0 ? void 0 : sibling.color) === types_1.RBTNColor.RED) {
sibling.color = types_1.RBTNColor.BLACK;
parent.color = types_1.RBTNColor.RED;
if ((sibling === null || sibling === void 0 ? void 0 : sibling.color) === 'RED') {
sibling.color = 'BLACK';
parent.color = 'RED';
this._leftRotate(parent);

@@ -551,5 +549,5 @@ sibling = parent.right;

// Case 3: Sibling's left child is black
if (((_b = (_a = sibling === null || sibling === void 0 ? void 0 : sibling.left) === null || _a === void 0 ? void 0 : _a.color) !== null && _b !== void 0 ? _b : types_1.RBTNColor.BLACK) === types_1.RBTNColor.BLACK) {
if (((_b = (_a = sibling === null || sibling === void 0 ? void 0 : sibling.left) === null || _a === void 0 ? void 0 : _a.color) !== null && _b !== void 0 ? _b : 'BLACK') === 'BLACK') {
if (sibling)
sibling.color = types_1.RBTNColor.RED;
sibling.color = 'RED';
node = parent;

@@ -560,6 +558,6 @@ }

if (sibling === null || sibling === void 0 ? void 0 : sibling.left)
sibling.left.color = types_1.RBTNColor.BLACK;
sibling.left.color = 'BLACK';
if (sibling)
sibling.color = parent.color;
parent.color = types_1.RBTNColor.BLACK;
parent.color = 'BLACK';
this._rightRotate(parent);

@@ -573,6 +571,6 @@ node = this.root;

// Cases 1 and 2: Sibling is red or both children of sibling are black
if ((sibling === null || sibling === void 0 ? void 0 : sibling.color) === types_1.RBTNColor.RED) {
sibling.color = types_1.RBTNColor.BLACK;
if ((sibling === null || sibling === void 0 ? void 0 : sibling.color) === 'RED') {
sibling.color = 'BLACK';
if (parent)
parent.color = types_1.RBTNColor.RED;
parent.color = 'RED';
this._rightRotate(parent);

@@ -583,5 +581,5 @@ if (parent)

// Case 3: Sibling's left child is black
if (((_d = (_c = sibling === null || sibling === void 0 ? void 0 : sibling.right) === null || _c === void 0 ? void 0 : _c.color) !== null && _d !== void 0 ? _d : types_1.RBTNColor.BLACK) === types_1.RBTNColor.BLACK) {
if (((_d = (_c = sibling === null || sibling === void 0 ? void 0 : sibling.right) === null || _c === void 0 ? void 0 : _c.color) !== null && _d !== void 0 ? _d : 'BLACK') === 'BLACK') {
if (sibling)
sibling.color = types_1.RBTNColor.RED;
sibling.color = 'RED';
node = parent;

@@ -592,7 +590,7 @@ }

if (sibling === null || sibling === void 0 ? void 0 : sibling.right)
sibling.right.color = types_1.RBTNColor.BLACK;
sibling.right.color = 'BLACK';
if (sibling)
sibling.color = parent.color;
if (parent)
parent.color = types_1.RBTNColor.BLACK;
parent.color = 'BLACK';
this._leftRotate(parent);

@@ -605,3 +603,3 @@ node = this.root;

if (node) {
node.color = types_1.RBTNColor.BLACK;
node.color = 'BLACK';
}

@@ -608,0 +606,0 @@ }

60

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

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

*/
import type { BinaryTreeDeleteResult, BSTNKeyOrNode, BTNCallback, KeyOrNodeOrEntry, TreeMultiMapNested, TreeMultiMapNodeNested, TreeMultiMapOptions } from '../../types';
import type { BinaryTreeDeleteResult, BSTNKeyOrNode, BTNCallback, IterationType, KeyOrNodeOrEntry, TreeMultiMapNested, TreeMultiMapNodeNested, TreeMultiMapOptions } from '../../types';
import { RBTNColor } from '../../types';
import { IBinaryTree } from '../../interfaces';

@@ -14,12 +15,14 @@ import { RedBlackTree, RedBlackTreeNode } from './rb-tree';

/**
* The constructor function initializes an instance of a class with a key, value, and count.
* @param {K} key - The key parameter is of type K, which represents the type of the key for the
* constructor. It is required and must be provided when creating an instance of the class.
* @param {V} [value] - The `value` parameter is an optional parameter of type `V`. It represents the
* value associated with the key in the constructor. If no value is provided, it will be `undefined`.
* @param [count=1] - The "count" parameter is an optional parameter that specifies the number of
* times the key-value pair should be repeated. If no value is provided for "count", it defaults to
* 1.
* The constructor function initializes a Red-Black Tree node with a key, value, count, and color.
* @param {K} key - The key parameter represents the key of the node in the Red-Black Tree. It is
* used to identify and locate the node within the tree.
* @param {V} [value] - The `value` parameter is an optional parameter that represents the value
* associated with the key in the Red-Black Tree node. It is not required and can be omitted when
* creating a new node.
* @param [count=1] - The `count` parameter represents the number of occurrences of a particular key
* in the Red-Black Tree. It is an optional parameter with a default value of 1.
* @param {RBTNColor} [color=BLACK] - The `color` parameter is used to specify the color of the node
* in a Red-Black Tree. It is optional and has a default value of `'BLACK'`.
*/
constructor(key: K, value?: V, count?: number);
constructor(key: K, value?: V, count?: number, color?: RBTNColor);
protected _count: number;

@@ -55,15 +58,30 @@ /**

get count(): number;
getMutableCount(): number;
/**
* The function creates a new TreeMultiMapNode object with the specified key, value, and count.
* Time Complexity: O(n)
* Space Complexity: O(1)
*/
/**
* Time Complexity: O(n)
* Space Complexity: O(1)
*
* The function calculates the sum of the count property of all nodes in a tree using depth-first
* search.
* @returns the sum of the count property of all nodes in the tree.
*/
getComputedCount(): number;
/**
* The function creates a new TreeMultiMapNode with the specified key, value, color, and count.
* @param {K} key - The key parameter represents the key of the node being created. It is of type K,
* which is a generic type that can be replaced with any specific type when using the function.
* @param {V} [value] - The `value` parameter is an optional parameter that represents the value
* associated with the key in the node. It is of type `V`, which can be any data type.
* @param {number} [count] - The `count` parameter represents the number of occurrences of a
* key-value pair in the TreeMultiMap. It is an optional parameter, so if it is not provided, it will
* default to 1.
* @returns a new instance of the TreeMultiMapNode class, casted as NODE.
* which is a generic type representing the key type of the node.
* @param {V} [value] - The `value` parameter represents the value associated with the key in the
* node. It is an optional parameter, which means it can be omitted when calling the `createNode`
* function. If provided, it should be of type `V`.
* @param {RBTNColor} [color=BLACK] - The color parameter is used to specify the color of the node in
* a Red-Black Tree. It can have two possible values: 'RED' or 'BLACK'. The default value is 'BLACK'.
* @param {number} [count] - The `count` parameter represents the number of occurrences of a key in
* the tree. It is an optional parameter and is used to keep track of the number of values associated
* with a key in the tree.
* @returns A new instance of the TreeMultiMapNode class is being returned.
*/
createNode(key: K, value?: V, count?: number): NODE;
createNode(key: K, value?: V, color?: RBTNColor, count?: number): NODE;
/**

@@ -169,3 +187,3 @@ * The function creates a new instance of a TreeMultiMap with the specified options and returns it.

*/
perfectlyBalance(iterationType?: import("../../types").IterationType): boolean;
perfectlyBalance(iterationType?: IterationType): boolean;
/**

@@ -172,0 +190,0 @@ * Time complexity: O(n)

70

dist/data-structures/binary-tree/tree-multi-map.js
"use strict";
Object.defineProperty(exports, "__esModule", { value: true });
exports.TreeMultiMap = exports.TreeMultiMapNode = void 0;
const types_1 = require("../../types");
const rb_tree_1 = require("./rb-tree");
class TreeMultiMapNode extends rb_tree_1.RedBlackTreeNode {
/**
* The constructor function initializes an instance of a class with a key, value, and count.
* @param {K} key - The key parameter is of type K, which represents the type of the key for the
* constructor. It is required and must be provided when creating an instance of the class.
* @param {V} [value] - The `value` parameter is an optional parameter of type `V`. It represents the
* value associated with the key in the constructor. If no value is provided, it will be `undefined`.
* @param [count=1] - The "count" parameter is an optional parameter that specifies the number of
* times the key-value pair should be repeated. If no value is provided for "count", it defaults to
* 1.
* The constructor function initializes a Red-Black Tree node with a key, value, count, and color.
* @param {K} key - The key parameter represents the key of the node in the Red-Black Tree. It is
* used to identify and locate the node within the tree.
* @param {V} [value] - The `value` parameter is an optional parameter that represents the value
* associated with the key in the Red-Black Tree node. It is not required and can be omitted when
* creating a new node.
* @param [count=1] - The `count` parameter represents the number of occurrences of a particular key
* in the Red-Black Tree. It is an optional parameter with a default value of 1.
* @param {RBTNColor} [color=BLACK] - The `color` parameter is used to specify the color of the node
* in a Red-Black Tree. It is optional and has a default value of `'BLACK'`.
*/
constructor(key, value, count = 1) {
super(key, value);
constructor(key, value, count = 1, color = 'BLACK') {
super(key, value, color);
this._count = 1;

@@ -63,3 +64,15 @@ this.count = count;

}
getMutableCount() {
/**
* Time Complexity: O(n)
* Space Complexity: O(1)
*/
/**
* Time Complexity: O(n)
* Space Complexity: O(1)
*
* The function calculates the sum of the count property of all nodes in a tree using depth-first
* search.
* @returns the sum of the count property of all nodes in the tree.
*/
getComputedCount() {
let sum = 0;

@@ -70,14 +83,17 @@ this.dfs(node => (sum += node.count));

/**
* The function creates a new TreeMultiMapNode object with the specified key, value, and count.
* The function creates a new TreeMultiMapNode with the specified key, value, color, and count.
* @param {K} key - The key parameter represents the key of the node being created. It is of type K,
* which is a generic type that can be replaced with any specific type when using the function.
* @param {V} [value] - The `value` parameter is an optional parameter that represents the value
* associated with the key in the node. It is of type `V`, which can be any data type.
* @param {number} [count] - The `count` parameter represents the number of occurrences of a
* key-value pair in the TreeMultiMap. It is an optional parameter, so if it is not provided, it will
* default to 1.
* @returns a new instance of the TreeMultiMapNode class, casted as NODE.
* which is a generic type representing the key type of the node.
* @param {V} [value] - The `value` parameter represents the value associated with the key in the
* node. It is an optional parameter, which means it can be omitted when calling the `createNode`
* function. If provided, it should be of type `V`.
* @param {RBTNColor} [color=BLACK] - The color parameter is used to specify the color of the node in
* a Red-Black Tree. It can have two possible values: 'RED' or 'BLACK'. The default value is 'BLACK'.
* @param {number} [count] - The `count` parameter represents the number of occurrences of a key in
* the tree. It is an optional parameter and is used to keep track of the number of values associated
* with a key in the tree.
* @returns A new instance of the TreeMultiMapNode class is being returned.
*/
createNode(key, value, count) {
return new TreeMultiMapNode(key, value, count);
createNode(key, value, color = 'BLACK', count) {
return new TreeMultiMapNode(key, value, count, color);
}

@@ -120,7 +136,7 @@ /**

else {
node = this.createNode(key, value, count);
node = this.createNode(key, value, 'BLACK', count);
}
}
else if (!this.isNode(keyOrNodeOrEntry)) {
node = this.createNode(keyOrNodeOrEntry, value, count);
node = this.createNode(keyOrNodeOrEntry, value, 'BLACK', count);
}

@@ -277,3 +293,3 @@ else {

// If the original color was black, fix the tree
if (originalColor === types_1.RBTNColor.BLACK) {
if (originalColor === 'BLACK') {
this._deleteFixup(replacementNode);

@@ -315,3 +331,3 @@ }

perfectlyBalance(iterationType = this.iterationType) {
const sorted = this.dfs(node => node, 'in'), n = sorted.length;
const sorted = this.dfs(node => node, 'IN'), n = sorted.length;
if (sorted.length < 1)

@@ -383,3 +399,3 @@ return false;

const { key, value, count, color } = destNode;
const tempNode = this.createNode(key, value, count);
const tempNode = this.createNode(key, value, color, count);
if (tempNode) {

@@ -386,0 +402,0 @@ tempNode.color = color;

2

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

@@ -162,3 +162,3 @@ /**

* Depth-first search (DFS) method, different traversal orders can be selected。
* @param order - Traverse order parameter: 'in' (in-order), 'pre' (pre-order) or 'post' (post-order).
* @param order - Traverse order parameter: 'IN' (in-order), 'PRE' (pre-order) or 'POST' (post-order).
* @returns An array containing elements traversed in the specified order.

@@ -165,0 +165,0 @@ */

10

dist/data-structures/heap/heap.js

@@ -232,6 +232,6 @@ "use strict";

* Depth-first search (DFS) method, different traversal orders can be selected。
* @param order - Traverse order parameter: 'in' (in-order), 'pre' (pre-order) or 'post' (post-order).
* @param order - Traverse order parameter: 'IN' (in-order), 'PRE' (pre-order) or 'POST' (post-order).
* @returns An array containing elements traversed in the specified order.
*/
dfs(order = 'pre') {
dfs(order = 'PRE') {
const result = [];

@@ -242,3 +242,3 @@ // Auxiliary recursive function, traverses the binary heap according to the traversal order

if (index < this.size) {
if (order === 'in') {
if (order === 'IN') {
_dfs(left);

@@ -248,3 +248,3 @@ result.push(this.elements[index]);

}
else if (order === 'pre') {
else if (order === 'PRE') {
result.push(this.elements[index]);

@@ -254,3 +254,3 @@ _dfs(left);

}
else if (order === 'post') {
else if (order === 'POST') {
_dfs(left);

@@ -257,0 +257,0 @@ _dfs(right);

2

dist/types/common.d.ts

@@ -12,3 +12,3 @@ export type BSTVariant = 'STANDARD' | 'INVERSE';

export type Comparator<K> = (a: K, b: K) => number;
export type DFSOrderPattern = 'pre' | 'in' | 'post';
export type DFSOrderPattern = 'PRE' | 'IN' | 'POST';
export type NodeDisplayLayout = [string[], number, number, number];

@@ -15,0 +15,0 @@ export type BTNCallback<N, D = any> = (node: N) => D;

5

dist/types/data-structures/binary-tree/rb-tree.d.ts
import { RedBlackTree, RedBlackTreeNode } from '../../../data-structures';
import type { BSTOptions } from "./bst";
export declare enum RBTNColor {
RED = 1,
BLACK = 0
}
export type RBTNColor = 'RED' | 'BLACK';
export type RedBlackTreeNodeNested<K, V> = RedBlackTreeNode<K, V, RedBlackTreeNode<K, V, RedBlackTreeNode<K, V, RedBlackTreeNode<K, V, RedBlackTreeNode<K, V, RedBlackTreeNode<K, V, RedBlackTreeNode<K, V, RedBlackTreeNode<K, V, RedBlackTreeNode<K, V, RedBlackTreeNode<K, V, RedBlackTreeNode<K, V, RedBlackTreeNode<K, V, RedBlackTreeNode<K, V, RedBlackTreeNode<K, V, RedBlackTreeNode<K, V, RedBlackTreeNode<K, V, RedBlackTreeNode<K, V, RedBlackTreeNode<K, V, RedBlackTreeNode<K, V, RedBlackTreeNode<K, V, RedBlackTreeNode<K, V, RedBlackTreeNode<K, V, RedBlackTreeNode<K, V, RedBlackTreeNode<K, V, RedBlackTreeNode<K, V, RedBlackTreeNode<K, V, RedBlackTreeNode<K, V, RedBlackTreeNode<K, V, RedBlackTreeNode<K, V, RedBlackTreeNode<K, V, RedBlackTreeNode<K, V, RedBlackTreeNode<K, V, RedBlackTreeNode<K, V, RedBlackTreeNode<K, V, RedBlackTreeNode<K, V, RedBlackTreeNode<K, V, RedBlackTreeNode<K, V, RedBlackTreeNode<K, V, RedBlackTreeNode<K, V, RedBlackTreeNode<K, V, RedBlackTreeNode<K, V, RedBlackTreeNode<K, V, RedBlackTreeNode<K, V, RedBlackTreeNode<K, V, RedBlackTreeNode<K, V, RedBlackTreeNode<K, V, RedBlackTreeNode<K, V, RedBlackTreeNode<K, V, RedBlackTreeNode<K, V, RedBlackTreeNode<K, V, any>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>;
export type RedBlackTreeNested<K, V, N extends RedBlackTreeNode<K, V, N>> = RedBlackTree<K, V, N, RedBlackTree<K, V, N, RedBlackTree<K, V, N, RedBlackTree<K, V, N, RedBlackTree<K, V, N, RedBlackTree<K, V, N, RedBlackTree<K, V, N, RedBlackTree<K, V, N, RedBlackTree<K, V, N, RedBlackTree<K, V, N, RedBlackTree<K, V, N, RedBlackTree<K, V, N, RedBlackTree<K, V, N, RedBlackTree<K, V, N, RedBlackTree<K, V, N, RedBlackTree<K, V, N, RedBlackTree<K, V, N, RedBlackTree<K, V, N, RedBlackTree<K, V, N, RedBlackTree<K, V, N, RedBlackTree<K, V, N, RedBlackTree<K, V, N, RedBlackTree<K, V, N, RedBlackTree<K, V, N, RedBlackTree<K, V, N, RedBlackTree<K, V, N, RedBlackTree<K, V, N, RedBlackTree<K, V, N, RedBlackTree<K, V, N, RedBlackTree<K, V, N, RedBlackTree<K, V, N, RedBlackTree<K, V, N, RedBlackTree<K, V, N, RedBlackTree<K, V, N, RedBlackTree<K, V, N, RedBlackTree<K, V, N, RedBlackTree<K, V, N, RedBlackTree<K, V, N, RedBlackTree<K, V, N, RedBlackTree<K, V, N, RedBlackTree<K, V, N, RedBlackTree<K, V, N, RedBlackTree<K, V, N, RedBlackTree<K, V, N, RedBlackTree<K, V, N, RedBlackTree<K, V, N, RedBlackTree<K, V, N, RedBlackTree<K, V, N, RedBlackTree<K, V, N, RedBlackTree<K, V, N, any>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>;
export type RBTreeOptions<K> = Omit<BSTOptions<K>, 'variant'> & {};

6

dist/types/data-structures/binary-tree/rb-tree.js
"use strict";
Object.defineProperty(exports, "__esModule", { value: true });
exports.RBTNColor = void 0;
var RBTNColor;
(function (RBTNColor) {
RBTNColor[RBTNColor["RED"] = 1] = "RED";
RBTNColor[RBTNColor["BLACK"] = 0] = "BLACK";
})(RBTNColor = exports.RBTNColor || (exports.RBTNColor = {}));

4

package.json
{
"name": "red-black-tree-typed",
"version": "1.50.8",
"version": "1.50.9",
"description": "RedBlackTree. Javascript & Typescript Data Structure.",

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

"dependencies": {
"data-structure-typed": "^1.50.8"
"data-structure-typed": "^1.50.9"
}
}

20

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

@@ -15,2 +15,3 @@ /**

BTNCallback,
IterationType,
KeyOrNodeOrEntry

@@ -89,3 +90,16 @@ } from '../../types';

getMutableCount(): number {
/**
* Time Complexity: O(n)
* Space Complexity: O(1)
*/
/**
* Time Complexity: O(n)
* Space Complexity: O(1)
*
* The function calculates the sum of the count property of all nodes in a tree using depth-first
* search.
* @returns the sum of the count property of all nodes in the tree.
*/
getComputedCount(): number {
let sum = 0;

@@ -321,4 +335,4 @@ this.dfs(node => (sum += node.count));

*/
override perfectlyBalance(iterationType = this.iterationType): boolean {
const sorted = this.dfs(node => node, 'in'),
override perfectlyBalance(iterationType: IterationType = this.iterationType): boolean {
const sorted = this.dfs(node => node, 'IN'),
n = sorted.length;

@@ -325,0 +339,0 @@ if (sorted.length < 1) return false;

43

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

@@ -213,3 +213,6 @@ /**

*/
override ensureNode(keyOrNodeOrEntry: KeyOrNodeOrEntry<K, V, NODE>, iterationType = 'ITERATIVE'): NODE | undefined {
override ensureNode(
keyOrNodeOrEntry: KeyOrNodeOrEntry<K, V, NODE>,
iterationType: IterationType = 'ITERATIVE'
): NODE | undefined {
let res: NODE | undefined;

@@ -325,3 +328,3 @@ if (this.isRealNode(keyOrNodeOrEntry)) {

isBalanceAdd = true,
iterationType = this.iterationType
iterationType: IterationType = this.iterationType
): boolean[] {

@@ -427,3 +430,4 @@ const inserted: boolean[] = [];

*/
override getNodeByKey(key: K, iterationType = 'ITERATIVE'): NODE | undefined {
override getNodeByKey(key: K, iterationType: IterationType = 'ITERATIVE'): NODE | undefined {
// return this.getNodes(key, this._defaultOneParamCallback, true, this.root, iterationType)[0];
if (!this.isRealNode(this.root)) return undefined;

@@ -486,3 +490,3 @@ if (iterationType === 'RECURSIVE') {

beginRoot: KeyOrNodeOrEntry<K, V, NODE> = this.root,
iterationType = this.iterationType
iterationType: IterationType = this.iterationType
): NODE[] {

@@ -572,3 +576,3 @@ beginRoot = this.ensureNode(beginRoot);

callback: C = this._defaultOneParamCallback as C,
pattern: DFSOrderPattern = 'in',
pattern: DFSOrderPattern = 'IN',
beginRoot: KeyOrNodeOrEntry<K, V, NODE> = this.root,

@@ -605,3 +609,3 @@ iterationType: IterationType = 'ITERATIVE'

beginRoot: KeyOrNodeOrEntry<K, V, NODE> = this.root,
iterationType = this.iterationType
iterationType: IterationType = this.iterationType
): ReturnType<C>[] {

@@ -637,3 +641,3 @@ return super.bfs(callback, beginRoot, iterationType, false);

beginRoot: KeyOrNodeOrEntry<K, V, NODE> = this.root,
iterationType = this.iterationType
iterationType: IterationType = this.iterationType
): ReturnType<C>[][] {

@@ -709,3 +713,3 @@ return super.listLevels(callback, beginRoot, iterationType, false);

targetNode: KeyOrNodeOrEntry<K, V, NODE> = this.root,
iterationType = this.iterationType
iterationType: IterationType = this.iterationType
): ReturnType<C>[] {

@@ -762,4 +766,4 @@ targetNode = this.ensureNode(targetNode);

*/
perfectlyBalance(iterationType = this.iterationType): boolean {
const sorted = this.dfs(node => node, 'in'),
perfectlyBalance(iterationType: IterationType = this.iterationType): boolean {
const sorted = this.dfs(node => node, 'IN'),
n = sorted.length;

@@ -824,3 +828,3 @@ this.clear();

*/
isAVLBalanced(iterationType = this.iterationType): boolean {
isAVLBalanced(iterationType: IterationType = this.iterationType): boolean {
if (!this.root) return true;

@@ -897,2 +901,11 @@

/**
* The function `_lt` compares two values `a` and `b` using an extractor function and returns true if
* `a` is less than `b` based on the specified variant.
* @param {K} a - The parameter "a" is of type "K", which means it can be any type. It represents the
* first value to be compared in the function.
* @param {K} b - The parameter `b` is of type `K`, which means it can be any type. It is used as one
* of the arguments for the comparison in the `_lt` function.
* @returns a boolean value.
*/
protected _lt(a: K, b: K): boolean {

@@ -907,2 +920,10 @@ const extractedA = this.extractor(a);

/**
* The function compares two values using a custom extractor function and returns true if the first
* value is greater than the second value.
* @param {K} a - The parameter "a" is of type K, which means it can be any type.
* @param {K} b - The parameter "b" is of type K, which means it can be any type. It is used as one
* of the arguments for the comparison in the function.
* @returns a boolean value.
*/
protected _gt(a: K, b: K): boolean {

@@ -909,0 +930,0 @@ const extractedA = this.extractor(a);

88

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

@@ -5,2 +5,3 @@ import type {

BTNCallback,
IterationType,
KeyOrNodeOrEntry,

@@ -29,5 +30,5 @@ RBTreeOptions,

* @param {RBTNColor} color - The `color` parameter is used to specify the color of the Red-Black
* Tree Node. It is an optional parameter with a default value of `RBTNColor.BLACK`.
* Tree Node. It is an optional parameter with a default value of `'BLACK'`.
*/
constructor(key: K, value?: V, color: RBTNColor = RBTNColor.BLACK) {
constructor(key: K, value?: V, color: RBTNColor = 'BLACK') {
super(key, value);

@@ -111,8 +112,8 @@ this._color = color;

* @param {RBTNColor} color - The "color" parameter is used to specify the color of the node in a
* Red-Black Tree. It is an optional parameter with a default value of "RBTNColor.BLACK". The color
* can be either "RBTNColor.RED" or "RBTNColor.BLACK".
* Red-Black Tree. It is an optional parameter with a default value of "'BLACK'". The color
* can be either "'RED'" or "'BLACK'".
* @returns The method is returning a new instance of a RedBlackTreeNode with the specified key,
* value, and color.
*/
override createNode(key: K, value?: V, color: RBTNColor = RBTNColor.BLACK): NODE {
override createNode(key: K, value?: V, color: RBTNColor = 'BLACK'): NODE {
return new RedBlackTreeNode<K, V, NODE>(key, value, color) as NODE;

@@ -162,6 +163,6 @@ }

} else {
node = this.createNode(key, value, RBTNColor.RED);
node = this.createNode(key, value, 'RED');
}
} else if (!this.isNode(keyOrNodeOrEntry)) {
node = this.createNode(keyOrNodeOrEntry, value, RBTNColor.RED);
node = this.createNode(keyOrNodeOrEntry, value, 'RED');
} else {

@@ -239,5 +240,4 @@ return;

beginRoot: BSTNKeyOrNode<K, NODE> = this.root,
iterationType = this.iterationType
iterationType: IterationType = this.iterationType
): NODE | null | undefined {
// if ((identifier as any) instanceof RedBlackTreeNode) callback = (node => node) as C;
return this.getNodes(identifier, callback, true, beginRoot, iterationType)[0] ?? undefined;

@@ -290,3 +290,3 @@ }

if (this.isRealNode(this._root)) {
this._root.color = RBTNColor.BLACK;
this._root.color = 'BLACK';
} else {

@@ -372,3 +372,3 @@ return false;

// If the original color was black, fix the tree
if (originalColor === RBTNColor.BLACK) {
if (originalColor === 'BLACK') {
this._deleteFixup(replacementNode);

@@ -461,3 +461,3 @@ }

node.right = this.SENTINEL;
node.color = RBTNColor.RED;
node.color = 'RED';

@@ -511,3 +511,3 @@ this._insertFixup(node);

// Continue fixing the tree as long as the parent of z is red
while (z?.parent?.color === RBTNColor.RED) {
while (z?.parent?.color === 'RED') {
// Check if the parent of z is the left child of its parent

@@ -517,7 +517,7 @@ if (z.parent === z.parent.parent?.left) {

const y = z.parent.parent.right;
if (y?.color === RBTNColor.RED) {
if (y?.color === 'RED') {
// Set colors to restore properties of Red-Black Tree
z.parent.color = RBTNColor.BLACK;
y.color = RBTNColor.BLACK;
z.parent.parent.color = RBTNColor.RED;
z.parent.color = 'BLACK';
y.color = 'BLACK';
z.parent.parent.color = 'RED';
// Move up the tree to continue fixing

@@ -536,4 +536,4 @@ z = z.parent.parent;

if (z && this.isRealNode(z.parent) && this.isRealNode(z.parent.parent)) {
z.parent.color = RBTNColor.BLACK;
z.parent.parent.color = RBTNColor.RED;
z.parent.color = 'BLACK';
z.parent.parent.color = 'RED';
this._rightRotate(z.parent.parent);

@@ -546,6 +546,6 @@ }

const y: NODE | undefined = z?.parent?.parent?.left;
if (y?.color === RBTNColor.RED) {
z.parent.color = RBTNColor.BLACK;
y.color = RBTNColor.BLACK;
z.parent.parent!.color = RBTNColor.RED;
if (y?.color === 'RED') {
z.parent.color = 'BLACK';
y.color = 'BLACK';
z.parent.parent!.color = 'RED';
z = z.parent.parent;

@@ -559,4 +559,4 @@ } else {

if (z && this.isRealNode(z.parent) && this.isRealNode(z.parent.parent)) {
z.parent.color = RBTNColor.BLACK;
z.parent.parent.color = RBTNColor.RED;
z.parent.color = 'BLACK';
z.parent.parent.color = 'RED';
this._leftRotate(z.parent.parent);

@@ -569,3 +569,3 @@ }

// Ensure that the root is black after fixing
if (this.isRealNode(this._root)) this._root.color = RBTNColor.BLACK;
if (this.isRealNode(this._root)) this._root.color = 'BLACK';
}

@@ -590,5 +590,5 @@

// Early exit condition
if (!node || node === this.root || node.color === RBTNColor.BLACK) {
if (!node || node === this.root || node.color === 'BLACK') {
if (node) {
node.color = RBTNColor.BLACK; // Ensure the final node is black
node.color = 'BLACK'; // Ensure the final node is black
}

@@ -598,3 +598,3 @@ return;

while (node && node !== this.root && node.color === RBTNColor.BLACK) {
while (node && node !== this.root && node.color === 'BLACK') {
const parent: NODE | undefined = node.parent;

@@ -610,5 +610,5 @@

// Cases 1 and 2: Sibling is red or both children of sibling are black
if (sibling?.color === RBTNColor.RED) {
sibling.color = RBTNColor.BLACK;
parent.color = RBTNColor.RED;
if (sibling?.color === 'RED') {
sibling.color = 'BLACK';
parent.color = 'RED';
this._leftRotate(parent);

@@ -619,10 +619,10 @@ sibling = parent.right;

// Case 3: Sibling's left child is black
if ((sibling?.left?.color ?? RBTNColor.BLACK) === RBTNColor.BLACK) {
if (sibling) sibling.color = RBTNColor.RED;
if ((sibling?.left?.color ?? 'BLACK') === 'BLACK') {
if (sibling) sibling.color = 'RED';
node = parent;
} else {
// Case 4: Adjust colors and perform a right rotation
if (sibling?.left) sibling.left.color = RBTNColor.BLACK;
if (sibling?.left) sibling.left.color = 'BLACK';
if (sibling) sibling.color = parent.color;
parent.color = RBTNColor.BLACK;
parent.color = 'BLACK';
this._rightRotate(parent);

@@ -636,5 +636,5 @@ node = this.root;

// Cases 1 and 2: Sibling is red or both children of sibling are black
if (sibling?.color === RBTNColor.RED) {
sibling.color = RBTNColor.BLACK;
if (parent) parent.color = RBTNColor.RED;
if (sibling?.color === 'RED') {
sibling.color = 'BLACK';
if (parent) parent.color = 'RED';
this._rightRotate(parent);

@@ -645,10 +645,10 @@ if (parent) sibling = parent.left;

// Case 3: Sibling's left child is black
if ((sibling?.right?.color ?? RBTNColor.BLACK) === RBTNColor.BLACK) {
if (sibling) sibling.color = RBTNColor.RED;
if ((sibling?.right?.color ?? 'BLACK') === 'BLACK') {
if (sibling) sibling.color = 'RED';
node = parent;
} else {
// Case 4: Adjust colors and perform a left rotation
if (sibling?.right) sibling.right.color = RBTNColor.BLACK;
if (sibling?.right) sibling.right.color = 'BLACK';
if (sibling) sibling.color = parent.color;
if (parent) parent.color = RBTNColor.BLACK;
if (parent) parent.color = 'BLACK';
this._leftRotate(parent);

@@ -662,3 +662,3 @@ node = this.root;

if (node) {
node.color = RBTNColor.BLACK;
node.color = 'BLACK';
}

@@ -665,0 +665,0 @@ }

73

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

@@ -12,2 +12,3 @@ /**

BTNCallback,
IterationType,
KeyOrNodeOrEntry,

@@ -28,13 +29,15 @@ TreeMultiMapNested,

/**
* The constructor function initializes an instance of a class with a key, value, and count.
* @param {K} key - The key parameter is of type K, which represents the type of the key for the
* constructor. It is required and must be provided when creating an instance of the class.
* @param {V} [value] - The `value` parameter is an optional parameter of type `V`. It represents the
* value associated with the key in the constructor. If no value is provided, it will be `undefined`.
* @param [count=1] - The "count" parameter is an optional parameter that specifies the number of
* times the key-value pair should be repeated. If no value is provided for "count", it defaults to
* 1.
* The constructor function initializes a Red-Black Tree node with a key, value, count, and color.
* @param {K} key - The key parameter represents the key of the node in the Red-Black Tree. It is
* used to identify and locate the node within the tree.
* @param {V} [value] - The `value` parameter is an optional parameter that represents the value
* associated with the key in the Red-Black Tree node. It is not required and can be omitted when
* creating a new node.
* @param [count=1] - The `count` parameter represents the number of occurrences of a particular key
* in the Red-Black Tree. It is an optional parameter with a default value of 1.
* @param {RBTNColor} [color=BLACK] - The `color` parameter is used to specify the color of the node
* in a Red-Black Tree. It is optional and has a default value of `'BLACK'`.
*/
constructor(key: K, value?: V, count = 1) {
super(key, value);
constructor(key: K, value?: V, count = 1, color: RBTNColor = 'BLACK') {
super(key, value, color);
this.count = count;

@@ -96,3 +99,16 @@ }

getMutableCount(): number {
/**
* Time Complexity: O(n)
* Space Complexity: O(1)
*/
/**
* Time Complexity: O(n)
* Space Complexity: O(1)
*
* The function calculates the sum of the count property of all nodes in a tree using depth-first
* search.
* @returns the sum of the count property of all nodes in the tree.
*/
getComputedCount(): number {
let sum = 0;

@@ -104,14 +120,17 @@ this.dfs(node => (sum += node.count));

/**
* The function creates a new TreeMultiMapNode object with the specified key, value, and count.
* The function creates a new TreeMultiMapNode with the specified key, value, color, and count.
* @param {K} key - The key parameter represents the key of the node being created. It is of type K,
* which is a generic type that can be replaced with any specific type when using the function.
* @param {V} [value] - The `value` parameter is an optional parameter that represents the value
* associated with the key in the node. It is of type `V`, which can be any data type.
* @param {number} [count] - The `count` parameter represents the number of occurrences of a
* key-value pair in the TreeMultiMap. It is an optional parameter, so if it is not provided, it will
* default to 1.
* @returns a new instance of the TreeMultiMapNode class, casted as NODE.
* which is a generic type representing the key type of the node.
* @param {V} [value] - The `value` parameter represents the value associated with the key in the
* node. It is an optional parameter, which means it can be omitted when calling the `createNode`
* function. If provided, it should be of type `V`.
* @param {RBTNColor} [color=BLACK] - The color parameter is used to specify the color of the node in
* a Red-Black Tree. It can have two possible values: 'RED' or 'BLACK'. The default value is 'BLACK'.
* @param {number} [count] - The `count` parameter represents the number of occurrences of a key in
* the tree. It is an optional parameter and is used to keep track of the number of values associated
* with a key in the tree.
* @returns A new instance of the TreeMultiMapNode class is being returned.
*/
override createNode(key: K, value?: V, count?: number): NODE {
return new TreeMultiMapNode(key, value, count) as NODE;
override createNode(key: K, value?: V, color: RBTNColor = 'BLACK', count?: number): NODE {
return new TreeMultiMapNode(key, value, count, color) as NODE;
}

@@ -160,6 +179,6 @@

} else {
node = this.createNode(key, value, count);
node = this.createNode(key, value, 'BLACK', count);
}
} else if (!this.isNode(keyOrNodeOrEntry)) {
node = this.createNode(keyOrNodeOrEntry, value, count);
node = this.createNode(keyOrNodeOrEntry, value, 'BLACK', count);
} else {

@@ -322,3 +341,3 @@ return;

// If the original color was black, fix the tree
if (originalColor === RBTNColor.BLACK) {
if (originalColor === 'BLACK') {
this._deleteFixup(replacementNode);

@@ -365,4 +384,4 @@ }

*/
override perfectlyBalance(iterationType = this.iterationType): boolean {
const sorted = this.dfs(node => node, 'in'),
override perfectlyBalance(iterationType: IterationType = this.iterationType): boolean {
const sorted = this.dfs(node => node, 'IN'),
n = sorted.length;

@@ -441,3 +460,3 @@ if (sorted.length < 1) return false;

const { key, value, count, color } = destNode;
const tempNode = this.createNode(key, value, count);
const tempNode = this.createNode(key, value, color, count);
if (tempNode) {

@@ -444,0 +463,0 @@ tempNode.color = color;

10

src/data-structures/heap/heap.ts

@@ -250,6 +250,6 @@ /**

* Depth-first search (DFS) method, different traversal orders can be selected。
* @param order - Traverse order parameter: 'in' (in-order), 'pre' (pre-order) or 'post' (post-order).
* @param order - Traverse order parameter: 'IN' (in-order), 'PRE' (pre-order) or 'POST' (post-order).
* @returns An array containing elements traversed in the specified order.
*/
dfs(order: DFSOrderPattern = 'pre'): E[] {
dfs(order: DFSOrderPattern = 'PRE'): E[] {
const result: E[] = [];

@@ -262,11 +262,11 @@

if (index < this.size) {
if (order === 'in') {
if (order === 'IN') {
_dfs(left);
result.push(this.elements[index]);
_dfs(right);
} else if (order === 'pre') {
} else if (order === 'PRE') {
result.push(this.elements[index]);
_dfs(left);
_dfs(right);
} else if (order === 'post') {
} else if (order === 'POST') {
_dfs(left);

@@ -273,0 +273,0 @@ _dfs(right);

2

src/types/common.ts

@@ -16,3 +16,3 @@ export type BSTVariant = 'STANDARD' | 'INVERSE';

export type DFSOrderPattern = 'pre' | 'in' | 'post';
export type DFSOrderPattern = 'PRE' | 'IN' | 'POST';

@@ -19,0 +19,0 @@ export type NodeDisplayLayout = [string[], number, number, number];

2

src/types/data-structures/binary-tree/rb-tree.ts
import { RedBlackTree, RedBlackTreeNode } from '../../../data-structures';
import type { BSTOptions } from "./bst";
export enum RBTNColor { RED = 1, BLACK = 0}
export type RBTNColor = 'RED' | 'BLACK';

@@ -6,0 +6,0 @@ export type RedBlackTreeNodeNested<K, V> = RedBlackTreeNode<K, V, RedBlackTreeNode<K, V, RedBlackTreeNode<K, V, RedBlackTreeNode<K, V, RedBlackTreeNode<K, V, RedBlackTreeNode<K, V, RedBlackTreeNode<K, V, RedBlackTreeNode<K, V, RedBlackTreeNode<K, V, RedBlackTreeNode<K, V, RedBlackTreeNode<K, V, RedBlackTreeNode<K, V, RedBlackTreeNode<K, V, RedBlackTreeNode<K, V, RedBlackTreeNode<K, V, RedBlackTreeNode<K, V, RedBlackTreeNode<K, V, RedBlackTreeNode<K, V, RedBlackTreeNode<K, V, RedBlackTreeNode<K, V, RedBlackTreeNode<K, V, RedBlackTreeNode<K, V, RedBlackTreeNode<K, V, RedBlackTreeNode<K, V, RedBlackTreeNode<K, V, RedBlackTreeNode<K, V, RedBlackTreeNode<K, V, RedBlackTreeNode<K, V, RedBlackTreeNode<K, V, RedBlackTreeNode<K, V, RedBlackTreeNode<K, V, RedBlackTreeNode<K, V, RedBlackTreeNode<K, V, RedBlackTreeNode<K, V, RedBlackTreeNode<K, V, RedBlackTreeNode<K, V, RedBlackTreeNode<K, V, RedBlackTreeNode<K, V, RedBlackTreeNode<K, V, RedBlackTreeNode<K, V, RedBlackTreeNode<K, V, RedBlackTreeNode<K, V, RedBlackTreeNode<K, V, RedBlackTreeNode<K, V, RedBlackTreeNode<K, V, RedBlackTreeNode<K, V, RedBlackTreeNode<K, V, RedBlackTreeNode<K, V, RedBlackTreeNode<K, V, RedBlackTreeNode<K, V, any>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>

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

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

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

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

SocketSocket SOC 2 Logo

Product

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

About

Packages

npm

Go

Maven

PyPI

Rubygems

Stay in touch

Get open source security insights delivered straight into your inbox.

  • Terms
  • Privacy
  • Security

Made with ⚡️ by Socket Inc