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
(root: Node | None, value: int)
| 33 | |
| 34 | |
| 35 | def split(root: Node | None, value: int) -> tuple[Node | None, Node | None]: |
| 36 | """ |
| 37 | We split current tree into 2 trees with value: |
| 38 | |
| 39 | Left tree contains all values less than split value. |
| 40 | Right tree contains all values greater or equal, than split value |
| 41 | """ |
| 42 | if root is None or root.value is None: # None tree is split into 2 Nones |
| 43 | return None, None |
| 44 | elif value < root.value: |
| 45 | """ |
| 46 | Right tree's root will be current node. |
| 47 | Now we split(with the same value) current node's left son |
| 48 | Left tree: left part of that split |
| 49 | Right tree's left son: right part of that split |
| 50 | """ |
| 51 | left, root.left = split(root.left, value) |
| 52 | return left, root |
| 53 | else: |
| 54 | """ |
| 55 | Just symmetric to previous case |
| 56 | """ |
| 57 | root.right, right = split(root.right, value) |
| 58 | return root, right |
| 59 | |
| 60 | |
| 61 | def merge(left: Node | None, right: Node | None) -> Node | None: |