.gif)
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
License
For personal and professional use. You cannot resell or redistribute these repositories in their original state.
Customer Reviews
There are no reviews.
