设计 AVL 树的类

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

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

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

在

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

重写

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

以上是设计 AVL 树的类的详细内容。更多信息请关注PHP中文网其他相关文章！