Treap's node Treap is a binary tree by value and heap by priority
| 4 | |
| 5 | |
| 6 | class Node: |
| 7 | """ |
| 8 | Treap's node |
| 9 | Treap is a binary tree by value and heap by priority |
| 10 | """ |
| 11 | |
| 12 | def __init__(self, value: int | None = None): |
| 13 | self.value = value |
| 14 | self.prior = random() |
| 15 | self.left: Node | None = None |
| 16 | self.right: Node | None = None |
| 17 | |
| 18 | def __repr__(self) -> str: |
| 19 | from pprint import pformat |
| 20 | |
| 21 | if self.left is None and self.right is None: |
| 22 | return f"'{self.value}: {self.prior:.5}'" |
| 23 | else: |
| 24 | return pformat( |
| 25 | {f"{self.value}: {self.prior:.5}": (self.left, self.right)}, indent=1 |
| 26 | ) |
| 27 | |
| 28 | def __str__(self) -> str: |
| 29 | value = str(self.value) + " " |
| 30 | left = str(self.left or "") |
| 31 | right = str(self.right or "") |
| 32 | return value + left + right |
| 33 | |
| 34 | |
| 35 | def split(root: Node | None, value: int) -> tuple[Node | None, Node | None]: |