AVLTree クラスは、BST クラスを拡張して、insert メソッドと delete メソッドをオーバーライドします。必要に応じてツリーのバランスを再調整します。以下のコードは、AVLTree クラスの完全なソース コードを示します。
package demo; public class AVLTree<E extends Comparable<E>> extends BST<E> { /** 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<E> createNewNode(E e) { return new AVLTreeNode<E>(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<E> 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<E>)(node.right)).height; else if (node.right == null) // node has no right subtree node.height = 1 + ((AVLTreeNode<E>)(node.left)).height; else node.height = 1 + Math.max(((AVLTreeNode<E>)(node.right)).height, ((AVLTreeNode<E>)(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<TreeNode<E>> path = path(e); for (int i = path.size() - 1; i >= 0; i--) { AVLTreeNode<E> A = (AVLTreeNode<E>)(path.get(i)); updateHeight(A); AVLTreeNode<E> parentOfA = (A == root) ? null : (AVLTreeNode<E>)(path.get(i - 1)); switch (balanceFactor(A)) { case -2: if (balanceFactor((AVLTreeNode<E>)A.left) <= 0) { balanceLL(A, parentOfA); // Perform LL rotation } else { balanceLR(A, parentOfA); // Perform LR rotation } break; case +2: if (balanceFactor((AVLTreeNode<E>)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<E> 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<E>)node.right).height - ((AVLTreeNode<E>)node.left).height; } /** Balance LL (see Figure 26.2) */ private void balanceLL(TreeNode<E> A, TreeNode<E> parentOfA) { TreeNode<E> 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<E>)A); updateHeight((AVLTreeNode<E>)B); } /** Balance LR (see Figure 26.4) */ private void balanceLR(TreeNode<E> A, TreeNode<E> parentOfA) { TreeNode<E> B = A.left; // A is left-heavy TreeNode<E> 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<E>)A); updateHeight((AVLTreeNode<E>)B); updateHeight((AVLTreeNode<E>)C); } /** Balance RR (see Figure 26.3) */ private void balanceRR(TreeNode<E> A, TreeNode<E> parentOfA) { TreeNode<E> 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<E>)A); updateHeight((AVLTreeNode<E>)B); } /** Balance RL (see Figure 26.5) */ private void balanceRL(TreeNode<E> A, TreeNode<E> parentOfA) { TreeNode<E> B = A.right; // A is right-heavy TreeNode<E> 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<E>)A); updateHeight((AVLTreeNode<E>)B); updateHeight((AVLTreeNode<E>)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<E> parent = null; TreeNode<E> 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<E> parentOfRightMost = current; TreeNode<E> 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<E extends Comparable<E>> extends BST.TreeNode<E> { protected int height = 0; // New data field public AVLTreeNode(E e) { super(e); } } }
AVLTree クラスは BST を拡張します。 BST クラスと同様、AVLTree クラスには、空の AVLTree を構築する引数なしのコンストラクター (5 行目) と、初期 AVLTree 要素の配列から (8 ~ 10 行目).
BST クラスで定義されている createNewNode() メソッドは、TreeNode を作成します。このメソッドは AVLTreeNode を返すようにオーバーライドされます (13 ~ 15 行目)。
AVLTree の insert メソッドは、18 ~ 27 行目でオーバーライドされます。このメソッドは、最初に BST の insert メソッドを呼び出し、次に balancePath(e) (行 23) を呼び出してツリーのバランスを確保します。
balancePath メソッドは、まず要素 e を含むノードからルートまでのパス上のノードを取得します (45 行目)。パス内の各ノードについて、高さを更新し (48 行目)、バランス係数を確認し (51 行目)、必要に応じて適切な回転を実行します (51 ~ 67 行目)。
回転を実行するための 4 つのメソッドが 82 ~ 178 行で定義されています。各メソッドは 2 つのTreeNode 引数 (A と parentOfA) を使用して呼び出され、ノード A で適切な回転を実行します。各回転がどのように実行されるかは、この記事の図で説明されています。回転後、ノード A、B、および C の高さが更新されます (行 98、125、148、175)。
AVLTree の delete メソッドは、183 ~ 248 行目でオーバーライドされます。このメソッドは、BST クラスで実装されたものと同じですが、2 つの場合 (行 218、243) で削除後にノードのバランスを再調整する必要がある点が異なります。
以上がAVLTree クラスの詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。