Entwerfen von Klassen für AVL-Bäume

Da es sich bei einem AVL-Baum um einen binären Suchbaum handelt, ist AVLTree als Unterklasse von BST konzipiert. Ein AVL-Baum ist ein Binärbaum, daher können Sie die Klasse AVLTree definieren, um die Klasse BST zu erweitern, wie in der Abbildung unten dargestellt. Die Klassen BST und TreeNode wurden in Section.

definiert

Um den Baum auszubalancieren, müssen Sie die Höhe jedes Knotens kennen. Der Einfachheit halber speichern Sie die Höhe jedes Knotens in AVLTreeNode und definieren AVLTreeNode als Unterklasse von BST.TreeNode. Beachten Sie, dass TreeNode als statische innere Klasse in BST definiert ist. AVLTreeNode wird als statische innere Klasse in AVLTree definiert. TreeNode enthält die Datenfelder element, left und right, die von AVLTreeNode geerbt werden. Somit enthält AVLTreeNode vier Datenfelder, wie in der Abbildung unten dargestellt.

In der Klasse BST erstellt die Methode createNewNode() ein TreeNode-Objekt. Diese Methode wird in der Klasse AVLTree überschrieben, um einen AVLTreeNode zu erstellen. Beachten Sie, dass der Rückgabetyp der Methode createNewNode() in der Klasse BST TreeNode ist, der Rückgabetyp der Methode createNewNode()-Methode in der Klasse AVLTree ist AVLTreeNode. Das ist in Ordnung, da AVLTreeNode eine Unterklasse von TreeNode ist.

Die Suche nach einem Element in einem

AVLTree ist dasselbe wie die Suche in einem regulären Binärbaum, daher funktioniert auch die in der Klasse BST definierte Methode search für AVLTree.

Die Methoden

insert und delete werden überschrieben, um ein Element einzufügen und zu löschen und bei Bedarf Neuausgleichsvorgänge durchzuführen, um sicherzustellen, dass der Baum ausgeglichen ist.

Das obige ist der detaillierte Inhalt vonEntwerfen von Klassen für AVL-Bäume. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!