设计 AVL 树的类

由于 AVL 树是二叉搜索树，因此 AVLTree 被设计为 BST 的子类。 AVL 树是二叉树，因此您可以定义 AVLTree 类来扩展 BST 类，如下图所示。 BST和TreeNode类在Section.

为了平衡树，你需要知道每个节点的高度。为了方便起见，将每个节点的高度存储在AVLTreeNode中，并将AVLTreeNode定义为BST.TreeNode的子类。请注意，TreeNode 在BST 中被定义为静态内部类。 AVLTreeNode 将被定义为AVLTree 中的静态内部类。 TreeNode 包含数据字段element、left 和 right，它们由AVLTreeNode继承。因此，AVLTreeNode包含四个数据字段，如下图所示。

在 BST 类中，createNewNode() 方法创建一个 TreeNode 对象。此方法在 AVLTree 类中被重写，以创建 AVLTreeNode。注意，BST类中的createNewNode()方法的返回类型是TreeNode，但AVLTree类中的createNewNode()方法的返回类型是AVLTreeNode。这很好，因为AVLTreeNode是TreeNode的子类。

在 AVLTree 中搜索元素与在常规二叉树中搜索相同，因此 BST 类中定义的 search 方法也适用于 AVLTree.

重写insert和delete方法来插入和删除元素，并在必要时执行重新平衡操作以确保树平衡。