Skip to main content
`Ctrl`+`K`

# BST

class astropy.table.BST(data, row_index, unique=False)

  Bases: `object`

  A basic binary search tree in pure Python, used as an engine for indexing.

  Parameters:
    data `Table`

      Sorted columns of the original table

    row_index `Column` `object`

      Row numbers corresponding to data columns

    unique bool

      Whether the values of the index must be unique. Defaults to False.

  Attributes Summary

  `height` | Return the BST height.

  Methods Summary

  `add`(key[, data]) | Add a key, data pair.
  `find`(key) | Return all data values corresponding to a given key.
  `find_node`(key) | Find the node associated with the given key.
  `is_valid`() | Returns whether this is a valid BST.
  `items`() | Return BST items in order as (key, data) pairs.
  `range`(lower, upper[, bounds]) | Return all nodes with keys in the given range.
  `range_nodes`(lower, upper[, bounds]) | Return nodes in the given range.
  `remove`(key[, data]) | Remove data corresponding to the given key.
  `replace_rows`(row_map) | Replace all rows with the values they map to in the given dictionary.
  `same_prefix`(val) | Assuming the given value has smaller length than keys, return nodes whose keys have this value as a prefix.
  `shift_left`(row) | Decrement all rows larger than the given row.
  `shift_right`(row) | Increment all rows greater than or equal to the given row.
  `sort`() | Make row order align with key order.
  `sorted_data`() | Return BST rows sorted by key values.
  `traverse`([order]) | Return nodes of the BST in the given order.

  Attributes Documentation

  height

    Return the BST height.

  Methods Documentation

  add(key, data=None)

    Add a key, data pair.

  find(key)

    Return all data values corresponding to a given key.

    Parameters:
      key `python:tuple`

        Input key

    Returns:
      data_vals `python:list`

        List of rows corresponding to the input key

  find_node(key)

    Find the node associated with the given key.

  is_valid()

    Returns whether this is a valid BST.

  items()

    Return BST items in order as (key, data) pairs.

  range(lower, upper, bounds=(True, True))

    Return all nodes with keys in the given range.

    Parameters:
      lower `python:tuple`

        Lower bound

      upper `python:tuple`

        Upper bound

      bounds(2,) `python:tuple` of bool

        Indicates whether the search should be inclusive or exclusive with respect to the endpoints. The first argument corresponds to an inclusive lower bound, and the second argument to an inclusive upper bound.

  range_nodes(lower, upper, bounds=(True, True))

    Return nodes in the given range.

  remove(key, data=None)

    Remove data corresponding to the given key.

    Parameters:
      key `python:tuple`

        The key to remove

      data `python:int` or `python:None`

        If None, remove the node corresponding to the given key. If not None, remove only the given data value from the node.

    Returns:
      successful bool

        True if removal was successful, false otherwise

  replace_rows(row_map)

    Replace all rows with the values they map to in the given dictionary. Any rows not present as keys in the dictionary will have their nodes deleted.

    Parameters:
      row_map `python:dict`

        Mapping of row numbers to new row numbers

  same_prefix(val)

    Assuming the given value has smaller length than keys, return nodes whose keys have this value as a prefix.

  shift_left(row)

    Decrement all rows larger than the given row.

  shift_right(row)

    Increment all rows greater than or equal to the given row.

  sort()

    Make row order align with key order.

  sorted_data()

    Return BST rows sorted by key values.

  traverse(order='inorder')

    Return nodes of the BST in the given order.

    Parameters:
      order `python:str`

        The order in which to recursively search the BST. Possible values are: “preorder”: current node, left subtree, right subtree “inorder”: left subtree, current node, right subtree “postorder”: left subtree, right subtree, current node