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:

  1. The methods add, remove, or contains 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.

  2. 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

AvlTree({int compare(T v1, T v2)?, dynamic withEquivalenceClasses = false})
Creates an AVL tree.

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 to reference.
inorderEqualOrSmaller(dynamic reference) Iterable
Returns an iterable traversing the values less than or equal to reference in reverse order, so that reference 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