min-heap-typed - npm Package Compare versions

Comparing version 1.40.0 to 1.41.0

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

@@ -305,2 +305,10 @@ /**
     /**
+     * The function `getSuccessor` returns the next node in a binary tree given a node `x`, or `null` if
+     * `x` is the last node.
+     * @param {N} x - N - a node in a binary tree
+     * @returns The function `getSuccessor` returns a value of type `N` (the successor node), or `null`
+     * if there is no successor, or `undefined` if the input `x` is `undefined`.
+     */
+    getSuccessor(x: N): N | null | undefined;
+    /**
      * The `morris` function performs a depth-first traversal of a binary tree using the Morris traversal
@@ -307,0 +315,0 @@ * algorithm and returns an array of values obtained by applying a callback function to each node.

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

@@ -816,3 +816,3 @@ "use strict";
             const queue = new queue_1.Queue([beginRoot]);
-            function traverse(level) {
+            const traverse = (level) => {
                 if (queue.size === 0)
@@ -827,3 +827,3 @@ return;
                 traverse(level + 1);
-            }
+            };
             traverse(0);
@@ -913,2 +913,20 @@ }
     }
+    /**
+     * The function `getSuccessor` returns the next node in a binary tree given a node `x`, or `null` if
+     * `x` is the last node.
+     * @param {N} x - N - a node in a binary tree
+     * @returns The function `getSuccessor` returns a value of type `N` (the successor node), or `null`
+     * if there is no successor, or `undefined` if the input `x` is `undefined`.
+     */
+    getSuccessor(x) {
+        if (x.right) {
+            return this.getLeftMost(x.right);
+        }
+        let y = x.parent;
+        while (y && y && x === y.right) {
+            x = y;
+            y = y.parent;
+        }
+        return y;
+    }
     // --- start additional methods ---
@@ -1043,2 +1061,3 @@ /**
             if (node.left) {
+                // @ts-ignore
                 yield* this[Symbol.iterator](node.left);
@@ -1048,2 +1067,3 @@ }
             if (node.right) {
+                // @ts-ignore
                 yield* this[Symbol.iterator](node.right);
@@ -1050,0 +1070,0 @@ }

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

@@ -46,3 +46,3 @@ /**
      * maintaining balance.
-     * @param {[BTNKey | N, N['value']][]} keysOrNodes - The `arr` parameter in the `addMany` function
+     * @param {[BTNKey | N, V][]} keysOrNodes - The `arr` parameter in the `addMany` function
      * represents an array of keys or nodes that need to be added to the binary search tree. It can be an
@@ -49,0 +49,0 @@ * array of `BTNKey` or `N` (which represents the node type in the binary search tree) or

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

@@ -129,3 +129,3 @@ "use strict";
      * maintaining balance.
-     * @param {[BTNKey | N, N['value']][]} keysOrNodes - The `arr` parameter in the `addMany` function
+     * @param {[BTNKey | N, V][]} keysOrNodes - The `arr` parameter in the `addMany` function
      * represents an array of keys or nodes that need to be added to the binary search tree. It can be an
@@ -132,0 +132,0 @@ * array of `BTNKey` or `N` (which represents the node type in the binary search tree) or

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

@@ -1,11 +0,97 @@
-import { BTNKey, RBColor, RBTreeNodeNested, RBTreeOptions } from '../../types';
-import { IBinaryTree } from '../../interfaces';
-import { BST, BSTNode } from './bst';
-export declare class RBTreeNode<V = any, N extends RBTreeNode<V, N> = RBTreeNodeNested<V>> extends BSTNode<V, N> {
-    constructor(key: BTNKey, value?: V);
-    color: RBColor;
+export declare class RBTreeNode {
+    key: number;
+    parent: RBTreeNode;
+    left: RBTreeNode;
+    right: RBTreeNode;
+    color: number;
+    constructor();
 }
-export declare class RBTree<V, N extends RBTreeNode<V, N> = RBTreeNode<V, RBTreeNodeNested<V>>> extends BST<V, N> implements IBinaryTree<V, N> {
-    constructor(options?: RBTreeOptions);
-    createNode(key: BTNKey, value?: V): N;
+export declare class RedBlackTree {
+    constructor();
+    protected _root: RBTreeNode;
+    get root(): RBTreeNode;
+    protected _NIL: RBTreeNode;
+    get NIL(): RBTreeNode;
+    /**
+     * The `insert` function inserts a new node with a given key into a red-black tree and fixes any
+     * violations of the red-black tree properties.
+     * @param {number} key - The key parameter is a number that represents the value to be inserted into
+     * the RBTree.
+     * @returns The function does not explicitly return anything.
+     */
+    insert(key: number): void;
+    /**
+     * The `delete` function in TypeScript is used to remove a node with a specific key from a red-black
+     * tree.
+     * @param {RBTreeNode} node - The `node` parameter is of type `RBTreeNode` and represents the current
+     * node being processed in the delete operation.
+     * @returns The `delete` function does not return anything. It has a return type of `void`.
+     */
+    delete(key: number): void;
+    /**
+     * The function `getNode` is a recursive depth-first search algorithm that searches for a node with a
+     * given key in a red-black tree.
+     * @param {number} key - The key parameter is a number that represents the value we are searching for
+     * in the RBTree.
+     * @param beginRoot - The `beginRoot` parameter is an optional parameter that represents the starting
+     * point for the search in the binary search tree. If no value is provided for `beginRoot`, it
+     * defaults to the root of the binary search tree (`this.root`).
+     * @returns a RBTreeNode.
+     */
+    getNode(key: number, beginRoot?: RBTreeNode): RBTreeNode;
+    /**
+     * The function returns the leftmost node in a red-black tree.
+     * @param {RBTreeNode} node - The parameter "node" is of type RBTreeNode, which represents a node in
+     * a Red-Black Tree.
+     * @returns The leftmost node in the given RBTreeNode.
+     */
+    getLeftMost(node: RBTreeNode): RBTreeNode;
+    /**
+     * The function returns the rightmost node in a red-black tree.
+     * @param {RBTreeNode} node - The parameter "node" is of type RBTreeNode.
+     * @returns the rightmost node in a red-black tree.
+     */
+    getRightMost(node: RBTreeNode): RBTreeNode;
+    /**
+     * The function returns the successor of a given node in a red-black tree.
+     * @param {RBTreeNode} x - RBTreeNode - The node for which we want to find the successor.
+     * @returns the successor of the given RBTreeNode.
+     */
+    getSuccessor(x: RBTreeNode): RBTreeNode;
+    /**
+     * The function returns the predecessor of a given node in a red-black tree.
+     * @param {RBTreeNode} x - The parameter `x` is of type `RBTreeNode`, which represents a node in a
+     * Red-Black Tree.
+     * @returns the predecessor of the given RBTreeNode 'x'.
+     */
+    getPredecessor(x: RBTreeNode): RBTreeNode;
+    /**
+     * The function performs a left rotation on a red-black tree node.
+     * @param {RBTreeNode} x - The parameter `x` is a RBTreeNode object.
+     */
+    protected _leftRotate(x: RBTreeNode): void;
+    /**
+     * The function performs a right rotation on a red-black tree node.
+     * @param {RBTreeNode} x - x is a RBTreeNode, which represents the node that needs to be right
+     * rotated.
+     */
+    protected _rightRotate(x: RBTreeNode): void;
+    /**
+     * The _fixDelete function is used to rebalance the Red-Black Tree after a node deletion.
+     * @param {RBTreeNode} x - The parameter `x` is of type `RBTreeNode`, which represents a node in a
+     * red-black tree.
+     */
+    protected _fixDelete(x: RBTreeNode): void;
+    /**
+     * The function `_rbTransplant` replaces one node in a red-black tree with another node.
+     * @param {RBTreeNode} u - The parameter "u" represents a RBTreeNode object.
+     * @param {RBTreeNode} v - The parameter "v" is a RBTreeNode object.
+     */
+    protected _rbTransplant(u: RBTreeNode, v: RBTreeNode): void;
+    /**
+     * The `_fixInsert` function is used to fix the red-black tree after an insertion operation.
+     * @param {RBTreeNode} k - The parameter `k` is a RBTreeNode object, which represents a node in a
+     * red-black tree.
+     */
+    protected _fixInsert(k: RBTreeNode): void;
 }

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

 "use strict";
 Object.defineProperty(exports, "__esModule", { value: true });
