avl_tree provides an implementation of an AVL Tree,
a self-balancing binary search-tree.
It's basically a port from an implementation in Java by Justin Wheterell.
This implementation includes two custom features usually not present in AVL trees:
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
The tree can (optionally) store multiple values which are equal with respect
to the tree ordering, but not identical with respect to Darts
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 stored in one tree node.
// 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
Creates a balanced tree of strings, ordered 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"]
Creates a tree of strings. The order is lexicographic with respect to the lowercase version of the strings. Strings which are equal modulo case are in the same equivalence class.
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"]
avl_tree is available from pub.dartlang.org. Add
dependencies: avl_tree: "^0.1.1"
See version history.
avl_tree is licensed under the Apache 2.0 license, see files LICENSE and NOTICE.
Add this to your package's pubspec.yaml file:
dependencies: avl_tree: ^0.2.1
You can install packages from the command line:
$ pub get
$ flutter packages get
Alternatively, your editor might support
pub get or
flutter packages get.
Check the docs for your editor to learn more.
Now in your Dart code, you can use:
|0.2.1||Jan 3, 2017|
|0.2.0+1||Nov 25, 2016|
|0.2.0||Nov 25, 2016|
|0.1.1+1||Jun 19, 2015|
|0.1.1||Jun 19, 2015|
|0.1.0+3||May 31, 2013|
|0.1.0+2||May 20, 2013|
|0.1.0||May 20, 2013|
|0.0.2||May 5, 2013|
Describes how popular the package is relative to other packages. [more]
Code health derived from static analysis. [more]
Reflects how tidy and up-to-date the package is. [more]
Weighted score of the above. [more]
The package version is not analyzed, because it does not support Dart 2. Until this is resolved, the package will receive a health and maintenance score of 0.
lib/src/avl_tree.dart. (-25.75 points)
lib/src/avl_tree.dart failed with 1 error, 2 hints:
line 158 col 37: The method 'compareTo' isn't defined for the class 'Object'.
line 51 col 3: This function has a return type of 'bool', but doesn't end with a return statement.
line 884 col 3: The method '_dump' isn't used.
Add SDK constraint in
pubspec.yaml. (-50 points)
For information about setting SDK constraint, please see https://www.dartlang.org/tools/pub/pubspec#sdk-constraints.
Package is too old. (-100 points)
The package was released more than two years ago.
CHANGELOG.md. (-20 points)
Changelog entries help clients to follow the progress in your code.
Maintain an example. (-10 points)
Create a short demo in the
example/ directory to show how to use this package. Common file name patterns include:
example.dart or you could also use