Order Statistics Tree

A plain sorted array answers "is X present" quickly but answers "how many values are below X" or "what is the 40th percentile value" only by scanning or re-sorting. This library keeps a binary search tree where each node stores its own subtree's total element count (size = own multiplicity + left subtree size + right subtree size), maintained incrementally on every insert and remove. That single augmentation is what turns rank and select into real O(depth) tree walks rather than disguised linear scans. Duplicates are supported properly - this is a multiset, not a plain set. Each distinct key lives in exactly one node with a multiplicity counter; inserting an existing key increments the counter instead of creating a second node, and removing decrements it, only unlinking the node once its count reaches zero. Rank(key) returns the count of elements strictly less than key (well-defined even if key itself was never inserted), and Select(k) returns the k-th smallest element, zero-indexed, counting every duplicate occurrence in its own slot. This is a plain, unbalanced BST - no AVL or red-black rotation logic. Average-case depth is O(log n) on randomly-ordered insertions, which the demo's larger randomised batch exercises; worst case is O(n) on adversarial, already-sorted insertion order, exactly like any unrotated BST. That trade-off is stated plainly here rather than implying a balancing guarantee the implementation does not have. Notes and limitations - Unbalanced BST: average O(log n) per operation on random insertion order, worst-case O(n) depth on adversarial (sorted-order) insertion. No rotation/rebalancing is implemented. - Keys are double - two values that differ only in floating-point rounding noise will be treated as distinct keys. Round or quantise inputs first if that matters for your use case. - Rank(key) for a key that is present returns the rank of its FIRST occurrence (i.e. Rank(key) <= Select-index <= Rank(key)+CountOf(key)-1 for every valid occurrence) - the demo's cross-check accounts for this explicitly rather than asserting a single exact index. - Not thread-safe beyond what a single MQL4 program thread already guarantees. Nodes are heap-allocated with new/delete internally; always call Clear() (or let the destructor run) rather than discarding a populated tree, to avoid leaking node memory.

Script · MT4 · v1.0 · Free

Tags: Binary Options · MT4 Script · MQL4 Source Code

MQL4 & MQL5 scripts · PolyMaria