Class AVLTree<K, V, R>

Represents a self-balancing AVL (Adelson-Velsky and Landis) Tree. This tree extends BST and performs rotations on add/delete to maintain balance.

Example

// basic AVLTree creation and add operation
 // Create a simple AVLTree with initial values
    const tree = new AVLTree([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;

    // Add a new element
    tree.add(3);
    console.log(tree.size); // 6;
    console.log([...tree.keys()]); // [1, 2, 3, 5, 8, 9];

Example

// AVLTree has and get operations
 const tree = new AVLTree<number>([11, 3, 15, 1, 8, 13, 16, 2, 6, 9, 12, 14, 4, 7, 10, 5]);

    // Check if element exists
    console.log(tree.has(6)); // true;
    console.log(tree.has(99)); // false;

    // Get node by key
    const node = tree.getNode(6);
    console.log(node?.key); // 6;

    // Verify tree is balanced
    console.log(tree.isAVLBalanced()); // true;

Example

// AVLTree delete and balance verification
 const tree = new AVLTree([11, 3, 15, 1, 8, 13, 16, 2, 6, 9, 12, 14, 4, 7, 10, 5]);

    // Delete an element
    tree.delete(10);
    console.log(tree.has(10)); // false;

    // Tree should remain balanced after deletion
    console.log(tree.isAVLBalanced()); // true;

    // Size decreased
    console.log(tree.size); // 15;

    // Remaining elements are still sorted
    const keys = [...tree.keys()];
    console.log(keys); // [1, 2, 3, 4, 5, 6, 7, 8, 9, 11, 12, 13, 14, 15, 16];

Example

// AVLTree for university ranking system with strict balance
 interface University {
      name: string;
      rank: number;
      students: number;
    }

    // AVLTree provides highest search efficiency with strict balance
    // (every node's left/right subtrees differ by at most 1 in height)
    const universityTree = new AVLTree<number, University>([
      [1, { name: 'MIT', rank: 1, students: 1200 }],
      [5, { name: 'Stanford', rank: 5, students: 1800 }],
      [3, { name: 'Harvard', rank: 3, students: 2300 }],
      [2, { name: 'Caltech', rank: 2, students: 400 }],
      [4, { name: 'CMU', rank: 4, students: 1500 }]
    ]);

    // Quick lookup by rank
    const mit = universityTree.get(1);
    console.log(mit?.name); // 'MIT';

    const cmulevel = universityTree.getHeight(4);
    console.log(typeof cmulevel); // 'number';

    // Tree maintains strict balance during insertions and deletions
    console.log(universityTree.isAVLBalanced()); // true;

    // Add more universities
    universityTree.add(6, { name: 'Oxford', rank: 6, students: 2000 });
    console.log(universityTree.isAVLBalanced()); // true;

    // Delete and verify balance is maintained
    universityTree.delete(2);
    console.log(universityTree.has(2)); // false;
    console.log(universityTree.isAVLBalanced()); // true;

    // Get all remaining universities in rank order
    const remainingRanks = [...universityTree.keys()];
    console.log(remainingRanks); // [1, 3, 4, 5, 6];
    console.log(universityTree.size); // 5;

Example

// Find elements in a range
 // In interval queries, AVL trees, with their strictly balanced structure and lower height, offer better query efficiency, making them ideal for frequent and high-performance interval queries. In contrast, Red-Black trees, with lower update costs, are more suitable for scenarios involving frequent insertions and deletions where the requirements for interval queries are less demanding.
    type Datum = { timestamp: Date; temperature: number };
    // Fixed dataset of CPU temperature readings
    const cpuData: Datum[] = [
      { timestamp: new Date('2024-12-02T00:00:00'), temperature: 55.1 },
      { timestamp: new Date('2024-12-02T00:01:00'), temperature: 56.3 },
      { timestamp: new Date('2024-12-02T00:02:00'), temperature: 54.8 },
      { timestamp: new Date('2024-12-02T00:03:00'), temperature: 57.2 },
      { timestamp: new Date('2024-12-02T00:04:00'), temperature: 58.0 },
      { timestamp: new Date('2024-12-02T00:05:00'), temperature: 59.4 },
      { timestamp: new Date('2024-12-02T00:06:00'), temperature: 60.1 },
      { timestamp: new Date('2024-12-02T00:07:00'), temperature: 61.3 },
      { timestamp: new Date('2024-12-02T00:08:00'), temperature: 62.0 },
      { timestamp: new Date('2024-12-02T00:09:00'), temperature: 63.5 },
      { timestamp: new Date('2024-12-02T00:10:00'), temperature: 64.0 },
      { timestamp: new Date('2024-12-02T00:11:00'), temperature: 62.8 },
      { timestamp: new Date('2024-12-02T00:12:00'), temperature: 61.5 },
      { timestamp: new Date('2024-12-02T00:13:00'), temperature: 60.2 },
      { timestamp: new Date('2024-12-02T00:14:00'), temperature: 59.8 },
      { timestamp: new Date('2024-12-02T00:15:00'), temperature: 58.6 },
      { timestamp: new Date('2024-12-02T00:16:00'), temperature: 57.4 },
      { timestamp: new Date('2024-12-02T00:17:00'), temperature: 56.2 },
      { timestamp: new Date('2024-12-02T00:18:00'), temperature: 55.7 },
      { timestamp: new Date('2024-12-02T00:19:00'), temperature: 54.5 },
      { timestamp: new Date('2024-12-02T00:20:00'), temperature: 53.2 },
      { timestamp: new Date('2024-12-02T00:21:00'), temperature: 52.8 },
      { timestamp: new Date('2024-12-02T00:22:00'), temperature: 51.9 },
      { timestamp: new Date('2024-12-02T00:23:00'), temperature: 50.5 },
      { timestamp: new Date('2024-12-02T00:24:00'), temperature: 49.8 },
      { timestamp: new Date('2024-12-02T00:25:00'), temperature: 48.7 },
      { timestamp: new Date('2024-12-02T00:26:00'), temperature: 47.5 },
      { timestamp: new Date('2024-12-02T00:27:00'), temperature: 46.3 },
      { timestamp: new Date('2024-12-02T00:28:00'), temperature: 45.9 },
      { timestamp: new Date('2024-12-02T00:29:00'), temperature: 45.0 }
    ];

    // Create an AVL tree to store CPU temperature data
    const cpuTemperatureTree = new AVLTree<Date, number, Datum>(cpuData, {
      toEntryFn: ({ timestamp, temperature }) => [timestamp, temperature]
    });

    // Query a specific time range (e.g., from 00:05 to 00:15)
    const rangeStart = new Date('2024-12-02T00:05:00');
    const rangeEnd = new Date('2024-12-02T00:15:00');
    const rangeResults = cpuTemperatureTree.rangeSearch([rangeStart, rangeEnd], node => ({
      minute: node ? node.key.getMinutes() : 0,
      temperature: cpuTemperatureTree.get(node ? node.key : undefined)
    }));

    console.log(rangeResults); // [
 //      { minute: 5, temperature: 59.4 },
 //      { minute: 6, temperature: 60.1 },
 //      { minute: 7, temperature: 61.3 },
 //      { minute: 8, temperature: 62 },
 //      { minute: 9, temperature: 63.5 },
 //      { minute: 10, temperature: 64 },
 //      { minute: 11, temperature: 62.8 },
 //      { minute: 12, temperature: 61.5 },
 //      { minute: 13, temperature: 60.2 },
 //      { minute: 14, temperature: 59.8 },
 //      { minute: 15, temperature: 58.6 }
 //    ];

Type Parameters

K = any
The type of the key.
V = any
The type of the value.
R = any
The type of the raw data object (if using toEntryFn).
1. Height-Balanced: Each node's left and right subtrees differ in height by no more than one.
2. Automatic Rebalancing: AVL trees rebalance themselves automatically during insertions and deletions.
3. Rotations for Balancing: Utilizes rotations (single or double) to maintain balance after updates.
4. Order Preservation: Maintains the binary search tree property where left child values are less than the parent, and right child values are greater.
5. Efficient Lookups: Offers O(log n) search time, where 'n' is the number of nodes, due to its balanced nature.
6. Complex Insertions and Deletions: Due to rebalancing, these operations are more complex than in a regular BST.
7. Path Length: The path length from the root to any leaf is longer compared to an unbalanced BST, but shorter than a linear chain of nodes.

Hierarchy (view full)

BST<K, V, R>
- AVLTree
  - AVLTreeMultiMap
  - AVLTreeCounter

Implements

IBinaryTree<K, V, R>

Index

Constructors

constructor

new AVLTree<K, V, R>(keysNodesEntriesOrRaws?, options?): AVLTree<K, V, R>
Creates an instance of AVLTree.
Type Parameters
- K = any
- V = any
- R = any
Parameters
- OptionalkeysNodesEntriesOrRaws: Iterable<
      | undefined
      | null
      | K
      | R
      | AVLTreeNode<K, V>
      | [undefined | null | K, undefined | V], any, any> = []
  An iterable of items to add.
- Optionaloptions: AVLTreeOptions<K, V, R>
  Configuration options for the AVL tree.
Returns AVLTree<K, V, R>
Remarks
Time O(N log N) (from addMany with balanced add). Space O(N).
Overrides BST.constructor
- Defined in data-structures/binary-tree/avl-tree.ts:366

Properties

`Protected`_comparator

_comparator: Comparator<K>

The comparator function used to determine the order of keys in the tree.

Remarks

Time O(1) Space O(1)

Accessors

comparator

get comparator(): Comparator<K>
Gets the comparator function used by the tree.

Returns Comparator<K>
The comparator function.

Remarks
Time O(1)
Inherited from BST.comparator
- Defined in data-structures/binary-tree/bst.ts:401

isDuplicate

get isDuplicate(): boolean
Gets whether the tree allows duplicate keys.

Returns boolean
True if duplicates are allowed, false otherwise.

Remarks
Time O(1)
Implementation of IBinaryTree.isDuplicate
Inherited from BST.isDuplicate
- Defined in data-structures/binary-tree/binary-tree.ts:400

isMapMode

get isMapMode(): boolean
Gets whether the tree is in Map mode.

Returns boolean
True if in Map mode, false otherwise.

Remarks
In Map mode (default), values are stored in an external Map, and nodes only hold keys. If false, values are stored directly on the nodes. Time O(1)
Implementation of IBinaryTree.isMapMode
Inherited from BST.isMapMode
- Defined in data-structures/binary-tree/binary-tree.ts:388

NIL

get NIL(): BinaryTreeNode<K, V>
Gets the sentinel NIL node (used in self-balancing trees like Red-Black Tree).

Returns BinaryTreeNode<K, V>
The NIL node.

Remarks
Time O(1)
Implementation of IBinaryTree.NIL
Inherited from BST.NIL
- Defined in data-structures/binary-tree/binary-tree.ts:448

root

get root(): OptNode<BSTNode<K, V>>
Gets the root node of the tree.

Returns OptNode<BSTNode<K, V>>
The root node.

Remarks
Time O(1)
Implementation of IBinaryTree.root
Inherited from BST.root
- Defined in data-structures/binary-tree/bst.ts:384

size

get size(): number
Gets the number of nodes in the tree.

Returns number
The size of the tree.

Remarks
Time O(1)
Implementation of IBinaryTree.size
Inherited from BST.size
- Defined in data-structures/binary-tree/binary-tree.ts:436

store

get store(): Map<K, undefined | V>
Gets the external value store (used in Map mode).

Returns Map<K, undefined | V>
The map storing key-value pairs.

Remarks
Time O(1)
Implementation of IBinaryTree.store
Inherited from BST.store
- Defined in data-structures/binary-tree/binary-tree.ts:412

toEntryFn

get toEntryFn(): undefined | ToEntryFn<K, V, R>
Gets the function used to convert raw data objects (R) into [key, value] entries.

Returns undefined | ToEntryFn<K, V, R>
The conversion function.

Remarks
Time O(1)
Implementation of IBinaryTree.toEntryFn
Inherited from BST.toEntryFn
- Defined in data-structures/binary-tree/binary-tree.ts:460

Methods

`Protected`_balanceFactor

_balanceFactor(node): number
(Protected) Calculates the balance factor (height(right) - height(left)).
Parameters
- node: AVLTreeNode<K, V>
  The node to check.
Returns number
The balance factor (positive if right-heavy, negative if left-heavy).

Remarks
Time O(1) (assumes heights are stored).
- Defined in data-structures/binary-tree/avl-tree.ts:587

`Protected`_balanceLL

_balanceLL(A): void
(Protected) Performs a Left-Left (LL) rotation (a single right rotation).
Parameters
- A: AVLTreeNode<K, V>
  The unbalanced node (root of the unbalanced subtree).
Returns void
Remarks
Time O(1), Space O(1)
- Defined in data-structures/binary-tree/avl-tree.ts:611

`Protected`_balanceLR

_balanceLR(A): void
(Protected) Performs a Left-Right (LR) double rotation.
Parameters
- A: AVLTreeNode<K, V>
  The unbalanced node (root of the unbalanced subtree).
Returns void
Remarks
Time O(1), Space O(1)
- Defined in data-structures/binary-tree/avl-tree.ts:646

`Protected`_balancePath

_balancePath(node): void
(Protected) Traverses up the tree from the specified node, updating heights and performing rotations as needed.
Parameters
- node:
      | undefined
      | null
      | K
      | AVLTreeNode<K, V>
      | [undefined | null | K, undefined | V]
  The node to start balancing from (e.g., the newly inserted node or parent of the deleted node).
Returns void
Remarks
Time O(log N) (O(H)), as it traverses the path to root. Space O(H) for the path array.
- Defined in data-structures/binary-tree/avl-tree.ts:788

`Protected`_balanceRL

_balanceRL(A): void
(Protected) Performs a Right-Left (RL) double rotation.
Parameters
- A: AVLTreeNode<K, V>
  The unbalanced node (root of the unbalanced subtree).
Returns void
Remarks
Time O(1), Space O(1)
- Defined in data-structures/binary-tree/avl-tree.ts:737

`Protected`_balanceRR

_balanceRR(A): void
(Protected) Performs a Right-Right (RR) rotation (a single left rotation).
Parameters
- A: AVLTreeNode<K, V>
  The unbalanced node (root of the unbalanced subtree).
Returns void
Remarks
Time O(1), Space O(1)
- Defined in data-structures/binary-tree/avl-tree.ts:698

`Protected`_bound

_bound(keyNodeEntryOrPredicate, isLower, iterationType): undefined | BSTNode<K, V>
(Protected) Core bound search implementation supporting all parameter types. Unified logic for both lowerBound and upperBound. Resolves various input types (Key, Node, Entry, Predicate) using parent class utilities.
Parameters
- keyNodeEntryOrPredicate:
      | undefined
      | null
      | K
      | BSTNode<K, V>
      | [undefined | null | K, undefined | V]
      | NodePredicate<BSTNode<K, V>>
  The key, node, entry, or predicate function to search for.
- isLower: boolean
  True for lowerBound (>=), false for upperBound (>).
- iterationType: IterationType
  The iteration type (RECURSIVE or ITERATIVE).
Returns undefined | BSTNode<K, V>
The first matching node, or undefined if no such node exists.
Inherited from BST._bound
- Defined in data-structures/binary-tree/bst.ts:1709

`Protected`_boundByKey

_boundByKey(key, isLower, iterationType): undefined | BSTNode<K, V>
(Protected) Binary search for bound by key with pruning optimization. Performs standard BST binary search, choosing left or right subtree based on comparator result. For lowerBound: finds first node where key >= target. For upperBound: finds first node where key > target.
Parameters
- key: K
  The target key to search for.
- isLower: boolean
  True for lowerBound (>=), false for upperBound (>).
- iterationType: IterationType
  The iteration type (RECURSIVE or ITERATIVE).
Returns undefined | BSTNode<K, V>
The first node matching the bound condition, or undefined if none exists.
Inherited from BST._boundByKey
- Defined in data-structures/binary-tree/bst.ts:1765

`Protected`_boundByPredicate

_boundByPredicate(predicate, iterationType): undefined | BSTNode<K, V>
(Protected) In-order traversal search by predicate. Falls back to linear in-order traversal when predicate-based search is required. Returns the first node that satisfies the predicate function. Note: Predicate-based search cannot leverage BST's binary search optimization. Time Complexity: O(n) since it may visit every node.
Parameters
- predicate: NodePredicate<BSTNode<K, V>>
  The predicate function to test nodes.
- iterationType: IterationType
  The iteration type (RECURSIVE or ITERATIVE).
Returns undefined | BSTNode<K, V>
The first node satisfying predicate, or undefined if none found.
Inherited from BST._boundByPredicate
- Defined in data-structures/binary-tree/bst.ts:1820

`Protected`_clearNodes

_clearNodes(): void
(Protected) Clears all nodes from the tree.

Returns void
Remarks
Time O(1)
Inherited from BST._clearNodes
- Defined in data-structures/binary-tree/binary-tree.ts:2482

`Protected`_clearValues

_clearValues(): void
(Protected) Clears all values from the external store.

Returns void
Remarks
Time O(N)
Inherited from BST._clearValues
- Defined in data-structures/binary-tree/binary-tree.ts:2491

`Protected`_clone

_clone(cloned): void
(Protected) Helper for cloning. Performs a BFS and adds all nodes to the new tree.
Parameters
- cloned: BinaryTree<K, V, R>
  The new, empty tree instance to populate.
Returns void
Remarks
Time O(N * M) (O(N) BFS + O(M) add for each node).
Inherited from BST._clone
- Defined in data-structures/binary-tree/binary-tree.ts:2212

`Protected`_compare

_compare(a, b): number
(Protected) Compares two keys using the tree's comparator and reverse setting.
Parameters
- a: K
  The first key.
- b: K
  The second key.
Returns number
A number (1, -1, or 0) representing the comparison.

Remarks
Time O(1) Space O(1)
Inherited from BST._compare
- Defined in data-structures/binary-tree/bst.ts:1960

`Protected`_createDefaultComparator

_createDefaultComparator(): Comparator<K>
(Protected) Creates the default comparator function for keys that don't have a custom comparator.

Returns Comparator<K>
The default comparator function.

Remarks
Time O(1) Space O(1)
Inherited from BST._createDefaultComparator
- Defined in data-structures/binary-tree/bst.ts:1442

`Protected`_createInstance

_createInstance<TK, TV, TR>(options?): this
(Protected) Creates a new, empty instance of the same AVLTree constructor.
Type Parameters
- TK = K
- TV = V
- TR = R
Parameters
- Optionaloptions: Partial<AVLTreeOptions<TK, TV, TR>>
  Options for the new tree.
Returns this
A new, empty tree.

Remarks
Time O(1)
Overrides BST._createInstance
- Defined in data-structures/binary-tree/avl-tree.ts:514

`Protected`_createLike

_createLike<TK, TV, TR>(iter?, options?): AVLTree<TK, TV, TR>
(Protected) Creates a new instance of the same AVLTree constructor, potentially with different generic types.
Type Parameters
- TK = K
- TV = V
- TR = R
Parameters
- Optionaliter: Iterable<
      | undefined
      | null
      | TK
      | TR
      | AVLTreeNode<TK, TV>
      | [undefined | null | TK, undefined | TV], any, any> = []
  An iterable to populate the new tree.
- Optionaloptions: Partial<AVLTreeOptions<TK, TV, TR>>
  Options for the new tree.
Returns AVLTree<TK, TV, TR>
A new AVLTree.

Remarks
Time O(N log N) (from constructor) due to processing the iterable.
Overrides BST._createLike
- Defined in data-structures/binary-tree/avl-tree.ts:531

`Protected`_DEFAULT_NODE_CALLBACK

_DEFAULT_NODE_CALLBACK(node): undefined | K
(Protected) Default callback function, returns the node's key.
Parameters
- node: undefined | null | BinaryTreeNode<K, V>
  The node.
Returns undefined | K
The node's key or undefined.

Remarks
Time O(1)
Inherited from BST._DEFAULT_NODE_CALLBACK
- Defined in data-structures/binary-tree/binary-tree.ts:2120

`Protected`_deleteByKey

_deleteByKey(key): boolean
(Private) Deletes a node by its key.
Parameters
- key: K
  The key of the node to delete.
Returns boolean
True if the node was found and deleted, false otherwise.

Remarks
Standard BST deletion algorithm. Time O(log N), O(N) worst-case. Space O(1).
Inherited from BST._deleteByKey
- Defined in data-structures/binary-tree/bst.ts:1971

`Protected`_dfs

_dfs<C>(callback, pattern?, onlyOne?, startNode?, iterationType?, includeNull?, shouldVisitLeft?, shouldVisitRight?, shouldVisitRoot?, shouldProcessRoot?): ReturnType<C>[]
Type Parameters
- C extends NodeCallback<BinaryTreeNode<K, V>>
  Callback type.
Parameters
- callback: C
  Function to call on nodes.
- Optionalpattern: DFSOrderPattern
  Traversal order.
- OptionalonlyOne: boolean
  Stop after first match.
- OptionalstartNode:
      | null
      | K
      | [undefined | null | K, undefined | V]
      | BinaryTreeNode<K, V>
  Starting node.
- OptionaliterationType: IterationType
  Traversal method.
- OptionalincludeNull: boolean
  Include nulls.
- OptionalshouldVisitLeft: ((node: undefined | null | BinaryTreeNode<K, V>) => boolean)
  Predicate to traverse left.
  - - (node): boolean
    - Parameters
      node: undefined | null | BinaryTreeNode<K, V>
      Returns boolean
- OptionalshouldVisitRight: ((node: undefined | null | BinaryTreeNode<K, V>) => boolean)
  Predicate to traverse right.
  - - (node): boolean
    - Parameters
      node: undefined | null | BinaryTreeNode<K, V>
      Returns boolean
- OptionalshouldVisitRoot: ((node: undefined | null | BinaryTreeNode<K, V>) => boolean)
  Predicate to visit root.
  - - (node): boolean
    - Parameters
      node: undefined | null | BinaryTreeNode<K, V>
      Returns boolean
- OptionalshouldProcessRoot: ((node: undefined | null | BinaryTreeNode<K, V>) => boolean)
  Predicate to process root.
  - - (node): boolean
    - Parameters
      node: undefined | null | BinaryTreeNode<K, V>
      Returns boolean
Returns ReturnType<C>[]
Array of callback results.
Inherited from BST._dfs
- Defined in data-structures/binary-tree/binary-tree.ts:1929

`Protected`_displayAux

_displayAux(node, options): NodeDisplayLayout
(Protected) Recursive helper for toVisual.
Parameters
- node: undefined | null | BinaryTreeNode<K, V>
  The current node.
- options: BinaryTreePrintOptions
  Print options.
Returns NodeDisplayLayout
Layout information for this subtree.

Remarks
Time O(N), Space O(N*H) or O(N^2)
Inherited from BST._displayAux
- Defined in data-structures/binary-tree/binary-tree.ts:2237

`Protected`_ensurePredicate

_ensurePredicate(keyNodeEntryOrPredicate): NodePredicate<BinaryTreeNode<K, V>>
(Protected) Converts a key, node, entry, or predicate into a standardized predicate function.
Parameters
- keyNodeEntryOrPredicate:
      | undefined
      | null
      | K
      | [undefined | null | K, undefined | V]
      | BinaryTreeNode<K, V>
      | NodePredicate<BinaryTreeNode<K, V>>
  The item to convert.
Returns NodePredicate<BinaryTreeNode<K, V>>
A predicate function.

Remarks
Time O(1)
Inherited from BST._ensurePredicate
- Defined in data-structures/binary-tree/binary-tree.ts:2391

`Protected`_extractKey

_extractKey(keyNodeOrEntry): undefined | null | K
(Protected) Extracts the key from a key, node, or entry.
Parameters
- keyNodeOrEntry:
      | undefined
      | null
      | K
      | [undefined | null | K, undefined | V]
      | BinaryTreeNode<K, V>
  The item.
Returns undefined | null | K
The extracted key.

Remarks
Time O(1)
Inherited from BST._extractKey
- Defined in data-structures/binary-tree/binary-tree.ts:2451

`Protected`_floorByKey

_floorByKey(key, iterationType): undefined | BSTNode<K, V>
(Protected) Binary search for floor by key with pruning optimization. Performs standard BST binary search, choosing left or right subtree based on comparator result. Finds first node where key <= target.
Parameters
- key: K
  The target key to search for.
- iterationType: IterationType
  The iteration type (RECURSIVE or ITERATIVE).
Returns undefined | BSTNode<K, V>
The first node with key <= target, or undefined if none exists.

Remarks
Time O(h) where h is tree height.
Inherited from BST._floorByKey
- Defined in data-structures/binary-tree/bst.ts:1474

`Protected`_floorByPredicate

_floorByPredicate(predicate, iterationType): undefined | BSTNode<K, V>
(Protected) In-order traversal search for floor by predicate. Falls back to linear in-order traversal when predicate-based search is required. Returns the last node that satisfies the predicate function.
Parameters
- predicate: NodePredicate<BSTNode<K, V>>
  The predicate function to test nodes.
- iterationType: IterationType
  The iteration type (RECURSIVE or ITERATIVE).
Returns undefined | BSTNode<K, V>
The last node satisfying predicate (highest key), or undefined if none found.

Remarks
Time Complexity: O(n) since it may visit every node. Space Complexity: O(h) for recursion, O(h) for iterative stack.
Inherited from BST._floorByPredicate
- Defined in data-structures/binary-tree/bst.ts:1527

`Protected`_getIterator

_getIterator(node?): IterableIterator<[K, undefined | V], any, any>
(Protected) Gets the iterator for the tree (default in-order).
Parameters
- Optionalnode: null | BinaryTreeNode<K, V> = ...
  The node to start iteration from.
Returns IterableIterator<[K, undefined | V], any, any>
An iterator for [key, value] pairs.

Remarks
Time O(N) for full iteration. O(H) to get the first element. Space O(H) for the iterative stack. O(H) for recursive stack.
Inherited from BST._getIterator
- Defined in data-structures/binary-tree/binary-tree.ts:2074

`Protected`_isPredicate

_isPredicate(p): p is NodePredicate<BinaryTreeNode<K, V>>
(Protected) Checks if an item is a predicate function.
Parameters
- p: any
  The item to check.
Returns p is NodePredicate<BinaryTreeNode<K, V>>
True if it's a function.

Remarks
Time O(1)
Inherited from BST._isPredicate
- Defined in data-structures/binary-tree/binary-tree.ts:2440

`Protected`_keyValueNodeOrEntryToNodeAndValue

_keyValueNodeOrEntryToNodeAndValue(keyNodeOrEntry, value?): [OptNode<BSTNode<K, V>>, undefined | V]
(Protected) Converts a key, node, or entry into a standardized [node, value] tuple.
Parameters
- keyNodeOrEntry:
      | undefined
      | null
      | K
      | BSTNode<K, V>
      | [undefined | null | K, undefined | V]
  The input item.
- Optionalvalue: V
  An optional value (used if input is just a key).
Returns [OptNode<BSTNode<K, V>>, undefined | V]
A tuple of [node, value].

Remarks
Time O(1)
Inherited from BST._keyValueNodeOrEntryToNodeAndValue
- Defined in data-structures/binary-tree/bst.ts:1932

`Protected`_lowerByKey

_lowerByKey(key, iterationType): undefined | BSTNode<K, V>
(Protected) Binary search for lower by key with pruning optimization. Performs standard BST binary search, choosing left or right subtree based on comparator result. Finds first node where key < target.
Parameters
- key: K
  The target key to search for.
- iterationType: IterationType
  The iteration type (RECURSIVE or ITERATIVE).
Returns undefined | BSTNode<K, V>
The first node with key < target, or undefined if none exists.

Remarks
Time O(h) where h is tree height.
Inherited from BST._lowerByKey
- Defined in data-structures/binary-tree/bst.ts:1592

`Protected`_lowerByPredicate

_lowerByPredicate(predicate, iterationType): undefined | BSTNode<K, V>
(Protected) In-order traversal search for lower by predicate. Falls back to linear in-order traversal when predicate-based search is required. Returns the node that satisfies the predicate and appears last in in-order traversal.
Parameters
- predicate: NodePredicate<BSTNode<K, V>>
  The predicate function to test nodes.
- iterationType: IterationType
  The iteration type (RECURSIVE or ITERATIVE).
Returns undefined | BSTNode<K, V>
The last node satisfying predicate (highest key < target), or undefined if none found.

Remarks
Time Complexity: O(n) since it may visit every node. Space Complexity: O(h) for recursion, O(h) for iterative stack.
Inherited from BST._lowerByPredicate
- Defined in data-structures/binary-tree/bst.ts:1645

`Protected`_replaceNode

_replaceNode(oldNode, newNode): AVLTreeNode<K, V>
(Protected) Replaces a node, ensuring height is copied.
Parameters
- oldNode: AVLTreeNode<K, V>
  The node to be replaced.
- newNode: AVLTreeNode<K, V>
  The node to insert.
Returns AVLTreeNode<K, V>
The newNode.

Remarks
Time O(1)
Overrides BST._replaceNode
- Defined in data-structures/binary-tree/avl-tree.ts:835

`Protected`_setRoot

_setRoot(v): void
(Protected) Sets the root node and clears its parent reference.
Parameters
- v: OptNode<BSTNode<K, V>>
  The node to set as root.
Returns void
Remarks
Time O(1)
Inherited from BST._setRoot
- Defined in data-structures/binary-tree/bst.ts:1947

`Protected`_setValue

_setValue(key, value): false | Map<K, undefined | V>
(Protected) Sets a value in the external store (Map mode).
Parameters
- key: undefined | null | K
  The key.
- value: undefined | V
  The value.
Returns false | Map<K, undefined | V>
True if successful.

Remarks
Time O(1) (average for Map.set).
Inherited from BST._setValue
- Defined in data-structures/binary-tree/binary-tree.ts:2472

`Protected`_snapshotOptions

_snapshotOptions<TK, TV, TR>(): BSTOptions<TK, TV, TR>
(Protected) Snapshots the current BST's configuration options.
Type Parameters
- TK = K
- TV = V
- TR = R
Returns BSTOptions<TK, TV, TR>
The options object.

Remarks
Time O(1)
Inherited from BST._snapshotOptions
- Defined in data-structures/binary-tree/bst.ts:1917

`Protected`_swapProperties

_swapProperties(srcNode, destNode): undefined | AVLTreeNode<K, V>
(Protected) Swaps properties of two nodes, including height.
Parameters
- srcNode: BSTNOptKeyOrNode<K, AVLTreeNode<K, V>>
  The source node.
- destNode: BSTNOptKeyOrNode<K, AVLTreeNode<K, V>>
  The destination node.
Returns undefined | AVLTreeNode<K, V>
The destNode (now holding srcNode's properties).

Remarks
Time O(H) (due to ensureNode), but O(1) if nodes are passed directly.
Overrides BST._swapProperties
- Defined in data-structures/binary-tree/avl-tree.ts:550

`Protected`_updateHeight

_updateHeight(node): void
(Protected) Recalculates and updates the height of a node based on its children's heights.
Parameters
- node: AVLTreeNode<K, V>
  The node to update.
Returns void
Remarks
Time O(1) (assumes children's heights are correct).
- Defined in data-structures/binary-tree/avl-tree.ts:599

[iterator]

[iterator](...args): IterableIterator<[K, undefined | V], any, any>
Default iterator yielding [key, value] entries.
Parameters
- Rest...args: any[]
Returns IterableIterator<[K, undefined | V], any, any>
Iterator of [K, V].

Remarks
Time O(n) to iterate, Space O(1)
Implementation of IBinaryTree.[iterator]
Inherited from BST.[iterator]
- Defined in data-structures/base/iterable-entry-base.ts:22

add

add(keyNodeOrEntry, value?): boolean
Adds a new node to the AVL tree and balances the tree path.
Parameters
- keyNodeOrEntry:
      | undefined
      | null
      | K
      | AVLTreeNode<K, V>
      | [undefined | null | K, undefined | V]
  The key, node, or entry to add.
- Optionalvalue: V
  The value, if providing just a key.
Returns boolean
True if the addition was successful, false otherwise.

Remarks
Time O(log N) (O(H) for BST add + O(H) for _balancePath). Space O(H) for path/recursion.
Implementation of IBinaryTree.add
Overrides BST.add
- Defined in data-structures/binary-tree/avl-tree.ts:410

addMany

addMany(keysNodesEntriesOrRaws, values?, isBalanceAdd?, iterationType?): boolean[]
Adds multiple items to the tree.
Parameters
- keysNodesEntriesOrRaws: Iterable<R | BTNRep<K, V, BSTNode<K, V>>, any, any>
  An iterable of items to add.
- Optionalvalues: Iterable<undefined | V, any, any>
  An optional parallel iterable of values.
- OptionalisBalanceAdd: boolean = true
  If true, builds a balanced tree from the items.
- OptionaliterationType: IterationType = ...
  The traversal method for balanced add (recursive or iterative).
Returns boolean[]
An array of booleans indicating the success of each individual add operation.

Remarks
If isBalanceAdd is true, sorts the input and builds a balanced tree. Time O(N log N) (due to sort and balanced add). If false, adds items one by one. Time O(N * H), which is O(N^2) worst-case. Space O(N) for sorting and recursion/iteration stack.
Implementation of IBinaryTree.addMany
Inherited from BST.addMany
- Defined in data-structures/binary-tree/bst.ts:779

bfs

bfs(): (undefined | K)[]
Returns (undefined | K)[]
Implementation of IBinaryTree.bfs
Inherited from BST.bfs
- Defined in data-structures/binary-tree/bst.ts:488
bfs<C>(callback, startNode?, iterationType?): ReturnType<C>[]
Type Parameters
- C extends NodeCallback<BSTNode<K, V>>
Parameters
- callback: C
- OptionalstartNode:
      | null
      | K
      | BSTNode<K, V>
      | [undefined | null | K, undefined | V]
- OptionaliterationType: IterationType
Returns ReturnType<C>[]
Implementation of IBinaryTree.bfs
Inherited from BST.bfs
- Defined in data-structures/binary-tree/bst.ts:489

ceiling

ceiling(keyNodeEntryOrPredicate): undefined | K
Returns the first key with a value >= target. Equivalent to Java TreeMap.ceiling. Time Complexity: O(log n) average, O(h) worst case. Space Complexity: O(h) for recursion, O(1) for iteration.
Parameters
- keyNodeEntryOrPredicate:
      | undefined
      | null
      | K
      | BSTNode<K, V>
      | [undefined | null | K, undefined | V]
      | NodePredicate<BSTNode<K, V>>
Returns undefined | K
Inherited from BST.ceiling
- Defined in data-structures/binary-tree/bst.ts:876
ceiling<C>(keyNodeEntryOrPredicate, callback, iterationType?): ReturnType<C>
Returns the first node with a key >= target and applies callback. Time Complexity: O(log n) average, O(h) worst case. Space Complexity: O(h) for recursion, O(1) for iteration.
Type Parameters
- C extends NodeCallback<BSTNode<K, V>>
Parameters
- keyNodeEntryOrPredicate:
      | undefined
      | null
      | K
      | BSTNode<K, V>
      | [undefined | null | K, undefined | V]
      | NodePredicate<BSTNode<K, V>>
- callback: C
- OptionaliterationType: IterationType
Returns ReturnType<C>
Inherited from BST.ceiling
- Defined in data-structures/binary-tree/bst.ts:891

clear

clear(): void
Clears the tree of all nodes and values.

Returns void
Remarks
Time O(N) if in Map mode (due to _store.clear()), O(1) otherwise. Space O(1)
Implementation of IBinaryTree.clear
Inherited from BST.clear
- Defined in data-structures/binary-tree/binary-tree.ts:1072

clone

clone(): this
Clones the tree.

Returns this
A new, cloned instance of the tree.

Remarks
Time O(N * M), where N is the number of nodes and M is the tree size during insertion (due to bfs + add, and add is O(M)). Space O(N) for the new tree and the BFS queue.
Implementation of IBinaryTree.clone
Inherited from BST.clone
- Defined in data-structures/binary-tree/binary-tree.ts:1837

createNode

createNode(key, value?): AVLTreeNode<K, V>
(Protected) Creates a new AVL tree node.
Parameters
- key: K
  The key for the new node.
- Optionalvalue: V
  The value for the new node.
Returns AVLTreeNode<K, V>
The newly created AVLTreeNode.

Remarks
Time O(1), Space O(1)
Implementation of IBinaryTree.createNode
Overrides BST.createNode
- Defined in data-structures/binary-tree/avl-tree.ts:385

createTree

createTree(options?): this
Creates a new, empty tree of the same type and configuration.
Parameters
- Optionaloptions: Partial<BinaryTreeOptions<K, V, R>>
  Optional overrides for the new tree's options.
Returns this
A new, empty tree instance.

Remarks
Time O(1) (excluding options cloning), Space O(1)
Implementation of IBinaryTree.createTree
Inherited from BST.createTree
- Defined in data-structures/binary-tree/binary-tree.ts:483

delete

delete(keyNodeOrEntry): BinaryTreeDeleteResult<AVLTreeNode<K, V>>[]
Deletes a node from the AVL tree and re-balances the tree.
Parameters
- keyNodeOrEntry:
      | undefined
      | null
      | K
      | AVLTreeNode<K, V>
      | [undefined | null | K, undefined | V]
  The node to delete.
Returns BinaryTreeDeleteResult<AVLTreeNode<K, V>>[]
An array containing deletion results.

Remarks
Time O(log N) (O(H) for BST delete + O(H) for _balancePath). Space O(H) for path/recursion.
Implementation of IBinaryTree.delete
Overrides BST.delete
- Defined in data-structures/binary-tree/avl-tree.ts:428

deleteWhere

deleteWhere(keyNodeEntryOrPredicate, onlyOne?, startNode?, iterationType?): BinaryTreeDeleteResult<BSTNode<K, V>>[]
Deletes nodes that match a key, node, entry, predicate, or range.
Parameters
- keyNodeEntryOrPredicate:
      | undefined
      | null
      | K
      | BSTNode<K, V>
      | [undefined | null | K, undefined | V]
      | NodePredicate<BSTNode<K, V>>
      | Range<K>
  The search criteria. Can be one of:
  - A key (type K): searches for exact key match using the comparator.
  - A BSTNode: searches for the matching node in the tree.
  - An entry tuple: searches for the key-value pair.
  - A NodePredicate function: tests each node and returns true for matches.
  - A Range object: searches for nodes whose keys fall within the specified range (inclusive/exclusive based on range settings).
  - null or undefined: treated as no match, returns empty results.
- onlyOne: boolean = false
  If true, stops the search after finding the first match and only deletes that one node. If false (default), searches for and deletes all matching nodes.
- startNode:
      | undefined
      | null
      | K
      | BSTNode<K, V>
      | [undefined | null | K, undefined | V] = ...
  The node to start the search from. Can be:
  - A key, node, or entry: the method resolves it to a node and searches from that subtree.
  - null or undefined: defaults to the root, searching the entire tree.
  - Default value: this._root (the tree's root).
- iterationType: IterationType = ...
  Controls the internal traversal implementation:
  - 'RECURSIVE': uses recursive function calls for traversal.
  - 'ITERATIVE': uses explicit stack-based iteration.
  - Default: this.iterationType (the tree's default iteration mode).
Returns BinaryTreeDeleteResult<BSTNode<K, V>>[]
A Map<K, boolean> containing the deletion results:
- Key: the matched node's key.
- Value: true if the deletion succeeded, false if it failed (e.g., key not found during deletion phase).
- If no nodes match the search criteria, the returned map is empty.
Remarks
Time Complexity: O(N) for search + O(M log N) for M deletions, where N is tree size. Space Complexity: O(M) for storing matched nodes and result map.
Inherited from BST.deleteWhere
- Defined in data-structures/binary-tree/bst.ts:1413

dfs

dfs(): (undefined | K)[]
Returns (undefined | K)[]
Implementation of IBinaryTree.dfs
Inherited from BST.dfs
- Defined in data-structures/binary-tree/bst.ts:456
dfs<C>(callback, pattern?, onlyOne?, startNode?, iterationType?): ReturnType<C>[]
Type Parameters
- C extends NodeCallback<BSTNode<K, V>>
Parameters
- callback: C
- Optionalpattern: DFSOrderPattern
- OptionalonlyOne: boolean
- OptionalstartNode:
      | null
      | K
      | BSTNode<K, V>
      | [undefined | null | K, undefined | V]
- OptionaliterationType: IterationType
Returns ReturnType<C>[]
Implementation of IBinaryTree.dfs
Inherited from BST.dfs
- Defined in data-structures/binary-tree/bst.ts:458

ensureNode

ensureNode(keyNodeOrEntry, iterationType?): OptNode<BSTNode<K, V>>
Ensures the input is a node. If it's a key or entry, it searches for the node.
Parameters
- keyNodeOrEntry:
      | undefined
      | null
      | K
      | BSTNode<K, V>
      | [undefined | null | K, undefined | V]
  The item to resolve to a node.
- OptionaliterationType: IterationType = ...
  The traversal method to use if searching.
Returns OptNode<BSTNode<K, V>>
The resolved node, or undefined if not found.

Remarks
Time O(log N) (height of the tree), O(N) worst-case.
Inherited from BST.ensureNode
- Defined in data-structures/binary-tree/bst.ts:425

entries

entries(): IterableIterator<[K, undefined | V], any, any>
Iterate over [key, value] pairs (may yield undefined values).

Returns IterableIterator<[K, undefined | V], any, any>
Iterator of [K, V | undefined].

Remarks
Time O(n), Space O(1)
Implementation of IBinaryTree.entries
Inherited from BST.entries
- Defined in data-structures/base/iterable-entry-base.ts:31

every

every(predicate, thisArg?): boolean
Test whether all entries satisfy the predicate.
Parameters
- predicate: EntryCallback<K, undefined | V, boolean>
  (key, value, index, self) => boolean.
- OptionalthisArg: any
  Optional this for callback.
Returns boolean
true if all pass; otherwise false.

Remarks
Time O(n), Space O(1)
Implementation of IBinaryTree.every
Inherited from BST.every
- Defined in data-structures/base/iterable-entry-base.ts:66

filter

filter(predicate, thisArg?): this
Creates a new tree containing only the entries that satisfy the predicate.
Parameters
- predicate: EntryCallback<K, undefined | V, boolean>
  A function to test each [key, value] pair.
- OptionalthisArg: unknown
  this context for the predicate.
Returns this
A new, filtered tree.

Remarks
Time O(N * M), where N is nodes in this tree, and M is size of the new tree during insertion (O(N) iteration + O(M) add for each item). Space O(N) for the new tree.
Implementation of IBinaryTree.filter
Inherited from BST.filter
- Defined in data-structures/binary-tree/binary-tree.ts:1851

find

find(callbackfn, thisArg?): undefined | [K, undefined | V]
Find the first entry that matches a predicate.
Parameters
- callbackfn: EntryCallback<K, undefined | V, boolean>
  (key, value, index, self) => boolean.
- OptionalthisArg: any
  Optional this for callback.
Returns undefined | [K, undefined | V]
Matching [key, value] or undefined.

Remarks
Time O(n), Space O(1)
Implementation of IBinaryTree.find
Inherited from BST.find
- Defined in data-structures/base/iterable-entry-base.ts:114

floor

floor(keyNodeEntryOrPredicate): undefined | K
Returns the first key with a value <= target. Equivalent to Java TreeMap.floor. Time Complexity: O(log n) average, O(h) worst case. Space Complexity: O(h) for recursion, O(1) for iteration.
Parameters
- keyNodeEntryOrPredicate:
      | undefined
      | null
      | K
      | BSTNode<K, V>
      | [undefined | null | K, undefined | V]
      | NodePredicate<BSTNode<K, V>>
Returns undefined | K
Inherited from BST.floor
- Defined in data-structures/binary-tree/bst.ts:1006
floor<C>(keyNodeEntryOrPredicate, callback, iterationType?): ReturnType<C>
Returns the first node with a key <= target and applies callback. Time Complexity: O(log n) average, O(h) worst case. Space Complexity: O(h) for recursion, O(1) for iteration.
Type Parameters
- C extends NodeCallback<BSTNode<K, V>>
Parameters
- keyNodeEntryOrPredicate:
      | undefined
      | null
      | K
      | BSTNode<K, V>
      | [undefined | null | K, undefined | V]
      | NodePredicate<BSTNode<K, V>>
- callback: C
- OptionaliterationType: IterationType
Returns ReturnType<C>
Inherited from BST.floor
- Defined in data-structures/binary-tree/bst.ts:1021

forEach

forEach(callbackfn, thisArg?): void
Visit each entry, left-to-right.
Parameters
- callbackfn: EntryCallback<K, undefined | V, void>
  (key, value, index, self) => void.
- OptionalthisArg: any
  Optional this for callback.
Returns void
Remarks
Time O(n), Space O(1)
Implementation of IBinaryTree.forEach
Inherited from BST.forEach
- Defined in data-structures/base/iterable-entry-base.ts:99

get

get(keyNodeEntryOrPredicate, startNode?, iterationType?): undefined | V
Gets the value associated with a key.
Parameters
- keyNodeEntryOrPredicate:
      | undefined
      | null
      | K
      | [undefined | null | K, undefined | V]
      | BinaryTreeNode<K, V>
  The key, node, or entry to get the value for.
- OptionalstartNode:
      | null
      | K
      | [undefined | null | K, undefined | V]
      | BinaryTreeNode<K, V> = ...
  The node to start searching from (if not in Map mode).
- OptionaliterationType: IterationType = ...
  The traversal method (if not in Map mode).
Returns undefined | V
The associated value, or undefined.

Remarks
Time O(log N), For BST, Red-Black Tree, and AVL Tree subclasses, the worst-case time is O(log N). Time O(1) if in Map mode. O(N) if not in Map mode (uses getNode). Space O(1) if in Map mode. O(H) or O(N) otherwise.
Implementation of IBinaryTree.get
Inherited from BST.get
- Defined in data-structures/binary-tree/binary-tree.ts:1020

getDepth

getDepth(dist, startNode?): number
Gets the depth of a node (distance from startNode).
Parameters
- dist:
      | undefined
      | null
      | K
      | [undefined | null | K, undefined | V]
      | BinaryTreeNode<K, V>
  The node to find the depth of.
- OptionalstartNode:
      | null
      | K
      | [undefined | null | K, undefined | V]
      | BinaryTreeNode<K, V> = ...
  The node to measure depth from (defaults to root).
Returns number
The depth (0 if dist is startNode).

Remarks
Time O(H), where H is the depth of the dist node relative to startNode. O(N) worst-case. Space O(1).
Implementation of IBinaryTree.getDepth
Inherited from BST.getDepth
- Defined in data-structures/binary-tree/binary-tree.ts:1159

getHeight

getHeight(startNode?, iterationType?): number
Gets the maximum height of the tree (longest path from startNode to a leaf).
Parameters
- OptionalstartNode:
      | null
      | K
      | [undefined | null | K, undefined | V]
      | BinaryTreeNode<K, V> = ...
  The node to start measuring from.
- OptionaliterationType: IterationType = ...
  The traversal method.
Returns number
The height ( -1 for an empty tree, 0 for a single-node tree).

Remarks
Time O(N), as it must visit every node. Space O(H) for recursive stack (O(N) worst-case) or O(N) for iterative stack (storing node + depth).
Implementation of IBinaryTree.getHeight
Inherited from BST.getHeight
- Defined in data-structures/binary-tree/binary-tree.ts:1184

getLeftMost

getLeftMost(): undefined | K
Returns undefined | K
Implementation of IBinaryTree.getLeftMost
Inherited from BST.getLeftMost
- Defined in data-structures/binary-tree/binary-tree.ts:1311
getLeftMost<C>(callback, startNode?, iterationType?): ReturnType<C>
Type Parameters
- C extends NodeCallback<undefined | BinaryTreeNode<K, V>>
Parameters
- callback: C
- OptionalstartNode:
      | null
      | K
      | [undefined | null | K, undefined | V]
      | BinaryTreeNode<K, V>
- OptionaliterationType: IterationType
Returns ReturnType<C>
Implementation of IBinaryTree.getLeftMost
Inherited from BST.getLeftMost
- Defined in data-structures/binary-tree/binary-tree.ts:1313

getMinHeight

getMinHeight(startNode?, iterationType?): number
Gets the minimum height of the tree (shortest path from startNode to a leaf).
Parameters
- OptionalstartNode:
      | null
      | K
      | [undefined | null | K, undefined | V]
      | BinaryTreeNode<K, V> = ...
  The node to start measuring from.
- OptionaliterationType: IterationType = ...
  The traversal method.
Returns number
The minimum height (-1 for empty, 0 for single node).

Remarks
Time O(N), as it must visit every node. Space O(H) for recursive stack (O(N) worst-case) or O(N) for iterative (due to depths Map).
Implementation of IBinaryTree.getMinHeight
Inherited from BST.getMinHeight
- Defined in data-structures/binary-tree/binary-tree.ts:1226

getNode

getNode(keyNodeEntryOrPredicate, startNode?, iterationType?): OptNode<BSTNode<K, V>>
Gets the first node matching a predicate.
Parameters
- keyNodeEntryOrPredicate:
      | undefined
      | null
      | K
      | BSTNode<K, V>
      | [undefined | null | K, undefined | V]
      | NodePredicate<BSTNode<K, V>>
  The key, node, entry, or predicate function to search for.
- OptionalstartNode: BSTNOptKeyOrNode<K, BSTNode<K, V>> = ...
  The node to start the search from.
- OptionaliterationType: IterationType = ...
  The traversal method.
Returns OptNode<BSTNode<K, V>>
The first matching node, or undefined if not found.

Remarks
Time O(log N) if searching by key, O(N) if searching by predicate. Space O(log N) or O(N).
Implementation of IBinaryTree.getNode
Inherited from BST.getNode
- Defined in data-structures/binary-tree/bst.ts:548

getNodes

getNodes(keyNodeEntryOrPredicate, onlyOne?, startNode?, iterationType?): BinaryTreeNode<K, V>[]
Gets all nodes matching a predicate.
Parameters
- keyNodeEntryOrPredicate:
      | undefined
      | null
      | K
      | [undefined | null | K, undefined | V]
      | BinaryTreeNode<K, V>
      | NodePredicate<BinaryTreeNode<K, V>>
  The key, node, entry, or predicate function to search for.
- OptionalonlyOne: boolean
  If true, stops after finding the first match.
- OptionalstartNode:
      | null
      | K
      | [undefined | null | K, undefined | V]
      | BinaryTreeNode<K, V>
  The node to start the search from.
- OptionaliterationType: IterationType
  The traversal method.
Returns BinaryTreeNode<K, V>[]
An array of matching nodes.

Remarks
Time O(N) (via search). Space O(H) or O(N) (via search).
Inherited from BST.getNodes
- Defined in data-structures/binary-tree/binary-tree.ts:960

getPathToRoot

getPathToRoot(beginNode): (undefined | K)[]
Parameters
- beginNode:
      | undefined
      | null
      | K
      | [undefined | null | K, undefined | V]
      | BinaryTreeNode<K, V>
Returns (undefined | K)[]
Implementation of IBinaryTree.getPathToRoot
Inherited from BST.getPathToRoot
- Defined in data-structures/binary-tree/binary-tree.ts:1273
getPathToRoot<C>(beginNode, callback, isReverse?): ReturnType<C>[]
Type Parameters
- C extends NodeCallback<undefined | BinaryTreeNode<K, V>>
Parameters
- beginNode:
      | undefined
      | null
      | K
      | [undefined | null | K, undefined | V]
      | BinaryTreeNode<K, V>
- callback: C
- OptionalisReverse: boolean
Returns ReturnType<C>[]
Implementation of IBinaryTree.getPathToRoot
Inherited from BST.getPathToRoot
- Defined in data-structures/binary-tree/binary-tree.ts:1277

getPredecessor

getPredecessor(node): BinaryTreeNode<K, V>
Gets the Morris traversal predecessor (rightmost node in the left subtree, or node itself).
Parameters
- node: BinaryTreeNode<K, V>
  The node to find the predecessor for.
Returns BinaryTreeNode<K, V>
The Morris predecessor.

Remarks
This is primarily a helper for Morris traversal. Time O(H), where H is the height of the left subtree. O(N) worst-case. Space O(1).
Inherited from BST.getPredecessor
- Defined in data-structures/binary-tree/binary-tree.ts:1411

getRightMost

getRightMost(): undefined | K
Returns undefined | K
Implementation of IBinaryTree.getRightMost
Inherited from BST.getRightMost
- Defined in data-structures/binary-tree/binary-tree.ts:1358
getRightMost<C>(callback, startNode?, iterationType?): ReturnType<C>
Type Parameters
- C extends NodeCallback<undefined | BinaryTreeNode<K, V>>
Parameters
- callback: C
- OptionalstartNode:
      | null
      | K
      | [undefined | null | K, undefined | V]
      | BinaryTreeNode<K, V>
- OptionaliterationType: IterationType
Returns ReturnType<C>
Implementation of IBinaryTree.getRightMost
Inherited from BST.getRightMost
- Defined in data-structures/binary-tree/binary-tree.ts:1360

getSuccessor

getSuccessor(x?): undefined | null | BinaryTreeNode<K, V>
Gets the in-order successor of a node in a BST.
Parameters
- Optionalx: null | K | BinaryTreeNode<K, V>
  The node to find the successor of.
Returns undefined | null | BinaryTreeNode<K, V>
The successor node, or null/undefined if none exists.

Remarks
Time O(H), where H is the tree height. O(N) worst-case. Space O(H) (due to getLeftMost stack).
Inherited from BST.getSuccessor
- Defined in data-structures/binary-tree/binary-tree.ts:1432

has

has(keyNodeEntryOrPredicate?, startNode?, iterationType?): boolean
Checks if a node matching the predicate exists in the tree.
Parameters
- OptionalkeyNodeEntryOrPredicate:
      | null
      | K
      | [undefined | null | K, undefined | V]
      | BinaryTreeNode<K, V>
      | NodePredicate<BinaryTreeNode<K, V>>
  The key, node, entry, or predicate to check for.
- OptionalstartNode:
      | null
      | K
      | [undefined | null | K, undefined | V]
      | BinaryTreeNode<K, V>
  The node to start the search from.
- OptionaliterationType: IterationType
  The traversal method.
Returns boolean
True if a matching node exists, false otherwise.

Remarks
Time O(log N), For BST, Red-Black Tree, and AVL Tree subclasses, the worst-case time is O(log N). Time O(N) in the worst case (via search). Space O(H) or O(N) (via search).
Implementation of IBinaryTree.has
Inherited from BST.has
- Defined in data-structures/binary-tree/binary-tree.ts:1042

hasValue

hasValue(value): boolean
Whether there exists an entry with the given value.
Parameters
- value: undefined | V
  Value to test.
Returns boolean
true if found; otherwise false.

Remarks
Time O(n), Space O(1)
Implementation of IBinaryTree.hasValue
Inherited from BST.hasValue
- Defined in data-structures/base/iterable-entry-base.ts:143

higher

higher(keyNodeEntryOrPredicate): undefined | K
Returns the first key with a value > target. Equivalent to Java TreeMap.higher. Time Complexity: O(log n) average, O(h) worst case. Space Complexity: O(h) for recursion, O(1) for iteration.
Parameters
- keyNodeEntryOrPredicate:
      | undefined
      | null
      | K
      | BSTNode<K, V>
      | [undefined | null | K, undefined | V]
      | NodePredicate<BSTNode<K, V>>
Returns undefined | K
Inherited from BST.higher
- Defined in data-structures/binary-tree/bst.ts:941
higher<C>(keyNodeEntryOrPredicate, callback, iterationType?): ReturnType<C>
Returns the first node with a key > target and applies callback. Time Complexity: O(log n) average, O(h) worst case. Space Complexity: O(h) for recursion, O(1) for iteration.
Type Parameters
- C extends NodeCallback<BSTNode<K, V>>
Parameters
- keyNodeEntryOrPredicate:
      | undefined
      | null
      | K
      | BSTNode<K, V>
      | [undefined | null | K, undefined | V]
      | NodePredicate<BSTNode<K, V>>
- callback: C
- OptionaliterationType: IterationType
Returns ReturnType<C>
Inherited from BST.higher
- Defined in data-structures/binary-tree/bst.ts:956

isAVLBalanced

isAVLBalanced(iterationType?): boolean
Checks if the tree meets the AVL balance condition (height difference <= 1).
Parameters
- OptionaliterationType: IterationType = ...
  The traversal method.
Returns boolean
True if the tree is AVL balanced, false otherwise.

Remarks
Time O(N), as it must visit every node to compute height. Space O(log N) for recursion or O(N) for iterative map.
Inherited from BST.isAVLBalanced
- Defined in data-structures/binary-tree/bst.ts:1306

isBST

isBST(startNode?, iterationType?): boolean
Checks if the tree is a valid Binary Search Tree (BST).
Parameters
- OptionalstartNode:
      | null
      | K
      | [undefined | null | K, undefined | V]
      | BinaryTreeNode<K, V> = ...
  The node to start checking from.
- OptionaliterationType: IterationType = ...
  The traversal method.
Returns boolean
True if it's a valid BST, false otherwise.

Remarks
Time O(N), as it must visit every node. Space O(H) for the call stack (recursive) or explicit stack (iterative), where H is the tree height (O(N) worst-case).
Implementation of IBinaryTree.isBST
Inherited from BST.isBST
- Defined in data-structures/binary-tree/binary-tree.ts:1108

isEmpty

isEmpty(): boolean
Checks if the tree is empty.

Returns boolean
True if the tree has no nodes, false otherwise.

Remarks
Time O(1), Space O(1)
Implementation of IBinaryTree.isEmpty
Inherited from BST.isEmpty
- Defined in data-structures/binary-tree/binary-tree.ts:1083

isEntry

isEntry(keyNodeOrEntry): keyNodeOrEntry is BTNEntry<K, V>
Checks if the given item is a [key, value] entry pair.
Parameters
- keyNodeOrEntry:
      | undefined
      | null
      | K
      | [undefined | null | K, undefined | V]
      | BinaryTreeNode<K, V>
  The item to check.
Returns keyNodeOrEntry is BTNEntry<K, V>
True if it's an entry, false otherwise.

Remarks
Time O(1), Space O(1)
Inherited from BST.isEntry
- Defined in data-structures/binary-tree/binary-tree.ts:620

isLeaf

isLeaf(keyNodeOrEntry): boolean
Checks if a node is a leaf (has no real children).
Parameters
- keyNodeOrEntry:
      | undefined
      | null
      | K
      | [undefined | null | K, undefined | V]
      | BinaryTreeNode<K, V>
  The node to check.
Returns boolean
True if the node is a leaf, false otherwise.

Remarks
Time O(N) if a key/entry is passed (due to ensureNode). O(1) if a node is passed. Space O(1) or O(H) (from ensureNode).
Inherited from BST.isLeaf
- Defined in data-structures/binary-tree/binary-tree.ts:606

isNIL

isNIL(keyNodeOrEntry): boolean
Checks if the given item is the sentinel NIL node.
Parameters
- keyNodeOrEntry:
      | undefined
      | null
      | K
      | [undefined | null | K, undefined | V]
      | BinaryTreeNode<K, V>
  The item to check.
Returns boolean
True if it's the NIL node, false otherwise.

Remarks
Time O(1), Space O(1)
Inherited from BST.isNIL
- Defined in data-structures/binary-tree/binary-tree.ts:575

isNode

isNode(keyNodeOrEntry): keyNodeOrEntry is AVLTreeNode<K, V>
Checks if the given item is an AVLTreeNode instance.
Parameters
- keyNodeOrEntry:
      | undefined
      | null
      | K
      | AVLTreeNode<K, V>
      | [undefined | null | K, undefined | V]
  The item to check.
Returns keyNodeOrEntry is AVLTreeNode<K, V>
True if it's an AVLTreeNode, false otherwise.

Remarks
Time O(1), Space O(1)
Overrides BST.isNode
- Defined in data-structures/binary-tree/avl-tree.ts:396

isPerfectlyBalanced

isPerfectlyBalanced(startNode?): boolean
Checks if the tree is perfectly balanced.
Parameters
- OptionalstartNode:
      | null
      | K
      | [undefined | null | K, undefined | V]
      | BinaryTreeNode<K, V> = ...
  The node to start checking from.
Returns boolean
True if perfectly balanced, false otherwise.

Remarks
A tree is perfectly balanced if the difference between min and max height is at most 1. Time O(N), as it requires two full traversals (getMinHeight and getHeight). Space O(H) or O(N) (from height calculation).
Implementation of IBinaryTree.isPerfectlyBalanced
Inherited from BST.isPerfectlyBalanced
- Defined in data-structures/binary-tree/binary-tree.ts:1094

isRange

isRange(keyNodeEntryOrPredicate): keyNodeEntryOrPredicate is Range<K>
Checks if the given item is a Range object.
Parameters
- keyNodeEntryOrPredicate:
      | undefined
      | null
      | K
      | [undefined | null | K, undefined | V]
      | BinaryTreeNode<K, V>
      | NodePredicate<BinaryTreeNode<K, V>>
      | Range<K>
  The item to check.
Returns keyNodeEntryOrPredicate is Range<K>
True if it's a Range, false otherwise.

Remarks
Time O(1), Space O(1)
Inherited from BST.isRange
- Defined in data-structures/binary-tree/binary-tree.ts:586

isRaw

isRaw(keyNodeEntryOrRaw): keyNodeEntryOrRaw is R
Checks if the given item is a raw data object (R) that needs conversion via toEntryFn.
Parameters
- keyNodeEntryOrRaw:
      | undefined
      | null
      | K
      | R
      | [undefined | null | K, undefined | V]
      | BinaryTreeNode<K, V>
  The item to check.
Returns keyNodeEntryOrRaw is R
True if it's a raw object, false otherwise.

Remarks
Time O(1), Space O(1)
Inherited from BST.isRaw
- Defined in data-structures/binary-tree/binary-tree.ts:535

isRealNode

isRealNode(keyNodeOrEntry): keyNodeOrEntry is BinaryTreeNode<K, V>
Checks if the given item is a "real" node (i.e., not null, undefined, or NIL).
Parameters
- keyNodeOrEntry:
      | undefined
      | null
      | K
      | [undefined | null | K, undefined | V]
      | BinaryTreeNode<K, V>
  The item to check.
Returns keyNodeOrEntry is BinaryTreeNode<K, V>
True if it's a real node, false otherwise.

Remarks
Time O(1), Space O(1)
Inherited from BST.isRealNode
- Defined in data-structures/binary-tree/binary-tree.ts:548

isRealNodeOrNull

isRealNodeOrNull(keyNodeOrEntry): keyNodeOrEntry is null | BinaryTreeNode<K, V>
Checks if the given item is either a "real" node or null.
Parameters
- keyNodeOrEntry:
      | undefined
      | null
      | K
      | [undefined | null | K, undefined | V]
      | BinaryTreeNode<K, V>
  The item to check.
Returns keyNodeOrEntry is null | BinaryTreeNode<K, V>
True if it's a real node or null, false otherwise.

Remarks
Time O(1), Space O(1)
Inherited from BST.isRealNodeOrNull
- Defined in data-structures/binary-tree/binary-tree.ts:562

isValidKey

isValidKey(key): key is K
Checks if the given key is valid (comparable).
Parameters
- key: any
  The key to validate.
Returns key is K
True if the key is valid, false otherwise.

Remarks
Time O(1)
Inherited from BST.isValidKey
- Defined in data-structures/binary-tree/bst.ts:452

keys

keys(): IterableIterator<K, any, any>
Iterate over keys only.

Returns IterableIterator<K, any, any>
Iterator of keys.

Remarks
Time O(n), Space O(1)
Implementation of IBinaryTree.keys
Inherited from BST.keys
- Defined in data-structures/base/iterable-entry-base.ts:42

leaves

leaves(): (undefined | K)[]
Returns (undefined | K)[]
Implementation of IBinaryTree.leaves
Inherited from BST.leaves
- Defined in data-structures/binary-tree/binary-tree.ts:1577
leaves<C>(callback, startNode?, iterationType?): ReturnType<C>[]
Type Parameters
- C extends NodeCallback<BinaryTreeNode<K, V>>
Parameters
- callback: C
- OptionalstartNode:
      | null
      | K
      | [undefined | null | K, undefined | V]
      | BinaryTreeNode<K, V>
- OptionaliterationType: IterationType
Returns ReturnType<C>[]
Implementation of IBinaryTree.leaves
Inherited from BST.leaves
- Defined in data-structures/binary-tree/binary-tree.ts:1579

lesserOrGreaterTraverse

lesserOrGreaterTraverse(): (undefined | K)[]
Returns (undefined | K)[]
Inherited from BST.lesserOrGreaterTraverse
- Defined in data-structures/binary-tree/bst.ts:1210
lesserOrGreaterTraverse<C>(callback, lesserOrGreater?, targetNode?, iterationType?): ReturnType<C>[]
Type Parameters
- C extends NodeCallback<BSTNode<K, V>>
Parameters
- callback: C
- OptionallesserOrGreater: number
- OptionaltargetNode:
      | null
      | K
      | BSTNode<K, V>
      | [undefined | null | K, undefined | V]
- OptionaliterationType: IterationType
Returns ReturnType<C>[]
Inherited from BST.lesserOrGreaterTraverse
- Defined in data-structures/binary-tree/bst.ts:1212

listLevels

listLevels(): (undefined | K)[][]
Returns (undefined | K)[][]
Implementation of IBinaryTree.listLevels
Inherited from BST.listLevels
- Defined in data-structures/binary-tree/bst.ts:513
listLevels<C>(callback, startNode?, iterationType?): ReturnType<C>[][]
Type Parameters
- C extends NodeCallback<BSTNode<K, V>>
Parameters
- callback: C
- OptionalstartNode:
      | null
      | K
      | BSTNode<K, V>
      | [undefined | null | K, undefined | V]
- OptionaliterationType: IterationType
Returns ReturnType<C>[][]
Implementation of IBinaryTree.listLevels
Inherited from BST.listLevels
- Defined in data-structures/binary-tree/bst.ts:515

lower

lower(keyNodeEntryOrPredicate): undefined | K
Returns the first key with a value < target. Equivalent to Java TreeMap.lower. Time Complexity: O(log n) average, O(h) worst case. Space Complexity: O(h) for recursion, O(1) for iteration.
Parameters
- keyNodeEntryOrPredicate:
      | undefined
      | null
      | K
      | BSTNode<K, V>
      | [undefined | null | K, undefined | V]
      | NodePredicate<BSTNode<K, V>>
Returns undefined | K
Inherited from BST.lower
- Defined in data-structures/binary-tree/bst.ts:1111
lower<C>(keyNodeEntryOrPredicate, callback, iterationType?): ReturnType<C>
Returns the first node with a key < target and applies callback. Time Complexity: O(log n) average, O(h) worst case. Space Complexity: O(h) for recursion, O(1) for iteration.
Type Parameters
- C extends NodeCallback<BSTNode<K, V>>
Parameters
- keyNodeEntryOrPredicate:
      | undefined
      | null
      | K
      | BSTNode<K, V>
      | [undefined | null | K, undefined | V]
      | NodePredicate<BSTNode<K, V>>
- callback: C
- OptionaliterationType: IterationType
Returns ReturnType<C>
Inherited from BST.lower
- Defined in data-structures/binary-tree/bst.ts:1126

map

map<MK, MV, MR>(callback, options?, thisArg?): AVLTree<MK, MV, MR>
Creates a new AVLTree by mapping each [key, value] pair.
Type Parameters
- MK = K
  New key type.
- MV = V
  New value type.
- MR = any
  New raw type.
Parameters
- callback: EntryCallback<K, undefined | V, [MK, MV]>
  A function to map each [key, value] pair.
- Optionaloptions: Partial<BinaryTreeOptions<MK, MV, MR>>
  Options for the new AVLTree.
- OptionalthisArg: unknown
  this context for the callback.
Returns AVLTree<MK, MV, MR>
A new, mapped AVLTree.

Remarks
Time O(N log N) (O(N) iteration + O(log M) add for each item into the new tree). Space O(N) for the new tree.
Implementation of IBinaryTree.map
Overrides BST.map
- Defined in data-structures/binary-tree/avl-tree.ts:490

merge

merge(anotherTree): void
Merges another tree into this one by adding all its nodes.
Parameters
- anotherTree: BinaryTree<K, V, R>
  The tree to merge.
Returns void
Remarks
Time O(N * M), same as addMany, where N is the size of anotherTree and M is the size of this tree. Space O(M) (from add).
Implementation of IBinaryTree.merge
Inherited from BST.merge
- Defined in data-structures/binary-tree/binary-tree.ts:776

morris

morris(): (undefined | K)[]
Returns (undefined | K)[]
Implementation of IBinaryTree.morris
Inherited from BST.morris
- Defined in data-structures/binary-tree/binary-tree.ts:1713
morris<C>(callback?, pattern?, startNode?): ReturnType<C>[]
Type Parameters
- C extends NodeCallback<BinaryTreeNode<K, V>>
Parameters
- Optionalcallback: C
- Optionalpattern: DFSOrderPattern
- OptionalstartNode:
      | null
      | K
      | [undefined | null | K, undefined | V]
      | BinaryTreeNode<K, V>
Returns ReturnType<C>[]
Implementation of IBinaryTree.morris
Inherited from BST.morris
- Defined in data-structures/binary-tree/binary-tree.ts:1715

perfectlyBalance

perfectlyBalance(iterationType?): boolean
Rebuilds the tree to be perfectly balanced.
Parameters
- OptionaliterationType: IterationType = ...
  The traversal method for the initial node export.
Returns boolean
True if successful, false if the tree was empty.

Remarks
AVL trees are already height-balanced, but this makes them perfectly balanced (minimal height and all leaves at N or N-1). Time O(N) (O(N) for DFS, O(N) for sorted build). Space O(N) for node array and recursion stack.
Overrides BST.perfectlyBalance
- Defined in data-structures/binary-tree/avl-tree.ts:449

print

print(options?, startNode?): void
Prints a visual representation of the tree to the console.
Parameters
- Optionaloptions: BinaryTreePrintOptions
  Options to control the output.
- OptionalstartNode:
      | null
      | K
      | [undefined | null | K, undefined | V]
      | BinaryTreeNode<K, V> = ...
  The node to start printing from.
Returns void
Remarks
Time O(N) (via toVisual). Space O(N*H) or O(N^2) (via toVisual).
Inherited from BST.print
- Defined in data-structures/binary-tree/binary-tree.ts:1922

rangeSearch

rangeSearch(range): (undefined | K)[]
Parameters
- range: Range<K> | [K, K]
Returns (undefined | K)[]
Inherited from BST.rangeSearch
- Defined in data-structures/binary-tree/bst.ts:685
rangeSearch<C>(range, callback, startNode?, iterationType?): ReturnType<C>[]
Type Parameters
- C extends NodeCallback<BSTNode<K, V>>
Parameters
- range: Range<K> | [K, K]
- callback: C
- OptionalstartNode:
      | null
      | K
      | BSTNode<K, V>
      | [undefined | null | K, undefined | V]
- OptionaliterationType: IterationType
Returns ReturnType<C>[]
Inherited from BST.rangeSearch
- Defined in data-structures/binary-tree/bst.ts:687

reduce

reduce<U>(callbackfn, initialValue): U
Reduce entries into a single accumulator.
Type Parameters
- U
Parameters
- callbackfn: ReduceEntryCallback<K, undefined | V, U>
  (acc, value, key, index, self) => acc.
- initialValue: U
  Initial accumulator.
Returns U
Final accumulator.

Remarks
Time O(n), Space O(1)
Implementation of IBinaryTree.reduce
Inherited from BST.reduce
- Defined in data-structures/base/iterable-entry-base.ts:171

refill

refill(keysNodesEntriesOrRaws, values?): void
Clears the tree and refills it with new items.
Parameters
- keysNodesEntriesOrRaws: Iterable<
      | undefined
      | null
      | K
      | R
      | [undefined | null | K, undefined | V]
      | BinaryTreeNode<K, V>, any, any>
  An iterable of items to add.
- Optionalvalues: Iterable<undefined | V, any, any>
  An optional parallel iterable of values.
Returns void
Remarks
Time O(N) (for clear) + O(N * M) (for addMany) = O(N * M). Space O(M) (from addMany).
Implementation of IBinaryTree.refill
Inherited from BST.refill
- Defined in data-structures/binary-tree/binary-tree.ts:787

search

search(keyNodeEntryOrPredicate, onlyOne?): (undefined | K)[]
Parameters
- keyNodeEntryOrPredicate:
      | undefined
      | null
      | K
      | BSTNode<K, V>
      | [undefined | null | K, undefined | V]
      | NodePredicate<BSTNode<K, V>>
      | Range<K>
- OptionalonlyOne: boolean
Returns (undefined | K)[]
Implementation of IBinaryTree.search
Inherited from BST.search
- Defined in data-structures/binary-tree/bst.ts:562
search<C>(keyNodeEntryOrPredicate, onlyOne, callback, startNode?, iterationType?): ReturnType<C>[]
Type Parameters
- C extends NodeCallback<BSTNode<K, V>>
Parameters
- keyNodeEntryOrPredicate:
      | undefined
      | null
      | K
      | BSTNode<K, V>
      | [undefined | null | K, undefined | V]
      | NodePredicate<BSTNode<K, V>>
      | Range<K>
- onlyOne: boolean
- callback: C
- OptionalstartNode:
      | null
      | K
      | BSTNode<K, V>
      | [undefined | null | K, undefined | V]
- OptionaliterationType: IterationType
Returns ReturnType<C>[]
Implementation of IBinaryTree.search
Inherited from BST.search
- Defined in data-structures/binary-tree/bst.ts:574

set

set(keyNodeOrEntry, value?): boolean
Adds or updates a new node to the tree.
Parameters
- keyNodeOrEntry:
      | undefined
      | null
      | K
      | [undefined | null | K, undefined | V]
      | BinaryTreeNode<K, V>
  The key, node, or entry to add or update.
- Optionalvalue: V
  The value, if providing just a key.
Returns boolean
True if the addition was successful, false otherwise.

Remarks
Time O(log N), For BST, Red-Black Tree, and AVL Tree subclasses, the worst-case time is O(log N). This implementation adds the node at the first available position in a level-order (BFS) traversal. This is NOT a Binary Search Tree insertion. Time O(N), where N is the number of nodes. It must traverse level-by-level to find an empty slot. Space O(N) in the worst case for the BFS queue (e.g., a full last level).
Implementation of IBinaryTree.set
Inherited from BST.set
- Defined in data-structures/binary-tree/binary-tree.ts:709

setMany

setMany(keysNodesEntriesOrRaws, values?): boolean[]
Adds or updates multiple items to the tree.
Parameters
- keysNodesEntriesOrRaws: Iterable<
      | undefined
      | null
      | K
      | R
      | [undefined | null | K, undefined | V]
      | BinaryTreeNode<K, V>, any, any>
  An iterable of items to add or update.
- Optionalvalues: Iterable<undefined | V, any, any>
  An optional parallel iterable of values.
Returns boolean[]
An array of booleans indicating the success of each individual add operation.

Remarks
Time O(N * M), where N is the number of items to add and M is the size of the tree at insertion (due to O(M) add operation). Space O(M) (from add) + O(N) (for the inserted array).
Inherited from BST.setMany
- Defined in data-structures/binary-tree/binary-tree.ts:761

some

some(predicate, thisArg?): boolean
Test whether any entry satisfies the predicate.
Parameters
- predicate: EntryCallback<K, undefined | V, boolean>
  (key, value, index, self) => boolean.
- OptionalthisArg: any
  Optional this for callback.
Returns boolean
true if any passes; otherwise false.

Remarks
Time O(n), Space O(1)
Implementation of IBinaryTree.some
Inherited from BST.some
- Defined in data-structures/base/iterable-entry-base.ts:83

toArray

toArray(): [K, undefined | V][]
Converts data structure to [key, value] pairs.

Returns [K, undefined | V][]
Array of entries.

Remarks
Time O(n), Space O(n)
Inherited from BST.toArray
- Defined in data-structures/base/iterable-entry-base.ts:186

toVisual

toVisual(startNode?, options?): string
Generates a string representation of the tree for visualization.
Parameters
- OptionalstartNode:
      | null
      | K
      | [undefined | null | K, undefined | V]
      | BinaryTreeNode<K, V> = ...
  The node to start printing from.
- Optionaloptions: BinaryTreePrintOptions
  Options to control the output (e.g., show nulls).
Returns string
The string representation of the tree.

Remarks
Time O(N), visits every node. Space O(N*H) or O(N^2) in the worst case, as the string width can grow significantly.
Inherited from BST.toVisual
- Defined in data-structures/binary-tree/binary-tree.ts:1889

values

values(): IterableIterator<undefined | V, any, any>
Iterate over values only.

Returns IterableIterator<undefined | V, any, any>
Iterator of values.

Remarks
Time O(n), Space O(1)
Implementation of IBinaryTree.values
Inherited from BST.values
- Defined in data-structures/base/iterable-entry-base.ts:53

Class AVLTree<K, V, R>

Example

Example

Example

Example

Example

Type Parameters

Hierarchy (view full)

Implements

Index

Constructors

Properties

Accessors

Methods

Constructors

constructor

Type Parameters

Parameters

Returns AVLTree<K, V, R>

Remarks

Properties

Protected_comparator

Remarks

Accessors

comparator

Returns Comparator<K>

Remarks

isDuplicate

Returns boolean

Remarks

isMapMode

Returns boolean

Remarks

NIL

Returns BinaryTreeNode<K, V>

Remarks

root

Returns OptNode<BSTNode<K, V>>

Remarks

size

Returns number

Remarks

store

Returns Map<K, undefined | V>

Remarks

toEntryFn

Returns undefined | ToEntryFn<K, V, R>

Remarks

Methods

Protected_balanceFactor

Parameters

Returns number

Remarks

Protected_balanceLL

Parameters

Returns void

Remarks

Protected_balanceLR

Parameters

Returns void

Remarks

Protected_balancePath

Parameters

Returns void

Remarks

Protected_balanceRL

Parameters

Returns void

Remarks

Protected_balanceRR

Parameters

Returns void

Remarks

Protected_bound

Parameters

Returns undefined | BSTNode<K, V>

Protected_boundByKey

Parameters

Returns undefined | BSTNode<K, V>

Protected_boundByPredicate

`Protected`_comparator

`Protected`_balanceFactor

`Protected`_balanceLL

`Protected`_balanceLR

`Protected`_balancePath

`Protected`_balanceRL

`Protected`_balanceRR

`Protected`_bound

`Protected`_boundByKey

`Protected`_boundByPredicate

`Protected`_clearNodes

`Protected`_clearValues

`Protected`_clone

`Protected`_compare

`Protected`_createDefaultComparator

`Protected`_createInstance

`Protected`_createLike

`Protected`_DEFAULT_NODE_CALLBACK

`Protected`_deleteByKey

`Protected`_dfs

`Protected`_displayAux

`Protected`_ensurePredicate

`Protected`_extractKey

`Protected`_floorByKey

`Protected`_floorByPredicate

`Protected`_getIterator