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

java.lang.Object
com.thomas.trees.BinarySearchTree<T>
com.thomas.trees.RedBlackTree<T>
Type Parameters:
T - The data type of the nodes of the Tree, must be comparable to support ordering
public class RedBlackTree<T extends Comparable<? super T>> extends BinarySearchTree<T>
A simple implentation of a Red Black Tree
See Also:

  • Field Details

    • NIL

      public final RedBlackNode<T extends Comparable<? super T>> NIL
      A Sentinel Null node
      Every null point points here instead

  • Constructor Details

    • RedBlackTree

      public RedBlackTree()
      Creates and empty Red-Black Tree

  • Method Details

    • root

      public RedBlackNode<T> root()
      Casts the root to a RedBlackNode
      Returns:
      The root as a RedBlackNode
      See Also:

    • isBlack

      public boolean isBlack(RedBlackNode<T> node)
      Returns true if the node is black
      Parameters:
      node - The node being checked
      Returns:
      Whether the node is black
      See Also:

    • isRed

      public boolean isRed(RedBlackNode<T> node)
      Returns true if the node is red
      Parameters:
      node - The node being checked
      Returns:
      Whether the node is black
      See Also:

    • setParent

      public void setParent(RedBlackNode<T> child, RedBlackNode<T> parent)
      Sets the parent of a child
      Guarding against setting the parent to NIL
      Parameters:
      child - The child node
      parent - The parent node
      See Also:

    • flipColours

      public void flipColours(RedBlackNode<T> node)
      Sets the node to RED and its children to BLACK
      Parameters:
      node - The node to flip
      See Also:

    • deleteMin

      public RedBlackNode<T> deleteMin(RedBlackNode<T> node)
      Deletes the minimun node from a subtree
      As this is a BST we assume that we can just go left to get the minimum value
      Parameters:
      node - the subtree
      Returns:
      The subtree with the minimum value deleted
      See Also:

    • moveRedLeft

      public RedBlackNode<T> moveRedLeft(RedBlackNode<T> node)
      Ensures the left child, or its left child is red before decending left during deletion
      Parameters:
      node - The node to fix
      Returns:
      The fixed node

    • moveRedRight

      public RedBlackNode<T> moveRedRight(RedBlackNode<T> node)
      Ensures the right child, or its left child is red before decending right during deletion
      Parameters:
      node - The node to fix
      Returns:
      The fixed node

    • fixAfterDelete

      public RedBlackNode<T> fixAfterDelete(RedBlackNode<T> node)
      Restores Red-Black properties on the way back up after a deletion This is not examined
      Parameters:
      node - The node to fix
      Returns:
      The fixed node

    • rotateLeft

      public RedBlackNode<T> rotateLeft(RedBlackNode<T> node)
      Rotates a node left
      Parameters:
      node - The node that needs to be rotated
      Returns:
      The new root of the subtree

    • rotateRight

      public RedBlackNode<T> rotateRight(RedBlackNode<T> node)
      Rotates a node right
      Parameters:
      node - The node that needs to be rotated
      Returns:
      The new root of the subtree

    • insert

      public void insert(T value)
      Inserts a value into the tree
      Overrides:
      insert in class BinarySearchTree<T extends Comparable<? super T>>
      Parameters:
      value - The data to be inserted
      See Also:

    • insert

      public RedBlackNode<T> insert(RedBlackNode<T> node, T value)
      Inserts a value into a subtree
      Also fixes Red-Black violations
      Parameters:
      node - The current node
      value - The data to be inserted
      Returns:
      A colour balanced subtree

    • delete

      public void delete(T value)
      Deletes a value from the tree This is not examined
      Overrides:
      delete in class BinarySearchTree<T extends Comparable<? super T>>
      Parameters:
      value - The value to be deleted
      See Also:

    • delete

      public RedBlackNode<T> delete(RedBlackNode<T> node, T value)
      Deletes a value from a subtree
      This is not examined
      Parameters:
      node - The curent node
      value - The value to be deleted
      Returns:
      A colour-balanced subtree