tree_structures

Description:

tree structures

tree_structures #
tree_structures is a Dart implementation of (currently only) a red-black self-balancing binary search tree in Dart with a possibility to output to Graphviz for previewing.
Red-black tree solution is based on the logic and structure of the Franck Bui-Huu's C implementation.
Because of the pure Dart solution, it can't really reach high speeds, so the usage is simply educational.
The implementation focuses on correctness, providing assertion for conformance to the red-black tree rules during testing.
It also takes advantage of the Sound null safety.
The tree is generic, accepting K extends Comparable for the key, and any V for the value types.
Right now the benchmark is as following (with comparison to a regular Map), using int as keys:
Count-based benchmark #
count: 500000

adding random to a regular [map]: 116ms

adding random to [randomTree]: 309ms
testing conformity of [randomTree]: 71ms
searching in [randomTree]: 227ms

adding sequential to [sequentialTree]: 242ms
testing conformity of [sequentialTree]: 35ms
successor & predecessor in [sequentialTree]: 58ms
deletion in [sequentialTree]: 81ms
copied to clipboard
Time-based benchmark #
finished with 1328915 loops (332357 inserts, 996558 skipped inserts, 332272 deletions) within 5000ms, keys in [0..100) range.
copied to clipboard
Keys output #
var tree = RBTree<int, dynamic>();
tree.insert(100, "data associated with 100");
tree.insert(150, "data associated with 150");
tree.remove(100);
tree.insert(200, "data associated with 200");
tree.insert(20, "data associated with 20");
tree.insert(25, "data associated with 25");
tree.insert(18, "data associated with 18");
tree.insert(120, "data associated with 120");
tree.insert(180, "data associated with 180");
copied to clipboard
Output:
(150(20<r(18<b)(25>b(120>r)))(200>b(180<r)))
copied to clipboard
forEach #
tree.forEach((node) {
print("${node.key}:${node.value}");
return true; // continue
});
copied to clipboard
Output:
18:data associated with 18
20:data associated with 20
25:data associated with 25
120:data associated with 120
150:data associated with 150
180:data associated with 180
200:data associated with 200
copied to clipboard
Output to Graphviz #
print(tree.output(OutputStyle.Graphviz));
copied to clipboard
Output:
digraph {
150[style=filled,color=black,fontcolor=white];
150 -> 20;
20[style=filled,color=tomato,fontcolor=white];
20 -> 18;
18[style=filled,color=black,fontcolor=white];
null0 [shape=point];
18 -> null0;
null1 [shape=point];
18 -> null1;
20 -> 25;
25[style=filled,color=black,fontcolor=white];
null2 [shape=point];
25 -> null2;
25 -> 120;
120[style=filled,color=tomato,fontcolor=white];
null3 [shape=point];
120 -> null3;
null4 [shape=point];
120 -> null4;
150 -> 200;
200[style=filled,color=black,fontcolor=white];
200 -> 180;
180[style=filled,color=tomato,fontcolor=white];
null5 [shape=point];
180 -> null5;
null6 [shape=point];
180 -> null6;
null7 [shape=point];
200 -> null7;
}
copied to clipboard
Graphviz to svg example output of the above tree (dot -Tsvg <file.dot> > exmple_output.svg):

pub.dev #
https://pub.dev/packages/tree_structures

License

For personal and professional use. You cannot resell or redistribute these repositories in their original state.

Share

• Share on Facebook
• Share on Twitter