BST

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

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)[source]

Add a key, data pair.

find(key)[source]

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)[source]

Find the node associated with the given key.

is_valid()[source]

Returns whether this is a valid BST.

items()[source]

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

range(lower, upper, bounds=(True, True))[source]

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))[source]

Return nodes in the given range.

remove(key, data=None)[source]

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)[source]

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)[source]

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

shift_left(row)[source]

Decrement all rows larger than the given row.

shift_right(row)[source]

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

sort()[source]

Make row order align with key order.

sorted_data()[source]

Return BST rows sorted by key values.

traverse(order='inorder')[source]

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