Classes¶

Functions¶

Module Contents¶

class data_structures.binary_tree.treap.Node(value: int | None = None)¶

Treap’s node Treap is a binary tree by value and heap by priority

__repr__() → str¶

__str__() → str¶

left: Node | None = None¶

prior¶

right: Node | None = None¶

value = None¶

data_structures.binary_tree.treap.erase(root: Node | None, value: int) → Node | None¶

Erase element

Split all nodes with values less into left, Split all nodes with values greater into right. Merge left, right

data_structures.binary_tree.treap.inorder(root: Node | None) → None¶

Just recursive print of a tree

data_structures.binary_tree.treap.insert(root: Node | None, value: int) → Node | None¶

Insert element

Split current tree with a value into left, right, Insert new node into the middle Merge left, node, right into root

data_structures.binary_tree.treap.interact_treap(root: Node | None, args: str) → Node | None¶

Commands: + value to add value into treap - value to erase all nodes with value

>>> root = interact_treap(None, "+1")
>>> inorder(root)
1,
>>> root = interact_treap(root, "+3 +5 +17 +19 +2 +16 +4 +0")
>>> inorder(root)
0,1,2,3,4,5,16,17,19,
>>> root = interact_treap(root, "+4 +4 +4")
>>> inorder(root)
0,1,2,3,4,4,4,4,5,16,17,19,
>>> root = interact_treap(root, "-0")
>>> inorder(root)
1,2,3,4,4,4,4,5,16,17,19,
>>> root = interact_treap(root, "-4")
>>> inorder(root)
1,2,3,5,16,17,19,
>>> root = interact_treap(root, "=0")
Unknown command

data_structures.binary_tree.treap.main() → None¶

After each command, program prints treap

data_structures.binary_tree.treap.merge(left: Node | None, right: Node | None) → Node | None¶

We merge 2 trees into one. Note: all left tree’s values must be less than all right tree’s

data_structures.binary_tree.treap.split(root: Node | None, value: int) → tuple[Node | None, Node | None]¶

We split current tree into 2 trees with value:

Left tree contains all values less than split value. Right tree contains all values greater or equal, than split value