mate.build.tob_chess_utils.range_avl_tree module

class mate.build.tob_chess_utils.range_avl_tree.RangeAVL

Bases: object

AVL binary search tree that uses non-overlapping integer ranges in Nodes.

Return type

None

find(val: int) → Optional[mate.build.tob_chess_utils.range_avl_tree.RangeAVLNode]

Returns the label associated with the range that val falls in, or None.

Parameters

val (int) –

Return type

Optional[mate.build.tob_chess_utils.range_avl_tree.RangeAVLNode]

find_min() → Optional[mate.build.tob_chess_utils.range_avl_tree.RangeAVLNode]

Return type

Optional[mate.build.tob_chess_utils.range_avl_tree.RangeAVLNode]

insert(range_lower: int, range_upper: int, label: Optional[str]) → None

Inserts a node with key k into the subtree rooted at this node. This AVL version guarantees the balance property: h = O(lg n).

Args:

range_lower: The lower bound of the node to be inserted. range_upper: The upper bound (exclusive) of the node to be inserted. label: A label to assign the range, otherwise f”range({range_lower}, {range_upper})”

Parameters

• range_lower (int) –

• range_upper (int) –

• label (Optional[str]) –

Return type

None

left_rotate(x: mate.build.tob_chess_utils.range_avl_tree.RangeAVLNode) → None

Parameters

x (mate.build.tob_chess_utils.range_avl_tree.RangeAVLNode) –

Return type

None

next_larger(k: int) → Optional[mate.build.tob_chess_utils.range_avl_tree.RangeAVLNode]

Parameters

k (int) –

Return type

Optional[mate.build.tob_chess_utils.range_avl_tree.RangeAVLNode]

rebalance(node: Optional[mate.build.tob_chess_utils.range_avl_tree.RangeAVLNode]) → None

Parameters

node (Optional[mate.build.tob_chess_utils.range_avl_tree.RangeAVLNode]) –

Return type

None

right_rotate(x: mate.build.tob_chess_utils.range_avl_tree.RangeAVLNode) → None

Parameters

x (mate.build.tob_chess_utils.range_avl_tree.RangeAVLNode) –

Return type

None

class mate.build.tob_chess_utils.range_avl_tree.RangeAVLNode(parent: Optional[mate.build.tob_chess_utils.range_avl_tree.RangeAVLNode], lower: int, upper: int, label: Optional[str])

Bases: object

A node in the RangeAVL tree.

Parameters

• parent (Optional[RangeAVLNode]) –

• lower (int) –

• upper (int) –

• label (Optional[str]) –

Return type

None

find(val: int) → Optional[mate.build.tob_chess_utils.range_avl_tree.RangeAVLNode]

Given a value val, return the label associated with the range in which it fits.

If no range exists that contains val, return None

Parameters

val (int) –

Return type

Optional[mate.build.tob_chess_utils.range_avl_tree.RangeAVLNode]

find_min() → Optional[mate.build.tob_chess_utils.range_avl_tree.RangeAVLNode]

Return type

Optional[mate.build.tob_chess_utils.range_avl_tree.RangeAVLNode]

height: int = -1

insert(node: mate.build.tob_chess_utils.range_avl_tree.RangeAVLNode) → None

Insertion node cannot overlap ranges of existing RangeAVLNodes.

Parameters

node (mate.build.tob_chess_utils.range_avl_tree.RangeAVLNode) –

Return type

None

next_larger() → Optional[mate.build.tob_chess_utils.range_avl_tree.RangeAVLNode]

Return type

Optional[mate.build.tob_chess_utils.range_avl_tree.RangeAVLNode]

mate.build.tob_chess_utils.range_avl_tree.height(node: Optional[mate.build.tob_chess_utils.range_avl_tree.RangeAVLNode]) → int

Parameters

node (Optional[mate.build.tob_chess_utils.range_avl_tree.RangeAVLNode]) –

Return type

int

mate.build.tob_chess_utils.range_avl_tree.inorder(node: Optional[mate.build.tob_chess_utils.range_avl_tree.RangeAVLNode]) → List[mate.build.tob_chess_utils.range_avl_tree.RangeAVLNode]

Parameters

node (Optional[mate.build.tob_chess_utils.range_avl_tree.RangeAVLNode]) –

Return type

List[mate.build.tob_chess_utils.range_avl_tree.RangeAVLNode]

mate.build.tob_chess_utils.range_avl_tree.update_height(node: mate.build.tob_chess_utils.range_avl_tree.RangeAVLNode) → None

Parameters

node (mate.build.tob_chess_utils.range_avl_tree.RangeAVLNode) –

Return type

None