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

Whether the values of the index must be unique

Attributes Summary

height

Return the BST height.

Methods Summary

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

Attributes Documentation

height

Return the BST height.

Methods Documentation

add(self, key, data=None)

Add a key, data pair.

find(self, 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(self, key)

Find the node associated with the given key.

is_valid(self)

Returns whether this is a valid BST.

items(self)

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

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

Return all nodes with keys in the given range.

Parameters

lowertuple

Lower bound

uppertuple

Upper bound

boundstuple (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(self, lower, upper, bounds=True, True)

Return nodes in the given range.

remove(self, 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(self, 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(self, val)

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

shift_left(self, row)

Decrement all rows larger than the given row.

shift_right(self, row)

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

sort(self)

Make row order align with key order.

sorted_data(self)

Return BST rows sorted by key values.

traverse(self, 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