tree_data_structures

This repository contains a collection of tree data structures I'm exploring. Included are:

1. AvlTree
2. RadixTree
3. PrintableTree

AvlTree

• Includes an AvlTree implementation that solely depends on the comparator defined for a single instance of the tree. All exposed methods depend on the comparator rather than a boolean predicate.

• Additional functionalities provided are as outlined by this Research Paper by Guy Blelloch, Daniel Ferizovic and Yihan Sun.

• The implementation has some basic operations of an AvlTree (which canonically is also a Set) and separate (planned) implementations for:

  1. Joining 2 AvlTrees via a mutually exclusive key ✅
  2. Joining 2 AvlTrees without key ✅
  3. Split an AvlTree via key ✅
  4. SplitLast ✅
  5. Insert via Split ❌
  6. Delete via Split ❌
  7. Union of 2 AvlTrees ✅ (Set operation)
  8. Intersection of 2 AvlTrees ✅ (Set operation)
  9. Difference of 2 AvlTrees ✅ (Set operation)

RadixTree (WIP)

A custom implementation of a prefix tree that uses:

1. A HashMap to store all the root nodes of the RadixTree.
2. An AvlTree to store all sub-nodes of a (root) node within a RadixTree.

PrintableTree

A basic interface for displaying (debugging) any tree implemented. All trees will explicitly implement this interface.