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

Comparing version 1.50.5 to 1.50.6

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 <[e-mail]>
- * @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;
 }

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

 "use strict";
-/**
- * data-structure-typed
- *
- * @author Tyler Zeng
- * @copyright Copyright (c) 2022 Tyler Zeng <[e-mail]>
- * @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;

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.

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 @@ /**

package.json

 {
   "name": "red-black-tree-typed",
-  "version": "1.50.5",
+  "version": "1.50.6",
   "description": "RedBlackTree. Javascript & Typescript Data Structure.",
@@ -145,4 +145,4 @@ "main": "dist/index.js",
   "dependencies": {
-    "data-structure-typed": "^1.50.4"
+    "data-structure-typed": "^1.50.6"
   }
 }

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

@@ -1,10 +0,2 @@
-/**
- * data-structure-typed
- *
- * @author Tyler Zeng
- * @copyright Copyright (c) 2022 Tyler Zeng <[e-mail]>
- * @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;
   }
 }

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 @@

No alert changes

Improved metrics

Total package byte prevSize

2115820

increased by0.24%

Lines of code

39791

increased by0.22%

Dependency changes

• Updateddata-structure-typed@^1.50.6