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 サイトの他の関連記事を参照してください。
![[Web フロントエンド] Node.js クイック スタート](https://img.php.cn/upload/course/000/000/067/662b5d34ba7c0227.png)
