Die Klasse AVLTree erweitert die Klasse BST, um die Methoden insert und delete zu überschreiben, um den Baum bei Bedarf neu auszubalancieren. Der folgende Code enthält den vollständigen Quellcode für die AVLTree-Klasse.
package demo; public class AVLTree> extends BST { /** Create an empty AVL tree */ public AVLTree() {} /** Create an AVL tree from an array of objects */ public AVLTree(E[] objects) { super(objects); } @Override /** Override createNewNode to create an AVLTreeNode */ protected AVLTreeNode createNewNode(E e) { return new AVLTreeNode (e); } @Override /** Insert an element and rebalance if necessary */ public boolean insert(E e) { boolean successful = super.insert(e); if (!successful) return false; // e is already in the tree else { balancePath(e); // Balance from e to the root if necessary } return true; // e is inserted } /** Update the height of a specified node */ private void updateHeight(AVLTreeNode node) { if (node.left == null && node.right == null) // node is a leaf node.height = 0; else if (node.left == null) // node has no left subtree node.height = 1 + ((AVLTreeNode )(node.right)).height; else if (node.right == null) // node has no right subtree node.height = 1 + ((AVLTreeNode )(node.left)).height; else node.height = 1 + Math.max(((AVLTreeNode )(node.right)).height, ((AVLTreeNode )(node.left)).height); } /** Balance the nodes in the path from the specified * node to the root if necessary */ private void balancePath(E e) { java.util.ArrayList > path = path(e); for (int i = path.size() - 1; i >= 0; i--) { AVLTreeNode A = (AVLTreeNode )(path.get(i)); updateHeight(A); AVLTreeNode parentOfA = (A == root) ? null : (AVLTreeNode )(path.get(i - 1)); switch (balanceFactor(A)) { case -2: if (balanceFactor((AVLTreeNode )A.left) <= 0) { balanceLL(A, parentOfA); // Perform LL rotation } else { balanceLR(A, parentOfA); // Perform LR rotation } break; case +2: if (balanceFactor((AVLTreeNode )A.right) >= 0) { balanceRR(A, parentOfA); // Perform RR rotation } else { balanceRL(A, parentOfA); // Perform RL rotation } } } } /** Return the balance factor of the node */ private int balanceFactor(AVLTreeNode node) { if (node.right == null) // node has no right subtree return -node.height; else if (node.left == null) // node has no left subtree return +node.height; else return ((AVLTreeNode )node.right).height - ((AVLTreeNode )node.left).height; } /** Balance LL (see Figure 26.2) */ private void balanceLL(TreeNode A, TreeNode parentOfA) { TreeNode B = A.left; // A is left-heavy and B is left-heavy if (A == root) { root = B; } else { if (parentOfA.left == A) { parentOfA.left = B; } else { parentOfA.right = B; } } A.left = B.right; // Make T2 the left subtree of A B.right = A; // Make A the left child of B updateHeight((AVLTreeNode )A); updateHeight((AVLTreeNode )B); } /** Balance LR (see Figure 26.4) */ private void balanceLR(TreeNode A, TreeNode parentOfA) { TreeNode B = A.left; // A is left-heavy TreeNode C = B.right; // B is right-heavy if (A == root) { root = C; } else { if (parentOfA.left == A) { parentOfA.left = C; } else { parentOfA.right = C; } } A.left = C.right; // Make T3 the left subtree of A B.right = C.left; // Make T2 the right subtree of B C.left = B; C.right = A; // Adjust heights updateHeight((AVLTreeNode )A); updateHeight((AVLTreeNode )B); updateHeight((AVLTreeNode )C); } /** Balance RR (see Figure 26.3) */ private void balanceRR(TreeNode A, TreeNode parentOfA) { TreeNode B = A.right; // A is right-heavy and B is right-heavy if (A == root) { root = B; } else { if (parentOfA.left == A) { parentOfA.left = B; } else { parentOfA.right = B; } } A.right = B.left; // Make T2 the right subtree of A B.left = A; updateHeight((AVLTreeNode )A); updateHeight((AVLTreeNode )B); } /** Balance RL (see Figure 26.5) */ private void balanceRL(TreeNode A, TreeNode parentOfA) { TreeNode B = A.right; // A is right-heavy TreeNode C = B.left; // B is left-heavy if (A == root) { root = C; } else { if (parentOfA.left == A) { parentOfA.left = C; } else { parentOfA.right = C; } } A.right = C.left; // Make T2 the right subtree of A B.left = C.right; // Make T3 the left subtree of B C.left = A; C.right = B; // Adjust heights updateHeight((AVLTreeNode )A); updateHeight((AVLTreeNode )B); updateHeight((AVLTreeNode )C); } @Override /** Delete an element from the AVL tree. * Return true if the element is deleted successfully * Return false if the element is not in the tree */ public boolean delete(E element) { if (root == null) return false; // Element is not in the tree // Locate the node to be deleted and also locate its parent node TreeNode parent = null; TreeNode current = root; while (current != null) { if (element.compareTo(current.element) < 0) { parent = current; current = current.left; } else if (element.compareTo(current.element) > 0) { parent = current; current = current.right; } else break; // Element is in the tree pointed by current } if (current == null) return false; // Element is not in the tree // Case 1: current has no left children (See Figure 25.10) if (current.left == null) { // Connect the parent with the right child of the current node if (parent == null) { root = current.right; } else { if (element.compareTo(parent.element) < 0) parent.left = current.right; else parent.right = current.right; // Balance the tree if necessary balancePath(parent.element); } } else { // Case 2: The current node has a left child // Locate the rightmost node in the left subtree of // the current node and also its parent TreeNode parentOfRightMost = current; TreeNode rightMost = current.left; while (rightMost.right != null) { parentOfRightMost = rightMost; rightMost = rightMost.right; // Keep going to the right } // Replace the element in current by the element in rightMost current.element = rightMost.element; // Eliminate rightmost node if (parentOfRightMost.right == rightMost) parentOfRightMost.right = rightMost.left; else // Special case: parentOfRightMost is current parentOfRightMost.left = rightMost.left; // Balance the tree if necessary balancePath(parentOfRightMost.element); } size--; return true; // Element inserted } /** AVLTreeNode is TreeNode plus height */ protected static class AVLTreeNode > extends BST.TreeNode { protected int height = 0; // New data field public AVLTreeNode(E e) { super(e); } } }
Die Klasse AVLTree erweitert BST. Wie die BST-Klasse verfügt auch die AVLTree-Klasse über einen Konstruktor ohne Argumente, der einen leeren AVLTree erstellt (Zeilen 5), und einen Konstruktor, der einen anfänglichen AVLTree aus einem Array von Elementen erstellt (Zeilen 8–10). .
Die in der Klasse BST definierte Methode createNewNode() erstellt einen TreeNode. Diese Methode wird überschrieben, um einen AVLTreeNode (Zeilen 13–15) zurückzugeben.
Die insert-Methode in AVLTree wird in den Zeilen 18–27 überschrieben. Die Methode ruft zuerst die insert-Methode in BST auf und ruft dann balancePath(e) (Zeile 23) auf, um sicherzustellen, dass der Baum ausgeglichen ist.
Die balancePath-Methode ruft zunächst die Knoten auf dem Pfad vom Knoten, der das Element e enthält, zur Wurzel ab (Zeile 45). Aktualisieren Sie für jeden Knoten im Pfad seine Höhe (Zeile 48), überprüfen Sie seinen Ausgleichsfaktor (Zeile 51) und führen Sie bei Bedarf entsprechende Drehungen durch (Zeilen 51–67).
Vier Methoden zur Durchführung von Rotationen sind in den Zeilen 82–178 definiert. Jede Methode wird mit zwei TreeNode-Argumenten – A und parentOfA – aufgerufen, um eine entsprechende Rotation am Knoten A durchzuführen. Wie jede Drehung durchgeführt wird, ist in den Abbildungen im Beitrag dargestellt. Nach der Rotation werden die Höhen der Knoten A, B und C aktualisiert (Zeilen 98, 125, 148, 175).
Die Methode delete in AVLTree wird in den Zeilen 183–248 überschrieben. Die Methode ist dieselbe wie die in der Klasse BST implementierte, außer dass Sie die Knoten nach dem Löschen in zwei Fällen neu ausbalancieren müssen (Zeilen 218, 243).
以上是Die AVLTree-Klasse的详细内容。更多信息请关注PHP中文网其他相关文章!