treap s node treap is a binary tree by value and heap by priority 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 right tree s root will be current node now we splitwith the same value current node s left son left tree left part of that split right tree s left son right part of that split just symmetric to previous case we merge 2 trees into one note all left tree s values must be less than all right tree s left will be root because it has more priority now we need to merge left s right son and right tree symmetric as well insert element split current tree with a value into left right insert new node into the middle merge left node right into root erase element split all nodes with values less into left split all nodes with values greater into right merge left right just recursive print of a tree commands value to add value into treap value to erase all nodes with value root interacttreapnone 1 inorderroot 1 root interacttreaproot 3 5 17 19 2 16 4 0 inorderroot 0 1 2 3 4 5 16 17 19 root interacttreaproot 4 4 4 inorderroot 0 1 2 3 4 4 4 4 5 16 17 19 root interacttreaproot 0 inorderroot 1 2 3 4 4 4 4 5 16 17 19 root interacttreaproot 4 inorderroot 1 2 3 5 16 17 19 root interacttreaproot 0 unknown command after each command program prints treap root none print enter numbers to create a tree value to add value into treap value to erase all nodes with value q to quit args input while args q root interacttreaproot args printroot args input printgood by if name main import doctest doctest testmod main treap s node treap is a binary tree by value and heap by priority 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 none tree is split into 2 nones right tree s root will be current node now we split with the same value current node s left son left tree left part of that split right tree s left son right part of that split just symmetric to previous case we merge 2 trees into one note all left tree s values must be less than all right tree s if one node is none return the other left will be root because it has more priority now we need to merge left s right son and right tree symmetric as well insert element split current tree with a value into left right insert new node into the middle merge left node right into root erase element split all nodes with values less into left split all nodes with values greater into right merge left right just recursive print of a tree 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 after each command program prints treap
from __future__ import annotations

from random import random


class Node:
    

    def __init__(self, value: int | None = None):
        self.value = value
        self.prior = random()
        self.left: Node | None = None
        self.right: Node | None = None

    def __repr__(self) -> str:
        from pprint import pformat

        if self.left is None and self.right is None:
            return f"'{self.value}: {self.prior:.5}'"
        else:
            return pformat(
                {f"{self.value}: {self.prior:.5}": (self.left, self.right)}, indent=1
            )

    def __str__(self) -> str:
        value = str(self.value) + " "
        left = str(self.left or "")
        right = str(self.right or "")
        return value + left + right


def split(root: Node | None, value: int) -> tuple[Node | None, Node | None]:
    
    if root is None:  
        return None, None
    elif root.value is None:
        return None, None
    else:
        if value < root.value:
            
            left, root.left = split(root.left, value)
            return left, root
        else:
            
            root.right, right = split(root.right, value)
            return root, right


def merge(left: Node | None, right: Node | None) -> Node | None:
    
    if (not left) or (not right):  
        return left or right
    elif left.prior < right.prior:
        
        left.right = merge(left.right, right)
        return left
    else:
        
        right.left = merge(left, right.left)
        return right


def insert(root: Node | None, value: int) -> Node | None:
    
    node = Node(value)
    left, right = split(root, value)
    return merge(merge(left, node), right)


def erase(root: Node | None, value: int) -> Node | None:
    
    left, right = split(root, value - 1)
    _, right = split(right, value)
    return merge(left, right)


def inorder(root: Node | None) -> None:
    
    if not root:  
        return
    else:
        inorder(root.left)
        print(root.value, end=",")
        inorder(root.right)


def interact_treap(root: Node | None, args: str) -> Node | None:
    
    for arg in args.split():
        if arg[0] == "+":
            root = insert(root, int(arg[1:]))

        elif arg[0] == "-":
            root = erase(root, int(arg[1:]))

        else:
            print("Unknown command")

    return root


def main() -> None:
    
    root = None
    print(
        "enter numbers to create a tree, + value to add value into treap, "
        "- value to erase all nodes with value. 'q' to quit. "
    )

    args = input()
    while args != "q":
        root = interact_treap(root, args)
        print(root)
        args = input()

    print("good by!")


if __name__ == "__main__":
    import doctest

    doctest.testmod()
    main()