Skip to main content

AVL Tree, Interval Tree, Trie and More. All kinds of Trees implemented in python3.

Project description

# pytrees ![](https://img.shields.io/badge/LICENSE-MIT-green.svg) ![](https://img.shields.io/badge/python-python3-color.svg)

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

Project details


Download files

Download the file for your platform. If you're not sure which to choose, learn more about installing packages.

Files for pytrees, version 0.0.1
Filename, size File type Python version Upload date Hashes
Filename, size pytrees-0.0.1.tar.gz (23.9 kB) File type Source Python version None Upload date Hashes View

Supported by

AWS AWS Cloud computing Datadog Datadog Monitoring DigiCert DigiCert EV certificate Facebook / Instagram Facebook / Instagram PSF Sponsor Fastly Fastly CDN Google Google Object Storage and Download Analytics Pingdom Pingdom Monitoring Salesforce Salesforce PSF Sponsor Sentry Sentry Error logging StatusPage StatusPage Status page