/**
 * data-structure-typed
 *
 * @author Pablo Zeng
 * @copyright Copyright (c) 2022 Pablo Zeng <zrwusa@gmail.com>
 * @license MIT License
 */
import type { BTNRep, CRUD, EntryCallback, FamilyPosition, NodePredicate, RBTNColor, IterationType, RedBlackTreeOptions } from '../../types';
import { BST } from './bst';
import { IBinaryTree } from '../../interfaces';
export declare class RedBlackTreeNode<K = any, V = any> {
    key: K;
    value?: V;
    parent?: RedBlackTreeNode<K, V>;
    /**
     * Create a Red-Black Tree node.
     * @remarks Time O(1), Space O(1)
     * @param key - Node key.
     * @param [value] - Node value (unused in map mode trees).
     * @param color - Node color.
     */
    constructor(key: K, value?: V, color?: RBTNColor);
    _left?: RedBlackTreeNode<K, V> | null | undefined;
    /**
     * Get the left child pointer.
     * @remarks Time O(1), Space O(1)
     * @returns Left child node, or null/undefined.
     */
    get left(): RedBlackTreeNode<K, V> | null | undefined;
    /**
     * Set the left child and update its parent pointer.
     * @remarks Time O(1), Space O(1)
     * @param v - New left node, or null/undefined.
     * @returns void
     */
    set left(v: RedBlackTreeNode<K, V> | null | undefined);
    _right?: RedBlackTreeNode<K, V> | null | undefined;
    /**
     * Get the right child pointer.
     * @remarks Time O(1), Space O(1)
     * @returns Right child node, or null/undefined.
     */
    get right(): RedBlackTreeNode<K, V> | null | undefined;
    /**
     * Set the right child and update its parent pointer.
     * @remarks Time O(1), Space O(1)
     * @param v - New right node, or null/undefined.
     * @returns void
     */
    set right(v: RedBlackTreeNode<K, V> | null | undefined);
    _height: number;
    /**
     * Gets the height of the node (used in self-balancing trees).
     * @remarks Time O(1), Space O(1)
     *
     * @returns The height.
     */
    get height(): number;
    set height(value: number);
    _color: RBTNColor;
    /**
     * Gets the color of the node (used in Red-Black trees).
     * @remarks Time O(1), Space O(1)
     *
     * @returns The node's color.
     */
    get color(): RBTNColor;
    /**
     * Sets the color of the node.
     * @remarks Time O(1), Space O(1)
     *
     * @param value - The new color.
     */
    set color(value: RBTNColor);
    _count: number;
    /**
     * Gets the count of nodes in the subtree rooted at this node (used in order-statistic trees).
     * @remarks Time O(1), Space O(1)
     *
     * @returns The subtree node count.
     */
    get count(): number;
    /**
     * Gets the position of the node relative to its parent.
     * @remarks Time O(1), Space O(1)
     *
     * @returns The family position (e.g., 'ROOT', 'LEFT', 'RIGHT').
     */
    get familyPosition(): FamilyPosition;
}
/**
 * Represents a Red-Black Tree (self-balancing BST) supporting map-like mode and stable O(log n) updates.
 * @remarks Operation complexity depends on the method; see each method's docs.
 * @template K
 * @template V
 * @template R
 * 1. Efficient self-balancing, but not completely balanced. Compared with AVLTree, the addition and deletion efficiency is high, but the query efficiency is slightly lower.
 * 2. It is BST itself. Compared with Heap which is not completely ordered, RedBlackTree is completely ordered.
 *
 * @example
 * // Red-Black Tree with key-value pairs for lookups
 *  interface Employee {
 *       id: number;
 *       name: string;
 *     }
 *
 *     // Create tree with employee data
 *     const employees = new RedBlackTree<number, Employee>([
 *       [1, { id: 1, name: 'Alice' }],
 *       [3, { id: 3, name: 'Charlie' }],
 *       [2, { id: 2, name: 'Bob' }]
 *     ]);
 *
 *     // Retrieve employee by ID
 *     const alice = employees.get(1);
 *     console.log(alice?.name); // 'Alice';
 *
 *     // Verify sorted order by ID
 *     console.log([...employees.keys()]); // [1, 2, 3];
 * @example
 * // Red-Black Tree range search for filtering
 *  interface Product {
 *       name: string;
 *       price: number;
 *     }
 *
 *     const products = new RedBlackTree<number, Product>([
 *       [10, { name: 'Item A', price: 10 }],
 *       [25, { name: 'Item B', price: 25 }],
 *       [40, { name: 'Item C', price: 40 }],
 *       [50, { name: 'Item D', price: 50 }]
 *     ]);
 *
 *     // Find products in price range [20, 45]
 *     const pricesInRange = products.rangeSearch([20, 45], node => {
 *       return products.get(node)?.name;
 *     });
 *
 *     console.log(pricesInRange); // ['Item B', 'Item C'];
 * @example
 * // Red-Black Tree as database index for stock market data
 *  interface StockPrice {
 *       symbol: string;
 *       volume: number;
 *       timestamp: Date;
 *     }
 *
 *     // Simulate real-time stock price index
 *     const priceIndex = new RedBlackTree<number, StockPrice>([
 *       [142.5, { symbol: 'AAPL', volume: 1000000, timestamp: new Date() }],
 *       [335.2, { symbol: 'MSFT', volume: 800000, timestamp: new Date() }],
 *       [3285.04, { symbol: 'AMZN', volume: 500000, timestamp: new Date() }],
 *       [267.98, { symbol: 'META', volume: 750000, timestamp: new Date() }],
 *       [234.57, { symbol: 'GOOGL', volume: 900000, timestamp: new Date() }]
 *     ]);
 *
 *     // Find highest-priced stock
 *     const maxPrice = priceIndex.getRightMost();
 *     console.log(priceIndex.get(maxPrice)?.symbol); // 'AMZN';
 *
 *     // Find stocks in price range [200, 400] for portfolio balancing
 *     const stocksInRange = priceIndex.rangeSearch([200, 400], node => {
 *       const stock = priceIndex.get(node);
 *       return {
 *         symbol: stock?.symbol,
 *         price: node,
 *         volume: stock?.volume
 *       };
 *     });
 *
 *     console.log(stocksInRange.length); // 3;
 *     console.log(stocksInRange.some((s: any) => s.symbol === 'GOOGL')); // true;
 *     console.log(stocksInRange.some((s: any) => s.symbol === 'META')); // true;
 *     console.log(stocksInRange.some((s: any) => s.symbol === 'MSFT')); // true;
 */
