avl_tree provides an implementation of am AVL Tree,
a self-balancing binary search-tree.
The implementation is basically a port from the implementation in Java by Justin Wheterell.
This implementation provides two custom features usually not present in AVL trees:
containsnot 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 stored in one tree node.
Simple example (not using advanced features)
// create a tree, and use some methods var tree = new AvlTree<int>(); tree.add(0); tree.add(1); tree.add(2); print(tree.inorder.toList()); // -> [0,1,2] tree.remove(2); print(tree.inorder.toList()); // -> [0,1] print(tree.contains(0)); // true
Depend on it
avl_tree is available from pub.dartlang.org. Add
dependencies: avl_tree: 0.0.2
See version history.
avl_tree is licensed under the Apache 2.0 license, see files LICENSE and NOTICE.