Available Implementations

AVL Tree

This action space organizes the intervals as an AVL tree. More information on the data structure can be found here.

class interval_spaces.tree_space.Node(x: Optional[float] = None, y: Optional[float] = None, left: Optional[object] = None, right: Optional[object] = None, height: int = 1)[source]

Bases: object

Node in the AVL tree which represents a valid interval

class interval_spaces.tree_space.TreeSpace(x: float, y: float)[source]

Bases: IntervalSpace

Interval Action Space as AVL tree

contains(x, root: object = 'root')[source]

Determines if a number is part of the action space

Parameters

  • x – Number

  • root – Node to start the search from or ‘root’ for searching the whole tree, default is ‘root’

Returns

Boolean indicating if it is part of the action space

draw = None
first_interval_after_or_within(x, root: Node = 'root')[source]

Returns the first interval after or within a number

Parameters

  • x – Number

  • root – Node to start the search from or ‘root’ for searching the whole tree, default is ‘root’

Returns

Tuple containing the lower and upper boundaries of the interval and a variable indicating if the number lies in the interval. For example:

(root.x, root.y), True

getBal(root: Node = 'root')[source]

Calculates balance factor

Parameters

  • root – Node to calculate the balance factor for or ‘root’ for the balance factor of the whole tree,

  • 'root' (default is) –

Returns

Integer indicating the balance factor

getHeight(root: Node = 'root')[source]

Returns the height of a Node

Parameters

root – Node to return the height from or ‘root’ for the height of the whole tree, default is ‘root’

Returns

Integer indicating the height

insert(x, y, root: Node = 'root')[source]

Adds an interval to the action space

Parameters

  • x – Lower bound of the interval

  • y – Upper bound of the interval

  • root – Node to start the insertion from or ‘root’ for inserting over the whole tree, default is ‘root’

Returns

Updated root node of the action space

lRotate(z: Node)[source]

Performs a left rotation. Switches roles of parent and child nodes.

Parameters

z (Node) – Parent node for the rotation

Returns

Updated parent Node

last_interval_before_or_within(x, root: Node = 'root')[source]

Returns the last interval before or within a number

Parameters

  • x – Number

  • root – Node to start the search from or ‘root’ for searching the whole tree, default is ‘root’

Returns

Tuple containing the lower and upper boundaries of the interval and a variable indicating if the number lies in the interval. For example:

(root.x, root.y), True

nearest_element(x, root: Node = 'root')[source]

Finds nearest action for a number in the action space. Larger actions preferred.

Parameters

  • x – Number

  • root – Node to start the search from or ‘root’ for searching the whole tree, default is ‘root’

Returns

Nearest element in the action space. It is the number itself if it is valid.

nearest_elements(x, root: Node = 'root')[source]

Finds nearest actions for a number in the action space

Parameters

  • x – Number

  • root – Node to start the search from or ‘root’ for searching the whole tree, default is ‘root’

Returns

Nearest elements in the action space. It is the number itself if it is valid.

order(root: Node = 'root')[source]

Returns all intervals of the action space ordered

Parameters

root – Node to start the search from or ‘root’ for searching the whole tree, default is ‘root’

Returns

[(0.1,0.5), (0.7,0.9)]

Return type

List of tuples containing the ordered intervals. For example

rRotate(z: Node)[source]

Performs a right rotation. Switches roles of parent and child nodes.

Parameters

z (Node) – Parent node for the rotation

Returns

Updated parent Node

remove(x, y, root: Node = 'root', adjust_size: bool = True)[source]

Removes an interval from the action space

Parameters

  • x – Lower bound of the interval

  • y – Upper bound of the interval

  • root – Node to start the removal from or ‘root’ for removing over the whole tree, default is ‘root’

Returns

Updated root node of the action space

root_tree = None
sample(root: Node = 'root') → float[source]

Sample a random action from a uniform distribution over the action space

Parameters

root – Root node of the action space, default is ‘root’

Returns

Sampled action as a float

size: Decimal = 0
smallest_interval(root: Node = 'root')[source]

Returns the Node of the smallest interval

Parameters

root – Node to start the search from or ‘root’ for searching the whole tree, default is ‘root’

Returns

Node of the smallest interval