AvlTree<T> class
Taken from https://github.com/Gubaer/dart-avl-tree
AvlTree is an implementation of a AVL Tree
(http://en.wikipedia.org/wiki/AVL_tree),a self-balancing binary search-tree.
The implementation is basically a port from the implementation in Java
by Justin Wheterell
(https://code.google.com/p/java-algorithms-implementation/).
This implementation provides two custom features usually not present in AVL trees:
-
The methods
add
,remove
, orcontains
not only accept a value to be added, removed, or tested, but optionally also a compare function to be used in this very invocation only. This comes in handy, if a more efficient compare function can be used in a specific invocation. Example: the dynamically changing search tree of intersecting line segments in the Bentley-Ottman-Algorithm. -
The tree can (optionally) store multiple values which are equal with respect to the tree ordering, but not identical with respect to Darts
identical()
function. One application is again the implementation of the Y-structure in the Bentley-Ottman-Algorithm, where multiple overlapping line segments can be handled as equivalence class of line segments.
A simple tree of ints
// create a tree, and use some methods, use the standard
// int.compareTo function for ordering
var tree = new AvlTree<int>();
tree.addAll([0,1,2]);
print(tree.inorder.toList()); // -> [0,1,2]
tree.remove(2);
print(tree.inorder.toList()); // -> [0,1]
print(tree.contains(0)); // true
A tree of strings in reverse lexicographic order
// a balanced tree of strings, ordered in reverse lexicographical
// order
var order = (String s1, String s2) => s2.compareTo(s1);
var tree = new AvlTree<String>(compare: order);
tree.addAll(["aaa", "zzz"]);
print(tree.inorder.toList); // ["zzz", "aaa"]
A tree of strings, lowercase ordering, with equivalence classes
lowerCaseCompare(s,t) => s.toLowerCase().compareTo(t.toLowerCase());
var tree = new AvlTree<String>(compare:lowerCaseCompare,
withEquivalenceClasses: true);
tree.addAll(["aaa", "zzz", "AAA"]);
print(tree.smallest); // -> ["aaa", "AAA"]
Constructors
Properties
- hashCode → int
-
The hash code for this object.
no setterinherited
- inorder → Iterable
-
Returns an iterable of all values traversing the tree
inorder. This is equivalent to an iterable of the
sorted values in the tree.
no setter
- inReverseOrder → Iterable
-
Returns an iterable of all values traversing the tree
in reverse order. See inorder for details.
no setter
- isEmpty → bool
-
Return true if the tree is empty
no setter
- largest → dynamic
-
Returns the largest value in the tree.
no setter
- length → int
-
returns the size of the tree
no setter
- runtimeType → Type
-
A representation of the runtime type of the object.
no setterinherited
- smallest → dynamic
-
Returns the smallest value in the tree.
no setter
Methods
-
add(
T? value, {int compare(T v1, T v2)? = null}) → void -
Adds a
value
to the tree. -
addAll(
Iterable< T> ? values, {int compare(T v1, T v2)? = null}) → void -
Adds the
values
to the tree. -
contains(
T value, {int compare(T v1, T v2)? = null}) → bool -
Returns true, if the tree contains
value
. -
inorderEqualOrLarger(
dynamic reference) → Iterable -
Returns an iterable
of the values starting with the first
node which is equal according to
reference
and consisting of all values equal or larger with respect toreference
. -
inorderEqualOrSmaller(
dynamic reference) → Iterable -
Returns an iterable traversing the values less than or equal to
reference
in reverse order, so thatreference
is first. See inorderEqualOrLarger for details. -
leftNeighbour(
dynamic reference) → dynamic -
Returns the largest value in the tree which is smaller than
reference
. -
noSuchMethod(
Invocation invocation) → dynamic -
Invoked when a nonexistent method or property is accessed.
inherited
-
remove(
T value, {int compare(T v1, T v2)? = null}) → bool -
Removes the
value
from the tree. -
rightNeighbour(
dynamic reference) → dynamic -
Returns the smallest value in the tree which is larger than
reference
. -
toString(
) → String -
A string representation of this object.
inherited
Operators
-
operator ==(
Object other) → bool -
The equality operator.
inherited