-exports.RBTree = exports.RBTreeNode = void 0;
+exports.RedBlackTree = exports.RBTreeNode = void 0;
 const types_1 = require("../../types");
-const bst_1 = require("./bst");
-class RBTreeNode extends bst_1.BSTNode {
-    constructor(key, value) {
-        super(key, value);
-        this.color = types_1.RBColor.RED;
+class RBTreeNode {
+    constructor() {
+        this.key = 0;
+        this.color = types_1.RBTNColor.BLACK;
+        this.parent = null;
+        this.left = null;
+        this.right = null;
     }
 }
 exports.RBTreeNode = RBTreeNode;
-class RBTree extends bst_1.BST {
-    constructor(options) {
-        super(options);
+class RedBlackTree {
+    constructor() {
+        this._NIL = new RBTreeNode();
+        this.NIL.color = types_1.RBTNColor.BLACK;
+        this.NIL.left = null;
+        this.NIL.right = null;
+        this._root = this.NIL;
     }
-    createNode(key, value) {
-        return new RBTreeNode(key, value);
+    get root() {
+        return this._root;
     }
+    get NIL() {
+        return this._NIL;
+    }
+    /**
+     * The `insert` function inserts a new node with a given key into a red-black tree and fixes any
+     * violations of the red-black tree properties.
+     * @param {number} key - The key parameter is a number that represents the value to be inserted into
+     * the RBTree.
+     * @returns The function does not explicitly return anything.
+     */
+    insert(key) {
+        const node = new RBTreeNode();
+        node.parent = null;
+        node.key = key;
+        node.left = this.NIL;
+        node.right = this.NIL;
+        node.color = types_1.RBTNColor.RED;
+        let y = null;
+        let x = this.root;
+        while (x !== this.NIL) {
+            y = x;
+            if (node.key < x.key) {
+                x = x.left;
+            }
+            else {
+                x = x.right;
+            }
+        }
+        node.parent = y;
+        if (y === null) {
+            this._root = node;
+        }
+        else if (node.key < y.key) {
+            y.left = node;
+        }
+        else {
+            y.right = node;
+        }
+        if (node.parent === null) {
+            node.color = types_1.RBTNColor.BLACK;
+            return;
+        }
+        if (node.parent.parent === null) {
+            return;
+        }
+        this._fixInsert(node);
+    }
+    /**
+     * The `delete` function in TypeScript is used to remove a node with a specific key from a red-black
+     * tree.
+     * @param {RBTreeNode} node - The `node` parameter is of type `RBTreeNode` and represents the current
+     * node being processed in the delete operation.
+     * @returns The `delete` function does not return anything. It has a return type of `void`.
+     */
+    delete(key) {
+        const helper = (node) => {
+            let z = this.NIL;
+            let x, y;
+            while (node !== this.NIL) {
+                if (node.key === key) {
+                    z = node;
+                }
+                if (node.key <= key) {
+                    node = node.right;
+                }
+                else {
+                    node = node.left;
+                }
+            }
+            if (z === this.NIL) {
+                console.log("Couldn't find key in the tree");
+                return;
+            }
+            y = z;
+            let yOriginalColor = y.color;
+            if (z.left === this.NIL) {
+                x = z.right;
+                this._rbTransplant(z, z.right);
+            }
+            else if (z.right === this.NIL) {
+                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 === 0) {
+                this._fixDelete(x);
+            }
+        };
+        helper(this.root);
+    }
+    /**
+     * The function `getNode` is a recursive depth-first search algorithm that searches for a node with a
+     * given key in a red-black tree.
+     * @param {number} key - The key parameter is a number that represents the value we are searching for
+     * in the RBTree.
+     * @param beginRoot - The `beginRoot` parameter is an optional parameter that represents the starting
+     * point for the search in the binary search tree. If no value is provided for `beginRoot`, it
+     * defaults to the root of the binary search tree (`this.root`).
+     * @returns a RBTreeNode.
+     */
+    getNode(key, beginRoot = this.root) {
+        const dfs = (node) => {
+            if (node === this.NIL || key === node.key) {
+                return node;
+            }
+            if (key < node.key) {
+                return dfs(node.left);
+            }
+            return dfs(node.right);
+        };
+        return dfs(beginRoot);
+    }
+    /**
+     * The function returns the leftmost node in a red-black tree.
+     * @param {RBTreeNode} node - The parameter "node" is of type RBTreeNode, which represents a node in
+     * a Red-Black Tree.
+     * @returns The leftmost node in the given RBTreeNode.
+     */
+    getLeftMost(node) {
+        while (node.left !== null && node.left !== this.NIL) {
+            node = node.left;
+        }
+        return node;
+    }
+    /**
+     * The function returns the rightmost node in a red-black tree.
+     * @param {RBTreeNode} node - The parameter "node" is of type RBTreeNode.
+     * @returns the rightmost node in a red-black tree.
+     */
+    getRightMost(node) {
+        while (node.right !== null && node.right !== this.NIL) {
+            node = node.right;
+        }
+        return node;
+    }
+    /**
+     * The function returns the successor of a given node in a red-black tree.
+     * @param {RBTreeNode} x - RBTreeNode - The node for which we want to find the successor.
+     * @returns the successor of the given RBTreeNode.
+     */
+    getSuccessor(x) {
+        if (x.right !== this.NIL) {
+            return this.getLeftMost(x.right);
+        }
+        let y = x.parent;
+        while (y !== this.NIL && y !== null && x === y.right) {
+            x = y;
+            y = y.parent;
+        }
+        return y;
+    }
+    /**
+     * The function returns the predecessor of a given node in a red-black tree.
+     * @param {RBTreeNode} x - The parameter `x` is of type `RBTreeNode`, which represents a node in a
+     * Red-Black Tree.
+     * @returns the predecessor of the given RBTreeNode 'x'.
+     */
+    getPredecessor(x) {
+        if (x.left !== this.NIL) {
+            return this.getRightMost(x.left);
+        }
+        let y = x.parent;
+        while (y !== this.NIL && x === y.left) {
+            x = y;
+            y = y.parent;
+        }
+        return y;
+    }
+    /**
+     * The function performs a left rotation on a red-black tree node.
+     * @param {RBTreeNode} x - The parameter `x` is a RBTreeNode object.
+     */
+    _leftRotate(x) {
+        const y = x.right;
+        x.right = y.left;
+        if (y.left !== this.NIL) {
+            y.left.parent = x;
+        }
+        y.parent = x.parent;
+        if (x.parent === null) {
+            this._root = y;
+        }
+        else if (x === x.parent.left) {
+            x.parent.left = y;
+        }
+        else {
+            x.parent.right = y;
+        }
+        y.left = x;
+        x.parent = y;
+    }
+    /**
+     * The function performs a right rotation on a red-black tree node.
+     * @param {RBTreeNode} x - x is a RBTreeNode, which represents the node that needs to be right
+     * rotated.
+     */
+    _rightRotate(x) {
+        const y = x.left;
+        x.left = y.right;
+        if (y.right !== this.NIL) {
+            y.right.parent = x;
+        }
+        y.parent = x.parent;
+        if (x.parent === null) {
+            this._root = y;
+        }
+        else if (x === x.parent.right) {
+            x.parent.right = y;
+        }
+        else {
+            x.parent.left = y;
+        }
+        y.right = x;
+        x.parent = y;
+    }
+    /**
+     * The _fixDelete function is used to rebalance the Red-Black Tree after a node deletion.
+     * @param {RBTreeNode} x - The parameter `x` is of type `RBTreeNode`, which represents a node in a
+     * red-black tree.
+     */
+    _fixDelete(x) {
+        let s;
+        while (x !== this.root && x.color === 0) {
+            if (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;
+                }
+                if (s.left.color === 0 && s.right.color === 0) {
+                    s.color = types_1.RBTNColor.RED;
+                    x = x.parent;
+                }
+                else {
+                    if (s.right.color === 0) {
+                        s.left.color = types_1.RBTNColor.BLACK;
+                        s.color = types_1.RBTNColor.RED;
+                        this._rightRotate(s);
+                        s = x.parent.right;
+                    }
+                    s.color = x.parent.color;
+                    x.parent.color = types_1.RBTNColor.BLACK;
+                    s.right.color = types_1.RBTNColor.BLACK;
+                    this._leftRotate(x.parent);
+                    x = 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;
+                }
+                if (s.right.color === 0 && s.right.color === 0) {
+                    s.color = types_1.RBTNColor.RED;
+                    x = x.parent;
+                }
+                else {
+                    if (s.left.color === 0) {
+                        s.right.color = types_1.RBTNColor.BLACK;
+                        s.color = types_1.RBTNColor.RED;
+                        this._leftRotate(s);
+                        s = x.parent.left;
+                    }
+                    s.color = x.parent.color;
+                    x.parent.color = types_1.RBTNColor.BLACK;
+                    s.left.color = types_1.RBTNColor.BLACK;
+                    this._rightRotate(x.parent);
+                    x = this.root;
+                }
+            }
+        }
+        x.color = types_1.RBTNColor.BLACK;
+    }
+    /**
+     * The function `_rbTransplant` replaces one node in a red-black tree with another node.
+     * @param {RBTreeNode} u - The parameter "u" represents a RBTreeNode object.
+     * @param {RBTreeNode} v - The parameter "v" is a RBTreeNode object.
+     */
+    _rbTransplant(u, v) {
+        if (u.parent === null) {
+            this._root = v;
+        }
+        else if (u === u.parent.left) {
+            u.parent.left = v;
+        }
+        else {
+            u.parent.right = v;
+        }
+        v.parent = u.parent;
+    }
+    /**
+     * The `_fixInsert` function is used to fix the red-black tree after an insertion operation.
+     * @param {RBTreeNode} k - The parameter `k` is a RBTreeNode object, which represents a node in a
+     * red-black tree.
+     */
+    _fixInsert(k) {
+        let u;
+        while (k.parent.color === 1) {
+            if (k.parent === k.parent.parent.right) {
+                u = k.parent.parent.left;
+                if (u.color === 1) {
+                    u.color = types_1.RBTNColor.BLACK;
+                    k.parent.color = types_1.RBTNColor.BLACK;
+                    k.parent.parent.color = types_1.RBTNColor.RED;
+                    k = k.parent.parent;
+                }
+                else {
+                    if (k === k.parent.left) {
+                        k = k.parent;
+                        this._rightRotate(k);
+                    }
+                    k.parent.color = types_1.RBTNColor.BLACK;
+                    k.parent.parent.color = types_1.RBTNColor.RED;
+                    this._leftRotate(k.parent.parent);
+                }
+            }
+            else {
+                u = k.parent.parent.right;
+                if (u.color === 1) {
+                    u.color = types_1.RBTNColor.BLACK;
+                    k.parent.color = types_1.RBTNColor.BLACK;
+                    k.parent.parent.color = types_1.RBTNColor.RED;
+                    k = k.parent.parent;
+                }
+                else {
+                    if (k === k.parent.right) {
+                        k = k.parent;
+                        this._leftRotate(k);
+                    }
+                    k.parent.color = types_1.RBTNColor.BLACK;
+                    k.parent.parent.color = types_1.RBTNColor.RED;
+                    this._rightRotate(k.parent.parent);
+                }
+            }
+            if (k === this.root) {
+                break;
+            }
+        }
+        this.root.color = types_1.RBTNColor.BLACK;
+    }
 }
-exports.RBTree = RBTree;
+exports.RedBlackTree = RedBlackTree;

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

@@ -1,8 +0,4 @@
-import { BinaryTreeOptions } from './binary-tree';
-import { RBTreeNode } from '../../../data-structures';
-export declare enum RBColor {
-    RED = "RED",
-    BLACK = "BLACK"
+export declare enum RBTNColor {
+    RED = 1,
+    BLACK = 0
 }
-export type RBTreeNodeNested<T> = RBTreeNode<T, RBTreeNode<T, RBTreeNode<T, RBTreeNode<T, RBTreeNode<T, RBTreeNode<T, RBTreeNode<T, RBTreeNode<T, RBTreeNode<T, RBTreeNode<T, RBTreeNode<T, RBTreeNode<T, RBTreeNode<T, RBTreeNode<T, RBTreeNode<T, RBTreeNode<T, RBTreeNode<T, RBTreeNode<T, RBTreeNode<T, RBTreeNode<T, RBTreeNode<T, RBTreeNode<T, RBTreeNode<T, RBTreeNode<T, RBTreeNode<T, RBTreeNode<T, RBTreeNode<T, RBTreeNode<T, RBTreeNode<T, RBTreeNode<T, RBTreeNode<T, RBTreeNode<T, RBTreeNode<T, RBTreeNode<T, RBTreeNode<T, RBTreeNode<T, RBTreeNode<T, RBTreeNode<T, RBTreeNode<T, RBTreeNode<T, RBTreeNode<T, RBTreeNode<T, RBTreeNode<T, RBTreeNode<T, RBTreeNode<T, RBTreeNode<T, RBTreeNode<T, RBTreeNode<T, RBTreeNode<T, RBTreeNode<T, any>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>;
-export type RBTreeOptions = BinaryTreeOptions & {};

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

 "use strict";
+// import {BinaryTreeOptions} from './binary-tree';
+// import {RBTreeNode} from '../../../data-structures';
 Object.defineProperty(exports, "__esModule", { value: true });
-exports.RBColor = void 0;
-var RBColor;
-(function (RBColor) {
-    RBColor["RED"] = "RED";
-    RBColor["BLACK"] = "BLACK";
-})(RBColor = exports.RBColor || (exports.RBColor = {}));
+exports.RBTNColor = void 0;
+var RBTNColor;
+(function (RBTNColor) {
+    RBTNColor[RBTNColor["RED"] = 1] = "RED";
+    RBTNColor[RBTNColor["BLACK"] = 0] = "BLACK";
+})(RBTNColor = exports.RBTNColor || (exports.RBTNColor = {}));
+// export type RBTreeNodeNested<T> = RBTreeNode<T, RBTreeNode<T, RBTreeNode<T, RBTreeNode<T, RBTreeNode<T, RBTreeNode<T, RBTreeNode<T, RBTreeNode<T, RBTreeNode<T, RBTreeNode<T, RBTreeNode<T, RBTreeNode<T, RBTreeNode<T, RBTreeNode<T, RBTreeNode<T, RBTreeNode<T, RBTreeNode<T, RBTreeNode<T, RBTreeNode<T, RBTreeNode<T, RBTreeNode<T, RBTreeNode<T, RBTreeNode<T, RBTreeNode<T, RBTreeNode<T, RBTreeNode<T, RBTreeNode<T, RBTreeNode<T, RBTreeNode<T, RBTreeNode<T, RBTreeNode<T, RBTreeNode<T, RBTreeNode<T, RBTreeNode<T, RBTreeNode<T, RBTreeNode<T, RBTreeNode<T, RBTreeNode<T, RBTreeNode<T, RBTreeNode<T, RBTreeNode<T, RBTreeNode<T, RBTreeNode<T, RBTreeNode<T, RBTreeNode<T, RBTreeNode<T, RBTreeNode<T, RBTreeNode<T, RBTreeNode<T, RBTreeNode<T, any>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>
+//
+// export type RBTreeOptions = BinaryTreeOptions & {}

package.json

 {
   "name": "min-heap-typed",
-  "version": "1.40.0",
+  "version": "1.41.0",
   "description": "Min Heap. Javascript & Typescript Data Structure.",
@@ -134,4 +134,4 @@ "main": "dist/index.js",
   "dependencies": {
-    "data-structure-typed": "^1.40.0"
+    "data-structure-typed": "^1.41.0"
   }
 }

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

@@ -953,3 +953,3 @@ /**
 
-      function traverse(level: number) {
+      const traverse = (level: number) => {
         if (queue.size === 0) return;
@@ -1052,2 +1052,22 @@
 
+  /**
+   * The function `getSuccessor` returns the next node in a binary tree given a node `x`, or `null` if
+   * `x` is the last node.
+   * @param {N} x - N - a node in a binary tree
+   * @returns The function `getSuccessor` returns a value of type `N` (the successor node), or `null`
+   * if there is no successor, or `undefined` if the input `x` is `undefined`.
+   */
+  getSuccessor(x: N): N | null | undefined{
+    if (x.right) {
+      return this.getLeftMost(x.right);
+    }
+
+    let y: N | null | undefined = x.parent;
+    while (y && y && x === y.right) {
+      x = y;
+      y = y.parent;
+    }
+    return y;
+  }
+
   // --- start additional methods ---
@@ -1185,2 +1205,3 @@
       if (node.left) {
+        // @ts-ignore
         yield* this[Symbol.iterator](node.left);
@@ -1190,2 +1211,3 @@ }
       if (node.right) {
+        // @ts-ignore
         yield* this[Symbol.iterator](node.right);
@@ -1192,0 +1214,0 @@ }

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

@@ -130,3 +130,3 @@ /**
    * maintaining balance.
-   * @param {[BTNKey | N, N['value']][]} keysOrNodes - The `arr` parameter in the `addMany` function
+   * @param {[BTNKey | N, V][]} keysOrNodes - The `arr` parameter in the `addMany` function
    * represents an array of keys or nodes that need to be added to the binary search tree. It can be an
@@ -157,6 +157,6 @@ * array of `BTNKey` or `N` (which represents the node type in the binary search tree) or
     const inserted: (N | null | undefined)[] = [];
-    const combinedArr: [BTNKey | N, N['value']][] = keysOrNodes.map((value, index) => [value, data?.[index]]);
+    const combinedArr: [BTNKey | N, V][] = keysOrNodes.map((value:(BTNKey | N), index) => [value, data?.[index]] as [BTNKey | N, V]);
     let sorted = [];
 
-    function isNodeOrNullTuple(arr: [BTNKey | N, N['value']][]): arr is [N, N['value']][] {
+    function isNodeOrNullTuple(arr: [BTNKey | N, V][]): arr is [N, V][] {
       for (const [keyOrNode] of arr) if (keyOrNode instanceof BSTNode) return true;
@@ -166,3 +166,3 @@ return false;
 
-    function isBinaryTreeKeyOrNullTuple(arr: [BTNKey | N, N['value']][]): arr is [BTNKey, N['value']][] {
+    function isBinaryTreeKeyOrNullTuple(arr: [BTNKey | N, V][]): arr is [BTNKey, V][] {
       for (const [keyOrNode] of arr) if (typeof keyOrNode === 'number') return true;
@@ -169,0 +169,0 @@ return false;

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

@@ -1,358 +0,426 @@
-import {BTNKey, RBColor, RBTreeNodeNested, RBTreeOptions} from '../../types';
-import {IBinaryTree} from '../../interfaces';
-import {BST, BSTNode} from './bst';
+import {RBTNColor} from "../../types";
 
-export class RBTreeNode<V = any, N extends RBTreeNode<V, N> = RBTreeNodeNested<V>> extends BSTNode<V, N> {
-  constructor(key: BTNKey, value?: V) {
-    super(key, value);
-    this.color = RBColor.RED;
+export class RBTreeNode {
+  key: number = 0;
+  parent: RBTreeNode;
+  left: RBTreeNode;
+  right: RBTreeNode;
+  color: number = RBTNColor.BLACK;
+
+  constructor() {
+    this.parent = null as unknown as RBTreeNode;
+    this.left = null as unknown as RBTreeNode;
+    this.right = null as unknown as RBTreeNode;
   }
+}
 
-  color: RBColor;
+export class RedBlackTree {
+  
+  constructor() {
+    this._NIL = new RBTreeNode();
+    this.NIL.color = RBTNColor.BLACK;
+    this.NIL.left = null as unknown as RBTreeNode;
+    this.NIL.right = null as unknown as RBTreeNode;
+    this._root = this.NIL;
+  }
 
-}
+  protected _root: RBTreeNode;
 
-export class RBTree<V, N extends RBTreeNode<V, N> = RBTreeNode<V, RBTreeNodeNested<V>>>
-  extends BST<V, N>
-  implements IBinaryTree<V, N> {
-  constructor(options?: RBTreeOptions) {
-    super(options);
+  get root(): RBTreeNode {
+    return this._root;
   }
 
-  override createNode(key: BTNKey, value?: V): N {
-    return new RBTreeNode(key, value) as N;
+  protected _NIL: RBTreeNode;
+
+  get NIL(): RBTreeNode {
+    return this._NIL;
   }
 
-  // override add(keyOrNode: BTNKey | N | null, value?: V): N | null | undefined {
-  //   const inserted = super.add(keyOrNode, value);
-  //   if (inserted) this._fixInsertViolation(inserted);
-  //   return inserted;
-  // }
-  //
-  // // Method for fixing insert violations in a red-black tree
-  // protected _fixInsertViolation(node: N) {
-  //   while (node !== this.root! && node.color === RBColor.RED && node.parent!.color === RBColor.RED) {
-  //     const parent = node.parent!;
-  //     const grandparent = parent.parent!;
-  //     let uncle: N | null | undefined = null;
-  //
-  //     if (parent === grandparent.left) {
-  //       uncle = grandparent.right;
-  //
-  //       // Case 1: The uncle node is red
-  //       if (uncle && uncle.color === RBColor.RED) {
-  //         grandparent.color = RBColor.RED;
-  //         parent.color = RBColor.BLACK;
-  //         uncle.color = RBColor.BLACK;
-  //         node = grandparent;
-  //       } else {
-  //         // Case 2: The uncle node is black, and the current node is a right child
-  //         if (node === parent.right) {
-  //           this._rotateLeft(parent);
-  //           node = parent;
-  //           // Update parent reference
-  //           node.parent = grandparent;
-  //           parent.parent = node;
-  //         }
-  //
-  //         // Case 3: The uncle node is black, and the current node is a left child
-  //         parent.color = RBColor.BLACK;
-  //         grandparent.color = RBColor.RED;
-  //         this._rotateRight(grandparent);
-  //       }
-  //     } else {
-  //       // Symmetric case: The parent is the right child of the grandparent
-  //       uncle = grandparent.left;
-  //
-  //       // Case 1: The uncle node is red
-  //       if (uncle && uncle.color === RBColor.RED) {
-  //         grandparent.color = RBColor.RED;
-  //         parent.color = RBColor.BLACK;
-  //         uncle.color = RBColor.BLACK;
-  //         node = grandparent;
-  //       } else {
-  //         // Case 2: The uncle node is black, and the current node is a left child
-  //         if (node === parent.left) {
-  //           this._rotateRight(parent);
-  //           node = parent;
-  //           // Update parent reference
-  //           node.parent = grandparent;
-  //           parent.parent = node;
-  //         }
-  //
-  //         // Case 3: The uncle node is black, and the current node is a right child
-  //         parent.color = RBColor.BLACK;
-  //         grandparent.color = RBColor.RED;
-  //         this._rotateLeft(grandparent);
-  //       }
-  //     }
-  //   }
-  //
-  //   // The root node is always black
-  //   this.root!.color = RBColor.BLACK;
-  // }
-  //
-  // // Left rotation operation
-  // protected _rotateLeft(node: N) {
-  //   const rightChild = node.right;
-  //   node.right = rightChild!.left;
-  //
-  //   if (rightChild!.left) {
-  //     rightChild!.left.parent = node;
-  //   }
-  //
-  //   rightChild!.parent = node.parent;
-  //
-  //   if (node === this.root) {
-  //     // @ts-ignore
-  //     this._setRoot(rightChild);
-  //   } else if (node === node.parent!.left) {
-  //     node.parent!.left = rightChild;
-  //   } else {
-  //     node.parent!.right = rightChild;
-  //   }
-  //
-  //   rightChild!.left = node;
-  //   node.parent = rightChild;
-  // }
-  //
-  // // Right rotation operation
-  // protected _rotateRight(node: N) {
-  //   const leftChild = node.left;
-  //   node.left = leftChild!.right;
-  //
-  //   if (leftChild!.right) {
-  //     leftChild!.right.parent = node;
-  //   }
-  //
-  //   leftChild!.parent = node.parent;
-  //
-  //   if (node === this.root) {
-  //     // @ts-ignore
-  //     this._setRoot(leftChild);
-  //   } else if (node === node.parent!.right) {
-  //     node.parent!.right = leftChild;
-  //   } else {
-  //     node.parent!.left = leftChild;
-  //   }
-  //
-  //   leftChild!.right = node;
-  //   node.parent = leftChild;
-  // }
-  //
-  // protected _isNodeRed(node: N | null | undefined): boolean {
-  //   return node ? node.color === RBColor.RED : false;
-  // }
-  //
-  // // Find the sibling node
-  // protected _findSibling(node: N): N | null | undefined {
-  //   if (!node.parent) {
-  //     return undefined;
-  //   }
-  //
-  //   return node === node.parent.left ? node.parent.right : node.parent.left;
-  // }
-  //
-  // // Remove a node
-  // protected _removeNode(node: N, replacement: N | null | undefined): void {
-  //   if (node === this.root && !replacement) {
-  //     // If there's only the root node and no replacement, simply delete the root node
-  //     this._setRoot(null);
-  //   } else if (node === this.root || this._isNodeRed(node)) {
-  //     // If the node is the root or a red node, delete it directly
-  //     if (node.parent!.left === node) {
-  //       node.parent!.left = replacement;
-  //     } else {
-  //       node.parent!.right = replacement;
-  //     }
-  //
-  //     if (replacement) {
-  //       replacement.parent = node.parent!;
-  //       replacement.color = RBColor.BLACK; // Set the replacement node's color to black
-  //     }
-  //   } else {
-  //     // If the node is a black node, perform removal and repair
-  //     const sibling = this._findSibling(node);
-  //
-  //     if (node.parent!.left === node) {
-  //       node.parent!.left = replacement;
-  //     } else {
-  //       node.parent!.right = replacement;
-  //     }
-  //
-  //     if (replacement) {
-  //       replacement.parent = node.parent;
-  //     }
-  //
-  //     if (!this._isNodeRed(sibling)) {
-  //       // If the sibling node is black, perform repair
-  //       this._fixDeleteViolation(replacement || node);
-  //     }
-  //   }
-  //
-  //   if (node.parent) {
-  //     node.parent = null;
-  //   }
-  //   node.left = null;
-  //   node.right = null;
-  // }
-  //
-  // override delete(keyOrNode: BTNKey | N): BinaryTreeDeletedResult<N>[] {
-  //   const node = this.get(keyOrNode);
-  //   const result: BinaryTreeDeletedResult<N>[] = [{deleted: undefined, needBalanced: null}];
-  //   if (!node) return result; // Node does not exist
-  //
-  //   const replacement = this._getReplacementNode(node);
-  //
-  //   const isRed = this._isNodeRed(node);
-  //   const isRedReplacement = this._isNodeRed(replacement);
-  //
-  //   // Remove the node
-  //   this._removeNode(node, replacement);
-  //
-  //   if (isRed || isRedReplacement) {
-  //     // If the removed node is red or the replacement node is red, no repair is needed
-  //     return result;
-  //   }
-  //
-  //   // Repair any violation introduced by the removal
-  //   this._fixDeleteViolation(replacement);
-  //
-  //   return result;
-  // }
-  //
-  // // Repair operation after node deletion
-  // protected _fixDeleteViolation(node: N | null | undefined) {
-  //   let sibling;
-  //
-  //   while (node && node !== this.root && !this._isNodeRed(node)) {
-  //     if (node === node.parent!.left) {
-  //       sibling = node.parent!.right;
-  //
-  //       if (sibling && this._isNodeRed(sibling)) {
-  //         // Case 1: The sibling node is red
-  //         sibling.color = RBColor.BLACK;
-  //         node.parent!.color = RBColor.RED;
-  //         this._rotateLeft(node.parent!);
-  //         sibling = node.parent!.right;
-  //       }
-  //
-  //       if (!sibling) return;
-  //
-  //       if (
-  //         (!sibling.left || sibling.left.color === RBColor.BLACK) &&
-  //         (!sibling.right || sibling.right.color === RBColor.BLACK)
-  //       ) {
-  //         // Case 2: The sibling node and its children are all black
-  //         sibling.color = RBColor.RED;
-  //         node = node.parent!;
-  //       } else {
-  //         if (!(sibling.right && this._isNodeRed(sibling.right))) {
-  //           // Case 3: The sibling node is black, and the left child is red, the right child is black
-  //           sibling.left!.color = RBColor.BLACK;
-  //           sibling.color = RBColor.RED;
-  //           this._rotateRight(sibling);
-  //           sibling = node.parent!.right;
-  //         }
-  //
-  //         // Case 4: The sibling node is black, and the right child is red
-  //         if (sibling) {
-  //           sibling.color = node.parent!.color;
-  //         }
-  //         if (node.parent) {
-  //           node.parent.color = RBColor.BLACK;
-  //         }
-  //         if (sibling!.right) {
-  //           sibling!.right.color = RBColor.BLACK;
-  //         }
-  //         this._rotateLeft(node.parent!);
-  //         node = this.root;
-  //       }
-  //     } else {
-  //       // Symmetric case: The parent is the right child of the grandparent
-  //       sibling = node.parent!.left;
-  //
-  //       if (sibling && this._isNodeRed(sibling)) {
-  //         // Case 1: The sibling node is red
-  //         sibling.color = RBColor.BLACK;
-  //         node.parent!.color = RBColor.RED;
-  //         this._rotateRight(node.parent!);
-  //         sibling = node.parent!.left;
-  //       }
-  //
-  //       if (!sibling) return;
-  //
-  //       if (
-  //         (!sibling.left || sibling.left.color === RBColor.BLACK) &&
-  //         (!sibling.right || sibling.right.color === RBColor.BLACK)
-  //       ) {
-  //         // Case 2: The sibling node and its children are all black
-  //         sibling.color = RBColor.RED;
-  //         node = node.parent!;
-  //       } else {
-  //         if (!(sibling.left && this._isNodeRed(sibling.left))) {
-  //           // Case 3: The sibling node is black, and the right child is red, the left child is black
-  //           sibling.right!.color = RBColor.BLACK;
-  //           sibling.color = RBColor.RED;
-  //           this._rotateLeft(sibling);
-  //           sibling = node.parent!.left;
-  //         }
-  //
-  //         // Case 4: The sibling node is black, and the left child is red
-  //         if (sibling) {
-  //           sibling.color = node.parent!.color;
-  //         }
-  //         if (node.parent) {
-  //           node.parent.color = RBColor.BLACK;
-  //         }
-  //         if (sibling!.left) {
-  //           sibling!.left.color = RBColor.BLACK;
-  //         }
-  //         this._rotateRight(node.parent!);
-  //         node = this.root;
-  //       }
-  //     }
-  //   }
-  //
-  //   if (node) {
-  //     node.color = RBColor.BLACK;
-  //   }
-  // }
-  //
-  // protected _findMin(node: N): N {
-  //   while (node.left) {
-  //     node = node.left;
-  //   }
-  //   return node;
-  // }
-  //
-  // // Get the replacement node
-  // protected _getReplacementNode(node: N): N | null | undefined {
-  //   if (node.left && node.right) {
-  //     return this._findSuccessor(node);
-  //   }
-  //
-  //   if (!node.left && !node.right) {
-  //     return null; // Return a fake node with color black
-  //   }
-  //
-  //   return node.left || node.right;
-  // }
-  //
-  // // Find the successor node
-  // protected _findSuccessor(node: N): N | null | undefined {
-  //   if (node.right) {
-  //     // If the node has a right child, find the minimum node in the right subtree as the successor
-  //     return this._findMin(node.right);
-  //   }
-  //
-  //   // Otherwise, traverse upward until finding the first parent whose left child is the current node
-  //   let parent = node.parent;
-  //   while (parent && node === parent.right) {
-  //     node = parent;
-  //     parent = parent.parent;
-  //   }
-  //
-  //   return parent;
-  // }
-}
+  /**
+   * The `insert` function inserts a new node with a given key into a red-black tree and fixes any
+   * violations of the red-black tree properties.
+   * @param {number} key - The key parameter is a number that represents the value to be inserted into
+   * the RBTree.
+   * @returns The function does not explicitly return anything.
+   */
+  insert(key: number): void {
+
+    const node: RBTreeNode = new RBTreeNode();
+    node.parent = null as unknown as RBTreeNode;
+    node.key = key;
+    node.left = this.NIL;
+    node.right = this.NIL;
+    node.color = RBTNColor.RED;
+
+    let y: RBTreeNode = null as unknown as RBTreeNode;
+    let x: RBTreeNode = this.root;
+
+    while (x !== this.NIL) {
+      y = x;
+      if (node.key < x.key) {
+        x = x.left;
+      } else {
+        x = x.right;
+      }
+    }
+
+    node.parent = y;
+    if (y === null) {
+      this._root = node;
+    } else if (node.key < y.key) {
+      y.left = node;
+    } else {
+      y.right = node;
+    }
+
+    if (node.parent === null) {
+      node.color = RBTNColor.BLACK;
+      return;
+    }
+
+    if (node.parent.parent === null) {
+      return;
+    }
+
+    this._fixInsert(node);
+  }
+
+  /**
+   * The `delete` function in TypeScript is used to remove a node with a specific key from a red-black
+   * tree.
+   * @param {RBTreeNode} node - The `node` parameter is of type `RBTreeNode` and represents the current
+   * node being processed in the delete operation.
+   * @returns The `delete` function does not return anything. It has a return type of `void`.
+   */
+  delete(key: number): void {
+    const helper = (node: RBTreeNode): void => {
+
+      let z: RBTreeNode = this.NIL;
+      let x: RBTreeNode, y: RBTreeNode;
+      while (node !== this.NIL) {
+        if (node.key === key) {
+          z = node;
+        }
+
+        if (node.key <= key) {
+          node = node.right;
+        } else {
+          node = node.left;
+        }
+      }
+
+      if (z === this.NIL) {
+        console.log("Couldn't find key in the tree");
+        return;
+      }
+
+      y = z;
+      let yOriginalColor: number = y.color;
+      if (z.left === this.NIL) {
+        x = z.right;
+        this._rbTransplant(z, z.right);
+      } else if (z.right === this.NIL) {
+        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 === 0) {
+        this._fixDelete(x);
+      }
+    }
+    helper(this.root);
+  }
+
+  /**
+   * The function `getNode` is a recursive depth-first search algorithm that searches for a node with a
+   * given key in a red-black tree.
+   * @param {number} key - The key parameter is a number that represents the value we are searching for
+   * in the RBTree.
+   * @param beginRoot - The `beginRoot` parameter is an optional parameter that represents the starting
+   * point for the search in the binary search tree. If no value is provided for `beginRoot`, it
+   * defaults to the root of the binary search tree (`this.root`).
+   * @returns a RBTreeNode.
+   */
+  getNode(key: number, beginRoot = this.root): RBTreeNode {
+    const dfs = (node: RBTreeNode): RBTreeNode => {
+      if (node === this.NIL || key === node.key) {
+        return node;
+      }
+
+      if (key < node.key) {
+        return dfs(node.left);
+      }
+      return dfs(node.right);
+    }
+    return dfs(beginRoot);
+  }
+
+
+  /**
+   * The function returns the leftmost node in a red-black tree.
+   * @param {RBTreeNode} node - The parameter "node" is of type RBTreeNode, which represents a node in
+   * a Red-Black Tree.
+   * @returns The leftmost node in the given RBTreeNode.
+   */
+  getLeftMost(node: RBTreeNode): RBTreeNode {
+    while (node.left !== null && node.left !== this.NIL) {
+      node = node.left;
+    }
+    return node;
+  }
+
+
+  /**
+   * The function returns the rightmost node in a red-black tree.
+   * @param {RBTreeNode} node - The parameter "node" is of type RBTreeNode.
+   * @returns the rightmost node in a red-black tree.
+   */
+  getRightMost(node: RBTreeNode): RBTreeNode {
+    while (node.right !== null && node.right !== this.NIL) {
+      node = node.right;
+    }
+    return node;
+  }
+
+  /**
+   * The function returns the successor of a given node in a red-black tree.
+   * @param {RBTreeNode} x - RBTreeNode - The node for which we want to find the successor.
+   * @returns the successor of the given RBTreeNode.
+   */
+  getSuccessor(x: RBTreeNode): RBTreeNode {
+
+    if (x.right !== this.NIL) {
+      return this.getLeftMost(x.right);
+    }
+
+    let y: RBTreeNode = x.parent;
+    while (y !== this.NIL && y !== null && x === y.right) {
+      x = y;
+      y = y.parent;
+    }
+    return y;
+  }
+
+  /**
+   * The function returns the predecessor of a given node in a red-black tree.
+   * @param {RBTreeNode} x - The parameter `x` is of type `RBTreeNode`, which represents a node in a
+   * Red-Black Tree.
+   * @returns the predecessor of the given RBTreeNode 'x'.
+   */
+  getPredecessor(x: RBTreeNode): RBTreeNode {
+
+    if (x.left !== this.NIL) {
+      return this.getRightMost(x.left);
+    }
+
+    let y: RBTreeNode = x.parent;
+    while (y !== this.NIL && x === y.left) {
+      x = y;
+      y = y.parent;
+    }
+
+    return y;
+  }
+
+  /**
+   * The function performs a left rotation on a red-black tree node.
+   * @param {RBTreeNode} x - The parameter `x` is a RBTreeNode object.
+   */
+  protected _leftRotate(x: RBTreeNode): void {
+    const y: RBTreeNode = x.right;
+    x.right = y.left;
+    if (y.left !== this.NIL) {
+      y.left.parent = x;
+    }
+    y.parent = x.parent;
+    if (x.parent === null) {
+      this._root = y;
+    } else if (x === x.parent.left) {
+      x.parent.left = y;
+    } else {
+      x.parent.right = y;
+    }
+    y.left = x;
+    x.parent = y;
+  }
+
+  /**
+   * The function performs a right rotation on a red-black tree node.
+   * @param {RBTreeNode} x - x is a RBTreeNode, which represents the node that needs to be right
+   * rotated.
+   */
+  protected _rightRotate(x: RBTreeNode): void {
+    const y: RBTreeNode = x.left;
+    x.left = y.right;
+    if (y.right !== this.NIL) {
+      y.right.parent = x;
+    }
+    y.parent = x.parent;
+    if (x.parent === null) {
+      this._root = y;
+    } else if (x === x.parent.right) {
+      x.parent.right = y;
+    } else {
+      x.parent.left = y;
+    }
+    y.right = x;
+    x.parent = y;
+  }
+
+  /**
+   * The _fixDelete function is used to rebalance the Red-Black Tree after a node deletion.
+   * @param {RBTreeNode} x - The parameter `x` is of type `RBTreeNode`, which represents a node in a
+   * red-black tree.
+   */
+  protected _fixDelete(x: RBTreeNode): void {
+    let s: RBTreeNode;
+    while (x !== this.root && x.color === 0) {
+      if (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;
+        }
+
+        if (s.left.color === 0 && s.right.color === 0) {
+
+          s.color = RBTNColor.RED;
+          x = x.parent;
+        } else {
+          if (s.right.color === 0) {
+
+            s.left.color = RBTNColor.BLACK;
+            s.color = RBTNColor.RED;
+            this._rightRotate(s);
+            s = x.parent.right;
+          }
+
+          s.color = x.parent.color;
+          x.parent.color = RBTNColor.BLACK;
+          s.right.color = RBTNColor.BLACK;
+          this._leftRotate(x.parent);
+          x = 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;
+        }
+
+        if (s.right.color === 0 && s.right.color === 0) {
+
+          s.color = RBTNColor.RED;
+          x = x.parent;
+        } else {
+          if (s.left.color === 0) {
+
+            s.right.color = RBTNColor.BLACK;
+            s.color = RBTNColor.RED;
+            this._leftRotate(s);
+            s = x.parent.left;
+          }
+
+          s.color = x.parent.color;
+          x.parent.color = RBTNColor.BLACK;
+          s.left.color = RBTNColor.BLACK;
+          this._rightRotate(x.parent);
+          x = this.root;
+        }
+      }
+    }
+    x.color = RBTNColor.BLACK;
+  }
+
+  /**
+   * The function `_rbTransplant` replaces one node in a red-black tree with another node.
+   * @param {RBTreeNode} u - The parameter "u" represents a RBTreeNode object.
+   * @param {RBTreeNode} v - The parameter "v" is a RBTreeNode object.
+   */
+  protected _rbTransplant(u: RBTreeNode, v: RBTreeNode): void {
+    if (u.parent === null) {
+      this._root = v;
+    } else if (u === u.parent.left) {
+      u.parent.left = v;
+    } else {
+      u.parent.right = v;
+    }
+    v.parent = u.parent;
+  }
+
+  /**
+   * The `_fixInsert` function is used to fix the red-black tree after an insertion operation.
+   * @param {RBTreeNode} k - The parameter `k` is a RBTreeNode object, which represents a node in a
+   * red-black tree.
+   */
+  protected _fixInsert(k: RBTreeNode): void {
+    let u: RBTreeNode;
+    while (k.parent.color === 1) {
+      if (k.parent === k.parent.parent.right) {
+        u = k.parent.parent.left;
+        if (u.color === 1) {
+
+          u.color = RBTNColor.BLACK;
+          k.parent.color = RBTNColor.BLACK;
+          k.parent.parent.color = RBTNColor.RED;
+          k = k.parent.parent;
+        } else {
+          if (k === k.parent.left) {
+
+            k = k.parent;
+            this._rightRotate(k);
+          }
+
+          k.parent.color = RBTNColor.BLACK;
+          k.parent.parent.color = RBTNColor.RED;
+          this._leftRotate(k.parent.parent);
+        }
+      } else {
+        u = k.parent.parent.right;
+
+        if (u.color === 1) {
+
+          u.color = RBTNColor.BLACK;
+          k.parent.color = RBTNColor.BLACK;
+          k.parent.parent.color = RBTNColor.RED;
+          k = k.parent.parent;
+        } else {
+          if (k === k.parent.right) {
+
+            k = k.parent;
+            this._leftRotate(k);
+          }
+
+          k.parent.color = RBTNColor.BLACK;
+          k.parent.parent.color = RBTNColor.RED;
+          this._rightRotate(k.parent.parent);
+        }
+      }
+      if (k === this.root) {
+        break;
+      }
+    }
+    this.root.color = RBTNColor.BLACK;
+  }
+}

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

@@ -1,8 +0,8 @@
-import {BinaryTreeOptions} from './binary-tree';
-import {RBTreeNode} from '../../../data-structures';
+// import {BinaryTreeOptions} from './binary-tree';
+// import {RBTreeNode} from '../../../data-structures';
 
-export enum RBColor { RED = 'RED', BLACK = 'BLACK'}
+export enum RBTNColor { RED = 1, BLACK = 0}
 
-export type RBTreeNodeNested<T> = RBTreeNode<T, RBTreeNode<T, RBTreeNode<T, RBTreeNode<T, RBTreeNode<T, RBTreeNode<T, RBTreeNode<T, RBTreeNode<T, RBTreeNode<T, RBTreeNode<T, RBTreeNode<T, RBTreeNode<T, RBTreeNode<T, RBTreeNode<T, RBTreeNode<T, RBTreeNode<T, RBTreeNode<T, RBTreeNode<T, RBTreeNode<T, RBTreeNode<T, RBTreeNode<T, RBTreeNode<T, RBTreeNode<T, RBTreeNode<T, RBTreeNode<T, RBTreeNode<T, RBTreeNode<T, RBTreeNode<T, RBTreeNode<T, RBTreeNode<T, RBTreeNode<T, RBTreeNode<T, RBTreeNode<T, RBTreeNode<T, RBTreeNode<T, RBTreeNode<T, RBTreeNode<T, RBTreeNode<T, RBTreeNode<T, RBTreeNode<T, RBTreeNode<T, RBTreeNode<T, RBTreeNode<T, RBTreeNode<T, RBTreeNode<T, RBTreeNode<T, RBTreeNode<T, RBTreeNode<T, RBTreeNode<T, RBTreeNode<T, any>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>
-
-export type RBTreeOptions = BinaryTreeOptions & {}
+// export type RBTreeNodeNested<T> = RBTreeNode<T, RBTreeNode<T, RBTreeNode<T, RBTreeNode<T, RBTreeNode<T, RBTreeNode<T, RBTreeNode<T, RBTreeNode<T, RBTreeNode<T, RBTreeNode<T, RBTreeNode<T, RBTreeNode<T, RBTreeNode<T, RBTreeNode<T, RBTreeNode<T, RBTreeNode<T, RBTreeNode<T, RBTreeNode<T, RBTreeNode<T, RBTreeNode<T, RBTreeNode<T, RBTreeNode<T, RBTreeNode<T, RBTreeNode<T, RBTreeNode<T, RBTreeNode<T, RBTreeNode<T, RBTreeNode<T, RBTreeNode<T, RBTreeNode<T, RBTreeNode<T, RBTreeNode<T, RBTreeNode<T, RBTreeNode<T, RBTreeNode<T, RBTreeNode<T, RBTreeNode<T, RBTreeNode<T, RBTreeNode<T, RBTreeNode<T, RBTreeNode<T, RBTreeNode<T, RBTreeNode<T, RBTreeNode<T, RBTreeNode<T, RBTreeNode<T, RBTreeNode<T, RBTreeNode<T, RBTreeNode<T, RBTreeNode<T, any>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>
+//
+// export type RBTreeOptions = BinaryTreeOptions & {}

New alerts

License Policy Violation

License

This package is not allowed per your license policy. Review the package's license to ensure compliance.

Found 1 instance in 1 package

Fixed alerts

License Policy Violation

License

This package is not allowed per your license policy. Review the package's license to ensure compliance.

Found 1 instance in 1 package

Major refactor

Supply chain risk

Package has recently undergone a major refactor. It may be unstable or indicate significant internal changes. Use caution when updating to versions that include significant changes.

Found 1 instance in 1 package

Improved metrics

Total package byte prevSize

1285620

increased by1.39%

Lines of code

25356

increased by2.09%

Number of medium supply chain risk alerts

2

decreased by-33.33%

Dependency changes

• Updateddata-structure-typed@^1.41.0