data_structures.binary_tree.treap

Classes

Node	Treap's node

Functions

erase(→ Node | None)	Erase element
inorder(→ None)	Just recursive print of a tree
insert(→ Node | None)	Insert element
interact_treap(→ Node | None)	Commands:
main(→ None)	After each command, program prints treap
merge(→ Node | None)	We merge 2 trees into one.
split(→ tuple[Node | None, Node | None])	We split current tree into 2 trees with value:

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

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