Create an AVLTreeMultiMap and optionally bulk-insert items.
OptionalkeysNodesEntriesOrRaws: Iterable<Iterable of keys/nodes/entries/raw items to insert.
Optionaloptions: AVLTreeMultiMapOptions<K, V[], R>Options for AVLTreeMultiMap (comparator, reverse, map mode).
New AVLTreeMultiMap instance.
Protected_comparatorThe comparator function used to determine the order of keys in the tree.
Gets whether the tree allows duplicate keys.
True if duplicates are allowed, false otherwise.
Gets whether the tree is in Map mode.
True if in Map mode, false otherwise.
Gets the sentinel NIL node (used in self-balancing trees like Red-Black Tree).
The NIL node.
Gets the number of nodes in the tree.
The size of the tree.
Protected_balance(Protected) Calculates the balance factor (height(right) - height(left)).
The node to check.
The balance factor (positive if right-heavy, negative if left-heavy).
Protected_balanceLL(Protected) Performs a Left-Left (LL) rotation (a single right rotation).
The unbalanced node (root of the unbalanced subtree).
Protected_balanceLR(Protected) Performs a Left-Right (LR) double rotation.
The unbalanced node (root of the unbalanced subtree).
Protected_balanceProtected_balanceRL(Protected) Performs a Right-Left (RL) double rotation.
The unbalanced node (root of the unbalanced subtree).
Protected_balanceRR(Protected) Performs a Right-Right (RR) rotation (a single left rotation).
The unbalanced node (root of the unbalanced subtree).
Protected_bound(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.
The key, node, entry, or predicate function to search for.
True for lowerBound (>=), false for upperBound (>).
The iteration type (RECURSIVE or ITERATIVE).
The first matching node, or undefined if no such node exists.
Protected_bound(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.
The target key to search for.
True for lowerBound (>=), false for upperBound (>).
The iteration type (RECURSIVE or ITERATIVE).
The first node matching the bound condition, or undefined if none exists.
Protected_bound(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.
The first node satisfying predicate, or undefined if none found.
Protected_clearProtected_clearProtected_clone(Protected) Helper for cloning. Performs a BFS and adds all nodes to the new tree.
The new, empty tree instance to populate.
Protected_compareProtected_createProtected_createProtected_createProtected_DEFAULT_(Protected) Default callback function, returns the node's key.
The node.
The node's key or undefined.
Protected_delete(Private) Deletes a node by its key.
The key of the node to delete.
True if the node was found and deleted, false otherwise.
Protected_dfsCallback type.
Function to call on nodes.
Optionalpattern: DFSOrderPatternTraversal order.
OptionalonlyOne: booleanStop after first match.
OptionalstartNode: Starting node.
OptionaliterationType: IterationTypeTraversal method.
OptionalincludeNull: booleanInclude nulls.
OptionalshouldVisitLeft: ((node: undefined | null | BinaryTreeNode<K, V[]>) => boolean)Predicate to traverse left.
OptionalshouldVisitRight: ((node: undefined | null | BinaryTreeNode<K, V[]>) => boolean)Predicate to traverse right.
OptionalshouldVisitRoot: ((node: undefined | null | BinaryTreeNode<K, V[]>) => boolean)Predicate to visit root.
OptionalshouldProcessRoot: ((node: undefined | null | BinaryTreeNode<K, V[]>) => boolean)Predicate to process root.
Array of callback results.
Protected_display(Protected) Recursive helper for toVisual.
The current node.
Print options.
Layout information for this subtree.
Protected_ensure(Protected) Converts a key, node, entry, or predicate into a standardized predicate function.
The item to convert.
A predicate function.
Protected_extractProtected_floor(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.
The target key to search for.
The iteration type (RECURSIVE or ITERATIVE).
The first node with key <= target, or undefined if none exists.
Protected_floor(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.
The last node satisfying predicate (highest key), or undefined if none found.
Protected_get(Protected) Gets the iterator for the tree (default in-order).
Optionalnode: null | BinaryTreeNode<K, V[]> = ...The node to start iteration from.
An iterator for [key, value] pairs.
Protected_is(Protected) Checks if an item is a predicate function.
The item to check.
True if it's a function.
Protected_keyProtected_lower(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.
The target key to search for.
The iteration type (RECURSIVE or ITERATIVE).
The first node with key < target, or undefined if none exists.
Protected_lower(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.
The last node satisfying predicate (highest key < target), or undefined if none found.
Protected_replace(Protected) Replaces a node, ensuring height is copied.
The node to be replaced.
The node to insert.
The newNode.
Protected_setProtected_setProtected_snapshotProtected_swap(Protected) Swaps properties of two nodes, including height.
The source node.
The destination node.
The destNode (now holding srcNode's properties).
Protected_update(Protected) Recalculates and updates the height of a node based on its children's heights.
The node to update.
Adds multiple items to the tree.
An iterable of items to add.
Optionalvalues: Iterable<undefined | V[], any, any>An optional parallel iterable of values.
OptionalisBalanceAdd: boolean = trueIf true, builds a balanced tree from the items.
OptionaliterationType: IterationType = ...The traversal method for balanced add (recursive or iterative).
An array of booleans indicating the success of each individual add operation.
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.
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.
(Protected) Creates a new AVL tree node.
The newly created AVLTreeNode.
Deletes a node from the AVL tree and re-balances the tree.
An array containing deletion results.
Deletes nodes that match a key, node, entry, predicate, or range.
The search criteria. Can be one of:
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.
The node to start the search from. Can be:
Controls the internal traversal implementation:
A Map<K, boolean> containing the deletion results:
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.
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.
Gets the value associated with a key.
The key, node, or entry to get the value for.
OptionalstartNode: The node to start searching from (if not in Map mode).
OptionaliterationType: IterationType = ...The traversal method (if not in Map mode).
The associated value, or undefined.
Gets the first node matching a predicate.
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.
The first matching node, or undefined if not found.
Gets all nodes matching a predicate.
The key, node, entry, or predicate function to search for.
OptionalonlyOne: booleanIf true, stops after finding the first match.
OptionalstartNode: The node to start the search from.
OptionaliterationType: IterationTypeThe traversal method.
An array of matching nodes.
Gets the Morris traversal predecessor (rightmost node in the left subtree, or node itself).
The node to find the predecessor for.
The Morris predecessor.
Gets the in-order successor of a node in a BST.
Optionalx: null | K | BinaryTreeNode<K, V[]>The node to find the successor of.
The successor node, or null/undefined if none exists.
Checks if a node matching the predicate exists in the tree.
OptionalkeyNodeEntryOrPredicate: The key, node, entry, or predicate to check for.
OptionalstartNode: The node to start the search from.
OptionaliterationType: IterationTypeThe traversal method.
True if a matching node exists, false otherwise.
Whether there exists an entry with the given value.
Value to test.
true if found; otherwise false.
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.
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.
Checks if the given item is a AVLTreeMultiMapNode instance.
True if it's a AVLTreeMultiMapNode, false otherwise.
Checks if the given item is a Range object.
The item to check.
True if it's a Range, false otherwise.
Checks if the given item is a "real" node (i.e., not null, undefined, or NIL).
True if it's a real node, false otherwise.
Checks if the given item is either a "real" node or null.
True if it's a real node or null, false otherwise.
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.
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.
Create a new tree by mapping each [key, values] bucket.
A new AVLTreeMultiMap when mapping to array values; see overloads.
Create a new tree by mapping each [key, values] bucket.
A new AVLTree when mapping to non-array values; see overloads.
Merges another tree into this one by adding all its nodes.
The tree to merge.
OptionalstartNode: OptionaliterationType: IterationTypeAdds or updates a new node to the tree.
True if the addition was successful, false otherwise.
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).
AVL-tree–based multimap (key → array of values). Preserves O(log N) updates and supports map-like mode.
Remarks
Time O(1), Space O(1)