Class BinarySearchTree<T extends Comparable<? super T>>

java.lang.Object
com.thomas.trees.BinarySearchTree<T>
Type Parameters:
T - The type of the Node
Direct Known Subclasses:
AVLTree
public class BinarySearchTree<T extends Comparable<? super T>> extends Object
A simple implentation of a Binaray Search Tree
See Also:

  • Constructor Details

    • BinarySearchTree

      public BinarySearchTree()
      Initializes an empty Binary Search Tree

    • BinarySearchTree

      public BinarySearchTree(BTNode<T> node)
      Initializes a Binary search tree with a root node
      Parameters:
      node - The root node
      See Also:

  • Method Details

    • getRoot

      public BTNode<T> getRoot()
      Gets the root of the Binary Search Tree
      Returns:
      The root node
      See Also:

    • setRoot

      public void setRoot(BTNode<T> value)
      Sets the root of the tree
      Parameters:
      value - The new root of the tree

    • getHeight

      public int getHeight()
      Gets the height of the Binary Search Tree
      Returns:
      The height of the tree
      See Also:

    • recursiveHeight

      public int recursiveHeight(BTNode<T> node)
      Recursively gets the height of the tree
      Parameters:
      node - The current node that is beeing travered
      Returns:
      The hight of the current subtree

    • getSize

      public int getSize()
      Gets the size of the tree
      Returns:
      The size of the tree
      See Also:

    • recursiveSize

      public int recursiveSize(BTNode<T> node)
      Recursively gets the size of a node
      Parameters:
      node - The current node beeing traversed
      Returns:
      The size of the node

    • find

      public BTNode<T> find(T search)
      Searches the tree for a value
      Parameters:
      search - The search value
      Returns:
      A BTNode with that value or null
      See Also:

    • find

      public BTNode<T> find(BTNode<T> node, T search)
      Searches a node for a value
      Parameters:
      node - The current node being searached
      search - The searach value
      Returns:
      A BTNode with the value or null
      See Also:

    • insert

      public void insert(T value)
      Inserts a node into the tree
      Parameters:
      value - The data to be inserted
      See Also:

    • insert

      public void insert(BTNode<T> node, T value)
      Inserts a value into a subtree
      Parameters:
      node - The current node
      value - The value to be inserted

    • delete

      public void delete(T value)
      Deletes a value from the tree
      Parameters:
      value - the key to be deleted
      See Also:

    • delete

      public BTNode<T> delete(BTNode<T> node, T value)
      Deletes a value from a sub Tree
      Parameters:
      node - The current node
      value - The value to be deleted
      Returns:
      A new root for the sub tree

    • findMin

      public BTNode<T> findMin(BTNode<T> node)
      Gets the minimun node of a subtree
      Parameters:
      node - The node beeing inspected
      Returns:
      The smalled node

    • removeMin

      public BTNode<T> removeMin(BTNode<T> node)
      Deletes the minimun node from a subtree
      Parameters:
      node - The subtree beeing inspected
      Returns:
      The a new subtree root

    • pre_order

      public void pre_order(Consumer<T> action)
      Uses pre-order traversal on the tree
      Parameters:
      action - The visitor operation
      See Also:

    • pre_order

      public void pre_order(BTNode<T> node, Consumer<T> action)
      Uses pre-order traversal on a Node
      Parameters:
      node - The current node
      action - The visitor Operation

    • in_order

      public void in_order(Consumer<T> action)
      Uses in-order traversal on the tree
      Parameters:
      action - The visitor operation
      See Also:

    • in_order

      public void in_order(BTNode<T> node, Consumer<T> action)
      Uses in-order traversal on a Node
      Parameters:
      node - The current Node
      action - The visitor Operation

    • post_order

      public void post_order(Consumer<T> action)
      Uses post-order traversal on the tree
      Parameters:
      action - The visitor operation
      See Also:

    • post_order

      public void post_order(BTNode<T> node, Consumer<T> action)
      Uses post-order traversal on a Node
      Parameters:
      node - The current Node
      action - The visitor Operation

    • level_order

      public void level_order(Consumer<T> action)
      Uses level-order traversal on the tree
      Parameters:
      action - The visitor Operation
      See Also:

    • level_order

      public void level_order(BTNode<T> node, Consumer<T> action)
      Uses level-order traversal on a Node
      Parameters:
      node - The current Node
      action - The visitor Operation