MOAL.data_structures.trees package

Submodules

MOAL.data_structures.trees.avl_trees module

class MOAL.data_structures.trees.avl_trees.AVLTree[source]

Bases: MOAL.data_structures.trees.binary_search_trees.BinarySearchTree

AVL tree nodes all calculate a balance factor to determine rotations and keep tree in balance for best performance:

bf = height(left_sub_tree) - height(right_sub_tree)

-1, 0, 1 balance factors are all considered to be within balanced range.

unbalanced tree

(-2) / / (0) (-1)

/ / (0) (-1)
_put(key, val, current_node)[source]
_rebalance(node)[source]
_rotate_left(rotation_root)[source]
_rotate_right(rotation_root)[source]
_update_balance(node)[source]

MOAL.data_structures.trees.binary_search_trees module

class MOAL.data_structures.trees.binary_search_trees.BinarySearchTree[source]

Bases: object

BST Code sample originally from interactivepython.org /runestone/static/pythonds/Trees/bst.html#lst-bst1, with some modifications.

__contains__(key)[source]
__delitem__(key)[source]
__getitem__(key)[source]
__init__()[source]
__iter__()[source]
__len__()[source]
__setitem__(key, value)[source]
_get(key, current_node)[source]
_put(key, val, current_node)[source]
_swap_current(current_node, side)[source]
delete(key)[source]
find_min()[source]
find_successor()[source]
get(key)[source]
length()[source]
put(key, val)[source]
remove(current_node)[source]
splice_out()[source]
class MOAL.data_structures.trees.binary_search_trees.Node(key, val, left=None, right=None, parent=None)[source]
__init__(key, val, left=None, right=None, parent=None)
__iter__()
has_any_children()
has_both_children()
has_left_child()
has_right_child()
is_leaf()
is_left_child()
is_right_child()
is_root()
swap_node(key, value, left_child, right_child)
MOAL.data_structures.trees.binary_search_trees.populate_bst(bst, count=1)[source]
MOAL.data_structures.trees.binary_search_trees.recurse_bst(node, lastkey)[source]

MOAL.data_structures.trees.binary_trees module

MOAL.data_structures.trees.cartesian_trees module

MOAL.data_structures.trees.heaps module

class MOAL.data_structures.trees.heaps.BinHeap(new_list)[source]

Bases: MOAL.data_structures.trees.binary_search_trees.BinarySearchTree

__init__(new_list)
del_min()
insert(item)
min_child_index(i)
swap_down(i)
swap_up(i)
class MOAL.data_structures.trees.heaps.PriorityQueue(*args, **kwargs)[source]

Bases: MOAL.data_structures.trees.heaps.BinHeap, object

__init__(*args, **kwargs)

MOAL.data_structures.trees.merkle_tree module

MOAL.data_structures.trees.order_statistic_bst module

class MOAL.data_structures.trees.order_statistic_bst.OrderStatisticBST[source]

Bases: MOAL.data_structures.trees.binary_search_trees.BinarySearchTree

[From Wikipedia]

“In computer science, an order statistic tree is a variant of the binary search tree, that supports two additional operations beyond insertion, lookup and deletion:

  • Select(i) - find the ‘i’th’ smallest element stored in the tree

  • Rank(x) - find the rank of element x in the tree, i.e. its index in

    the sorted list of elements of the tree

Both operations can be performed in O(log n) time in the average case; when a self-balancing tree is used as the base data structure, this bound also applies in the worst case.”

_put(*args)[source]

Override default behavior to augment size property.

rank(node)[source]
select(size)[source]

MOAL.data_structures.trees.radix_tree module

class MOAL.data_structures.trees.radix_tree.NaiveRadixTree(is_root=False, alphabet=None)[source]

Bases: MOAL.data_structures.trees.trie.NaiveTrie

_get_offset(string)

Calculate the offset of self value and a string. e.g. pot / potato = ato, position = 3 (used like [3:])

add(string)

Add a node to this path, or augment it by updating the substring.

view(indent=0, divider=None)

MOAL.data_structures.trees.splay_trees module

class MOAL.data_structures.trees.splay_trees.SplayNode(key, val, left=None, right=None, parent=None)[source]

Bases: MOAL.data_structures.trees.binary_search_trees.Node

class MOAL.data_structures.trees.splay_trees.SplayTree[source]

Bases: MOAL.data_structures.trees.avl_trees.AVLTree

_put(*args, **kwargs)
find(key)

Find an item by key

has_grandparent(node)
left_rotate(node)

Left rotation along a node

put(key, val)

Inserts an item into the tree, and then splays the value all the way back up to the root (if applicable).

remove(key)

Removes an item (if found), from the tree.

right_rotate(node)

Right rotation along a node

splay(node)

The primary splay operation. Splaying happens all the way up the tree (until node no longer has a parent). Three methods are available when splaying:

  1. zig step:

    (1) /

  1. zig-zig step:

    (2) /

(1) /
  1. zig-zag step:
subtree_maximum(node)

Find the subtree maximum by checking for the largest right child – keep traversing downward until no right_child is left.

subtree_minimum(node)

Find the subtree minimum by checking for the smallest left child – keep traversing downward until no left_child is left.

