Package com.abstractkamen.datastructures.impl.trees.search

Class AvlTree<T>

java.lang.Object
com.abstractkamen.datastructures.impl.trees.search.AvlTree<T>
Type Parameters:
T - type of elements
All Implemented Interfaces:
BinarySearchTree<T>, Iterable<T>
public class AvlTree<T> extends Object implements BinarySearchTree<T>
An AVL implementation of the BinarySearchTree interface. Currently, does not support concurrent modification.

  • Constructor Summary

    Constructors
    Constructor
    Description
    AvlTree(Comparator<T> comparator)
    Create an AvlTree<T> with a custom comparator and allowed duplicate values.
    AvlTree(Comparator<T> comparator, boolean allowDuplicates)
    Create an AvlTree<T> with a custom comparator and flag for duplicate values.

  • Method Summary

    Modifier and Type
    Method
    Description
    void
    add(T item)
    Adds an item to the tree.
    void
    clear()
    Remove all elements from this tree.
    boolean
    contains(T item)
    Check if an item exists in the tree.
    int
    containsCount(T item)
    Check how many items are equal to item there are in the tree.
    static <T extends Comparable<T>>
    AvlTree<T>
    createComparable()
    Create an AvlTree<T> with natural order comparator in a type safe way.
    static <T extends Comparable<T>>
    AvlTree<T>
    createComparable(boolean allowDuplicates)
    Create an AvlTree<T> with natural order comparator in a type safe way and flag for duplicate values.
    Iterator<T>
    descendingIterator()
    Get an iterator over the elements in this tree, in descending order.
    T
    greater(T item)
    Get the first item greater than item.
    int
    height()
    Get the height of this tree.
    boolean
    isEmpty()
    Returns true if tree has no elements.
    Iterator<T>
    iterator()
     
    T
    lesser(T item)
    Get the first item lesser than item.
    T
    max()
    Get the maximum item.
    T
    min()
    Get the minimum item.
    String
    prettyString()
    Get a detailed representation of the structure of this tree.
    void
    remove(T item)
    Removes an item to from the tree.
    int
    size()
    Get the current number of elements in the tree.
    Stream<T>
    stream()
    Get a sequential stream over elements in this tree.
    String
    toString()
     

    Methods inherited from class java.lang.Object

    clone, equals, finalize, getClass, hashCode, notify, notifyAll, wait, wait, wait

    Methods inherited from interface java.lang.Iterable

    forEach, spliterator

  • Constructor Details

    • AvlTree

      public AvlTree(Comparator<T> comparator)
      Create an AvlTree<T> with a custom comparator and allowed duplicate values.
      Parameters:
      comparator - custom comparator

    • AvlTree

      public AvlTree(Comparator<T> comparator, boolean allowDuplicates)
      Create an AvlTree<T> with a custom comparator and flag for duplicate values.
      Parameters:
      comparator - custom comparator
      allowDuplicates - flag for duplicate values

  • Method Details

    • createComparable

      public static <T extends Comparable<T>> AvlTree<T> createComparable()
      Create an AvlTree<T> with natural order comparator in a type safe way.
      Type Parameters:
      T - comparable type

    • createComparable

      public static <T extends Comparable<T>> AvlTree<T> createComparable(boolean allowDuplicates)
      Create an AvlTree<T> with natural order comparator in a type safe way and flag for duplicate values.
      Type Parameters:
      T - comparable type
      Parameters:
      allowDuplicates - flag for duplicate values

    • isEmpty

      public boolean isEmpty()
      Description copied from interface: BinarySearchTree
      Returns true if tree has no elements.
      Specified by:
      isEmpty in interface BinarySearchTree<T>
      Returns:
      true if tree has no elements.

    • size

      public int size()
      Description copied from interface: BinarySearchTree
      Get the current number of elements in the tree.
      Specified by:
      size in interface BinarySearchTree<T>
      Returns:
      current number of elements

    • add

      public void add(T item)
      Description copied from interface: BinarySearchTree
      Adds an item to the tree.
      Specified by:
      add in interface BinarySearchTree<T>
      Parameters:
      item - to be added

    • remove

      public void remove(T item)
      Description copied from interface: BinarySearchTree
      Removes an item to from the tree.
      Specified by:
      remove in interface BinarySearchTree<T>
      Parameters:
      item - to be removed

    • contains

      public boolean contains(T item)
      Description copied from interface: BinarySearchTree
      Check if an item exists in the tree.
      Specified by:
      contains in interface BinarySearchTree<T>
      Parameters:
      item - to check
      Returns:
      true if item exists in the tree

    • containsCount

      public int containsCount(T item)
      Description copied from interface: BinarySearchTree
      Check how many items are equal to item there are in the tree.
      Specified by:
      containsCount in interface BinarySearchTree<T>
      Parameters:
      item - to check
      Returns:
      number of items equal to item

    • height

      public int height()
      Description copied from interface: BinarySearchTree
      Get the height of this tree.
      Specified by:
      height in interface BinarySearchTree<T>
      Returns:
      the current height of this tree

    • greater

      public T greater(T item)
      Description copied from interface: BinarySearchTree
      Get the first item greater than item.
      Specified by:
      greater in interface BinarySearchTree<T>
      Parameters:
      item - to check
      Returns:
      found greater item or null if no item is greater

    • lesser

      public T lesser(T item)
      Description copied from interface: BinarySearchTree
      Get the first item lesser than item.
      Specified by:
      lesser in interface BinarySearchTree<T>
      Parameters:
      item - to check
      Returns:
      found lesser item or null if no item is lesser

    • min

      public T min()
      Description copied from interface: BinarySearchTree
      Get the minimum item.
      Specified by:
      min in interface BinarySearchTree<T>
      Returns:
      minimum item

    • max

      public T max()
      Description copied from interface: BinarySearchTree
      Get the maximum item.
      Specified by:
      max in interface BinarySearchTree<T>
      Returns:
      maximum item

    • prettyString

      public String prettyString()
      Description copied from interface: BinarySearchTree
      Get a detailed representation of the structure of this tree.
      Specified by:
      prettyString in interface BinarySearchTree<T>
      Returns:
      detailed pretty string

    • stream

      public Stream<T> stream()
      Description copied from interface: BinarySearchTree
      Get a sequential stream over elements in this tree.
      Specified by:
      stream in interface BinarySearchTree<T>
      Returns:
      a sequential stream over elements in this tree

    • clear

      public void clear()
      Description copied from interface: BinarySearchTree
      Remove all elements from this tree.
      Specified by:
      clear in interface BinarySearchTree<T>

    • descendingIterator

      public Iterator<T> descendingIterator()
      Description copied from interface: BinarySearchTree
      Get an iterator over the elements in this tree, in descending order.
      Specified by:
      descendingIterator in interface BinarySearchTree<T>
      Returns:
      descending order iterator over the elements in this tree

    • iterator

      public Iterator<T> iterator()
      Specified by:
      iterator in interface Iterable<T>

    • toString

      public String toString()
      Overrides:
      toString in class Object