BinarySearchTree

Implements a mostly @nogc-able container format, with relatively fast access times. Mostly based upon the AVT tree algorithm with small modifications, with the intent to replace D's default associative arrays for GC-free operations, and better speed (theoretical worst-case access times: aArray's = n, this' = log2(n)). Tree traversal through D's Range capabilities. TODO: <ul> <li>Implement tree traversal.</li> <li>Improve tree optimization speeds.</li> <li>Fix potential memory leakage issues.</li> </ul>

Members

Functions

collectNodes Node*[] collectNodes(Node* source): Undocumented in source. Be warned that the author may not have intended to support it.
findMax Node* findMax(): Finds the largest value from the root.
findMax Node* findMax(Node* from): Finds the largest value from the given root.
findMin Node* findMin(): Finds the smallest value from the root.
findMin Node* findMin(Node* from): Finds the smallest value from the given root.
getPtr E* getPtr(K key): Gets the pointer of an element.
insertAt
bool insertAt(Node** node, K key, E val): Inserts an item at the given point. Returns true if the height of the tree have been raised.
opApply int opApply(int delegate(Node) @(nogc) dg): Used for foreach iteration.
opIndex E opIndex(K key): Gets an element without allocation. Returns E.init if key not found.
opIndexAssign E opIndexAssign(E value, K i): Inserts a new element with some automatic optimization. TODO: Make the optimization better.
optimize
void optimize(Node** node): Optimizes a BinarySearchTree by distributing nodes evenly.
rebalanceTree void rebalanceTree(): Rebalances a tree.
rebalanceTree
void rebalanceTree(Node** node): Undocumented in source. Be warned that the author may not have intended to support it.
remove void remove(K key): Removes an element by key.
rotateLeft
void rotateLeft(Node** node): Rotates the subtree to the left by one.
rotateLeftRight
void rotateLeftRight(Node** node): Rotates the subtree to the right then to the left.
rotateRight
void rotateRight(Node** node): Rotates the subtree to the right by one.
rotateRightLeft
void rotateRightLeft(Node** node): Rotates the subtree to the right then to the left.
toString string toString(): Undocumented in source. Be warned that the author may not have intended to support it.

Properties

length size_t length [@property getter]: Returns the number of elements in the tree.

Structs

Node struct Node: Implements a single tree node.

BinarySearchTree

Members

Functions

Properties

Structs

Meta

Source