Since an AVL tree is a binary search tree, AVLTree is designed as a subclass of BST. An AVL tree is a binary tree, so you can define the AVLTree class to extend the BST class, as shown in Figure below. The BST and TreeNode classes were defined in Section.

In order to balance the tree, you need to know each node’s height. For convenience, store the height of each node in AVLTreeNode and define AVLTreeNode to be a subclass of BST.TreeNode. Note that TreeNode is defined as a static inner class in BST. AVLTreeNode will be defined as a static inner class in AVLTree. TreeNode contains the data fields element, left, and right, which are inherited by AVLTreeNode. Thus, AVLTreeNode contains four data fields, as shown in Figure below.

In the BST class, the createNewNode() method creates a TreeNode object. This method is overridden in the AVLTree class to create an AVLTreeNode. Note that the return type of the createNewNode() method in the BST class is TreeNode, but the return type of the createNewNode() method in the AVLTree class is AVLTreeNode. This is fine, since AVLTreeNode is a subclass of TreeNode.

Searching for an element in an AVLTree is the same as searching in a regular binary tree, so the search method defined in the BST class also works for AVLTree.

The insert and delete methods are overridden to insert and delete an element and perform rebalancing operations if necessary to ensure that the tree is balanced.