astro py:docs

- Index
- Modules

### Navigation

- next »
- « previous |
- Astropy v1.1.1 »
- Data Tables (`astropy.table`) »
- BST

# 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 (defaults to False)

  > Whether the values of the index must be unique

  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 : tuple

    > Input key

    Returns:

    data_vals : 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 : tuple

    > Lower bound

    upper : tuple

    > Upper bound

    bounds : tuple (x, y) of bools

    > Indicates whether the search should be inclusive or exclusive with respect to the endpoints. The first argument x corresponds to an inclusive lower bound, and the second argument y 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 : tuple

    > The key to remove

    data : int or 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 : 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=u'inorder')

    Return nodes of the BST in the given order.

    Parameters:

    order : 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