Package edu.claflin.finder.algo.clustering.struct

# Class BinarySearchTree<T extends TreeNodeInfo>

java.lang.Object
edu.claflin.finder.algo.clustering.struct.BinarySearchTree<T>

public class BinarySearchTree<T extends TreeNodeInfo> extends Object

- ## Field Summary

  Fields
  Modifier and Type
  Field
  Description
  `private boolean`
  `allow_duplicates`
  `private TreeNode<T>`
  `root`

- ## Constructor Summary

  Constructors
  Constructor
  Description
  `BinarySearchTree()`
  Create an empty BinarySearchTree.
  `BinarySearchTree(boolean dup)`

- ## Method Summary

  Modifier and Type
  Method
  Description
  `void`
  `add(T info)`
  Addd a new Tree Node with the given j index and q value
  `private void`
  `add(T info, TreeNode<T> p)`
  Recursive implementation of add.
  `boolean`
  `allows_duplicates()`
  `List<T>`
  `asList()`
  `private void`
  `asList(List<T> l, TreeNode<T> p)`
  `void`
  `clear()`
  `boolean`
  `contains(T info)`
  Is the specified ElemntType in the BinarySearchTree?
  `private boolean`
  `contains(T info, TreeNode<T> p)`
  `private void`
  `createBackbone()`
  Time complexity: O(n)
  `private void`
  `createPerfectBST()`
  Time complexity: O(n)
  `void`
  `DSW()`
  `T`
  `get(T info)`
  `private TreeNode<T>`
  `get(T info, TreeNode<T> p)`
  `int`
  `getHeight()`
  `private int`
  `getHeight(TreeNode<T> p)`
  `T`
  `getMax()`
  `T`
  `getMax(TreeNode<T> p)`
  `T`
  `getMin()`
  `private T`
  `getMin(TreeNode<T> p)`
  `Double`
  `getVal(T info)`
  `private int`
  `greatestPowerOf2LessThanN(int n)`
  .
  `boolean`
  `isEmpty()`
  Is the BinarySearchTree empty?
  `private void`
  `makeRotations(int bound)`
  `void`
  `mergeTrees(BinarySearchTree<T> that)`
  `private void`
  `mergeTrees(BinarySearchTree<T> that, TreeNode<T> p)`
  `int`
  `MSB(int n)`
  Return the index of most significant set bit: index of least significant bit is 0.
  `void`
  `remove(T info)`
  `private TreeNode<T>`
  `remove(T info, TreeNode<T> p)`
  `private void`
  `rotateLeft(TreeNode<T> grandParent, TreeNode<T> parent, TreeNode<T> rightChild)`
  `private TreeNode<T>`
  `rotateRight(TreeNode<T> grandParent, TreeNode<T> parent, TreeNode<T> leftChild)`
  `void`
  `set(T info)`
  `String`
  `toString()`
  Gets an inorder String representation of the BinarySearchTree.
  `private String`
  `toString(TreeNode<T> p)`
  Recursive implementation of inorder toString.

  ### Methods inherited from class java.lang.Object

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

- ## Field Details

  - ### root

    private TreeNode<T extends TreeNodeInfo> root

  - ### allow_duplicates

    private boolean allow_duplicates

- ## Constructor Details

  - ### BinarySearchTree

    public BinarySearchTree()
    Create an empty BinarySearchTree.

  - ### BinarySearchTree

    public BinarySearchTree(boolean dup)

- ## Method Details

  - ### allows_duplicates

    public boolean allows_duplicates()

  - ### isEmpty

    public boolean isEmpty()
    Is the BinarySearchTree empty?
    Returns:
      true if empty, false otherwise

  - ### clear

    public void clear()

  - ### add

    public void add(T info)
    Addd a new Tree Node with the given j index and q value
    Parameters:
      `info` - the key

  - ### add

    private void add(T info, TreeNode<T> p)
    Recursive implementation of add.
    Parameters:
      `info` - the key
      `p` - the current top Tree Node

  - ### getVal

    public Double getVal(T info)

  - ### get

    public T get(T info)

  - ### get

    private TreeNode<T> get(T info, TreeNode<T> p)

  - ### set

    public void set(T info)

  - ### contains

    public boolean contains(T info)
    Is the specified ElemntType in the BinarySearchTree?
    Parameters:
      `info` - the key
    Returns:
      true if it is contained, false otherwise

  - ### contains

    private boolean contains(T info, TreeNode<T> p)

  - ### toString

    public String toString()
    Gets an inorder String representation of the BinarySearchTree.
    Overrides:
      `toString` in class `Object`
    Returns:
      the BinarySearchTree as a String

  - ### toString

    private String toString(TreeNode<T> p)
    Recursive implementation of inorder toString.
    Parameters:
      `p` - the current TreeNode to print and recursive parameter
    Returns:
      the BinarySearchTree as a String

  - ### getMin

    public T getMin()

  - ### getMin

    private T getMin(TreeNode<T> p)

  - ### getMax

    public T getMax()

  - ### getMax

    public T getMax(TreeNode<T> p)

  - ### remove

    public void remove(T info)

  - ### remove

    private TreeNode<T> remove(T info, TreeNode<T> p)

  - ### getHeight

    public int getHeight()

  - ### getHeight

    private int getHeight(TreeNode<T> p)

  - ### DSW

    public void DSW()

  - ### createBackbone

    private void createBackbone()
    Time complexity: O(n)

  - ### rotateRight

    private TreeNode<T> rotateRight(TreeNode<T> grandParent, TreeNode<T> parent, TreeNode<T> leftChild)

  - ### createPerfectBST

    private void createPerfectBST()
    Time complexity: O(n)

  - ### greatestPowerOf2LessThanN

    private int greatestPowerOf2LessThanN(int n)
    . Time complexity: log(n)
    Parameters:
      `n` - the inout number
    Returns:
      the greatest power of 2 less than N

  - ### MSB

    public int MSB(int n)
    Return the index of most significant set bit: index of least significant bit is 0. Time complexity: log(n)
    Parameters:
      `n` - the input number
    Returns:
      the index of most significant set bit

  - ### makeRotations

    private void makeRotations(int bound)

  - ### rotateLeft

    private void rotateLeft(TreeNode<T> grandParent, TreeNode<T> parent, TreeNode<T> rightChild)

  - ### mergeTrees

    public void mergeTrees(BinarySearchTree<T> that)

  - ### mergeTrees

    private void mergeTrees(BinarySearchTree<T> that, TreeNode<T> p)

  - ### asList

    public List<T> asList()

  - ### asList

    private void asList(List<T> l, TreeNode<T> p)