avl_tree 0.2.1

  • README.md
  • Installing
  • Versions
  • 34

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:

  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 stored in one tree node.

Examples

A balanced 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

Reverse lexicographic order

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"]

A tree of strings with equivalence classes

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"]

API documentation

See output from dartdoc

Depend on it

avl_tree is available from pub.dartlang.org. Add

dependencies:
  avl_tree: "^0.1.1"

to your pubspec.yaml.

See version history.

Status

Build Status

License

avl_tree is licensed under the Apache 2.0 license, see files LICENSE and NOTICE.

Use this package as a library

1. Depend on it

Add this to your package's pubspec.yaml file:


dependencies:
  avl_tree: "^0.2.1"

2. Install it

You can install packages from the command line:

with pub:


$ pub get

with Flutter:


$ flutter packages get

Alternatively, your editor might support pub get or flutter packages get. Check the docs for your editor to learn more.

3. Import it

Now in your Dart code, you can use:


      import 'package:avl_tree/avl_tree.dart';
  
Version Uploaded Documentation Archive
0.2.1 Jan 3, 2017 Go to the documentation of avl_tree 0.2.1 Download avl_tree 0.2.1 archive
0.2.0+1 Nov 25, 2016 Go to the documentation of avl_tree 0.2.0+1 Download avl_tree 0.2.0+1 archive
0.2.0 Nov 25, 2016 Go to the documentation of avl_tree 0.2.0 Download avl_tree 0.2.0 archive
0.1.1+1 Jun 19, 2015 Go to the documentation of avl_tree 0.1.1+1 Download avl_tree 0.1.1+1 archive
0.1.1 Jun 19, 2015 Go to the documentation of avl_tree 0.1.1 Download avl_tree 0.1.1 archive
0.1.0+3 May 31, 2013 Go to the documentation of avl_tree 0.1.0+3 Download avl_tree 0.1.0+3 archive
0.1.0+2 May 20, 2013 Go to the documentation of avl_tree 0.1.0+2 Download avl_tree 0.1.0+2 archive
0.1.0 May 20, 2013 Go to the documentation of avl_tree 0.1.0 Download avl_tree 0.1.0 archive
0.0.2 May 5, 2013 Go to the documentation of avl_tree 0.0.2 Download avl_tree 0.0.2 archive

Analysis

We analyzed this package on May 22, 2018, and provided a score, details, and suggestions below. Analysis was completed with status completed using:

  • Dart: 2.0.0-dev.54.0
  • pana: 0.11.1

Scores

Popularity:
Describes how popular the package is relative to other packages. [more]
0 / 100
Health:
Code health derived from static analysis. [more]
80 / 100
Maintenance:
Reflects how tidy and up-to-date the package is. [more]
49 / 100
Overall score:
Weighted score of the above. [more]
34
Learn more about scoring.

Platforms

Detected platforms: Flutter, web, other

No platform restriction found in primary library package:avl_tree/avl_tree.dart.

Suggestions

  • Maintain CHANGELOG.md.

    Changelog entries help clients to follow the progress in your code.

  • Fix analysis and formatting issues.

    Analysis or formatting checks reported 1 error 3 hints.

    Strong-mode analysis of lib/src/avl_tree.dart failed with the following error:

    line: 158 col: 37
    The method 'compareTo' isn't defined for the class 'Object'.

  • Package is pre-v1 release.

    While there is nothing inherently wrong with versions of 0.*.*, it usually means that the author is still experimenting with the general direction API.

  • Maintain an example.

    Create a short demo in the example/ directory to show how to use this package. Common file name patterns include: main.dart, example.dart or you could also use avl_tree.dart.

Dependencies

Package Constraint Resolved Available
Dev dependencies
test ^0.12.18