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)
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.
-
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_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.”
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]¶
-
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:
zig step:
(1) /
zig-zig step:
(2) /
(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:
The tree has exactly n leaves numbered from 1 to n.
Except for the root, every internal node has at least two children.
Each edge is labeled with a non-empty substring of S.
- No two edges starting out of a node can have string-labels beginning
with the same character.
- 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)
-
-
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:]]
-
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.