Java를 사용하여 AVL 트리 알고리즘을 구현하는 방법
소개:
AVL 트리는 삽입 및 삭제 작업 중에 자동으로 균형을 유지하여 트리 높이가 항상 유지되도록 할 수 있는 자체 균형 이진 검색 트리입니다. . 이번 글에서는 자바를 이용하여 AVL 트리 알고리즘을 구현하는 방법을 알아보고 구체적인 코드 예시를 제공하겠습니다.
1. AVL 트리의 기본 설명 및 특성:
AVL 트리는 1962년 G. M. Adelson-Velsky와 Evgenii Landis에 의해 제안되었습니다. AVL 트리에서는 각 노드의 왼쪽 하위 트리와 오른쪽 하위 트리의 높이 차이가 1을 초과할 수 없습니다. 1을 초과하면 자동 밸런싱을 위해 회전 동작이 필요합니다. 일반 이진 검색 트리와 비교하여 AVL 트리는 검색, 삽입 및 삭제 성능이 더 좋습니다.
2. AVL 트리의 노드 구현:
Java에서는 사용자 정의 노드 클래스를 사용하여 AVL 트리를 구현할 수 있습니다. 각 노드에는 왼쪽 및 오른쪽 하위 트리에 대한 값과 참조뿐만 아니라 노드의 높이를 기록하는 변수도 포함되어 있습니다.
class AVLNode { int val; AVLNode left, right; int height; AVLNode(int val) { this.val = val; this.height = 1; } }
3. 노드 높이 계산:
AVL 트리 알고리즘을 구현하기 전에 노드 높이를 계산하는 함수가 필요합니다. 이 함수는 왼쪽 하위 트리와 오른쪽 하위 트리의 높이를 재귀적으로 계산한 후 둘 중 더 큰 값에 1을 더하여 현재 노드의 높이를 구합니다.
int getHeight(AVLNode node) { if (node == null) { return 0; } return Math.max(getHeight(node.left), getHeight(node.right)) + 1; }
4. AVL 트리의 회전 작업 구현:
작업을 삽입하고 삭제할 때 트리의 균형을 유지하려면 AVL 트리를 회전해야 합니다. 왼손 및 오른손 작업을 모두 구현하겠습니다.
AVLNode leftRotate(AVLNode node) { AVLNode newRoot = node.right; AVLNode temp = newRoot.left; newRoot.left = node; node.right = temp; node.height = Math.max(getHeight(node.left), getHeight(node.right)) + 1; newRoot.height = Math.max(getHeight(newRoot.left), getHeight(newRoot.right)) + 1; return newRoot; }
AVLNode rightRotate(AVLNode node) { AVLNode newRoot = node.left; AVLNode temp = newRoot.right; newRoot.right = node; node.left = temp; node.height = Math.max(getHeight(node.left), getHeight(node.right)) + 1; newRoot.height = Math.max(getHeight(newRoot.left), getHeight(newRoot.right)) + 1; return newRoot; }
5. 삽입 작업 구현:
새 노드를 삽입할 때 먼저 이진 검색 트리의 규칙에 따라 삽입된 다음 삽입 경로에서 노드의 균형 요소에 따라 조정됩니다. 회전 작업 및 노드 업데이트가 포함됩니다.
AVLNode insert(AVLNode node, int val) { if (node == null) { return new AVLNode(val); } if (val < node.val) { node.left = insert(node.left, val); } else if (val > node.val) { node.right = insert(node.right, val); } else { // 如果节点已经存在,不进行插入 return node; } node.height = Math.max(getHeight(node.left), getHeight(node.right)) + 1; int balanceFactor = getBalanceFactor(node); // 左左情况,需要进行右旋 if (balanceFactor > 1 && val < node.left.val) { return rightRotate(node); } // 左右情况,需要进行左旋后再进行右旋 if (balanceFactor > 1 && val > node.left.val) { node.left = leftRotate(node.left); return rightRotate(node); } // 右右情况,需要进行左旋 if (balanceFactor < -1 && val > node.right.val) { return leftRotate(node); } // 右左情况,需要进行右旋后再进行左旋 if (balanceFactor < -1 && val < node.right.val) { node.right = rightRotate(node.right); return leftRotate(node); } return node; }
6. 삭제 작업 구현:
노드를 삭제할 때 먼저 이진 검색 트리의 규칙에 따라 삭제된 다음 삭제 경로에서 노드의 균형 요소에 따라 조정됩니다. 작업 및 노드 높이 업데이트.
AVLNode delete(AVLNode node, int val) { if (node == null) { return node; } if (val < node.val) { node.left = delete(node.left, val); } else if (val > node.val) { node.right = delete(node.right, val); } else { if (node.left == null || node.right == null) { node = (node.left != null) ? node.left : node.right; } else { AVLNode successor = findMin(node.right); node.val = successor.val; node.right = delete(node.right, node.val); } } if (node == null) { return node; } node.height = Math.max(getHeight(node.left), getHeight(node.right)) + 1; int balanceFactor = getBalanceFactor(node); // 左左情况,需要进行右旋 if (balanceFactor > 1 && getBalanceFactor(node.left) >= 0) { return rightRotate(node); } // 左右情况,需要进行左旋后再进行右旋 if (balanceFactor > 1 && getBalanceFactor(node.left) < 0) { node.left = leftRotate(node.left); return rightRotate(node); } // 右右情况,需要进行左旋 if (balanceFactor < -1 && getBalanceFactor(node.right) <= 0) { return leftRotate(node); } // 右左情况,需要进行右旋后再进行左旋 if (balanceFactor < -1 && getBalanceFactor(node.right) > 0) { node.right = rightRotate(node.right); return leftRotate(node); } return node; } AVLNode findMin(AVLNode node) { while (node.left != null) { node = node.left; } return node; }
7. 테스트 예:
우리가 구현한 AVL 트리 알고리즘의 정확성을 확인하기 위해 다음 예를 사용하여 테스트할 수 있습니다.
public static void main(String[] args) { AVLTree tree = new AVLTree(); tree.root = tree.insert(tree.root, 10); tree.root = tree.insert(tree.root, 20); tree.root = tree.insert(tree.root, 30); tree.root = tree.insert(tree.root, 40); tree.root = tree.insert(tree.root, 50); tree.root = tree.insert(tree.root, 25); tree.inOrderTraversal(tree.root); }
출력 결과:
10 20 25 30 40 50
요약:
이 기사에서는 Java를 사용하여 AVL 트리 알고리즘을 구현하는 방법을 소개하고 특정 코드 예제를 제공합니다. 삽입 및 삭제 작업을 구현함으로써 AVL 트리가 항상 균형을 이루도록 보장하여 검색, 삽입 및 삭제 성능을 향상시킬 수 있습니다. 나는 이 글을 공부함으로써 독자들이 AVL 트리 알고리즘을 더 잘 이해하고 적용할 수 있다고 믿습니다.
위 내용은 Java를 사용하여 AVL 트리 알고리즘을 구현하는 방법의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!