Binary Search Tree

A binary search tree is the right structure whenever values arrive one at a time over the life of a program and both membership testing and a sorted read are needed - a plain array can give you one of those cheaply (ArraySort for the sorted read, or a hash-style scan for membership) but not both without redoing work on every insert. CBinarySearchTree gives Insert/Remove/Contains at O(log n) on typical input and InOrderToArray() at O(n) whenever a sorted snapshot is actually needed, instead of paying for that ordering on every single insert. Nodes are allocated with new and freed with delete, and every deletion path frees exactly the node it detaches - Clear() and the destructor both walk the tree freeing every node, so a tree going out of scope, or an EA calling Clear() to reset state between sessions, never leaks memory for the life of the terminal process. Remove() is the part almost every from-scratch BST gets wrong on the first attempt, because it has three distinct cases and neither MQL4 nor MQL5 has a pointer-to-pointer parameter to make the classic C++ implementation work unmodified. This header uses the "return the new subtree" shape instead: every recursive helper returns the (possibly unchanged, possibly replaced) subtree root, and the caller reassigns node.left or node.right to it. A leaf is simply deleted and NULL returned in its place. A node with one child is deleted and that child returned in its place. A node with two children copies its in-order successor's value up (the smallest value in its right subtree) and then recursively removes that successor - which is now guaranteed to have at most one child, so the recursion always lands back in one of the first two cases. The demo builds a specific eleven-value tree shaped so three separate, individually named Remove() calls trigger exactly the leaf, one-child, and two-children cases in turn, rather than leaving which case fires to chance. No duplicate values are stored. Insert() returns false and leaves the tree unchanged when the value is already present, which is what makes this structure usable as an ordered set as well as a sorted container - the demo shows a repeated Insert() being rejected with the count unchanged. Notes and limitations - This is a plain, unbalanced binary search tree, not an AVL or red-black tree. Insert order matters: values inserted in already-sorted order degrade it into a near-linear chain with O(n) operations instead of O(log n). Use Height() as a sanity check - a height noticeably above roughly log2(Count())+1 signals close-to-sorted input. - Values are plain doubles, compared with < and >; there is no epsilon tolerance, so two values that differ only in floating-point noise are treated as distinct. Normalise values before inserting if that matters for the use case (price levels, for example). - Not thread-safe, which matches both platforms' single-threaded-per-chart execution model; nothing here changes that.

Script · MT5 · v1.0 · Free

Tags: Binary Options · MT5 Script · MQL5 Source Code

MQL4 & MQL5 scripts · PolyMaria