RadixTree

Radix tree as defined is defined in Wikipedia: https://en.wikipedia.org/wiki/Radix_tree

A data structure that represents a space-optimized trie (prefix tree) in which each node that is the only child is merged with its parent

It would be easier to follow by example, or try it on a helpful app like this one: https://www.cs.usfca.edu/~galles/visualization/RadixTree.html

Say we have the following list of chars:

[ [ "r", "o", "m", "a", "n", "e" ] , [ "r", "o", "m", "u", "l", "u", "s" ] , [ "r", "u", "b", "e", "n", "s" ] , [ "r", "u", "b", "e", "r" ] , [ "r", "u", "b", "i", "c", "o", "n" ] , [ "r", "u", "b", "i", "c", "u", "n", "d", "u", "s" ] ]

We would like to represent this as a Radix tree. Where letters that repeat are in parent nodes, and the rest are in child nodes.

It would look like this:

r
- ub
  - ic
    - undus
    - on
  - e
    - r
    - ns
- om
  - ulus
  - ane

This package allows inserting values to the tree in an Ordered and Un-ordered manner. The ordered one is presented above. The "order" is in relation to the position of each letter. That is, when we look for the letter "r" that is the beginning of the list , on an Ordered list, we match it only to other "r" letters that are also at the beginning.

An Un-ordered insert on the other hand doesn't care about the position of the chars, but rather if they exist or not.

Here's an example of how an un-ordered insert would result, assuming we have this list of Int.

[ [1, 2, 3] , [2, 1, 4] , [4, 5, 6] ]

This will result with:

1, 2
- 3
- 4
  - 5
  - 6

Build

empty : Tree (List a)

Create an empty Radix tree.

import Tree


empty
    |> Tree.label --> []

singleton : List a -> Tree (List a)

Create an Radix tree with a single value.

import Tree


singleton [1, 2, 3]
    |> Tree.label --> [1, 2, 3]

insert : List a -> Tree (List a) -> Tree (List a)

An Ordered insert of a value to the Radix tree.

import Tree


singleton [1, 2, 3]
    |> insert [1, 2, 4]
    |> Tree.label --> [1, 2]


singleton [1, 2, 3]
    |> insert [1, 2, 4]
    |> Tree.children --> [singleton [4], singleton [3]]

insertWith :

( List a -> List a -> List a, List a -> List a -> List a )

-> List a

-> Tree (List a)

Generalized insert, that accepts a tuple with the insert function, and the remove function to apply.

See the 'split' function.

insertUnOrdered : List a -> Tree (List a) -> Tree (List a)

An Un-ordered insert of a value to the Radix tree.

import Tree


singleton [1, 2, 3]
    |> insertUnOrdered [2, 1, 4]
    |> Tree.label --> [2, 1]

Lists manipulation

orderedIntersect : List a -> List a -> List a

Find the matching elements, with regard to their order in the list. That is, we look for matches starting from the first element.

orderedRemove : List a -> List a -> List a

Remove matching elements, with regard to their order in the list. That is, only if the elements are in the beginning fo the list they will be removed.

unOrderedIntersect : List a -> List a -> List a

Find the matching elements, regardless of their order in the list.

unOrderedRemove : List a -> List a -> List a

Remove matching elements, with no regard to of their order in the list. That is, even if the element is in the middle or end of the list, it will be removed.

Modules

RadixTree

Gizra/elm-radix-tree/1.0.0

RadixTree

Build

Lists manipulation

Modules