A binary search tree (BST)
A BST automatically arranges BinaryTreeNode objects so the resulting tree is a valid BST.
Example:
class Element implements polygonal.ds.Comparable<Element> {
var i:Int;
public function new(i:Int) {
this.i = i;
}
public function compare(other:Element):Int {
return other.i - i;
}
public function toString():String {
return Std.string(i);
}
}
...
var o = new polygonal.ds.Bst<Element>();
o.insert(new Element(1));
o.insert(new Element(0));
o.insert(new Element(2));
o.insert(new Element(7));
trace(o); //outputs:
[ Bst size=4
7
2
1
0
]
Constructor
Variables
read onlykey:Int = HashKey.next()
A unique identifier for this object.
A hash table transforms this key into an index of an array element by using a hash function.
reuseIterator:Bool = false
If true, reuses the iterator object instead of allocating a new one when calling this.iterator().
The default is false.
If this value is true, nested iterations will fail as only one iteration is allowed at a time.
Methods
clear (gc:Bool = false):Void
Removes all elements.
Parameters:
gc | if true, elements are nullified upon removal so the garbage collector can reclaim used memory. |
|---|
clone (byRef:Bool = true, ?copier:T ‑> T):Collection<T>
Creates and returns a shallow copy (structure only - default) or deep copy (structure & elements) of this binary search tree.
If byRef is true, primitive elements are copied by value whereas objects are copied by reference.
If byRef is false, the copier function is used for copying elements. If omitted, clone() is called on each element assuming all elements implement Cloneable.
find (val:T):BinaryTreeNode<T>
Finds the node that stores val.
Returns:
the node storing val or null if val does not exist.
free ():Void
Destroys this object by explicitly nullifying all nodes, pointers and elements for GC'ing used resources.
Improves GC efficiency/performance (optional).
insert (val:T):BinaryTreeNode<T>
Inserts val into the binary search tree.
Returns:
the inserted node storing val.
iterator ():Itr<T>
Returns a new BstIterator object to iterate over all elements contained in this BST.
The elements are visited by using a preorder traversal.
See:
remove (val:T):Bool
Removes all nodes containing val.
Returns:
true if at least one occurrence of val is nullified.
toArray ():Array<T>
Returns an array containing all elements in this BST.
The elements are added by applying a preorder traversal.