pytrees 0.0.1

Description:

pytrees 0.0.1

# pytrees
A collection of python3 implementations of trees. Including AVL Tree, Interval Tree and More.
## Classes
### AVL Tree
AVL Tree.
Balanced Binary Search Tree. Gurantee for balance.
API:

insert(self, val)
delete(self, key)
search(self, key)
getDepth(self)
preOrder(self)
inOrder(self)
postOrder(self)
countNodes(self)
buildFromList(cls, l)

### Interval Tree
Augmented data structure for checking overlaps of intervals. Gurantee for balance.
API:

queryOverlap(self, val)
queryAllOverlaps(self, val)
insert(self, val)
delete(self, key)
search(self, key)
getDepth(self)
preOrder(self)
inOrder(self)
postOrder(self)
countNodes(self)
buildFromList(cls, l)

### Binary Search Tree
Simple implementation of Binary Search Tree. No gurantee for balance.
API:

insert(self, val)
delete(self, key)
search(self, key)
getDepth(self)
preOrder(self)
inOrder(self)
postOrder(self)
countNodes(self)
buildFromList(cls, l)

### Trie (Prefix-Tree)
Prefix-tree. Useful for text search.
API:

insert(self, word)
search(self, word)
startsWith(self, prefix)
findAllWordsStartsWith(self, prefix)
buildFromList(cls, l)

### Binary Index Tree
A Fenwick tree or Binary Indexed Tree is a data structure that can efficiently update elements and calculate prefix sums in a table of numbers.
API:

update(self,i,k) –> update value k to index i
prefixSum(self,i) –> sum up [index 0, index 1, …, index i]
preview(self)
getSize(self)
buildFromList(cls, l)

Time Complexity: update & prefixSum, O(logN)
Space Complexity: O(N)
## Convention:

“key” and “val” are almost the same in this implementation. use term “key” for search and delete a particular node. use term “val” for other cases