The primary balancing rotation coefficient that is used for the
determination whether two subtrees of a node are in balance or
require adjustment by means of a rotation operation. The specific
rotation to be performed is determined by +gamma+.
The primary balancing rotation coefficient that is used for the determination whether two subtrees of a node are in balance or require adjustment by means of a rotation operation. The specific rotation to be performed is determined by `+gamma+`.
The secondary balancing rotation coefficient that is used for the
determination of whether a single or double rotation operation should
occur, once it has been decided based on +delta+ that a rotation is
indeed required.
The secondary balancing rotation coefficient that is used for the determination of whether a single or double rotation operation should occur, once it has been decided based on `+delta+` that a rotation is indeed required.
(kvlr [ksym vsym lsym rsym] n & body)destructure node n: key value left right. This is the principal destructuring macro for operating on regions of trees
destructure node n: key value left right. This is the principal destructuring macro for operating on regions of trees
(node-add-if-absent n k v cmp create)Insert key/value only if key doesn't exist. Returns new tree or nil if key exists. Single traversal - more efficient than contains? + add for assocEx.
Insert key/value only if key doesn't exist. Returns new tree or nil if key exists. Single traversal - more efficient than contains? + add for assocEx.
(node-chunks chunk-size n)Partition tree n into roughly equal subtrees of about chunk-size
elements.
Partition tree `n` into roughly equal subtrees of about `chunk-size` elements.
(node-compare accessor n1 n2)return 3-way comparison of the trees n1 and n2 using an accessor to compare specific node consitituent values: :k, :v, :kv, or any user-specifed function. Default, when not specified, to the entire node structure. return-value semantics: -1 -> n1 is LESS-THAN n2 0 -> n1 is EQUAL-TO n2 +1 -> n1 is GREATER-THAN n2
return 3-way comparison of the trees n1 and n2 using an accessor to compare specific node consitituent values: :k, :v, :kv, or any user-specifed function. Default, when not specified, to the entire node structure. return-value semantics: -1 -> n1 is LESS-THAN n2 0 -> n1 is EQUAL-TO n2 +1 -> n1 is GREATER-THAN n2
(node-concat2 l r)(node-concat2 l r create)Join two trees, the left rooted at l, and the right at r, performing a single balancing operation on the resulting tree, if needed. Assumes all keys in l are smaller than all keys in r, and the relative balance of l and r is such that no more than one rotation operation will be required to balance the resulting tree.
Join two trees, the left rooted at l, and the right at r, performing a single balancing operation on the resulting tree, if needed. Assumes all keys in l are smaller than all keys in r, and the relative balance of l and r is such that no more than one rotation operation will be required to balance the resulting tree.
(node-concat3 k v l r)(node-concat3 k v l r cmp create)Join two trees, the left rooted at l, and the right at r, with a new key/value, performing rotation operations on the resulting trees and subtrees. Assumes all keys in l are smaller than all keys in r, and the relative balance of l and r is such that no more than one rotation operation will be required to balance the resulting tree.
Join two trees, the left rooted at l, and the right at r, with a new key/value, performing rotation operations on the resulting trees and subtrees. Assumes all keys in l are smaller than all keys in r, and the relative balance of l and r is such that no more than one rotation operation will be required to balance the resulting tree.
(node-contains-long? n k)Primitive-specialized membership check for Long keys.
Use this when the caller only needs a boolean presence test. It avoids both
Comparator dispatch and the broader node-returning contract of node-find-long.
Primitive-specialized membership check for Long keys. Use this when the caller only needs a boolean presence test. It avoids both Comparator dispatch and the broader node-returning contract of `node-find-long`.
(node-contains-string? n k)String-specialized membership check.
Use this when the caller only needs presence/absence. It uses
String.compareTo directly and avoids the broader node-returning contract of
node-find-string.
String-specialized membership check. Use this when the caller only needs presence/absence. It uses `String.compareTo` directly and avoids the broader node-returning contract of `node-find-string`.
(node-contains? n k)(node-contains? n k cmp)Check if key k exists in tree.
Check if key k exists in tree.
(node-create k v l r)Join left and right subtrees at root k/v. Assumes all keys in l < k < all keys in r.
Join left and right subtrees at root k/v. Assumes all keys in l < k < all keys in r.
(node-create-weight-balanced k v l r)Join left and right weight-balanced subtrees at root k/v. Assumes all keys in l < k < all keys in r.
Join left and right weight-balanced subtrees at root k/v. Assumes all keys in l < k < all keys in r.
(node-create-weight-balanced-double k v l r)Join left and right weight-balanced subtrees at primitive double root k/v. Specialized for Double keys - avoids boxing overhead. Assumes all keys in l < k < all keys in r.
Join left and right weight-balanced subtrees at primitive double root k/v. Specialized for Double keys - avoids boxing overhead. Assumes all keys in l < k < all keys in r.
(node-create-weight-balanced-interval i v l r)Join left and right weight-balanced interval subtrees at root k/v. Assumes all keys in l < k < all keys in r.
Join left and right weight-balanced interval subtrees at root k/v. Assumes all keys in l < k < all keys in r.
(node-create-weight-balanced-long k v l r)Join left and right weight-balanced subtrees at primitive long root k/v. Specialized for Long keys - avoids boxing overhead. Assumes all keys in l < k < all keys in r.
Join left and right weight-balanced subtrees at primitive long root k/v. Specialized for Long keys - avoids boxing overhead. Assumes all keys in l < k < all keys in r.
(node-disjoint? n1 n2)Return true if the two trees share no elements. Short-circuits on the first common element found. Complexity: O(m log(n/m + 1)) where m <= n.
Return true if the two trees share no elements. Short-circuits on the first common element found. Complexity: O(m log(n/m + 1)) where m <= n.
(node-entry-seq n)(node-entry-seq n cnt)Return an efficient seq of map entries from tree rooted at n.
Return an efficient seq of map entries from tree rooted at n.
(node-entry-seq-reverse n)(node-entry-seq-reverse n cnt)Return an efficient reverse seq of map entries from tree rooted at n.
Return an efficient reverse seq of map entries from tree rooted at n.
(node-enum-first enum)Return the current node from an enumerator frame.
Return the current node from an enumerator frame.
(node-enum-prior enum)Advance reverse enumerator to the next (prior) node.
Advance reverse enumerator to the next (prior) node.
(node-enum-rest enum)Advance forward enumerator to the next node.
Advance forward enumerator to the next node.
(node-enumerator n)(node-enumerator n enum)Efficient mechanism to accomplish partial enumeration of tree-structure into a seq representation without incurring the overhead of operating over the entire tree. Used internally for implementation of higher-level collection api routines.
Returns an EnumFrame representing the leftmost spine of the tree, where each frame holds (current-node, right-subtree, next-frame).
Efficient mechanism to accomplish partial enumeration of tree-structure into a seq representation without incurring the overhead of operating over the entire tree. Used internally for implementation of higher-level collection api routines. Returns an EnumFrame representing the leftmost spine of the tree, where each frame holds (current-node, right-subtree, next-frame).
(node-enumerator-reverse n)(node-enumerator-reverse n enum)Reverse enumerator: builds rightmost spine where each frame holds (current-node, left-subtree, next-frame).
Reverse enumerator: builds rightmost spine where each frame holds (current-node, left-subtree, next-frame).
(node-find n k)(node-find n k cmp)(node-find n k not-found cmp)find a node in n whose key = k.
Returns a node implementing INode, or not-found when absent.
Arity notes:
(node-find n k) uses the current dynamic comparator(node-find n k cmp) uses an explicit comparator(node-find n k not-found cmp) uses both an explicit fallback and comparatorfind a node in n whose key = k. Returns a node implementing INode, or `not-found` when absent. Arity notes: - `(node-find n k)` uses the current dynamic comparator - `(node-find n k cmp)` uses an explicit comparator - `(node-find n k not-found cmp)` uses both an explicit fallback and comparator
(node-find-long n k)(node-find-long n k not-found)Primitive-specialized node lookup for Long keys.
Use this when the caller needs the matching node rather than just a boolean.
Kept separate from node-contains-long? so membership-only call sites can stay
on the minimal boolean path.
Primitive-specialized node lookup for Long keys. Use this when the caller needs the matching node rather than just a boolean. Kept separate from `node-contains-long?` so membership-only call sites can stay on the minimal boolean path.
(node-find-nearest n k & [gt-or-lt])Find the nearest k according to relation expressed by :< or :>
Find the nearest k according to relation expressed by :< or :>
(node-find-string n k)(node-find-string n k not-found)String-specialized node lookup.
Use this when the caller needs the matching node rather than just a boolean.
Kept separate from node-contains-string? so membership-only call sites can
stay on the minimal boolean path.
String-specialized node lookup. Use this when the caller needs the matching node rather than just a boolean. Kept separate from `node-contains-string?` so membership-only call sites can stay on the minimal boolean path.
(node-find-val n k not-found)(node-find-val n k not-found cmp)Find value for key k in tree. Returns the value or not-found.
Find value for key k in tree. Returns the value or not-found.
(node-find-val-long n k not-found)Primitive-specialized value lookup for Long keys.
Use this when the caller needs only the associated value (or not-found),
without materializing the broader node-returning path.
Primitive-specialized value lookup for Long keys. Use this when the caller needs only the associated value (or `not-found`), without materializing the broader node-returning path.
(node-find-val-string n k not-found)String-specialized value lookup.
Use this when the caller needs only the associated value (or not-found),
without materializing the broader node-returning path.
String-specialized value lookup. Use this when the caller needs only the associated value (or `not-found`), without materializing the broader node-returning path.
(node-fold chunk-size n combinef reducef)Parallel fold to support clojure.core.reducers/CollFold.
Splits the tree into chunks, then folds them in parallel via r/fold. Splitting is done eagerly in the caller's thread (where dynamic bindings are available); each chunk's sequential reduce uses node-reduce which needs no bindings.
Parallel fold to support clojure.core.reducers/CollFold. Splits the tree into chunks, then folds them in parallel via r/fold. Splitting is done eagerly in the caller's thread (where dynamic bindings are available); each chunk's sequential reduce uses node-reduce which needs no bindings.
(node-greatest n)Return the node containing the maximum key of the tree rooted at n.
Return the node containing the maximum key of the tree rooted at n.
(node-greatest-kv n)Return [k v] for the maximum key of the tree rooted at n.
Return [k v] for the maximum key of the tree rooted at n.
(node-healthy? n)verify node n and all descendants satisfy the node-invariants
of a weight-balanced binary tree.
verify node `n` and all descendants satisfy the node-invariants of a weight-balanced binary tree.
(node-key-seq n)(node-key-seq n cnt)Return an efficient seq of keys from tree rooted at n.
Return an efficient seq of keys from tree rooted at n.
(node-key-seq-reverse n)(node-key-seq-reverse n cnt)Return an efficient reverse seq of keys from tree rooted at n.
Return an efficient reverse seq of keys from tree rooted at n.
(node-least n)Return the node containing the minimum key of the tree rooted at n.
Return the node containing the minimum key of the tree rooted at n.
(node-least-kv n)Return [k v] for the minimum key of the tree rooted at n.
Return [k v] for the minimum key of the tree rooted at n.
(node-map-compare n1 n2)Compare two map trees element-by-element. Keys are compared using the bound compare comparator; on key equality, values are compared using clojure.lang.Util/compare to handle arbitrary value types.
Compare two map trees element-by-element. Keys are compared using the bound *compare* comparator; on key equality, values are compared using clojure.lang.Util/compare to handle arbitrary value types.
(node-map-merge n1 n2 merge-fn)Merge two maps in worst case linear time.
Merge two maps in worst case linear time.
(node-map-merge-parallel n1 n2 merge-fn)Parallel map merge using ForkJoinPool.
Algorithm: Split T1 at T2's root key, recursively merge subtrees, resolve collisions with merge-fn. Fork-join parallelism for large trees.
Parallel map merge using ForkJoinPool. Algorithm: Split T1 at T2's root key, recursively merge subtrees, resolve collisions with merge-fn. Fork-join parallelism for large trees.
(node-nth n index)Return nth node from the beginning of the ordered tree rooted at n. (Logarithmic Time)
Return nth node from the beginning of the ordered tree rooted at n. (Logarithmic Time)
(node-predecessor n k)Find the predecessor of key k (greatest element strictly less than k). Returns the node, or nil if no predecessor exists. O(log n) - single traversal that tracks the last right turn.
Find the predecessor of key k (greatest element strictly less than k). Returns the node, or nil if no predecessor exists. O(log n) - single traversal that tracks the last right turn.
(node-rank n k)(node-rank n k cmp)Return the rank (sequential position) of a given KEY within the ordered tree rooted at n. (Logarithmic Time)
Return the rank (sequential position) of a given KEY within the ordered tree rooted at n. (Logarithmic Time)
(node-reduce-kv f init root)Reduce tree key/value pairs from least to greatest via (f acc k v). Supports early termination via clojure.core/reduced.
Reduce tree key/value pairs from least to greatest via (f acc k v). Supports early termination via clojure.core/reduced.
(node-reduce-kv-right f init root)Reduce tree key/value pairs from greatest to least via (f acc k v). Supports early termination via clojure.core/reduced.
Reduce tree key/value pairs from greatest to least via (f acc k v). Supports early termination via clojure.core/reduced.
(node-remove n k)(node-remove n k cmp create)remove the node whose key is equal to k, if present.
remove the node whose key is equal to k, if present.
(node-remove-greatest n)Return a tree the same as the one rooted at n, with the node containing the maximum key removed. See node-greatest.
Return a tree the same as the one rooted at n, with the node containing the maximum key removed. See node-greatest.
(node-remove-least n)(node-remove-least n create)Return a tree the same as the one rooted at n, with the node containing the minimum key removed. See node-least.
Return a tree the same as the one rooted at n, with the node containing the minimum key removed. See node-least.
(node-run! n f)Eagerly apply f to each node of the tree rooted at n, from least to greatest.
Eagerly apply f to each node of the tree rooted at n, from least to greatest.
(node-run-kv! n f)Eagerly apply f to each key/value pair in the tree rooted at n, from least to greatest.
Eagerly apply f to each key/value pair in the tree rooted at n, from least to greatest.
(node-run-kv-reverse! n f)Eagerly apply f to each key/value pair in the tree rooted at n, from greatest to least.
Eagerly apply f to each key/value pair in the tree rooted at n, from greatest to least.
(node-run-reverse! n f)Eagerly apply f to each node of the tree rooted at n, from greatest to least.
Eagerly apply f to each node of the tree rooted at n, from greatest to least.
(node-seq n)Return a (lazy) seq of nodes in tree rooted at n in the order they occur. (Logarithmic Time)
Return a (lazy) seq of nodes in tree rooted at n in the order they occur. (Logarithmic Time)
(node-seq-reverse n)Return a (lazy) seq of nodes in tree rooted at n in reverse order.
Return a (lazy) seq of nodes in tree rooted at n in reverse order.
(node-set-difference-parallel n1 n2)Parallel set difference using ForkJoinPool.
Algorithm: Split T1 at T2's root, recursively compute difference, never include T2's root (since we're computing T1 - T2).
Complexity: Same as union - O(m+n) work, O(log^2 n) span.
Parallel set difference using ForkJoinPool. Algorithm: Split T1 at T2's root, recursively compute difference, never include T2's root (since we're computing T1 - T2). Complexity: Same as union - O(m+n) work, O(log^2 n) span.
(node-set-intersection n1 n2)set intersection
set intersection
(node-set-intersection-parallel n1 n2)Parallel set intersection using ForkJoinPool.
Algorithm: Split T1 at T2's root, recursively intersect subtrees, include root only if present in both trees.
Complexity: Same as union - O(m+n) work, O(log^2 n) span.
Parallel set intersection using ForkJoinPool. Algorithm: Split T1 at T2's root, recursively intersect subtrees, include root only if present in both trees. Complexity: Same as union - O(m+n) work, O(log^2 n) span.
(node-set-union-parallel n1 n2)Parallel set union using ForkJoinPool.
Algorithm: Adams' divide-and-conquer with work-stealing parallelism.
Complexity: Work: O(m + n) Span: O(log^2 n) Speedup: Near-linear up to ~16 cores for large trees
Parallel set union using ForkJoinPool. Algorithm: Adams' divide-and-conquer with work-stealing parallelism. 1. Split T1 at T2's root key 2. Recursively union (T1.left, T2.left) and (T1.right, T2.right) in parallel 3. Join results at T2's root Complexity: Work: O(m + n) Span: O(log^2 n) Speedup: Near-linear up to ~16 cores for large trees
(node-singleton k v)Create and return a newly allocated, balanced tree containing a single association, that of key K with value V.
Create and return a newly allocated, balanced tree containing a single association, that of key K with value V.
(node-size n)returns the balance metric of the tree rooted at n.
returns the balance metric of the tree rooted at n.
(node-split n k)returns a triple (l present r) where: l is the set of elements of n that are < k, r is the set of elements of n that are > k, present is false if n contains no element equal to k, or (k v) if n contains an element with key equal to k.
returns a triple (l present r) where: l is the set of elements of n that are < k, r is the set of elements of n that are > k, present is false if n contains no element equal to k, or (k v) if n contains an element with key equal to k.
(node-split-greater n k)return a tree of all nodes whose key is greater than k (Logarithmic time).
return a tree of all nodes whose key is greater than k (Logarithmic time).
(node-split-lesser n k)return a tree of all nodes whose key is less than k (Logarithmic time).
return a tree of all nodes whose key is less than k (Logarithmic time).
(node-split-nth n i)return a tree of all nodes whose position is >= i. (Logarithmic Time)
return a tree of all nodes whose position is >= i. (Logarithmic Time)
(node-stitch k v l r)(node-stitch k v l r create)Join left and right subtrees at root k/v, performing a single or double rotation to restore weight balance if needed.
This is the tree's fundamental balancing constructor. It assumes all keys
in l are less than k, all keys in r are greater than k, and that
at most one single or double rotation is needed to restore balance.
The 5-arity form takes an explicit node constructor as its final argument
and is used in hot internal paths to avoid dynamic-var indirection. The
4-arity form uses the current *t-join* binding.
Join left and right subtrees at root k/v, performing a single or double rotation to restore weight balance if needed. This is the tree's fundamental balancing constructor. It assumes all keys in `l` are less than `k`, all keys in `r` are greater than `k`, and that at most one single or double rotation is needed to restore balance. The 5-arity form takes an explicit node constructor as its final argument and is used in hot internal paths to avoid dynamic-var indirection. The 4-arity form uses the current `*t-join*` binding.
(node-subseq n from)(node-subseq n from to)Return a seq of nodes for the slice of the tree from position
from to to (inclusive).
Return a seq of nodes for the slice of the tree from position `from` to `to` (inclusive).
(node-subset? super sub)return true if sub is a subset of super
return true if `sub` is a subset of `super`
(node-successor n k)Find the successor of key k (least element strictly greater than k). Returns the node, or nil if no successor exists. O(log n) - single traversal that tracks the last left turn.
Find the successor of key k (least element strictly greater than k). Returns the node, or nil if no successor exists. O(log n) - single traversal that tracks the last left turn.
(node-vec n & {:keys [accessor reverse?]})Eagerly return a vector of all nodes in tree rooted at n in the specified order, optionally using an accessor to extract specific node consitituent values: :k, :v, :kv, or any user-specifed function. Default, when not specified, to the entire node structure.
Eagerly return a vector of all nodes in tree rooted at n in the specified order, optionally using an accessor to extract specific node consitituent values: :k, :v, :kv, or any user-specifed function. Default, when not specified, to the entire node structure.
(node-weight n)Returns node weight for rotation calculations using the 'revised non-variant algorithm' for weight balanced binary trees. Weight = size + 1.
Returns node weight for rotation calculations using the 'revised non-variant algorithm' for weight balanced binary trees. Weight = size + 1.
(rotate-double-left create ak av x c)Double left rotation. Move Y1 (the left subtree of B, which is the left subtree of C, which is the right subtree of A) into the left subtree. Required when: weight(X) < δ × weight(C) and weight(Y) >= γ × weight(Z).
,---, ,---,
| A | | B |
___:---:___ ____:---:____
,---: :---, ,---: :---,
| X | | C | | A | | C |
'---' :---: => :---: :---:
,---: :---, ,---: :---, ,---: :---,
| B | | Z | | X | | y1| | y2| | Z |
:---: '---' '---' '---' '---' '---'
,---: :---,
| y1| | y2|
'---' '---'
Double left rotation. Move Y1 (the left subtree of B, which is the left
subtree of C, which is the right subtree of A) into the left subtree.
Required when: weight(X) < δ × weight(C) and weight(Y) >= γ × weight(Z).
,---, ,---,
| A | | B |
___:---:___ ____:---:____
,---: :---, ,---: :---,
| X | | C | | A | | C |
'---' :---: => :---: :---:
,---: :---, ,---: :---, ,---: :---,
| B | | Z | | X | | y1| | y2| | Z |
:---: '---' '---' '---' '---' '---'
,---: :---,
| y1| | y2|
'---' '---'
(rotate-double-right create ck cv a z)Double right rotation. Move Y2 (the right subtree of B, which is the right subtree of A, which is the left subtree of C) into the right subtree. Required when: weight(Z) < δ × weight(A) and weight(Y) >= γ × weight(X).
,---, ,---,
| C | | B |
___:---:___ ____:---:____
,---: :---, ,---: :---,
| A | | Z | | A | | C |
:---: '---' => :---: :---:
,---: :---, ,---: :---, ,---: :---, | X | | B | | X | | y1| | y2| | Z | '---' :---: '---' '---' '---' '---' ,---: :---, | y1| | y2| '---' '---'
Double right rotation. Move Y2 (the right subtree of B, which is the right
subtree of A, which is the left subtree of C) into the right subtree.
Required when: weight(Z) < δ × weight(A) and weight(Y) >= γ × weight(X).
,---, ,---,
| C | | B |
___:---:___ ____:---:____
,---: :---, ,---: :---,
| A | | Z | | A | | C |
:---: '---' => :---: :---:
,---: :---, ,---: :---, ,---: :---,
| X | | B | | X | | y1| | y2| | Z |
'---' :---: '---' '---' '---' '---'
,---: :---,
| y1| | y2|
'---' '---'
(rotate-single-left create ak av x b)Single left rotation. Move Y (the left subtree of the right subtree of A) into the left subtree. Required when: weight(X) < δ × weight(B) and weight(Y) < γ × weight(Z).
,---, ,---,
| A | | B |
:---: :---:
: : : :
,---: :---, ,---: :---,
| X | | B | => | A | | Z |
'---' :---: :---: '---'
,---: :---, ,---: :---,
| Y | | Z | | X | | Y |
'---' '---' '---' '---'
Single left rotation. Move Y (the left subtree of the right subtree of A)
into the left subtree. Required when: weight(X) < δ × weight(B) and
weight(Y) < γ × weight(Z).
,---, ,---,
| A | | B |
:---: :---:
: : : :
,---: :---, ,---: :---,
| X | | B | => | A | | Z |
'---' :---: :---: '---'
,---: :---, ,---: :---,
| Y | | Z | | X | | Y |
'---' '---' '---' '---'
(rotate-single-right create bk bv a z)Single right rotation. Move Y (the right subtree of the left subtree of B) into the right subtree. Required when: weight(Z) < δ × weight(A) and weight(Y) < γ × weight(X).
,---, ,---,
| B | | A |
:---: :---:
: : : :
,---: :---, ,---: :---,
| A | | Z | => | X | | B |
:---: '---' '---' :---:
,---: :---, ,---: :---, | X | | Y | | Y | | Z | '---' '---' '---' '---'
Single right rotation. Move Y (the right subtree of the left subtree of B)
into the right subtree. Required when: weight(Z) < δ × weight(A) and
weight(Y) < γ × weight(X).
,---, ,---,
| B | | A |
:---: :---:
: : : :
,---: :---, ,---: :---,
| A | | Z | => | X | | B |
:---: '---' '---' :---:
,---: :---, ,---: :---,
| X | | Y | | Y | | Z |
'---' '---' '---' '---'
cljdoc builds & hosts documentation for Clojure/Script libraries
| Ctrl+k | Jump to recent docs |
| ← | Move to previous article |
| → | Move to next article |
| Ctrl+/ | Jump to the search field |