BST¶
-
class
astropy.table.
BST
(data, row_index, unique=False)[source] [edit on github]¶ 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] [edit on github]¶ Add a key, data pair.
-
find
(key)[source] [edit on github]¶ 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] [edit on github]¶ Find the node associated with the given key.
-
is_valid
()[source] [edit on github]¶ Returns whether this is a valid BST.
-
items
()[source] [edit on github]¶ Return BST items in order as (key, data) pairs.
-
range
(lower, upper, bounds=(True, True))[source] [edit on github]¶ 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] [edit on github]¶ Return nodes in the given range.
-
remove
(key, data=None)[source] [edit on github]¶ 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] [edit on github]¶ 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] [edit on github]¶ Assuming the given value has smaller length than keys, return nodes whose keys have this value as a prefix.
-
shift_left
(row)[source] [edit on github]¶ Decrement all rows larger than the given row.
-
shift_right
(row)[source] [edit on github]¶ Increment all rows greater than or equal to the given row.
-
sort
()[source] [edit on github]¶ Make row order align with key order.
-
sorted_data
()[source] [edit on github]¶ Return BST rows sorted by key values.
-
traverse
(order='inorder')[source] [edit on github]¶ 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