Package dsa.lab07.solutions

Class BinarySearchTree.Node<Key extends Comparable<Key>,Value>

java.lang.Object
dsa.lab07.solutions.BinarySearchTree.Node<Key,Value>
Type Parameters:
Key - the key type
Value - the value type
Enclosing class:
BinarySearchTree<Key extends Comparable<Key>,Value>
protected static class BinarySearchTree.Node<Key extends Comparable<Key>,Value> extends Object
A node in a binary search tree.

  • Field Details

  • Constructor Details

  • Method Details

    • findNode

      public BinarySearchTree.Node<Key,Value> findNode(Key key) throws NoSuchElementException
      Find the node containing the item with the given key within this subtree.
      Parameters:
      key - the key
      Returns:
      the node
      Throws:
      NoSuchElementException - if no node has key key

    • insert

      public BinarySearchTree.Node<Key,Value> insert(MapItem<Key,Value> item)
      Insert the given item within this subtree.

      If there's already an item with the same key, that item is replaced with this one, and that node is returned.

      If instead there isn't already an item with the same key, a new node is inserted and returned.

      Parameters:
      item - the item
      Returns:
      the node containing the item, once inserted

    • remove

      public BinarySearchTree.Node<Key,Value> remove()
      Remove the item that this node contains from the tree, and return the node removed.

      The removed node is only this node if this is a leaf.

      If this node isn't a leaf, find a suitable leaf node (if this has a left subtree, then its maximum node, otherwise the right subtree's minimum), copy its item into this node, and remove and return that node.

      Returns:
      the removed node

    • previous

      public MapItem<Key,Value> previous(Key key)
      Get the item within this subtree that would be the predecessor of one with the given key.

      There may or may not be an item with the given key.

      Parameters:
      key - a key
      Returns:
      the previous item (by key), or null if there is none

    • next

      public MapItem<Key,Value> next(Key key)
      Get the item within this subtree that would be the successor of one with the given key.

      There may or may not be an item with the given key.

      Parameters:
      key - a key
      Returns:
      the next item (by key), or null if there is none

    • minNode

      public BinarySearchTree.Node<Key,Value> minNode()
      Get the node in this subtree with the least key.
      Returns:
      the minimum node (the leftmost descendant)

    • maxNode

      public BinarySearchTree.Node<Key,Value> maxNode()
      Get the node in this subtree with the greatest key.
      Returns:
      the maximum node (the rightmost descendant)

    • min

      public MapItem<Key,Value> min()
      Get the item in this subtree with the least key.
      Returns:
      the minimum item (by key)

    • max

      public MapItem<Key,Value> max()
      Get the item in this subtree with the greatest key.
      Returns:
      the maximum item (by key)