BinarySearchTree2

Implements a binary search tree without a key, meaning elements can be looked up in a different fashion, eg. through opEquals method overriding

struct BinarySearchTree2 (

Elem

) {

Elem lookup(K key);

Elem add(Elem elem);

void rebalanceTree();

void rebalanceTree(Node** node);

size_t length [@property getter];

bool insertAt(Node** node, Elem elem);

void remove(Elem elem);

void rotateLeft(Node** node);

void rotateRight(Node** node);

void rotateRightLeft(Node** node);

void rotateLeftRight(Node** node);

void optimize(Node** node);

Node* findMin();

Node* findMin(Node* from);

Node* findMax();

Node* findMax(Node* from);

string toString();

}

Members

Functions

add Elem add(Elem elem): Inserts a new element with some automatic optimization. TODO: Make the optimization better.
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.
insertAt
bool insertAt(Node** node, Elem elem): Inserts an item at the given point. Returns true if the height of the tree have been raised.
lookup Elem lookup(K key): Gets an element without allocation. Returns E.init if key not found.
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(Elem elem): 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: Nodes for each branches.

Meta

Source

See Implementation

PixelPerfectEngine system binarySearchTree structs