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행).
회전을 수행하는 네 가지 방법은 82~178행에 정의되어 있습니다. 각 메서드는 두 개의TreeNode 인수(A 및 parentOfA)를 사용하여 호출되어 노드 A에서 적절한 회전을 수행합니다. 각 회전이 수행되는 방식은 게시물의 그림에 설명되어 있습니다. 회전 후 A, B, C 노드의 높이가 업데이트됩니다(98, 125, 148, 175행).
AVLTree의 delete 메서드는 183~248행에서 재정의됩니다. 방법은 BST 클래스에서 구현한 방법과 동일하지만 두 가지 경우(218, 243행) 삭제 후 노드의 균형을 다시 맞춰야 한다는 점만 다릅니다.
위 내용은 AVLTree 클래스의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!
![[웹 프런트엔드] Node.js 빠른 시작](https://img.php.cn/upload/course/000/000/067/662b5d34ba7c0227.png)