swap(node_u, node_v)

Swap two nodes.

MOAL.data_structures.trees.suffix_tree module

class MOAL.data_structures.trees.suffix_tree.BaseSuffixTree(word)[source]

Bases: object

[From Wikipedia:]

“A suffix tree is a compressed Trie containing all the suffixes of the given text as their keys and positions in the text as their values.”

”...The suffix tree for the string S of length n is defined as a tree such that:

  1. The tree has exactly n leaves numbered from 1 to n.

  2. Except for the root, every internal node has at least two children.

  3. Each edge is labeled with a non-empty substring of S.

  4. No two edges starting out of a node can have string-labels beginning

    with the same character.

  5. The string obtained by concatenating all the string-labels

    found on the path from the root to leaf i spells out suffix S[i..n], for i from 1 to n.

– CONSTRUCTION –

banana seems to be the canonical example, so we’ll keep with tradition.

First, let’s get some information about the string.

>>> l, s = len(banana), 'banana'

Now we can use this data to construct our tree. Note: there are some implementations that seem to omit the sub-substrings, but we’ll cover both as two different classes, which we’ll call shallow, and deep. The required storage for the deep one is significantly greater.

Either version could be easily represented using a list or dictionary. See the individual classes for details.

— FUN FACTS (Wikipedia): —

”...there have been practical works for constructing disk-based suffix trees which scale to (few) GB/hours. The state of the art methods are TDD, TRELLIS, DiGeST, B2ST...

...ERA can index the entire human genome in 19 minutes on an 8-core desktop computer with 16GB RAM. On a simple Linux cluster with 16 nodes (4GB RAM per node), ERA can index the entire human genome in less than 9 minutes.” “

__getitem__(key)
__init__(word)

Init function.

__setitem__(key, val)
__str__()
_populate()
class MOAL.data_structures.trees.suffix_tree.DeepSuffixTree(word)[source]

Bases: MOAL.data_structures.trees.suffix_tree.BaseSuffixTree

The deeper tree can be up to l levels deep and l levels wide – where l is the length of the initial string.

_populate(*args, **kwargs)
Example: banana_tree = {

# [banana] 0: { .... ........... .....................

0: ‘ana’, # You get the idea... 1: {

1: ‘na’, 2: ‘n’

}, 2: ‘n’

}, 1: ‘na’, 2: ‘n’

.

Lookups:

“banana” -> banana_tree[0][0] “ana” -> banana_tree[0][1][2],

banana_tree[0][2][1], banana_tree[0][3][0], .. .

I’m not sure what the use of the above, (what I might call the “Recursive SuperSet(TM)”) is, but I’m sure it has some interesting mathematical properties, like the fact that each subset has exactly 1 less number of values than the previous sublist – but I suppose that is a pedestrian fact for many recursive structures.

Another (preferably) visual way to represent this, is reminiscent of the example suffix tree generated with Ukkonen’s algorithm, given in the link.

I think it’s a bit clearer and easier to understand. Also, interestingly enough, you can get a normal looking tree by tilting this one 45 degrees clockwise around the top corner - (1, 6)

In this representation, each node is spaced by the len(subst) + 4) ... and the ‘dimensions’ for each node are = (depth, breadth)

(B, D) represents the breadth, and depth.

(1, 6) (5, 5) (4, 4) (3, 3) (2, 2)(1, 1) banana anana nana ana na n$ 0 ——–|——–|——-|——|—-| | | .... ... .. . $ (4, 4) (3, 3) (2, 2) (1, 1)

nana ana na n$ |——-|——|—–| | ... .. . (3, 3) (2, 2)(1, 1) ana na n$ |——|—–| | | $ (2, 2) (1, 1) an n$ |
(0, 0) # This gives us another way to represent sentinels
a$
class MOAL.data_structures.trees.suffix_tree.GeneralizedSuffixTree(words)[source]

Bases: MOAL.data_structures.trees.suffix_tree.DeepSuffixTree

A tree of suffix subtrees – a suffix forest?

__init__(words)
__str__()
class MOAL.data_structures.trees.suffix_tree.ShallowSuffixTree(word)[source]

Bases: MOAL.data_structures.trees.suffix_tree.BaseSuffixTree

Shallow: substrings(string) = [

‘banana’, # s[0:] ‘anana’, # s[1:] ‘nana’, # s[2:] ‘ana’, # s[3:] ‘na’, # s[4:] ‘a’, # s[5:]

]

_populate(*args, **kwargs)[source]
class MOAL.data_structures.trees.suffix_tree.UkkonenSuffixTree[source]

Bases: MOAL.data_structures.trees.suffix_tree.BaseSuffixTree

A more efficient algorithm. See programmerspatch.blogspot.com.au

/2013/02/ukkonens-suffix-tree-algorithm.html for more information.
__init__()[source]

MOAL.data_structures.trees.trie module

class MOAL.data_structures.trees.trie.NaiveTrie(is_root=False, alphabet=None)[source]

Bases: MOAL.data_structures.trees.binary_search_trees.BinarySearchTree

__init__(is_root=False, alphabet=None)
add(string)
view(node=None, spacer=1)

A quick and dirty way to view the nested nature of the tree