Network of binary search trees with inheritance and polymorphism

Python Hard classes

Task «Network of binary search trees with inheritance and polymorphism»

Implement the `Node` class for a binary search tree (BST) node with `insert`, `search`, and `delete` methods. Create the `BST` class, which stores the root and contains the methods `insert` (adding a value), `search` (searching for a value, returns `True`/`False`), `delete` (removing a value), and `get_height` (tree height). Then create the `AVLTree` class, inheriting from `BST`, overriding `insert` and `delete` to support balancing (with rotations). Input data: a sequence of commands. Commands: `"insert x"` — add x, `"delete x"` — remove x (if present), `"search x"` — output `"found"` or `"not found"`, `"height"` — output the tree height. For `AVLTree`, after each insertion/deletion, the balance is checked (difference in subtree heights <= 1) and the corresponding rotation is performed. Constraints: -10^9 <= x <= 10^9, number of commands up to 10^5.

Input Format

First line: a single integer n (1 <= n <= 10^5) — the number of commands. Then n lines, each containing a command: insert x, delete x, search x, or height.

Output Format

For each `search` command, output "found" or "not found" on a separate line. For the `height` command, output a single integer — the height of the tree (height of an empty tree = 0).

Examples

Example 1

INPUT

OUTPUT

Example 2

INPUT

2
0 0 0
2 -2 2 -2

OUTPUT

main.py