Socket
Socket
Sign inDemoInstall

min-heap-typed

Package Overview
Dependencies
Maintainers
1
Versions
151
Alerts
File Explorer

Advanced tools

License
Socket logo

Install Socket

Detect and block malicious and high-risk dependencies

Install

min-heap-typed - npm Package Compare versions

Comparing version 1.50.5 to 1.50.6

293

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

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

/**
* data-structure-typed
*
* @author Tyler Zeng
* @copyright Copyright (c) 2022 Tyler Zeng <zrwusa@gmail.com>
* @license MIT License
*/
import { BinaryTreeDeleteResult, BSTNKeyOrNode, BTNCallback, KeyOrNodeOrEntry, RBTNColor, RBTreeOptions, RedBlackTreeNested, RedBlackTreeNodeNested } from '../../types';
import type { BinaryTreeDeleteResult, BSTNKeyOrNode, BTNCallback, KeyOrNodeOrEntry, RBTreeOptions, RedBlackTreeNested, RedBlackTreeNodeNested } from '../../types';
import { RBTNColor } from '../../types';
import { BST, BSTNode } from './bst';

@@ -27,3 +21,3 @@ import { IBinaryTree } from '../../interfaces';

* The function returns the color value of a variable.
* @returns The color value stored in the protected variable `_color`.
* @returns The color value stored in the private variable `_color`.
*/

@@ -37,34 +31,26 @@ get color(): RBTNColor;

}
/**
* 1. Each node is either red or black.
* 2. The root node is always black.
* 3. Leaf nodes are typically Sentinel nodes and are considered black.
* 4. Red nodes must have black children.
* 5. Black balance: Every path from any node to each of its leaf nodes contains the same number of black nodes.
*/
export declare class RedBlackTree<K = any, V = any, NODE extends RedBlackTreeNode<K, V, NODE> = RedBlackTreeNode<K, V, RedBlackTreeNodeNested<K, V>>, TREE extends RedBlackTree<K, V, NODE, TREE> = RedBlackTree<K, V, NODE, RedBlackTreeNested<K, V, NODE>>> extends BST<K, V, NODE, TREE> implements IBinaryTree<K, V, NODE, TREE> {
/**
* This is the constructor function for a Red-Black Tree data structure in TypeScript, which
* initializes the tree with optional nodes and options.
* @param [keysOrNodesOrEntries] - The `keysOrNodesOrEntries` parameter is an optional iterable of `KeyOrNodeOrEntry<K, V, NODE>`
* objects. It represents the initial nodes that will be added to the RBTree during its
* construction. If this parameter is provided, the `addMany` method is called to add all the
* nodes to the
* @param [options] - The `options` parameter is an optional object that allows you to customize the
* behavior of the RBTree. It is of type `Partial<RBTreeOptions>`, which means that you can provide
* only a subset of the properties defined in the `RBTreeOptions` interface.
* This is the constructor function for a Red-Black Tree data structure in TypeScript.
* @param keysOrNodesOrEntries - The `keysOrNodesOrEntries` parameter is an iterable object that can
* contain keys, nodes, or entries. It is used to initialize the RBTree with the provided keys,
* nodes, or entries.
* @param [options] - The `options` parameter is an optional object that can be passed to the
* constructor. It allows you to customize the behavior of the RBTree. It can include properties such
* as `compareKeys`, `compareValues`, `allowDuplicates`, etc. These properties define how the RBTree
* should compare keys and
*/
constructor(keysOrNodesOrEntries?: Iterable<KeyOrNodeOrEntry<K, V, NODE>>, options?: RBTreeOptions<K>);
protected _Sentinel: NODE;
protected _SENTINEL: NODE;
/**
* The function returns the value of the `_Sentinel` property.
* @returns The method is returning the value of the `_Sentinel` property.
* The function returns the value of the _SENTINEL property.
* @returns The method is returning the value of the `_SENTINEL` property.
*/
get Sentinel(): NODE;
protected _root: NODE;
get SENTINEL(): NODE;
protected _root: NODE | undefined;
/**
* The function returns the root node.
* @returns The root node of the data structure.
* The function returns the root node of a tree or undefined if there is no root.
* @returns The root node of the tree structure, or undefined if there is no root node.
*/
get root(): NODE;
get root(): NODE | undefined;
protected _size: number;

@@ -78,9 +64,9 @@ /**

* The function creates a new Red-Black Tree node with the specified key, value, and color.
* @param {K} key - The key parameter is the key value associated with the node. It is used to
* identify and compare nodes in the Red-Black Tree.
* @param {K} key - The key parameter represents the key of the node being created. It is of type K,
* which is a generic type representing the key's data type.
* @param {V} [value] - The `value` parameter is an optional parameter that represents the value
* associated with the node. It is of type `V`, which is a generic type that can be replaced with any
* specific type when using the `createNode` method.
* associated with the key in the node. It is not required and can be omitted if not needed.
* @param {RBTNColor} color - The "color" parameter is used to specify the color of the node in a
* Red-Black Tree. It can be either "RED" or "BLACK". By default, the color is set to "BLACK".
* 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".
* @returns The method is returning a new instance of a RedBlackTreeNode with the specified key,

@@ -91,6 +77,6 @@ * value, and color.

/**
* The function creates a Red-Black Tree with the specified options and returns it.
* @param {RBTreeOptions} [options] - The `options` parameter is an optional object that can be
* passed to the `createTree` function. It is used to customize the behavior of the `RedBlackTree`
* class.
* The function creates a Red-Black Tree with the given options and returns it.
* @param [options] - The `options` parameter is an optional object that contains configuration
* options for creating the Red-Black Tree. It is of type `RBTreeOptions<K>`, where `K` represents
* the type of keys in the tree.
* @returns a new instance of a RedBlackTree object.

@@ -100,18 +86,38 @@ */

/**
* The function `keyValueOrEntryToNode` takes an keyOrNodeOrEntry and converts it into a node object if possible.
* @param keyOrNodeOrEntry - The `keyOrNodeOrEntry` parameter is of type `KeyOrNodeOrEntry<K, V, NODE>`, where:
* @param {V} [value] - The `value` parameter is an optional value that can be passed to the
* `keyValueOrEntryToNode` function. It represents the value associated with the keyOrNodeOrEntry node. If a value
* is provided, it will be used when creating the new node. If no value is provided, the new node
* @returns a node of type NODE or undefined.
* Time Complexity: O(1)
* Space Complexity: O(1)
*/
/**
* Time Complexity: O(1)
* Space Complexity: O(1)
*
* The function `keyValueOrEntryToNode` takes a key, value, or entry and returns a node if it is
* valid, otherwise it returns undefined.
* @param {KeyOrNodeOrEntry<K, V, NODE>} keyOrNodeOrEntry - The key, value, or entry to convert.
* @param {V} [value] - The value associated with the key (if `keyOrNodeOrEntry` is a key).
* @returns {NODE | undefined} - The corresponding Red-Black Tree node, or `undefined` if conversion fails.
*/
keyValueOrEntryToNode(keyOrNodeOrEntry: KeyOrNodeOrEntry<K, V, NODE>, value?: V): NODE | undefined;
/**
* The function checks if an keyOrNodeOrEntry is an instance of the RedBlackTreeNode class.
* @param keyOrNodeOrEntry - The `keyOrNodeOrEntry` parameter is of type `KeyOrNodeOrEntry<K, V, NODE>`.
* @returns a boolean value indicating whether the keyOrNodeOrEntry is an instance of the RedBlackTreeNode
* class.
* Time Complexity: O(1)
* Space Complexity: O(1)
* /
/**
* Time Complexity: O(1)
* Space Complexity: O(1)
*
* The function checks if the input is an instance of the RedBlackTreeNode class.
* @param {KeyOrNodeOrEntry<K, V, NODE>} keyOrNodeOrEntry - The object to check.
* @returns {boolean} - `true` if the object is a Red-Black Tree node, `false` otherwise.
*/
isNode(keyOrNodeOrEntry: KeyOrNodeOrEntry<K, V, NODE>): keyOrNodeOrEntry is NODE;
/**
* Time Complexity: O(1)
* Space Complexity: O(1)
*/
/**
* Time Complexity: O(1)
* Space Complexity: O(1)
*
* The function checks if a given node is a real node in a Red-Black Tree.

@@ -126,3 +132,2 @@ * @param {NODE | undefined} node - The `node` parameter is of type `NODE | undefined`, which means

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

@@ -133,12 +138,33 @@ /**

*
* The `add` function adds a new node to a binary search tree and performs necessary rotations and
* color changes to maintain the red-black tree properties.
* @param keyOrNodeOrEntry - The `keyOrNodeOrEntry` parameter can be either a key, a node, or an
* entry.
* @param {V} [value] - The `value` parameter represents the value associated with the key that is
* being added to the binary search tree.
* @returns The method `add` returns either the newly added node (`NODE`) or `undefined`.
* The `getNode` function retrieves a node from a Red-Black Tree based on the provided identifier and
* callback function.
* @param {ReturnType<C> | undefined} identifier - The `identifier` parameter is the value or key
* that you want to search for in the binary search tree. It can be of any type that is compatible
* with the type of nodes in the tree.
* @param {C} callback - The `callback` parameter is a function that will be called for each node in
* the tree. It is used to determine whether a node matches the given identifier. The `callback`
* function should take a node as its parameter and return a value that can be compared to the
* `identifier` parameter.
* @param beginRoot - The `beginRoot` parameter is the starting point for the search in the binary
* search tree. It can be either a key or a node. If it is a key, it will be converted to a node
* using the `ensureNode` method. If it is not provided, the `root`
* @param iterationType - The `iterationType` parameter is used to specify the type of iteration to
* be performed when searching for nodes in the binary search tree. It is an optional parameter and
* its default value is taken from the `iterationType` property of the class.
* @returns The method is returning a value of type `NODE | null | undefined`.
*/
add(keyOrNodeOrEntry: KeyOrNodeOrEntry<K, V, NODE>, value?: V): boolean;
getNode<C extends BTNCallback<NODE>>(identifier: ReturnType<C> | undefined, callback?: C, beginRoot?: BSTNKeyOrNode<K, NODE>, iterationType?: import("../../types").IterationType): NODE | null | undefined;
/**
* Time Complexity: O(1)
* Space Complexity: O(1)
*/
/**
* Time Complexity: O(1)
* Space Complexity: O(1)
*
* The "clear" function sets the root node of a data structure to a sentinel value and resets the
* size counter to zero.
*/
clear(): void;
/**
* Time Complexity: O(log n)

@@ -151,14 +177,12 @@ * Space Complexity: O(1)

*
* The `delete` function removes a node from a binary tree based on a given identifier and updates
* the tree accordingly.
* @param {ReturnType<C> | null | undefined} identifier - The `identifier` parameter is the value
* that you want to use to identify the node that you want to delete from the binary tree. It can be
* of any type that is returned by the callback function `C`. It can also be `null` or `undefined` if
* you don't want to
* @param {C} callback - The `callback` parameter is a function that takes a node of type `NODE` and
* returns a value of type `ReturnType<C>`. It is used to determine if a node should be deleted based
* on its identifier. The `callback` function is optional and defaults to `this._defaultOneParam
* @returns an array of `BinaryTreeDeleteResult<NODE>`.
* The function adds a new node to a Red-Black Tree data structure and returns a boolean indicating
* whether the operation was successful.
* @param keyOrNodeOrEntry - The `keyOrNodeOrEntry` parameter can be either a key, a node, or an
* entry.
* @param {V} [value] - The `value` parameter is the value associated with the key that is being
* added to the tree.
* @returns The method is returning a boolean value. It returns true if the node was successfully
* added or updated, and false otherwise.
*/
delete<C extends BTNCallback<NODE>>(identifier: ReturnType<C> | null | undefined, callback?: C): BinaryTreeDeleteResult<NODE>[];
add(keyOrNodeOrEntry: KeyOrNodeOrEntry<K, V, NODE>, value?: V): boolean;
/**

@@ -172,21 +196,22 @@ * Time Complexity: O(log n)

*
* The function `getNode` retrieves a single node from a binary tree based on a given identifier and
* callback function.
* @param {ReturnType<C> | undefined} identifier - The `identifier` parameter is the value used to
* identify the node you want to retrieve. It can be of any type that is the return type of the `C`
* callback function. If the `identifier` is `undefined`, it means you want to retrieve the first
* node that matches the other criteria
* @param {C} callback - The `callback` parameter is a function that will be called for each node in
* the binary tree. It is used to determine if a node matches the given identifier. The `callback`
* function should take a single parameter of type `NODE` (the type of the nodes in the binary tree) and
* @param {K | NODE | undefined} beginRoot - The `beginRoot` parameter is the starting point for
* searching for a node in a binary tree. It can be either a key value or a node object. If it is not
* provided, the search will start from the root of the binary tree.
* @param iterationType - The `iterationType` parameter is a variable that determines the type of
* iteration to be performed when searching for nodes in the binary tree. It is used in the
* `getNodes` method, which is called within the `getNode` method.
* @returns a value of type `NODE`, `null`, or `undefined`.
* The function `delete` in a binary tree class deletes a node from the tree and fixes the tree if
* necessary.
* @param {ReturnType<C> | null | undefined} identifier - The `identifier` parameter is the
* identifier of the node that needs to be deleted from the binary tree. It can be of any type that
* is returned by the callback function `C`. It can also be `null` or `undefined` if the node to be
* deleted is not found.
* @param {C} callback - The `callback` parameter is a function that is used to retrieve a node from
* the binary tree based on its identifier. It is an optional parameter and if not provided, the
* `_defaultOneParamCallback` function is used as the default callback. The callback function should
* return the identifier of the node to
* @returns an array of BinaryTreeDeleteResult<NODE> objects.
*/
getNode<C extends BTNCallback<NODE>>(identifier: ReturnType<C> | undefined, callback?: C, beginRoot?: BSTNKeyOrNode<K, NODE>, iterationType?: import("../../types").IterationType): NODE | null | undefined;
delete<C extends BTNCallback<NODE>>(identifier: ReturnType<C> | null | undefined, callback?: C): BinaryTreeDeleteResult<NODE>[];
/**
* The function sets the root of a tree-like structure and updates the parent property of the new
* root.
* @param {NODE | undefined} v - v is a parameter of type NODE or undefined.
*/
protected _setRoot(v: NODE | undefined): void;
/**
* Time Complexity: O(1)

@@ -199,5 +224,11 @@ * Space Complexity: O(1)

*
* The "clear" function sets the root node to the sentinel node and resets the size to 0.
* The function replaces an old node with a new node while preserving the color of the old node.
* @param {NODE} oldNode - The `oldNode` parameter represents the node that needs to be replaced in
* the data structure.
* @param {NODE} newNode - The `newNode` parameter is the new node that will replace the old node in
* the data structure.
* @returns The method is returning the result of calling the `_replaceNode` method from the
* superclass, with the `oldNode` and `newNode` parameters.
*/
clear(): void;
protected _replaceNode(oldNode: NODE, newNode: NODE): NODE;
/**

@@ -211,16 +242,11 @@ * Time Complexity: O(log n)

*
* The function returns the predecessor of a given node in a red-black tree.
* @param {RedBlackTreeNode} x - The parameter `x` is of type `RedBlackTreeNode`, which represents a node in a
* Red-Black Tree.
* @returns the predecessor of the given RedBlackTreeNode 'x'.
* The `_insert` function inserts or updates a node in a binary search tree and performs necessary
* fix-ups to maintain the red-black tree properties.
* @param {NODE} node - The `node` parameter represents the node that needs to be inserted into a
* binary search tree. It contains a `key` property that is used to determine the position of the
* node in the tree.
* @returns {'inserted' | 'updated'} - The result of the insertion.
*/
getPredecessor(x: NODE): NODE;
protected _insert(node: NODE): 'inserted' | 'updated';
/**
* The function sets the root node of a tree structure and updates the parent property of the new
* root node.
* @param {NODE} v - The parameter "v" is of type "NODE", which represents a node in a data
* structure.
*/
protected _setRoot(v: NODE): void;
/**
* Time Complexity: O(1)

@@ -233,19 +259,21 @@ * Space Complexity: O(1)

*
* The function performs a left rotation on a binary tree node.
* @param {RedBlackTreeNode} x - The parameter `x` is of type `NODE`, which likely represents a node in a binary tree.
* The function `_transplant` is used to replace a node `u` with another node `v` in a binary tree.
* @param {NODE} u - The parameter "u" represents a node in a binary tree.
* @param {NODE | undefined} v - The parameter `v` is of type `NODE | undefined`, which means it can
* either be a `NODE` object or `undefined`.
*/
protected _leftRotate(x: NODE): void;
protected _transplant(u: NODE, v: NODE | undefined): void;
/**
* Time Complexity: O(1)
* Time Complexity: O(log n)
* Space Complexity: O(1)
*/
/**
* Time Complexity: O(1)
* Time Complexity: O(log n)
* Space Complexity: O(1)
*
* The function performs a right rotation on a red-black tree node.
* @param {RedBlackTreeNode} x - x is a RedBlackTreeNode, which represents the node that needs to be right
* rotated.
* The `_insertFixup` function is used to fix the Red-Black Tree after inserting a new node.
* @param {NODE | undefined} z - The parameter `z` represents a node in the Red-Black Tree. It can
* either be a valid node object or `undefined`.
*/
protected _rightRotate(x: NODE): void;
protected _insertFixup(z: NODE | undefined): void;
/**

@@ -259,19 +287,23 @@ * Time Complexity: O(log n)

*
* The `_fixInsert` function is used to fix the red-black tree after an insertion operation.
* @param {RedBlackTreeNode} k - The parameter `k` is a RedBlackTreeNode object, which represents a node in a
* red-black tree.
* The `_deleteFixup` function is used to fix the red-black tree after a node deletion by adjusting
* the colors and performing rotations.
* @param {NODE | undefined} node - The `node` parameter represents a node in a Red-Black Tree data
* structure. It can be either a valid node object or `undefined`.
* @returns The function does not return any value. It has a return type of `void`.
*/
protected _fixInsert(k: NODE): void;
protected _deleteFixup(node: NODE | undefined): void;
/**
* Time Complexity: O(log n)
* Time Complexity: O(1)
* Space Complexity: O(1)
*/
/**
* Time Complexity: O(log n)
* Time Complexity: O(1)
* Space Complexity: O(1)
*
* The function `_fixDelete` is used to fix the red-black tree after a node deletion.
* @param {RedBlackTreeNode} x - The parameter `x` represents a node in a Red-Black Tree (RBT).
* The `_leftRotate` function performs a left rotation on a given node in a binary tree.
* @param {NODE | undefined} x - The parameter `x` is of type `NODE | undefined`. It represents a
* node in a binary tree or `undefined` if there is no node.
* @returns void, which means it does not return any value.
*/
protected _fixDelete(x: NODE): void;
protected _leftRotate(x: NODE | undefined): void;
/**

@@ -285,17 +317,8 @@ * Time Complexity: O(1)

*
* The function `_rbTransplant` replaces one node in a red-black tree with another node.
* @param {RedBlackTreeNode} u - The parameter "u" represents a RedBlackTreeNode object.
* @param {RedBlackTreeNode} v - The parameter "v" is a RedBlackTreeNode object.
* The `_rightRotate` function performs a right rotation on a given node in a binary tree.
* @param {NODE | undefined} y - The parameter `y` is of type `NODE | undefined`. It represents a
* node in a binary tree or `undefined` if there is no node.
* @returns void, which means it does not return any value.
*/
protected _rbTransplant(u: NODE, v: NODE): void;
/**
* The function replaces an old node with a new node while preserving the color of the old node.
* @param {NODE} oldNode - The `oldNode` parameter represents the node that needs to be replaced in a
* data structure. It is of type `NODE`, which is the type of the nodes in the data structure.
* @param {NODE} newNode - The `newNode` parameter is the node that will replace the `oldNode` in the
* data structure.
* @returns The method is returning the result of calling the `_replaceNode` method from the
* superclass, passing in the `oldNode` and `newNode` as arguments.
*/
protected _replaceNode(oldNode: NODE, newNode: NODE): NODE;
protected _rightRotate(y: NODE | undefined): void;
}