export declare class RedBlackTree<K = any, V = any, R = any> extends BST<K, V, R> implements IBinaryTree<K, V, R> {
    constructor(keysNodesEntriesOrRaws?: Iterable<K | RedBlackTreeNode<K, V> | [K | null | undefined, V | undefined] | null | undefined | R>, options?: RedBlackTreeOptions<K, V, R>);
    protected _root: RedBlackTreeNode<K, V> | undefined;
    /**
     * (Internal) Header sentinel:
     * - header.parent -> root
     * - header._left  -> min (or NIL)
     * - header._right -> max (or NIL)
     *
     * IMPORTANT:
     * - This header is NOT part of the actual tree.
     * - Do NOT use `header.left` / `header.right` accessors for wiring: those setters update `NIL.parent`
     *   and can corrupt sentinel invariants / cause hangs. Only touch `header._left/_right`.
     */
    protected _header: RedBlackTreeNode<K, V>;
    /**
     * (Internal) Cache of the current minimum and maximum nodes.
     * Used for fast-path insert/update when keys are monotonic or near-boundary.
     */
    protected _minNode: RedBlackTreeNode<K, V> | undefined;
    protected _maxNode: RedBlackTreeNode<K, V> | undefined;
    /**
     * Get the current root node.
     * @remarks Time O(1), Space O(1)
     * @returns Root node, or undefined.
     */
    get root(): RedBlackTreeNode<K, V> | undefined;
    /**
     * Create a red-black node for the given key/value (value ignored in map mode).
     * @remarks Time O(1), Space O(1)
     * @param key - See parameter type for details.
     * @param [value] - See parameter type for details.
     * @param color - See parameter type for details.
     * @returns A new RedBlackTreeNode instance.
     */
    createNode(key: K, value?: V, color?: RBTNColor): RedBlackTreeNode<K, V>;
    /**
     * Type guard: check whether the input is a RedBlackTreeNode.
     * @remarks Time O(1), Space O(1)
     * @param keyNodeOrEntry - See parameter type for details.
     * @returns True if the value is a RedBlackTreeNode.
     */
    isNode(keyNodeOrEntry: K | RedBlackTreeNode<K, V> | [K | null | undefined, V | undefined] | null | undefined): keyNodeOrEntry is RedBlackTreeNode<K, V>;
    /**
     * Remove all nodes, clear the key→value store (if in map mode) and internal caches.
     * @remarks Time O(n), Space O(1)
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
      * @example
   * // Remove all entries
   *  const rbt = new RedBlackTree<number>([1, 2, 3]);
   *     rbt.clear();
   *     console.log(rbt.isEmpty()); // true;
     */
    clear(): void;
    /**
     * (Internal) Find a node by key using a tight BST walk (no allocations).
     *
     * NOTE: This uses `header.parent` as the canonical root pointer.
     * @remarks Time O(log n) average, Space O(1)
     */
    protected _findNodeByKey(key: K): RedBlackTreeNode<K, V> | undefined;
    /**
     * (Internal) In-order predecessor of a node in a BST.
     * @remarks Time O(log n) average, Space O(1)
     */
    protected _predecessorOf(node: RedBlackTreeNode<K, V>): RedBlackTreeNode<K, V> | undefined;
    /**
     * (Internal) In-order successor of a node in a BST.
     * @remarks Time O(log n) average, Space O(1)
     */
    protected _successorOf(node: RedBlackTreeNode<K, V>): RedBlackTreeNode<K, V> | undefined;
    /**
     * (Internal) Attach a new node directly under a known parent/side (no search).
     *
     * This is a performance-oriented helper used by boundary fast paths and hinted insertion.
     * It will:
     * - wire parent/child pointers (using accessors, so parent pointers are updated)
     * - initialize children to NIL
     * - mark the new node RED, then run insert fix-up
     *
     * Precondition: the chosen slot (parent.left/parent.right) is empty (NIL/null/undefined).
     * @remarks Time O(log n) average, Space O(1)
     */
    protected _attachNewNode(parent: RedBlackTreeNode<K, V>, side: 'left' | 'right', node: RedBlackTreeNode<K, V>): void;
    /**
     * (Internal) a single source of truth for min/max is header._left/_right.
     * Keep legacy _minNode/_maxNode mirrored for compatibility.
     * @remarks Time O(1), Space O(1)
     */
    /**
     * (Internal) Update min cache pointers (header._left is the canonical min pointer).
     * @remarks Time O(1), Space O(1)
     */
    protected _setMinCache(node: RedBlackTreeNode<K, V> | undefined): void;
    /**
     * (Internal) Update max cache pointers (header._right is the canonical max pointer).
     * @remarks Time O(1), Space O(1)
     */
    protected _setMaxCache(node: RedBlackTreeNode<K, V> | undefined): void;
    /**
     * (Internal) Core set implementation returning the affected node.
     *
     * Hot path goals:
     * - Avoid double walks (search+insert): do a single traversal that either updates or inserts.
     * - Use header min/max caches to fast-path boundary inserts.
     * - Keep header._left/_right as canonical min/max pointers.
     *
     * Return value:
     * - `{ node, created:false }` when an existing key is updated
     * - `{ node, created:true }` when a new node is inserted
     * - `undefined` only on unexpected internal failure.
     * @remarks Time O(log n) average, Space O(1)
     */
    protected _setKVNode(key: K, nextValue?: V): {
        node: RedBlackTreeNode<K, V>;
        created: boolean;
    } | undefined;
    /**
     * (Internal) Boolean wrapper around `_setKVNode`.
     *
     * Includes a map-mode update fast-path:
     * - If `isMapMode=true` and the key already exists in `_store`, then updating the value does not
     *   require any tree search/rotation (tree shape depends only on key).
     * - This path is intentionally limited to `nextValue !== undefined` to preserve existing
     *   semantics for `undefined` values.
     * @remarks Time O(log n) average, Space O(1)
     */
    protected _setKV(key: K, nextValue?: V): boolean;
    /**
     * Insert/update using a hint node to speed up nearby insertions.
     *
     * close to the expected insertion position (often the previously returned node in a loop).
     *
     * When the hint is a good fit (sorted / nearly-sorted insertion), this can avoid most of the
     * normal root-to-leaf search and reduce constant factors.
     *
     * When the hint does not match (random workloads), this will fall back to the normal set path.
     * @remarks Time O(log n) average, Space O(1)
     */
    setWithHintNode(key: K, value: V, hint?: RedBlackTreeNode<K, V>): RedBlackTreeNode<K, V> | undefined;
    /**
     * Boolean wrapper for setWithHintNode.
     * @remarks Time O(log n) average, Space O(1)
     */
    setWithHint(key: K, value: V, hint?: RedBlackTreeNode<K, V>): boolean;
    /**
     * Insert or update a key/value (map mode) or key-only (set mode).
     *
     * This method is optimized for:
     * - monotonic inserts via min/max boundary fast paths
     * - updates via a single-pass search (no double walk)
     *
     * @remarks Time O(log n) average, Space O(1)
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
      * @example
   * // basic Red-Black Tree with simple number keys
   *  // Create a simple Red-Black Tree with numeric keys
   *     const tree = new RedBlackTree([5, 2, 8, 1, 9]);
   *
   *     tree.print();
   *     //   _2___
   *     //  /     \
   *     //  1    _8_
   *     //      /   \
   *     //      5   9
   *
   *     // Verify the tree maintains sorted order
   *     console.log([...tree.keys()]); // [1, 2, 5, 8, 9];
   *
   *     // Check size
   *     console.log(tree.size); // 5;
     */
    set(keyNodeOrEntry: K | RedBlackTreeNode<K, V> | [K | null | undefined, V | undefined] | null | undefined, value?: V): boolean;
    /**
     * Delete a node by key/node/entry and rebalance as needed.
     * @remarks Time O(log n) average, Space O(1)
     * @param keyNodeEntryRawOrPredicate - Key, node, or [key, value] entry identifying the node to delete.
     * @returns Array with deletion metadata (removed node, rebalancing hint if any).
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
      * @example
   * // Remove and rebalance
   *  const rbt = new RedBlackTree<number>([10, 5, 15, 3, 7]);
   *     rbt.delete(5);
   *     console.log(rbt.has(5)); // false;
   *     console.log(rbt.size); // 4;
     */
    delete(keyNodeEntryRawOrPredicate: BTNRep<K, V, RedBlackTreeNode<K, V>> | NodePredicate<RedBlackTreeNode<K, V> | null>): boolean;
    /**
     * Transform entries into a like-kind red-black tree with possibly different key/value types.
     * @remarks Time O(n) average, Space O(n)
     * @template MK
     * @template MV
     * @template MR
     * @param callback - Mapping function from (key, value, index, tree) to a new [key, value].
     * @param [options] - See parameter type for details.
     * @param [thisArg] - See parameter type for details.
     * @returns A new RedBlackTree with mapped entries.
     */
    /**
     * Red-Black trees are self-balancing — `perfectlyBalance` rebuilds via
     * sorted bulk insert, which naturally produces a balanced RBT.
     * @remarks Time O(N), Space O(N)
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
      * @example
   * // Rebalance tree
   *  const rbt = new RedBlackTree<number>([1, 2, 3, 4, 5]);
   *     rbt.perfectlyBalance();
   *     console.log(rbt.isAVLBalanced()); // true;
     */
    perfectlyBalance(_iterationType?: IterationType): boolean;
    /**
   * Transform to new tree
  
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
    * @example
 * // Transform to new tree
 *  const rbt = new RedBlackTree<number, number>([[1, 10], [2, 20]]);
 *     const doubled = rbt.map((v, k) => [k, (v ?? 0) * 2] as [number, number]);
 *     console.log([...doubled.values()]); // [20, 40];
   */
    map<MK = K, MV = V, MR = any>(callback: EntryCallback<K, V | undefined, [MK, MV]>, options?: Partial<RedBlackTreeOptions<MK, MV, MR>>, thisArg?: unknown): RedBlackTree<MK, MV, MR>;
    /**
     * (Internal) Create an empty instance of the same concrete tree type.
     * @remarks Time O(1) average, Space O(1)
     */
    protected _createInstance<TK = K, TV = V, TR = R>(options?: Partial<RedBlackTreeOptions<TK, TV, TR>>): this;
    /**
     * (Internal) Create a like-kind tree (same concrete class) populated from an iterable.
     * @remarks Time O(m log m) average (m = iterable length), Space O(m)
     */
    protected _createLike<TK = K, TV = V, TR = R>(iter?: Iterable<TK | RedBlackTreeNode<TK, TV> | [TK | null | undefined, TV | undefined] | null | undefined | TR>, options?: Partial<RedBlackTreeOptions<TK, TV, TR>>): RedBlackTree<TK, TV, TR>;
    /**
     * (Internal) Set the root pointer and keep header.parent in sync.
     * @remarks Time O(1), Space O(1)
     */
    protected _setRoot(v: RedBlackTreeNode<K, V> | undefined): void;
    /**
     * (Internal) Replace a node in place while preserving its color.
     * @remarks Time O(1) average, Space O(1)
     */
    protected _replaceNode(oldNode: RedBlackTreeNode<K, V>, newNode: RedBlackTreeNode<K, V>): RedBlackTreeNode<K, V>;
    /**
     * (Protected) Standard BST insert followed by red-black fix-up.
     * @remarks Time O(log n) average, Space O(1)
     * @param node - Node to insert.
     * @returns Status string: 'CREATED' or 'UPDATED'.
     */
    protected _insert(node: RedBlackTreeNode<K, V>): CRUD;
    /**
     * (Protected) Transplant a subtree in place of another during deletion.
     * @remarks Time O(1), Space O(1)
     * @param u - Node to replace.
     * @param v - Replacement subtree root (may be undefined).
     * @returns void
     */
    protected _transplant(u: RedBlackTreeNode<K, V>, v: RedBlackTreeNode<K, V> | undefined): void;
    /**
     * (Protected) Restore red-black properties after insertion (recolor/rotate).
     * @remarks Time O(log n) average, Space O(1)
     * @param z - Recently inserted node.
     * @returns void
     */
    protected _insertFixup(z: RedBlackTreeNode<K, V> | undefined): void;
    /**
     * (Protected) Restore red-black properties after deletion (recolor/rotate).
     * @remarks Time O(log n) average, Space O(1)
     * @param node - Child that replaced the deleted node (may be undefined).
     * @returns void
     */
    protected _deleteFixup(node: RedBlackTreeNode<K, V> | undefined): void;
    /**
     * (Protected) Perform a left rotation around x.
     * @remarks Time O(1), Space O(1)
     * @param x - Pivot node to rotate around.
     * @returns void
     */
    protected _leftRotate(x: RedBlackTreeNode<K, V> | undefined): void;
    /**
     * (Protected) Perform a right rotation around y.
     * @remarks Time O(1), Space O(1)
     * @param y - Pivot node to rotate around.
     * @returns void
     */
    protected _rightRotate(y: RedBlackTreeNode<K, V> | undefined): void;
}