具有继承和多态性的二叉搜索树网络

Python Hard classes

任务 «具有继承和多态性的二叉搜索树网络»

实现二叉搜索树（BST）的节点类 Node，包含方法 insert、search、delete。创建 BST 类，该类存储根节点并包含方法 insert（添加值）、search（搜索值，返回 True/False）、delete（删除值）和 get_height（树的高度）。然后创建 AVLTree 类，继承自 BST，重写 insert 和 delete 方法以支持平衡（通过旋转）。输入数据：一系列命令。命令包括："insert x" 添加 x，"delete x" 删除 x（如果存在），"search x" 输出 "found" 或 "not found"，"height" 输出树的高度。对于 AVLTree，每次插入/删除后检查平衡（子树高度差 <= 1）并执行相应的旋转。限制条件：-10^9 <= x <= 10^9，命令数量最多 10^5 条。

输入格式

第一行：一个整数 n（1 <= n <= 10^5）——命令的数量。接下来 n 行，每行包含一条命令：insert x、delete x、search x 或 height。

输出格式

对于每个 search 命令，在单独一行中输出 "found" 或 "not found"。对于 height 命令，输出一个整数——树的高度（空树的高度 = 0）。

示例

示例 1

输入

输出

示例 2

输入

2
0 0 0
2 -2 2 -2

输出

main.py