trees

package trees
General module for tree data structures

Concerns

  • trees: General module for tree data structures
    • abstract_tree: Introduce tree structures abstraction
    • bintree: Binary Tree data-structure
    • rbtree: A red–black tree is a data structure which is a type of self-balancing binary search tree.
    • trees: General module for tree data structures
    • trie: A trie (or prefix tree) is a datastructure used to perform prefix searches.

trees::abstract_tree

module abstract_tree

Introduce tree structures abstraction

Trees are a widely used abstract data type (ADT) or data structure implementing this ADT that simulates a hierarchical tree structure, with a root value and subtrees of children, represented as a set of linked nodes.

Introduces
  • TreeNode: Abstract node structure used in Tree implementation
  • TreeMap: Abstract tree map structure

trees::bintree

module bintree

Binary Tree data-structure

A binary tree is a tree data structure in which each node has at most two children (referred to as the left child and the right child). In a binary tree, the degree of each node can be at most two. Binary trees are used to implement binary search trees and binary heaps, and are used for efficient searching and sorting.

trees::rbtree

module rbtree

A red–black tree is a data structure which is a type of self-balancing binary search tree.

Balance is preserved by painting each node of the tree with one of two colors (typically called 'red' and 'black') in a way that satisfies certain properties, which collectively constrain how unbalanced the tree can become in the worst case. When the tree is modified, the new tree is subsequently rearranged and repainted to restore the coloring properties. The properties are designed in such a way that this rearranging and recoloring can be performed efficiently.

The balancing of the tree is not perfect but it is good enough to allow it to guarantee searching in O(log n) time, where n is the total number of elements in the tree. The insertion and deletion operations, along with the tree rearrangement and recoloring, are also performed in O(log n) time.

trees::trie

module trie

A trie (or prefix tree) is a datastructure used to perform prefix searches.

The trie uses an arborescent datastructure to perform searches on a prefix. With this version of the trie, you can link data to nodes so the trie can be used as a kind of Map by prefix.

var trie = new Trie[Int]
trie["foo"] = 1
trie["fooo"] = 2
trie["foooo"] = 3
trie["bar"] = 4
trie["baz"] = 5

# Get stored values by key
print trie.has_key("foo")
print trie["foo"] == 1

# Get stored values by prefix
assert trie.has_prefix("fo")
assert not trie.has_prefix("z")
assert trie.find_by_prefix("foo") == [1, 2, 3]
assert trie.find_by_prefix("bar") == [4]
assert trie.find_by_prefix("z").is_empty
Introduces
  • Trie: Trie data structure for prefix searches