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:

dataTable

Sorted columns of the original table

row_indexColumn object

Row numbers corresponding to data columns

uniquebool

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:

keytuple

Input key

Returns:

data_valslist

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:

lowertuple, None

Lower bound (no lower bound if None)

uppertuple, None

Upper bound (no upper bound if None)

bounds(2,) 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:

keytuple

The key to remove

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

successfulbool

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_mapdict

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:

orderstr

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