Conception de classes pour les arbres AVL

Puisqu'un arbre AVL est un arbre de recherche binaire, AVLTree est conçu comme une sous-classe de BST. Un arbre AVL est un arbre binaire, vous pouvez donc définir la classe AVLTree pour étendre la classe BST, comme le montre la figure ci-dessous. Les classes BST et TreeNode ont été définies dans la section.

Afin d’équilibrer l’arbre, vous devez connaître la hauteur de chaque nœud. Pour plus de commodité, stockez la hauteur de chaque nœud dans AVLTreeNode et définissez AVLTreeNode comme étant une sous-classe de BST.TreeNode. Notez que TreeNode est défini comme une classe interne statique dans BST. AVLTreeNode sera défini comme une classe interne statique dans AVLTree. TreeNode contient les champs de données élément, gauche et droite, qui sont hérités par AVLTreeNode. Ainsi, AVLTreeNode contient quatre champs de données, comme le montre la figure ci-dessous.

Dans la classe BST, la méthode createNewNode() crée un objet TreeNode. Cette méthode est remplacée dans la classe AVLTree pour créer un AVLTreeNode. Notez que le type de retour de la méthode createNewNode() dans la classe BST est TreeNode, mais le type de retour de createNewNode() La méthode dans la classe AVLTree est AVLTreeNode. C'est très bien, puisque AVLTreeNode est une sous-classe de TreeNode.

La recherche d'un élément dans un AVLTree est la même chose que la recherche dans un arbre binaire normal, donc la méthode search définie dans la classe BST fonctionne également pour AVLTree.

Les méthodes insert et delete sont surchargées pour insérer et supprimer un élément et effectuer des opérations de rééquilibrage si nécessaire pour garantir que l'arbre est équilibré.

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!