795

dist/data-structures/binary-tree/rb-tree.js
"use strict";
/**
* data-structure-typed
*
* @author Tyler Zeng
* @copyright Copyright (c) 2022 Tyler Zeng <zrwusa@gmail.com>
* @license MIT License
*/
Object.defineProperty(exports, "__esModule", { value: true });

@@ -31,3 +24,3 @@ exports.RedBlackTree = exports.RedBlackTreeNode = void 0;

* The function returns the color value of a variable.
* @returns The color value stored in the protected variable `_color`.
* @returns The color value stored in the private variable `_color`.
*/

@@ -46,39 +39,32 @@ get color() {

exports.RedBlackTreeNode = RedBlackTreeNode;
/**
* 1. Each node is either red or black.
* 2. The root node is always black.
* 3. Leaf nodes are typically Sentinel nodes and are considered black.
* 4. Red nodes must have black children.
* 5. Black balance: Every path from any node to each of its leaf nodes contains the same number of black nodes.
*/
class RedBlackTree extends bst_1.BST {
/**
* This is the constructor function for a Red-Black Tree data structure in TypeScript, which
* initializes the tree with optional nodes and options.
* @param [keysOrNodesOrEntries] - The `keysOrNodesOrEntries` parameter is an optional iterable of `KeyOrNodeOrEntry<K, V, NODE>`
* objects. It represents the initial nodes that will be added to the RBTree during its
* construction. If this parameter is provided, the `addMany` method is called to add all the
* nodes to the
* @param [options] - The `options` parameter is an optional object that allows you to customize the
* behavior of the RBTree. It is of type `Partial<RBTreeOptions>`, which means that you can provide
* only a subset of the properties defined in the `RBTreeOptions` interface.
* This is the constructor function for a Red-Black Tree data structure in TypeScript.
* @param keysOrNodesOrEntries - The `keysOrNodesOrEntries` parameter is an iterable object that can
* contain keys, nodes, or entries. It is used to initialize the RBTree with the provided keys,
* nodes, or entries.
* @param [options] - The `options` parameter is an optional object that can be passed to the
* constructor. It allows you to customize the behavior of the RBTree. It can include properties such
* as `compareKeys`, `compareValues`, `allowDuplicates`, etc. These properties define how the RBTree
* should compare keys and
*/
constructor(keysOrNodesOrEntries = [], options) {
super([], options);
this._Sentinel = new RedBlackTreeNode(NaN);
this._SENTINEL = new RedBlackTreeNode(NaN);
this._size = 0;
this._root = this._Sentinel;
if (keysOrNodesOrEntries)
super.addMany(keysOrNodesOrEntries);
this._root = this.SENTINEL;
if (keysOrNodesOrEntries) {
this.addMany(keysOrNodesOrEntries);
}
}
/**
* The function returns the value of the `_Sentinel` property.
* @returns The method is returning the value of the `_Sentinel` property.
* The function returns the value of the _SENTINEL property.
* @returns The method is returning the value of the `_SENTINEL` property.
*/
get Sentinel() {
return this._Sentinel;
get SENTINEL() {
return this._SENTINEL;
}
/**
* The function returns the root node.
* @returns The root node of the data structure.
* The function returns the root node of a tree or undefined if there is no root.
* @returns The root node of the tree structure, or undefined if there is no root node.
*/

@@ -97,9 +83,9 @@ get root() {

* The function creates a new Red-Black Tree node with the specified key, value, and color.
* @param {K} key - The key parameter is the key value associated with the node. It is used to
* identify and compare nodes in the Red-Black Tree.
* @param {K} key - The key parameter represents the key of the node being created. It is of type K,
* which is a generic type representing the key's data type.
* @param {V} [value] - The `value` parameter is an optional parameter that represents the value
* associated with the node. It is of type `V`, which is a generic type that can be replaced with any
* specific type when using the `createNode` method.
* associated with the key in the node. It is not required and can be omitted if not needed.
* @param {RBTNColor} color - The "color" parameter is used to specify the color of the node in a
* Red-Black Tree. It can be either "RED" or "BLACK". By default, the color is set to "BLACK".
* 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".
* @returns The method is returning a new instance of a RedBlackTreeNode with the specified key,

@@ -112,6 +98,6 @@ * value, and color.

/**
* The function creates a Red-Black Tree with the specified options and returns it.
* @param {RBTreeOptions} [options] - The `options` parameter is an optional object that can be
* passed to the `createTree` function. It is used to customize the behavior of the `RedBlackTree`
* class.
* The function creates a Red-Black Tree with the given options and returns it.
* @param [options] - The `options` parameter is an optional object that contains configuration
* options for creating the Red-Black Tree. It is of type `RBTreeOptions<K>`, where `K` represents
* the type of keys in the tree.
* @returns a new instance of a RedBlackTree object.

@@ -123,9 +109,15 @@ */

/**
* The function `keyValueOrEntryToNode` takes an keyOrNodeOrEntry and converts it into a node object if possible.
* @param keyOrNodeOrEntry - The `keyOrNodeOrEntry` parameter is of type `KeyOrNodeOrEntry<K, V, NODE>`, where:
* @param {V} [value] - The `value` parameter is an optional value that can be passed to the
* `keyValueOrEntryToNode` function. It represents the value associated with the keyOrNodeOrEntry node. If a value
* is provided, it will be used when creating the new node. If no value is provided, the new node
* @returns a node of type NODE or undefined.
* Time Complexity: O(1)
* Space Complexity: O(1)
*/
/**
* Time Complexity: O(1)
* Space Complexity: O(1)
*
* The function `keyValueOrEntryToNode` takes a key, value, or entry and returns a node if it is
* valid, otherwise it returns undefined.
* @param {KeyOrNodeOrEntry<K, V, NODE>} keyOrNodeOrEntry - The key, value, or entry to convert.
* @param {V} [value] - The value associated with the key (if `keyOrNodeOrEntry` is a key).
* @returns {NODE | undefined} - The corresponding Red-Black Tree node, or `undefined` if conversion fails.
*/
keyValueOrEntryToNode(keyOrNodeOrEntry, value) {

@@ -157,6 +149,13 @@ let node;

/**
* The function checks if an keyOrNodeOrEntry is an instance of the RedBlackTreeNode class.
* @param keyOrNodeOrEntry - The `keyOrNodeOrEntry` parameter is of type `KeyOrNodeOrEntry<K, V, NODE>`.
* @returns a boolean value indicating whether the keyOrNodeOrEntry is an instance of the RedBlackTreeNode
* class.
* Time Complexity: O(1)
* Space Complexity: O(1)
* /
/**
* Time Complexity: O(1)
* Space Complexity: O(1)
*
* The function checks if the input is an instance of the RedBlackTreeNode class.
* @param {KeyOrNodeOrEntry<K, V, NODE>} keyOrNodeOrEntry - The object to check.
* @returns {boolean} - `true` if the object is a Red-Black Tree node, `false` otherwise.
*/

@@ -167,2 +166,9 @@ isNode(keyOrNodeOrEntry) {

/**
* Time Complexity: O(1)
* Space Complexity: O(1)
*/
/**
* Time Complexity: O(1)
* Space Complexity: O(1)
*
* The function checks if a given node is a real node in a Red-Black Tree.

@@ -174,3 +180,3 @@ * @param {NODE | undefined} node - The `node` parameter is of type `NODE | undefined`, which means

isRealNode(node) {
if (node === this._Sentinel || node === undefined)
if (node === this._SENTINEL || node === undefined)
return false;

@@ -182,3 +188,2 @@ return node instanceof RedBlackTreeNode;

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

@@ -189,159 +194,18 @@ /**

*
* The `add` function adds a new node to a binary search tree and performs necessary rotations and
* color changes to maintain the red-black tree properties.
* @param keyOrNodeOrEntry - The `keyOrNodeOrEntry` parameter can be either a key, a node, or an
* entry.
* @param {V} [value] - The `value` parameter represents the value associated with the key that is
* being added to the binary search tree.
* @returns The method `add` returns either the newly added node (`NODE`) or `undefined`.
*/
add(keyOrNodeOrEntry, value) {
const newNode = this.keyValueOrEntryToNode(keyOrNodeOrEntry, value);
if (newNode === undefined)
return false;
newNode.left = this._Sentinel;
newNode.right = this._Sentinel;
let y = undefined;
let x = this.root;
while (x !== this._Sentinel) {
y = x;
if (x) {
if (newNode.key < x.key) {
x = x.left;
}
else if (newNode.key > x.key) {
x = x === null || x === void 0 ? void 0 : x.right;
}
else {
if (newNode !== x) {
this._replaceNode(x, newNode);
}
return false;
}
}
}
newNode.parent = y;
if (y === undefined) {
this._setRoot(newNode);
}
else if (newNode.key < y.key) {
y.left = newNode;
}
else {
y.right = newNode;
}
if (newNode.parent === undefined) {
newNode.color = types_1.RBTNColor.BLACK;
this._size++;
return false;
}
if (newNode.parent.parent === undefined) {
this._size++;
return false;
}
this._fixInsert(newNode);
this._size++;
return true;
}
/**
* Time Complexity: O(log n)
* Space Complexity: O(1)
*/
/**
* Time Complexity: O(log n)
* Space Complexity: O(1)
*
* The `delete` function removes a node from a binary tree based on a given identifier and updates
* the tree accordingly.
* @param {ReturnType<C> | null | undefined} identifier - The `identifier` parameter is the value
* that you want to use to identify the node that you want to delete from the binary tree. It can be
* of any type that is returned by the callback function `C`. It can also be `null` or `undefined` if
* you don't want to
* @param {C} callback - The `callback` parameter is a function that takes a node of type `NODE` and
* returns a value of type `ReturnType<C>`. It is used to determine if a node should be deleted based
* on its identifier. The `callback` function is optional and defaults to `this._defaultOneParam
* @returns an array of `BinaryTreeDeleteResult<NODE>`.
*/
delete(identifier, callback = this._defaultOneParamCallback) {
const ans = [];
if (identifier === null)
return ans;
const helper = (node) => {
let z = this._Sentinel;
let x, y;
while (node !== this._Sentinel) {
if (node && callback(node) === identifier) {
z = node;
}
if (node && identifier && callback(node) <= identifier) {
node = node.right;
}
else {
node = node === null || node === void 0 ? void 0 : node.left;
}
}
if (z === this._Sentinel) {
this._size--;
return;
}
y = z;
let yOriginalColor = y.color;
if (z.left === this._Sentinel) {
x = z.right;
this._rbTransplant(z, z.right);
}
else if (z.right === this._Sentinel) {
x = z.left;
this._rbTransplant(z, z.left);
}
else {
y = this.getLeftMost(z.right);
yOriginalColor = y.color;
x = y.right;
if (y.parent === z) {
x.parent = y;
}
else {
this._rbTransplant(y, y.right);
y.right = z.right;
y.right.parent = y;
}
this._rbTransplant(z, y);
y.left = z.left;
y.left.parent = y;
y.color = z.color;
}
if (yOriginalColor === types_1.RBTNColor.BLACK) {
this._fixDelete(x);
}
this._size--;
ans.push({ deleted: z, needBalanced: undefined });
};
helper(this.root);
return ans;
}
/**
* Time Complexity: O(log n)
* Space Complexity: O(1)
*/
/**
* Time Complexity: O(log n)
* Space Complexity: O(1)
*
* The function `getNode` retrieves a single node from a binary tree based on a given identifier and
* The `getNode` function retrieves a node from a Red-Black Tree based on the provided identifier and
* callback function.
* @param {ReturnType<C> | undefined} identifier - The `identifier` parameter is the value used to
* identify the node you want to retrieve. It can be of any type that is the return type of the `C`
* callback function. If the `identifier` is `undefined`, it means you want to retrieve the first
* node that matches the other criteria
* @param {ReturnType<C> | undefined} identifier - The `identifier` parameter is the value or key
* that you want to search for in the binary search tree. It can be of any type that is compatible
* with the type of nodes in the tree.
* @param {C} callback - The `callback` parameter is a function that will be called for each node in
* the binary tree. It is used to determine if a node matches the given identifier. The `callback`
* function should take a single parameter of type `NODE` (the type of the nodes in the binary tree) and
* @param {K | NODE | undefined} beginRoot - The `beginRoot` parameter is the starting point for
* searching for a node in a binary tree. It can be either a key value or a node object. If it is not
* provided, the search will start from the root of the binary tree.
* @param iterationType - The `iterationType` parameter is a variable that determines the type of
* iteration to be performed when searching for nodes in the binary tree. It is used in the
* `getNodes` method, which is called within the `getNode` method.
* @returns a value of type `NODE`, `null`, or `undefined`.
* the tree. It is used to determine whether a node matches the given identifier. The `callback`
* function should take a node as its parameter and return a value that can be compared to the
* `identifier` parameter.
* @param beginRoot - The `beginRoot` parameter is the starting point for the search in the binary
* search tree. It can be either a key or a node. If it is a key, it will be converted to a node
* using the `ensureNode` method. If it is not provided, the `root`
* @param iterationType - The `iterationType` parameter is used to specify the type of iteration to
* be performed when searching for nodes in the binary search tree. It is an optional parameter and
* its default value is taken from the `iterationType` property of the class.
* @returns The method is returning a value of type `NODE | null | undefined`.
*/

@@ -363,6 +227,7 @@ getNode(identifier, callback = this._defaultOneParamCallback, beginRoot = this.root, iterationType = this.iterationType) {

*
* The "clear" function sets the root node to the sentinel node and resets the size to 0.
* The "clear" function sets the root node of a data structure to a sentinel value and resets the
* size counter to zero.
*/
clear() {
this._root = this._Sentinel;
this._root = this.SENTINEL;
this._size = 0;

@@ -378,23 +243,105 @@ }

*
* The function returns the predecessor of a given node in a red-black tree.
* @param {RedBlackTreeNode} x - The parameter `x` is of type `RedBlackTreeNode`, which represents a node in a
* Red-Black Tree.
* @returns the predecessor of the given RedBlackTreeNode 'x'.
* The function adds a new node to a Red-Black Tree data structure and returns a boolean indicating
* whether the operation was successful.
* @param keyOrNodeOrEntry - The `keyOrNodeOrEntry` parameter can be either a key, a node, or an
* entry.
* @param {V} [value] - The `value` parameter is the value associated with the key that is being
* added to the tree.
* @returns The method is returning a boolean value. It returns true if the node was successfully
* added or updated, and false otherwise.
*/
getPredecessor(x) {
if (this.isRealNode(x.left)) {
return this.getRightMost(x.left);
add(keyOrNodeOrEntry, value) {
const newNode = this.keyValueOrEntryToNode(keyOrNodeOrEntry, value);
if (!this.isRealNode(newNode))
return false;
const insertStatus = this._insert(newNode);
if (insertStatus === 'inserted') {
// Ensure the root is black
if (this.isRealNode(this._root)) {
this._root.color = types_1.RBTNColor.BLACK;
}
else {
return false;
}
this._size++;
return true;
}
let y = x.parent;
while (this.isRealNode(y) && x === y.left) {
x = y;
y = y.parent;
else
return insertStatus === 'updated';
}
/**
* Time Complexity: O(log n)
* Space Complexity: O(1)
*/
/**
* Time Complexity: O(log n)
* Space Complexity: O(1)
*
* The function `delete` in a binary tree class deletes a node from the tree and fixes the tree if
* necessary.
* @param {ReturnType<C> | null | undefined} identifier - The `identifier` parameter is the
* identifier of the node that needs to be deleted from the binary tree. It can be of any type that
* is returned by the callback function `C`. It can also be `null` or `undefined` if the node to be
* deleted is not found.
* @param {C} callback - The `callback` parameter is a function that is used to retrieve a node from
* the binary tree based on its identifier. It is an optional parameter and if not provided, the
* `_defaultOneParamCallback` function is used as the default callback. The callback function should
* return the identifier of the node to
* @returns an array of BinaryTreeDeleteResult<NODE> objects.
*/
delete(identifier, callback = this._defaultOneParamCallback) {
if (identifier === null)
return [];
const results = [];
const nodeToDelete = this.isRealNode(identifier) ? identifier : this.getNode(identifier, callback);
if (!nodeToDelete) {
return results;
}
return y;
let originalColor = nodeToDelete.color;
let replacementNode;
if (!this.isRealNode(nodeToDelete.left)) {
replacementNode = nodeToDelete.right;
this._transplant(nodeToDelete, nodeToDelete.right);
}
else if (!this.isRealNode(nodeToDelete.right)) {
replacementNode = nodeToDelete.left;
this._transplant(nodeToDelete, nodeToDelete.left);
}
else {
const successor = this.getLeftMost(nodeToDelete.right);
if (successor) {
originalColor = successor.color;
replacementNode = successor.right;
if (successor.parent === nodeToDelete) {
if (this.isRealNode(replacementNode)) {
replacementNode.parent = successor;
}
}
else {
this._transplant(successor, successor.right);
successor.right = nodeToDelete.right;
if (this.isRealNode(successor.right)) {
successor.right.parent = successor;
}
}
this._transplant(nodeToDelete, successor);
successor.left = nodeToDelete.left;
if (this.isRealNode(successor.left)) {
successor.left.parent = successor;
}
successor.color = nodeToDelete.color;
}
}
this._size--;
// If the original color was black, fix the tree
if (originalColor === types_1.RBTNColor.BLACK) {
this._deleteFixup(replacementNode);
}
results.push({ deleted: nodeToDelete, needBalanced: undefined });
return results;
}
/**
* The function sets the root node of a tree structure and updates the parent property of the new
* root node.
* @param {NODE} v - The parameter "v" is of type "NODE", which represents a node in a data
* structure.
* The function sets the root of a tree-like structure and updates the parent property of the new
* root.
* @param {NODE | undefined} v - v is a parameter of type NODE or undefined.
*/

@@ -415,26 +362,61 @@ _setRoot(v) {

*
* The function performs a left rotation on a binary tree node.
* @param {RedBlackTreeNode} x - The parameter `x` is of type `NODE`, which likely represents a node in a binary tree.
* The function replaces an old node with a new node while preserving the color of the old node.
* @param {NODE} oldNode - The `oldNode` parameter represents the node that needs to be replaced in
* the data structure.
* @param {NODE} newNode - The `newNode` parameter is the new node that will replace the old node in
* the data structure.
* @returns The method is returning the result of calling the `_replaceNode` method from the
* superclass, with the `oldNode` and `newNode` parameters.
*/
_leftRotate(x) {
if (x.right) {
const y = x.right;
x.right = y.left;
if (y.left !== this._Sentinel) {
if (y.left)
y.left.parent = x;
_replaceNode(oldNode, newNode) {
newNode.color = oldNode.color;
return super._replaceNode(oldNode, newNode);
}
/**
* Time Complexity: O(log n)
* Space Complexity: O(1)
*/
/**
* Time Complexity: O(log n)
* Space Complexity: O(1)
*
* The `_insert` function inserts or updates a node in a binary search tree and performs necessary
* fix-ups to maintain the red-black tree properties.
* @param {NODE} node - The `node` parameter represents the node that needs to be inserted into a
* binary search tree. It contains a `key` property that is used to determine the position of the
* node in the tree.
* @returns {'inserted' | 'updated'} - The result of the insertion.
*/
_insert(node) {
var _a, _b;
let current = this.root;
let parent = undefined;
while (this.isRealNode(current)) {
parent = current;
if (node.key < current.key) {
current = (_a = current.left) !== null && _a !== void 0 ? _a : this.SENTINEL;
}
y.parent = x.parent;
if (x.parent === undefined) {
this._setRoot(y);
else if (node.key > current.key) {
current = (_b = current.right) !== null && _b !== void 0 ? _b : this.SENTINEL;
}
else if (x === x.parent.left) {
x.parent.left = y;
}
else {
x.parent.right = y;
this._replaceNode(current, node);
return 'updated';
}
y.left = x;
x.parent = y;
}
node.parent = parent;
if (!parent) {
this._setRoot(node);
}
else if (node.key < parent.key) {
parent.left = node;
}
else {
parent.right = node;
}
node.left = this.SENTINEL;
node.right = this.SENTINEL;
node.color = types_1.RBTNColor.RED;
this._insertFixup(node);
return 'inserted';
}

@@ -449,27 +431,20 @@ /**

*
* The function performs a right rotation on a red-black tree node.
* @param {RedBlackTreeNode} x - x is a RedBlackTreeNode, which represents the node that needs to be right
* rotated.
* The function `_transplant` is used to replace a node `u` with another node `v` in a binary tree.
* @param {NODE} u - The parameter "u" represents a node in a binary tree.
* @param {NODE | undefined} v - The parameter `v` is of type `NODE | undefined`, which means it can
* either be a `NODE` object or `undefined`.
*/
_rightRotate(x) {
if (x.left) {
const y = x.left;
x.left = y.right;
if (y.right !== this._Sentinel) {
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;
_transplant(u, v) {
if (!u.parent) {
this._setRoot(v);
}
else if (u === u.parent.left) {
u.parent.left = v;
}
else {
u.parent.right = v;
}
if (v) {
v.parent = u.parent;
}
}

@@ -484,58 +459,64 @@ /**

*
* The `_fixInsert` function is used to fix the red-black tree after an insertion operation.
* @param {RedBlackTreeNode} k - The parameter `k` is a RedBlackTreeNode object, which represents a node in a
* red-black tree.
* The `_insertFixup` function is used to fix the Red-Black Tree after inserting a new node.
* @param {NODE | undefined} z - The parameter `z` represents a node in the Red-Black Tree. It can
* either be a valid node object or `undefined`.
*/
_fixInsert(k) {
let u;
while (k.parent && k.parent.color === types_1.RBTNColor.RED) {
if (k.parent.parent && k.parent === k.parent.parent.right) {
u = k.parent.parent.left;
if (u && u.color === types_1.RBTNColor.RED) {
// Delay color flip
k.parent.color = types_1.RBTNColor.BLACK;
u.color = types_1.RBTNColor.BLACK;
k.parent.parent.color = types_1.RBTNColor.RED;
k = k.parent.parent;
_insertFixup(z) {
var _a, _b, _c, _d;
// 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) {
// Check if the parent of z is the left child of its parent
if (z.parent === ((_b = z.parent.parent) === null || _b === void 0 ? void 0 : _b.left)) {
// Case 1: The uncle (y) of z is red
const y = z.parent.parent.right;
if ((y === null || y === void 0 ? void 0 : y.color) === types_1.RBTNColor.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;
// Move up the tree to continue fixing
z = z.parent.parent;
}
else {
if (k === k.parent.left) {
k = k.parent;
this._rightRotate(k);
// Case 2: The uncle (y) of z is black, and z is a right child
if (z === z.parent.right) {
// Perform a left rotation to transform the case into Case 3
z = z.parent;
this._leftRotate(z);
}
// Check color before rotation
if (k.parent.color === types_1.RBTNColor.RED) {
k.parent.color = types_1.RBTNColor.BLACK;
k.parent.parent.color = types_1.RBTNColor.RED;
// Case 3: The uncle (y) of z is black, and z is a left child
// Adjust colors and perform a right rotation
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;
this._rightRotate(z.parent.parent);
}
this._leftRotate(k.parent.parent);
}
}
else {
u = k.parent.parent.right;
if (u && u.color === types_1.RBTNColor.RED) {
// Delay color flip
k.parent.color = types_1.RBTNColor.BLACK;
u.color = types_1.RBTNColor.BLACK;
k.parent.parent.color = types_1.RBTNColor.RED;
k = k.parent.parent;
// Symmetric case for the right child (left and right exchanged)
// Follow the same logic as above with left and right exchanged
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;
z = z.parent.parent;
}
else {
if (k === k.parent.right) {
k = k.parent;
this._leftRotate(k);
if (z === z.parent.left) {
z = z.parent;
this._rightRotate(z);
}
// Check color before rotation
if (k.parent.color === types_1.RBTNColor.RED) {
k.parent.color = types_1.RBTNColor.BLACK;
k.parent.parent.color = types_1.RBTNColor.RED;
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;
this._leftRotate(z.parent.parent);
}
this._rightRotate(k.parent.parent);
}
}
if (k === this.root) {
break;
}
}
this.root.color = types_1.RBTNColor.BLACK;
// Ensure that the root is black after fixing
if (this.isRealNode(this._root))
this._root.color = types_1.RBTNColor.BLACK;
}

@@ -550,68 +531,83 @@ /**

*
* The function `_fixDelete` is used to fix the red-black tree after a node deletion.
* @param {RedBlackTreeNode} x - The parameter `x` represents a node in a Red-Black Tree (RBT).
* The `_deleteFixup` function is used to fix the red-black tree after a node deletion by adjusting
* the colors and performing rotations.
* @param {NODE | undefined} node - The `node` parameter represents a node in a Red-Black Tree data
* structure. It can be either a valid node object or `undefined`.
* @returns The function does not return any value. It has a return type of `void`.
*/
_fixDelete(x) {
let s;
while (x !== this.root && x.color === types_1.RBTNColor.BLACK) {
if (x.parent && x === x.parent.left) {
s = x.parent.right;
if (s.color === 1) {
s.color = types_1.RBTNColor.BLACK;
x.parent.color = types_1.RBTNColor.RED;
this._leftRotate(x.parent);
s = x.parent.right;
_deleteFixup(node) {
var _a, _b, _c, _d;
// Early exit condition
if (!node || node === this.root || node.color === types_1.RBTNColor.BLACK) {
if (node) {
node.color = types_1.RBTNColor.BLACK; // Ensure the final node is black
}
return;
}
while (node && node !== this.root && node.color === types_1.RBTNColor.BLACK) {
const parent = node.parent;
if (!parent) {
break; // Ensure the loop terminates if there's an issue with the tree structure
}
if (node === parent.left) {
let sibling = parent.right;
// 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;
this._leftRotate(parent);
sibling = parent.right;
}
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;
x = x.parent;
// 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 (sibling)
sibling.color = types_1.RBTNColor.RED;
node = parent;
}
else {
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;
this._rightRotate(s);
s = x.parent.right;
}
if (s)
s.color = x.parent.color;
x.parent.color = types_1.RBTNColor.BLACK;
if (s && s.right)
s.right.color = types_1.RBTNColor.BLACK;
this._leftRotate(x.parent);
x = this.root;
// Case 4: Adjust colors and perform a right rotation
if (sibling === null || sibling === void 0 ? void 0 : sibling.left)
sibling.left.color = types_1.RBTNColor.BLACK;
if (sibling)
sibling.color = parent.color;
parent.color = types_1.RBTNColor.BLACK;
this._rightRotate(parent);
node = this.root;
}
}
else {
s = x.parent.left;
if (s.color === 1) {
s.color = types_1.RBTNColor.BLACK;
x.parent.color = types_1.RBTNColor.RED;
this._rightRotate(x.parent);
s = x.parent.left;
// Symmetric case for the right child (left and right exchanged)
let sibling = parent.left;
// 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 (parent)
parent.color = types_1.RBTNColor.RED;
this._rightRotate(parent);
if (parent)
sibling = parent.left;
}
if (s && s.right && s.right.color === types_1.RBTNColor.BLACK && s.right.color === types_1.RBTNColor.BLACK) {
s.color = types_1.RBTNColor.RED;
x = x.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 (sibling)
sibling.color = types_1.RBTNColor.RED;
node = parent;
}
else {
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;
this._leftRotate(s);
s = x.parent.left;
}
if (s)
s.color = x.parent.color;
x.parent.color = types_1.RBTNColor.BLACK;
if (s && s.left)
s.left.color = types_1.RBTNColor.BLACK;
this._rightRotate(x.parent);
x = this.root;
// Case 4: Adjust colors and perform a left rotation
if (sibling === null || sibling === void 0 ? void 0 : sibling.right)
sibling.right.color = types_1.RBTNColor.BLACK;
if (sibling)
sibling.color = parent.color;
if (parent)
parent.color = types_1.RBTNColor.BLACK;
this._leftRotate(parent);
node = this.root;
}
}
}
x.color = types_1.RBTNColor.BLACK;
// Ensure that the final node (possibly the root) is black
if (node) {
node.color = types_1.RBTNColor.BLACK;
}
}

@@ -626,32 +622,65 @@ /**

*
* The function `_rbTransplant` replaces one node in a red-black tree with another node.
* @param {RedBlackTreeNode} u - The parameter "u" represents a RedBlackTreeNode object.
* @param {RedBlackTreeNode} v - The parameter "v" is a RedBlackTreeNode object.
* The `_leftRotate` function performs a left rotation on a given node in a binary tree.
* @param {NODE | undefined} x - The parameter `x` is of type `NODE | undefined`. It represents a
* node in a binary tree or `undefined` if there is no node.
* @returns void, which means it does not return any value.
*/
_rbTransplant(u, v) {
if (u.parent === undefined) {
this._setRoot(v);
_leftRotate(x) {
if (!x || !x.right) {
return;
}
else if (u === u.parent.left) {
u.parent.left = v;
const y = x.right;
x.right = y.left;
if (this.isRealNode(y.left)) {
y.left.parent = x;
}
y.parent = x.parent;
if (!x.parent) {
this._setRoot(y);
}
else if (x === x.parent.left) {
x.parent.left = y;
}
else {
u.parent.right = v;
x.parent.right = y;
}
v.parent = u.parent;
y.left = x;
x.parent = y;
}
/**
* The function replaces an old node with a new node while preserving the color of the old node.
* @param {NODE} oldNode - The `oldNode` parameter represents the node that needs to be replaced in a
* data structure. It is of type `NODE`, which is the type of the nodes in the data structure.
* @param {NODE} newNode - The `newNode` parameter is the node that will replace the `oldNode` in the
* data structure.
* @returns The method is returning the result of calling the `_replaceNode` method from the
* superclass, passing in the `oldNode` and `newNode` as arguments.
* Time Complexity: O(1)
* Space Complexity: O(1)
*/
_replaceNode(oldNode, newNode) {
newNode.color = oldNode.color;
return super._replaceNode(oldNode, newNode);
/**
* Time Complexity: O(1)
* Space Complexity: O(1)
*
* The `_rightRotate` function performs a right rotation on a given node in a binary tree.
* @param {NODE | undefined} y - The parameter `y` is of type `NODE | undefined`. It represents a
* node in a binary tree or `undefined` if there is no node.
* @returns void, which means it does not return any value.
*/
_rightRotate(y) {
if (!y || !y.left) {
return;
}
const x = y.left;
y.left = x.right;
if (this.isRealNode(x.right)) {
x.right.parent = y;
}
x.parent = y.parent;
if (!y.parent) {
this._setRoot(x);
}
else if (y === y.parent.left) {
y.parent.left = x;
}
else {
y.parent.right = x;
}
x.right = y;
y.parent = x;
}
}
exports.RedBlackTree = RedBlackTree;

1

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

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

get count(): number;
getMutableCount(): number;
/**

@@ -56,0 +57,0 @@ * The function creates a new TreeMultiMapNode object with the specified key, value, and count.

160

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

@@ -61,6 +61,8 @@ "use strict";

get count() {
return this._count;
}
getMutableCount() {
let sum = 0;
this.dfs(node => (sum += node.count));
return sum;
// return this._count;
}

@@ -158,10 +160,11 @@ /**

const newNode = this.keyValueOrEntryToNode(keyOrNodeOrEntry, value, count);
if (newNode === undefined)
const orgCount = (newNode === null || newNode === void 0 ? void 0 : newNode.count) || 0;
const isSuccessAdded = super.add(newNode);
if (isSuccessAdded) {
this._count += orgCount;
return true;
}
else {
return false;
const orgNodeCount = (newNode === null || newNode === void 0 ? void 0 : newNode.count) || 0;
const inserted = super.add(newNode);
if (inserted) {
this._count += orgNodeCount;
}
return true;
}

@@ -193,82 +196,87 @@ /**

delete(identifier, callback = this._defaultOneParamCallback, ignoreCount = false) {
const deleteResults = [];
if (identifier === null)
return deleteResults;
// Helper function to perform deletion
const deleteHelper = (node) => {
// Initialize targetNode to the sentinel node
let targetNode = this._Sentinel;
let currentNode;
// Find the node to be deleted based on the identifier
while (node !== this._Sentinel) {
// Update targetNode if the current node matches the identifier
if (node && callback(node) === identifier) {
targetNode = node;
}
// Move to the right or left based on the comparison with the identifier
if (node && identifier && callback(node) <= identifier) {
node = node.right;
}
else {
node = node === null || node === void 0 ? void 0 : node.left;
}
return [];
const results = [];
const nodeToDelete = this.isRealNode(identifier) ? identifier : this.getNode(identifier, callback);
if (!nodeToDelete) {
return results;
}
let originalColor = nodeToDelete.color;
let replacementNode;
if (!this.isRealNode(nodeToDelete.left)) {
replacementNode = nodeToDelete.right;
if (ignoreCount || nodeToDelete.count <= 1) {
this._transplant(nodeToDelete, nodeToDelete.right);
this._count -= nodeToDelete.count;
}
// If the target node is not found, decrement size and return
if (targetNode === this._Sentinel) {
return;
else {
nodeToDelete.count--;
this._count--;
results.push({ deleted: nodeToDelete, needBalanced: undefined });
return results;
}
if (ignoreCount || targetNode.count <= 1) {
// Store the parent of the target node and its original color
let parentNode = targetNode;
let parentNodeOriginalColor = parentNode.color;
// Handle deletion based on the number of children of the target node
if (targetNode.left === this._Sentinel) {
// Target node has no left child - deletion case 1
currentNode = targetNode.right;
this._rbTransplant(targetNode, targetNode.right);
}
else if (!this.isRealNode(nodeToDelete.right)) {
replacementNode = nodeToDelete.left;
if (ignoreCount || nodeToDelete.count <= 1) {
this._transplant(nodeToDelete, nodeToDelete.left);
this._count -= nodeToDelete.count;
}
else {
nodeToDelete.count--;
this._count--;
results.push({ deleted: nodeToDelete, needBalanced: undefined });
return results;
}
}
else {
const successor = this.getLeftMost(nodeToDelete.right);
if (successor) {
originalColor = successor.color;
replacementNode = successor.right;
if (successor.parent === nodeToDelete) {
if (this.isRealNode(replacementNode)) {
replacementNode.parent = successor;
}
}
else if (targetNode.right === this._Sentinel) {
// Target node has no right child - deletion case 2
currentNode = targetNode.left;
this._rbTransplant(targetNode, targetNode.left);
}
else {
// Target node has both left and right children - deletion case 3
parentNode = this.getLeftMost(targetNode.right);
parentNodeOriginalColor = parentNode.color;
currentNode = parentNode.right;
if (parentNode.parent === targetNode) {
// Target node's right child becomes its parent's left child
currentNode.parent = parentNode;
if (ignoreCount || nodeToDelete.count <= 1) {
this._transplant(successor, successor.right);
this._count -= nodeToDelete.count;
}
else {
// Replace parentNode with its right child and update connections
this._rbTransplant(parentNode, parentNode.right);
parentNode.right = targetNode.right;
parentNode.right.parent = parentNode;
nodeToDelete.count--;
this._count--;
results.push({ deleted: nodeToDelete, needBalanced: undefined });
return results;
}
// Replace the target node with its in-order successor
this._rbTransplant(targetNode, parentNode);
parentNode.left = targetNode.left;
parentNode.left.parent = parentNode;
parentNode.color = targetNode.color;
successor.right = nodeToDelete.right;
if (this.isRealNode(successor.right)) {
successor.right.parent = successor;
}
}
// Fix the Red-Black Tree properties after deletion
if (parentNodeOriginalColor === types_1.RBTNColor.BLACK) {
this._fixDelete(currentNode);
if (ignoreCount || nodeToDelete.count <= 1) {
this._transplant(nodeToDelete, successor);
this._count -= nodeToDelete.count;
}
// Decrement the size and store information about the deleted node
this._size--;
this._count -= targetNode.count;
deleteResults.push({ deleted: targetNode, needBalanced: undefined });
else {
nodeToDelete.count--;
this._count--;
results.push({ deleted: nodeToDelete, needBalanced: undefined });
return results;
}
successor.left = nodeToDelete.left;
if (this.isRealNode(successor.left)) {
successor.left.parent = successor;
}
successor.color = nodeToDelete.color;
}
else {
targetNode.count--;
this._count--;
}
};
// Call the helper function with the root of the tree
deleteHelper(this.root);
// Return the result array
return deleteResults;
}
this._size--;
// If the original color was black, fix the tree
if (originalColor === types_1.RBTNColor.BLACK) {
this._deleteFixup(replacementNode);
}
results.push({ deleted: nodeToDelete, needBalanced: undefined });
return results;
}

@@ -275,0 +283,0 @@ /**

4

package.json
{
"name": "min-heap-typed",
"version": "1.50.5",
"version": "1.50.6",
"description": "Min Heap. Javascript & Typescript Data Structure.",

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

"dependencies": {
"data-structure-typed": "^1.50.4"
"data-structure-typed": "^1.50.6"
}
}

822

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

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

/**
* data-structure-typed
*
* @author Tyler Zeng
* @copyright Copyright (c) 2022 Tyler Zeng <zrwusa@gmail.com>
* @license MIT License
*/
import {
import type {
BinaryTreeDeleteResult,

@@ -14,3 +6,2 @@ BSTNKeyOrNode,

KeyOrNodeOrEntry,
RBTNColor,
RBTreeOptions,

@@ -20,2 +11,3 @@ RedBlackTreeNested,

} from '../../types';
import { RBTNColor } from '../../types';
import { BST, BSTNode } from './bst';

@@ -49,3 +41,3 @@ import { IBinaryTree } from '../../interfaces';

* The function returns the color value of a variable.
* @returns The color value stored in the protected variable `_color`.
* @returns The color value stored in the private variable `_color`.
*/

@@ -65,9 +57,2 @@ get color(): RBTNColor {

/**
* 1. Each node is either red or black.
* 2. The root node is always black.
* 3. Leaf nodes are typically Sentinel nodes and are considered black.
* 4. Red nodes must have black children.
* 5. Black balance: Every path from any node to each of its leaf nodes contains the same number of black nodes.
*/
export class RedBlackTree<

@@ -82,11 +67,10 @@ K = any,

/**
* This is the constructor function for a Red-Black Tree data structure in TypeScript, which
* initializes the tree with optional nodes and options.
* @param [keysOrNodesOrEntries] - The `keysOrNodesOrEntries` parameter is an optional iterable of `KeyOrNodeOrEntry<K, V, NODE>`
* objects. It represents the initial nodes that will be added to the RBTree during its
* construction. If this parameter is provided, the `addMany` method is called to add all the
* nodes to the
* @param [options] - The `options` parameter is an optional object that allows you to customize the
* behavior of the RBTree. It is of type `Partial<RBTreeOptions>`, which means that you can provide
* only a subset of the properties defined in the `RBTreeOptions` interface.
* This is the constructor function for a Red-Black Tree data structure in TypeScript.
* @param keysOrNodesOrEntries - The `keysOrNodesOrEntries` parameter is an iterable object that can
* contain keys, nodes, or entries. It is used to initialize the RBTree with the provided keys,
* nodes, or entries.
* @param [options] - The `options` parameter is an optional object that can be passed to the
* constructor. It allows you to customize the behavior of the RBTree. It can include properties such
* as `compareKeys`, `compareValues`, `allowDuplicates`, etc. These properties define how the RBTree
* should compare keys and
*/

@@ -96,23 +80,26 @@ constructor(keysOrNodesOrEntries: Iterable<KeyOrNodeOrEntry<K, V, NODE>> = [], options?: RBTreeOptions<K>) {

this._root = this._Sentinel;
if (keysOrNodesOrEntries) super.addMany(keysOrNodesOrEntries);
this._root = this.SENTINEL;
if (keysOrNodesOrEntries) {
this.addMany(keysOrNodesOrEntries);
}
}
protected _Sentinel: NODE = new RedBlackTreeNode<K, V>(NaN as K) as unknown as NODE;
protected _SENTINEL: NODE = new RedBlackTreeNode<K, V>(NaN as K) as unknown as NODE;
/**
* The function returns the value of the `_Sentinel` property.
* @returns The method is returning the value of the `_Sentinel` property.
* The function returns the value of the _SENTINEL property.
* @returns The method is returning the value of the `_SENTINEL` property.
*/
get Sentinel(): NODE {
return this._Sentinel;
get SENTINEL(): NODE {
return this._SENTINEL;
}
protected _root: NODE;
protected _root: NODE | undefined;
/**
* The function returns the root node.
* @returns The root node of the data structure.
* The function returns the root node of a tree or undefined if there is no root.
* @returns The root node of the tree structure, or undefined if there is no root node.
*/
get root(): NODE {
get root(): NODE | undefined {
return this._root;

@@ -133,9 +120,9 @@ }

* The function creates a new Red-Black Tree node with the specified key, value, and color.
* @param {K} key - The key parameter is the key value associated with the node. It is used to
* identify and compare nodes in the Red-Black Tree.
* @param {K} key - The key parameter represents the key of the node being created. It is of type K,
* which is a generic type representing the key's data type.
* @param {V} [value] - The `value` parameter is an optional parameter that represents the value
* associated with the node. It is of type `V`, which is a generic type that can be replaced with any
* specific type when using the `createNode` method.
* associated with the key in the node. It is not required and can be omitted if not needed.
* @param {RBTNColor} color - The "color" parameter is used to specify the color of the node in a
* Red-Black Tree. It can be either "RED" or "BLACK". By default, the color is set to "BLACK".
* 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".
* @returns The method is returning a new instance of a RedBlackTreeNode with the specified key,

@@ -149,6 +136,6 @@ * value, and color.

/**
* The function creates a Red-Black Tree with the specified options and returns it.
* @param {RBTreeOptions} [options] - The `options` parameter is an optional object that can be
* passed to the `createTree` function. It is used to customize the behavior of the `RedBlackTree`
* class.
* The function creates a Red-Black Tree with the given options and returns it.
* @param [options] - The `options` parameter is an optional object that contains configuration
* options for creating the Red-Black Tree. It is of type `RBTreeOptions<K>`, where `K` represents
* the type of keys in the tree.
* @returns a new instance of a RedBlackTree object.

@@ -164,9 +151,16 @@ */

/**
* The function `keyValueOrEntryToNode` takes an keyOrNodeOrEntry and converts it into a node object if possible.
* @param keyOrNodeOrEntry - The `keyOrNodeOrEntry` parameter is of type `KeyOrNodeOrEntry<K, V, NODE>`, where:
* @param {V} [value] - The `value` parameter is an optional value that can be passed to the
* `keyValueOrEntryToNode` function. It represents the value associated with the keyOrNodeOrEntry node. If a value
* is provided, it will be used when creating the new node. If no value is provided, the new node
* @returns a node of type NODE or undefined.
* Time Complexity: O(1)
* Space Complexity: O(1)
*/
/**
* Time Complexity: O(1)
* Space Complexity: O(1)
*
* The function `keyValueOrEntryToNode` takes a key, value, or entry and returns a node if it is
* valid, otherwise it returns undefined.
* @param {KeyOrNodeOrEntry<K, V, NODE>} keyOrNodeOrEntry - The key, value, or entry to convert.
* @param {V} [value] - The value associated with the key (if `keyOrNodeOrEntry` is a key).
* @returns {NODE | undefined} - The corresponding Red-Black Tree node, or `undefined` if conversion fails.
*/
override keyValueOrEntryToNode(keyOrNodeOrEntry: KeyOrNodeOrEntry<K, V, NODE>, value?: V): NODE | undefined {

@@ -195,6 +189,13 @@ let node: NODE | undefined;

/**
* The function checks if an keyOrNodeOrEntry is an instance of the RedBlackTreeNode class.
* @param keyOrNodeOrEntry - The `keyOrNodeOrEntry` parameter is of type `KeyOrNodeOrEntry<K, V, NODE>`.
* @returns a boolean value indicating whether the keyOrNodeOrEntry is an instance of the RedBlackTreeNode
* class.
* Time Complexity: O(1)
* Space Complexity: O(1)
* /
/**
* Time Complexity: O(1)
* Space Complexity: O(1)
*
* The function checks if the input is an instance of the RedBlackTreeNode class.
* @param {KeyOrNodeOrEntry<K, V, NODE>} keyOrNodeOrEntry - The object to check.
* @returns {boolean} - `true` if the object is a Red-Black Tree node, `false` otherwise.
*/

@@ -206,2 +207,10 @@ override isNode(keyOrNodeOrEntry: KeyOrNodeOrEntry<K, V, NODE>): keyOrNodeOrEntry is NODE {

/**
* Time Complexity: O(1)
* Space Complexity: O(1)
*/
/**
* Time Complexity: O(1)
* Space Complexity: O(1)
*
* The function checks if a given node is a real node in a Red-Black Tree.

@@ -213,3 +222,3 @@ * @param {NODE | undefined} node - The `node` parameter is of type `NODE | undefined`, which means

override isRealNode(node: NODE | undefined): node is NODE {
if (node === this._Sentinel || node === undefined) return false;
if (node === this._SENTINEL || node === undefined) return false;
return node instanceof RedBlackTreeNode;

@@ -221,3 +230,2 @@ }

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

@@ -229,59 +237,81 @@

*
* The `add` function adds a new node to a binary search tree and performs necessary rotations and
* color changes to maintain the red-black tree properties.
* The `getNode` function retrieves a node from a Red-Black Tree based on the provided identifier and
* callback function.
* @param {ReturnType<C> | undefined} identifier - The `identifier` parameter is the value or key
* that you want to search for in the binary search tree. It can be of any type that is compatible
* with the type of nodes in the tree.
* @param {C} callback - The `callback` parameter is a function that will be called for each node in
* the tree. It is used to determine whether a node matches the given identifier. The `callback`
* function should take a node as its parameter and return a value that can be compared to the
* `identifier` parameter.
* @param beginRoot - The `beginRoot` parameter is the starting point for the search in the binary
* search tree. It can be either a key or a node. If it is a key, it will be converted to a node
* using the `ensureNode` method. If it is not provided, the `root`
* @param iterationType - The `iterationType` parameter is used to specify the type of iteration to
* be performed when searching for nodes in the binary search tree. It is an optional parameter and
* its default value is taken from the `iterationType` property of the class.
* @returns The method is returning a value of type `NODE | null | undefined`.
*/
override getNode<C extends BTNCallback<NODE>>(
identifier: ReturnType<C> | undefined,
callback: C = this._defaultOneParamCallback as C,
beginRoot: BSTNKeyOrNode<K, NODE> = this.root,
iterationType = this.iterationType
): NODE | null | undefined {
if ((identifier as any) instanceof RedBlackTreeNode) callback = (node => node) as C;
beginRoot = this.ensureNode(beginRoot);
return this.getNodes(identifier, callback, true, beginRoot, iterationType)[0] ?? undefined;
}
/**
* Time Complexity: O(1)
* Space Complexity: O(1)
*/
/**
* Time Complexity: O(1)
* Space Complexity: O(1)
*
* The "clear" function sets the root node of a data structure to a sentinel value and resets the
* size counter to zero.
*/
override clear() {
this._root = this.SENTINEL;
this._size = 0;
}
/**
* Time Complexity: O(log n)
* Space Complexity: O(1)
*/
/**
* Time Complexity: O(log n)
* Space Complexity: O(1)
*
* The function adds a new node to a Red-Black Tree data structure and returns a boolean indicating
* whether the operation was successful.
* @param keyOrNodeOrEntry - The `keyOrNodeOrEntry` parameter can be either a key, a node, or an
* entry.
* @param {V} [value] - The `value` parameter represents the value associated with the key that is
* being added to the binary search tree.
* @returns The method `add` returns either the newly added node (`NODE`) or `undefined`.
* @param {V} [value] - The `value` parameter is the value associated with the key that is being
* added to the tree.
* @returns The method is returning a boolean value. It returns true if the node was successfully
* added or updated, and false otherwise.
*/
override add(keyOrNodeOrEntry: KeyOrNodeOrEntry<K, V, NODE>, value?: V): boolean {
const newNode = this.keyValueOrEntryToNode(keyOrNodeOrEntry, value);
if (newNode === undefined) return false;
if (!this.isRealNode(newNode)) return false;
newNode.left = this._Sentinel;
newNode.right = this._Sentinel;
const insertStatus = this._insert(newNode);
let y: NODE | undefined = undefined;
let x: NODE | undefined = this.root;
while (x !== this._Sentinel) {
y = x;
if (x) {
if (newNode.key < x.key) {
x = x.left;
} else if (newNode.key > x.key) {
x = x?.right;
} else {
if (newNode !== x) {
this._replaceNode(x, newNode);
}
return false;
}
if (insertStatus === 'inserted') {
// Ensure the root is black
if (this.isRealNode(this._root)) {
this._root.color = RBTNColor.BLACK;
} else {
return false;
}
}
newNode.parent = y;
if (y === undefined) {
this._setRoot(newNode);
} else if (newNode.key < y.key) {
y.left = newNode;
} else {
y.right = newNode;
}
if (newNode.parent === undefined) {
newNode.color = RBTNColor.BLACK;
this._size++;
return false;
}
if (newNode.parent.parent === undefined) {
this._size++;
return false;
}
this._fixInsert(newNode);
this._size++;
return true;
return true;
} else return insertStatus === 'updated';
}

@@ -298,109 +328,84 @@

*
* The `delete` function removes a node from a binary tree based on a given identifier and updates
* the tree accordingly.
* @param {ReturnType<C> | null | undefined} identifier - The `identifier` parameter is the value
* that you want to use to identify the node that you want to delete from the binary tree. It can be
* of any type that is returned by the callback function `C`. It can also be `null` or `undefined` if
* you don't want to
* @param {C} callback - The `callback` parameter is a function that takes a node of type `NODE` and
* returns a value of type `ReturnType<C>`. It is used to determine if a node should be deleted based
* on its identifier. The `callback` function is optional and defaults to `this._defaultOneParam
* @returns an array of `BinaryTreeDeleteResult<NODE>`.
* The function `delete` in a binary tree class deletes a node from the tree and fixes the tree if
* necessary.
* @param {ReturnType<C> | null | undefined} identifier - The `identifier` parameter is the
* identifier of the node that needs to be deleted from the binary tree. It can be of any type that
* is returned by the callback function `C`. It can also be `null` or `undefined` if the node to be
* deleted is not found.
* @param {C} callback - The `callback` parameter is a function that is used to retrieve a node from
* the binary tree based on its identifier. It is an optional parameter and if not provided, the
* `_defaultOneParamCallback` function is used as the default callback. The callback function should
* return the identifier of the node to
* @returns an array of BinaryTreeDeleteResult<NODE> objects.
*/
delete<C extends BTNCallback<NODE>>(
override delete<C extends BTNCallback<NODE>>(
identifier: ReturnType<C> | null | undefined,
callback: C = this._defaultOneParamCallback as C
): BinaryTreeDeleteResult<NODE>[] {
const ans: BinaryTreeDeleteResult<NODE>[] = [];
if (identifier === null) return ans;
const helper = (node: NODE | undefined): void => {
let z: NODE = this._Sentinel;
let x: NODE | undefined, y: NODE;
while (node !== this._Sentinel) {
if (node && callback(node) === identifier) {
z = node;
}
if (identifier === null) return [];
const results: BinaryTreeDeleteResult<NODE>[] = [];
if (node && identifier && callback(node) <= identifier) {
node = node.right;
const nodeToDelete = this.isRealNode(identifier) ? identifier : this.getNode(identifier, callback);
if (!nodeToDelete) {
return results;
}
let originalColor = nodeToDelete.color;
let replacementNode: NODE | undefined;
if (!this.isRealNode(nodeToDelete.left)) {
replacementNode = nodeToDelete.right;
this._transplant(nodeToDelete, nodeToDelete.right);
} else if (!this.isRealNode(nodeToDelete.right)) {
replacementNode = nodeToDelete.left;
this._transplant(nodeToDelete, nodeToDelete.left);
} else {
const successor = this.getLeftMost(nodeToDelete.right);
if (successor) {
originalColor = successor.color;
replacementNode = successor.right;
if (successor.parent === nodeToDelete) {
if (this.isRealNode(replacementNode)) {
replacementNode.parent = successor;
}
} else {
node = node?.left;
this._transplant(successor, successor.right);
successor.right = nodeToDelete.right;
if (this.isRealNode(successor.right)) {
successor.right.parent = successor;
}
}
}
if (z === this._Sentinel) {
this._size--;
return;
this._transplant(nodeToDelete, successor);
successor.left = nodeToDelete.left;
if (this.isRealNode(successor.left)) {
successor.left.parent = successor;
}
successor.color = nodeToDelete.color;
}
}
this._size--;
y = z;
let yOriginalColor: number = y.color;
if (z.left === this._Sentinel) {
x = z.right;
this._rbTransplant(z, z.right!);
} else if (z.right === this._Sentinel) {
x = z.left;
this._rbTransplant(z, z.left!);
} else {
y = this.getLeftMost(z.right)!;
yOriginalColor = y.color;
x = y.right;
if (y.parent === z) {
x!.parent = y;
} else {
this._rbTransplant(y, y.right!);
y.right = z.right;
y.right!.parent = y;
}
// If the original color was black, fix the tree
if (originalColor === RBTNColor.BLACK) {
this._deleteFixup(replacementNode);
}
this._rbTransplant(z, y);
y.left = z.left;
y.left!.parent = y;
y.color = z.color;
}
if (yOriginalColor === RBTNColor.BLACK) {
this._fixDelete(x!);
}
this._size--;
ans.push({ deleted: z, needBalanced: undefined });
};
helper(this.root);
return ans;
results.push({ deleted: nodeToDelete, needBalanced: undefined });
return results;
}
/**
* Time Complexity: O(log n)
* Space Complexity: O(1)
* The function sets the root of a tree-like structure and updates the parent property of the new
* root.
* @param {NODE | undefined} v - v is a parameter of type NODE or undefined.
*/
/**
* Time Complexity: O(log n)
* Space Complexity: O(1)
*
* The function `getNode` retrieves a single node from a binary tree based on a given identifier and
* callback function.
* @param {ReturnType<C> | undefined} identifier - The `identifier` parameter is the value used to
* identify the node you want to retrieve. It can be of any type that is the return type of the `C`
* callback function. If the `identifier` is `undefined`, it means you want to retrieve the first
* node that matches the other criteria
* @param {C} callback - The `callback` parameter is a function that will be called for each node in
* the binary tree. It is used to determine if a node matches the given identifier. The `callback`
* function should take a single parameter of type `NODE` (the type of the nodes in the binary tree) and
* @param {K | NODE | undefined} beginRoot - The `beginRoot` parameter is the starting point for
* searching for a node in a binary tree. It can be either a key value or a node object. If it is not
* provided, the search will start from the root of the binary tree.
* @param iterationType - The `iterationType` parameter is a variable that determines the type of
* iteration to be performed when searching for nodes in the binary tree. It is used in the
* `getNodes` method, which is called within the `getNode` method.
* @returns a value of type `NODE`, `null`, or `undefined`.
*/
getNode<C extends BTNCallback<NODE>>(
identifier: ReturnType<C> | undefined,
callback: C = this._defaultOneParamCallback as C,
beginRoot: BSTNKeyOrNode<K, NODE> = this.root,
iterationType = this.iterationType
): NODE | null | undefined {
if ((identifier as any) instanceof RedBlackTreeNode) callback = (node => node) as C;
beginRoot = this.ensureNode(beginRoot);
return this.getNodes(identifier, callback, true, beginRoot, iterationType)[0] ?? undefined;
protected override _setRoot(v: NODE | undefined) {
if (v) {
v.parent = undefined;
}
this._root = v;
}

@@ -417,7 +422,14 @@

*
* The "clear" function sets the root node to the sentinel node and resets the size to 0.
* The function replaces an old node with a new node while preserving the color of the old node.
* @param {NODE} oldNode - The `oldNode` parameter represents the node that needs to be replaced in
* the data structure.
* @param {NODE} newNode - The `newNode` parameter is the new node that will replace the old node in
* the data structure.
* @returns The method is returning the result of calling the `_replaceNode` method from the
* superclass, with the `oldNode` and `newNode` parameters.
*/
override clear() {
this._root = this._Sentinel;
this._size = 0;
protected override _replaceNode(oldNode: NODE, newNode: NODE): NODE {
newNode.color = oldNode.color;
return super._replaceNode(oldNode, newNode);
}

@@ -434,64 +446,41 @@

*
* The function returns the predecessor of a given node in a red-black tree.
* @param {RedBlackTreeNode} x - The parameter `x` is of type `RedBlackTreeNode`, which represents a node in a
* Red-Black Tree.
* @returns the predecessor of the given RedBlackTreeNode 'x'.
* The `_insert` function inserts or updates a node in a binary search tree and performs necessary
* fix-ups to maintain the red-black tree properties.
* @param {NODE} node - The `node` parameter represents the node that needs to be inserted into a
* binary search tree. It contains a `key` property that is used to determine the position of the
* node in the tree.
* @returns {'inserted' | 'updated'} - The result of the insertion.
*/
override getPredecessor(x: NODE): NODE {
if (this.isRealNode(x.left)) {
return this.getRightMost(x.left)!;
}
protected _insert(node: NODE): 'inserted' | 'updated' {
let current = this.root;
let parent: NODE | undefined = undefined;
let y: NODE | undefined = x.parent;
while (this.isRealNode(y) && x === y.left) {
x = y!;
y = y!.parent;
while (this.isRealNode(current)) {
parent = current;
if (node.key < current.key) {
current = current.left ?? this.SENTINEL;
} else if (node.key > current.key) {
current = current.right ?? this.SENTINEL;
} else {
this._replaceNode(current, node);
return 'updated';
}
}
return y!;
}
node.parent = parent;
/**
* The function sets the root node of a tree structure and updates the parent property of the new
* root node.
* @param {NODE} v - The parameter "v" is of type "NODE", which represents a node in a data
* structure.
*/
protected override _setRoot(v: NODE) {
if (v) {
v.parent = undefined;
if (!parent) {
this._setRoot(node);
} else if (node.key < parent.key) {
parent.left = node;
} else {
parent.right = node;
}
this._root = v;
}
/**
* Time Complexity: O(1)
* Space Complexity: O(1)
*/
node.left = this.SENTINEL;
node.right = this.SENTINEL;
node.color = RBTNColor.RED;
/**
* Time Complexity: O(1)
* Space Complexity: O(1)
*
* The function performs a left rotation on a binary tree node.
* @param {RedBlackTreeNode} x - The parameter `x` is of type `NODE`, which likely represents a node in a binary tree.
*/
protected _leftRotate(x: NODE): void {
if (x.right) {
const y: NODE = x.right;
x.right = y.left;
if (y.left !== this._Sentinel) {
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;
}
this._insertFixup(node);
return 'inserted';
}

@@ -508,24 +497,19 @@

*
* The function performs a right rotation on a red-black tree node.
* @param {RedBlackTreeNode} x - x is a RedBlackTreeNode, which represents the node that needs to be right
* rotated.
* The function `_transplant` is used to replace a node `u` with another node `v` in a binary tree.
* @param {NODE} u - The parameter "u" represents a node in a binary tree.
* @param {NODE | undefined} v - The parameter `v` is of type `NODE | undefined`, which means it can
* either be a `NODE` object or `undefined`.
*/
protected _rightRotate(x: NODE): void {
if (x.left) {
const y: NODE = x.left;
x.left = y.right;
if (y.right !== this._Sentinel) {
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;
protected _transplant(u: NODE, v: NODE | undefined): void {
if (!u.parent) {
this._setRoot(v);
} else if (u === u.parent.left) {
u.parent.left = v;
} else {
u.parent.right = v;
}
if (v) {
v.parent = u.parent;
}
}

@@ -542,60 +526,62 @@

*
* The `_fixInsert` function is used to fix the red-black tree after an insertion operation.
* @param {RedBlackTreeNode} k - The parameter `k` is a RedBlackTreeNode object, which represents a node in a
* red-black tree.
* The `_insertFixup` function is used to fix the Red-Black Tree after inserting a new node.
* @param {NODE | undefined} z - The parameter `z` represents a node in the Red-Black Tree. It can
* either be a valid node object or `undefined`.
*/
protected _fixInsert(k: NODE): void {
let u: NODE | undefined;
while (k.parent && k.parent.color === RBTNColor.RED) {
if (k.parent.parent && k.parent === k.parent.parent.right) {
u = k.parent.parent.left;
if (u && u.color === RBTNColor.RED) {
// Delay color flip
k.parent.color = RBTNColor.BLACK;
u.color = RBTNColor.BLACK;
k.parent.parent.color = RBTNColor.RED;
k = k.parent.parent;
protected _insertFixup(z: NODE | undefined): void {
// Continue fixing the tree as long as the parent of z is red
while (z?.parent?.color === RBTNColor.RED) {
// Check if the parent of z is the left child of its parent
if (z.parent === z.parent.parent?.left) {
// Case 1: The uncle (y) of z is red
const y = z.parent.parent.right;
if (y?.color === RBTNColor.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;
// Move up the tree to continue fixing
z = z.parent.parent;
} else {
if (k === k.parent.left) {
k = k.parent;
this._rightRotate(k);
// Case 2: The uncle (y) of z is black, and z is a right child
if (z === z.parent.right) {
// Perform a left rotation to transform the case into Case 3
z = z.parent;
this._leftRotate(z);
}
// Check color before rotation
if (k.parent!.color === RBTNColor.RED) {
k.parent!.color = RBTNColor.BLACK;
k.parent!.parent!.color = RBTNColor.RED;
// Case 3: The uncle (y) of z is black, and z is a left child
// Adjust colors and perform a right rotation
if (z && this.isRealNode(z.parent) && this.isRealNode(z.parent.parent)) {
z.parent.color = RBTNColor.BLACK;
z.parent.parent.color = RBTNColor.RED;
this._rightRotate(z.parent.parent);
}
this._leftRotate(k.parent!.parent!);
}
} else {
u = k.parent!.parent!.right;
if (u && u.color === RBTNColor.RED) {
// Delay color flip
k.parent.color = RBTNColor.BLACK;
u.color = RBTNColor.BLACK;
k.parent.parent!.color = RBTNColor.RED;
k = k.parent.parent!;
// Symmetric case for the right child (left and right exchanged)
// Follow the same logic as above with left and right exchanged
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;
z = z.parent.parent;
} else {
if (k === k.parent.right) {
k = k.parent;
this._leftRotate(k);
if (z === z.parent.left) {
z = z.parent;
this._rightRotate(z);
}
// Check color before rotation
if (k.parent!.color === RBTNColor.RED) {
k.parent!.color = RBTNColor.BLACK;
k.parent!.parent!.color = RBTNColor.RED;
if (z && this.isRealNode(z.parent) && this.isRealNode(z.parent.parent)) {
z.parent.color = RBTNColor.BLACK;
z.parent.parent.color = RBTNColor.RED;
this._leftRotate(z.parent.parent);
}
this._rightRotate(k.parent!.parent!);
}
}
}
if (k === this.root) {
break;
}
}
this.root.color = RBTNColor.BLACK;
// Ensure that the root is black after fixing
if (this.isRealNode(this._root)) this._root.color = RBTNColor.BLACK;
}

@@ -612,63 +598,78 @@

*
* The function `_fixDelete` is used to fix the red-black tree after a node deletion.
* @param {RedBlackTreeNode} x - The parameter `x` represents a node in a Red-Black Tree (RBT).
* The `_deleteFixup` function is used to fix the red-black tree after a node deletion by adjusting
* the colors and performing rotations.
* @param {NODE | undefined} node - The `node` parameter represents a node in a Red-Black Tree data
* structure. It can be either a valid node object or `undefined`.
* @returns The function does not return any value. It has a return type of `void`.
*/
protected _fixDelete(x: NODE): void {
let s: NODE | undefined;
while (x !== this.root && x.color === RBTNColor.BLACK) {
if (x.parent && x === x.parent.left) {
s = x.parent.right!;
if (s.color === 1) {
s.color = RBTNColor.BLACK;
x.parent.color = RBTNColor.RED;
this._leftRotate(x.parent);
s = x.parent.right!;
protected _deleteFixup(node: NODE | undefined): void {
// Early exit condition
if (!node || node === this.root || node.color === RBTNColor.BLACK) {
if (node) {
node.color = RBTNColor.BLACK; // Ensure the final node is black
}
return;
}
while (node && node !== this.root && node.color === RBTNColor.BLACK) {
const parent: NODE | undefined = node.parent;
if (!parent) {
break; // Ensure the loop terminates if there's an issue with the tree structure
}
if (node === parent.left) {
let sibling = parent.right;
// 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;
this._leftRotate(parent);
sibling = parent.right;
}
if (s.left !== undefined && s.left.color === RBTNColor.BLACK && s.right && s.right.color === RBTNColor.BLACK) {
s.color = RBTNColor.RED;
x = x.parent;
// Case 3: Sibling's left child is black
if ((sibling?.left?.color ?? RBTNColor.BLACK) === RBTNColor.BLACK) {
if (sibling) sibling.color = RBTNColor.RED;
node = parent;
} else {
if (s.right && s.right.color === RBTNColor.BLACK) {
if (s.left) s.left.color = RBTNColor.BLACK;
s.color = RBTNColor.RED;
this._rightRotate(s);
s = x.parent.right;
}
if (s) s.color = x.parent.color;
x.parent.color = RBTNColor.BLACK;
if (s && s.right) s.right.color = RBTNColor.BLACK;
this._leftRotate(x.parent);
x = this.root;
// Case 4: Adjust colors and perform a right rotation
if (sibling?.left) sibling.left.color = RBTNColor.BLACK;
if (sibling) sibling.color = parent.color;
parent.color = RBTNColor.BLACK;
this._rightRotate(parent);
node = this.root;
}
} else {
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;
// Symmetric case for the right child (left and right exchanged)
let sibling = parent.left;
// 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;
this._rightRotate(parent);
if (parent) sibling = parent.left;
}
if (s && s.right && s.right.color === RBTNColor.BLACK && s.right.color === RBTNColor.BLACK) {
s.color = RBTNColor.RED;
x = x.parent!;
// Case 3: Sibling's left child is black
if ((sibling?.right?.color ?? RBTNColor.BLACK) === RBTNColor.BLACK) {
if (sibling) sibling.color = RBTNColor.RED;
node = parent;
} else {
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;
}
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;
// Case 4: Adjust colors and perform a left rotation
if (sibling?.right) sibling.right.color = RBTNColor.BLACK;
if (sibling) sibling.color = parent.color;
if (parent) parent.color = RBTNColor.BLACK;
this._leftRotate(parent);
node = this.root;
}
}
}
x.color = RBTNColor.BLACK;
// Ensure that the final node (possibly the root) is black
if (node) {
node.color = RBTNColor.BLACK;
}
}

@@ -685,31 +686,72 @@

*
* The function `_rbTransplant` replaces one node in a red-black tree with another node.
* @param {RedBlackTreeNode} u - The parameter "u" represents a RedBlackTreeNode object.
* @param {RedBlackTreeNode} v - The parameter "v" is a RedBlackTreeNode object.
* The `_leftRotate` function performs a left rotation on a given node in a binary tree.
* @param {NODE | undefined} x - The parameter `x` is of type `NODE | undefined`. It represents a
* node in a binary tree or `undefined` if there is no node.
* @returns void, which means it does not return any value.
*/
protected _rbTransplant(u: NODE, v: NODE): void {
if (u.parent === undefined) {
this._setRoot(v);
} else if (u === u.parent.left) {
u.parent.left = v;
protected _leftRotate(x: NODE | undefined): void {
if (!x || !x.right) {
return;
}
const y = x.right;
x.right = y.left;
if (this.isRealNode(y.left)) {
y.left.parent = x;
}
y.parent = x.parent;
if (!x.parent) {
this._setRoot(y);
} else if (x === x.parent.left) {
x.parent.left = y;
} else {
u.parent.right = v;
x.parent.right = y;
}
v.parent = u.parent;
y.left = x;
x.parent = y;
}
/**
* The function replaces an old node with a new node while preserving the color of the old node.
* @param {NODE} oldNode - The `oldNode` parameter represents the node that needs to be replaced in a
* data structure. It is of type `NODE`, which is the type of the nodes in the data structure.
* @param {NODE} newNode - The `newNode` parameter is the node that will replace the `oldNode` in the
* data structure.
* @returns The method is returning the result of calling the `_replaceNode` method from the
* superclass, passing in the `oldNode` and `newNode` as arguments.
* Time Complexity: O(1)
* Space Complexity: O(1)
*/
protected _replaceNode(oldNode: NODE, newNode: NODE): NODE {
newNode.color = oldNode.color;
return super._replaceNode(oldNode, newNode);
/**
* Time Complexity: O(1)
* Space Complexity: O(1)
*
* The `_rightRotate` function performs a right rotation on a given node in a binary tree.
* @param {NODE | undefined} y - The parameter `y` is of type `NODE | undefined`. It represents a
* node in a binary tree or `undefined` if there is no node.
* @returns void, which means it does not return any value.
*/
protected _rightRotate(y: NODE | undefined): void {
if (!y || !y.left) {
return;
}
const x = y.left;
y.left = x.right;
if (this.isRealNode(x.right)) {
x.right.parent = y;
}
x.parent = y.parent;
if (!y.parent) {
this._setRoot(x);
} else if (y === y.parent.left) {
y.parent.left = x;
} else {
y.parent.right = x;
}
x.right = y;
y.parent = x;
}
}

161

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

@@ -91,6 +91,9 @@ /**

get count(): number {
return this._count;
}
getMutableCount(): number {
let sum = 0;
this.dfs(node => (sum += node.count));
return sum;
// return this._count;
}

@@ -196,10 +199,11 @@

const newNode = this.keyValueOrEntryToNode(keyOrNodeOrEntry, value, count);
if (newNode === undefined) return false;
const orgCount = newNode?.count || 0;
const isSuccessAdded = super.add(newNode);
const orgNodeCount = newNode?.count || 0;
const inserted = super.add(newNode);
if (inserted) {
this._count += orgNodeCount;
if (isSuccessAdded) {
this._count += orgCount;
return true;
} else {
return false;
}
return true;
}

@@ -237,88 +241,87 @@

): BinaryTreeDeleteResult<NODE>[] {
const deleteResults: BinaryTreeDeleteResult<NODE>[] = [];
if (identifier === null) return deleteResults;
if (identifier === null) return [];
const results: BinaryTreeDeleteResult<NODE>[] = [];
// Helper function to perform deletion
const deleteHelper = (node: NODE | undefined): void => {
// Initialize targetNode to the sentinel node
let targetNode: NODE = this._Sentinel;
let currentNode: NODE | undefined;
const nodeToDelete = this.isRealNode(identifier) ? identifier : this.getNode(identifier, callback);
// Find the node to be deleted based on the identifier
while (node !== this._Sentinel) {
// Update targetNode if the current node matches the identifier
if (node && callback(node) === identifier) {
targetNode = node;
}
if (!nodeToDelete) {
return results;
}
// Move to the right or left based on the comparison with the identifier
if (node && identifier && callback(node) <= identifier) {
node = node.right;
} else {
node = node?.left;
}
}
let originalColor = nodeToDelete.color;
let replacementNode: NODE | undefined;
// If the target node is not found, decrement size and return
if (targetNode === this._Sentinel) {
return;
if (!this.isRealNode(nodeToDelete.left)) {
replacementNode = nodeToDelete.right;
if (ignoreCount || nodeToDelete.count <= 1) {
this._transplant(nodeToDelete, nodeToDelete.right);
this._count -= nodeToDelete.count;
} else {
nodeToDelete.count--;
this._count--;
results.push({ deleted: nodeToDelete, needBalanced: undefined });
return results;
}
} else if (!this.isRealNode(nodeToDelete.right)) {
replacementNode = nodeToDelete.left;
if (ignoreCount || nodeToDelete.count <= 1) {
this._transplant(nodeToDelete, nodeToDelete.left);
this._count -= nodeToDelete.count;
} else {
nodeToDelete.count--;
this._count--;
results.push({ deleted: nodeToDelete, needBalanced: undefined });
return results;
}
} else {
const successor = this.getLeftMost(nodeToDelete.right);
if (successor) {
originalColor = successor.color;
replacementNode = successor.right;
if (ignoreCount || targetNode.count <= 1) {
// Store the parent of the target node and its original color
let parentNode = targetNode;
let parentNodeOriginalColor: number = parentNode.color;
// Handle deletion based on the number of children of the target node
if (targetNode.left === this._Sentinel) {
// Target node has no left child - deletion case 1
currentNode = targetNode.right;
this._rbTransplant(targetNode, targetNode.right!);
} else if (targetNode.right === this._Sentinel) {
// Target node has no right child - deletion case 2
currentNode = targetNode.left;
this._rbTransplant(targetNode, targetNode.left!);
if (successor.parent === nodeToDelete) {
if (this.isRealNode(replacementNode)) {
replacementNode.parent = successor;
}
} else {
// Target node has both left and right children - deletion case 3
parentNode = this.getLeftMost(targetNode.right)!;
parentNodeOriginalColor = parentNode.color;
currentNode = parentNode.right;
if (parentNode.parent === targetNode) {
// Target node's right child becomes its parent's left child
currentNode!.parent = parentNode;
if (ignoreCount || nodeToDelete.count <= 1) {
this._transplant(successor, successor.right);
this._count -= nodeToDelete.count;
} else {
// Replace parentNode with its right child and update connections
this._rbTransplant(parentNode, parentNode.right!);
parentNode.right = targetNode.right;
parentNode.right!.parent = parentNode;
nodeToDelete.count--;
this._count--;
results.push({ deleted: nodeToDelete, needBalanced: undefined });
return results;
}
// Replace the target node with its in-order successor
this._rbTransplant(targetNode, parentNode);
parentNode.left = targetNode.left;
parentNode.left!.parent = parentNode;
parentNode.color = targetNode.color;
successor.right = nodeToDelete.right;
if (this.isRealNode(successor.right)) {
successor.right.parent = successor;
}
}
// Fix the Red-Black Tree properties after deletion
if (parentNodeOriginalColor === RBTNColor.BLACK) {
this._fixDelete(currentNode!);
if (ignoreCount || nodeToDelete.count <= 1) {
this._transplant(nodeToDelete, successor);
this._count -= nodeToDelete.count;
} else {
nodeToDelete.count--;
this._count--;
results.push({ deleted: nodeToDelete, needBalanced: undefined });
return results;
}
// Decrement the size and store information about the deleted node
this._size--;
this._count -= targetNode.count;
deleteResults.push({ deleted: targetNode, needBalanced: undefined });
} else {
targetNode.count--;
this._count--;
successor.left = nodeToDelete.left;
if (this.isRealNode(successor.left)) {
successor.left.parent = successor;
}
successor.color = nodeToDelete.color;
}
};
}
this._size--;
// Call the helper function with the root of the tree
deleteHelper(this.root);
// If the original color was black, fix the tree
if (originalColor === RBTNColor.BLACK) {
this._deleteFixup(replacementNode);
}
// Return the result array
return deleteResults;
results.push({ deleted: nodeToDelete, needBalanced: undefined });
return results;
}

@@ -325,0 +328,0 @@ 

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