[자료구조] AVL 트리

2025. 2. 3. 20:35· CS/자료구조
목차
  1. AVL 트리란?
  2. AVL 트리 연산, 시간 복잡도
  3. AVL 트리 회전
  4. 1. LL 회전
  5. 2. RR 회전
  6. 3. LR 회전
  7. 4. RL 회전
  8. AVL 트리 구현
  9. AVL Node
  10. AVL Tree
  11. AVL Main
728x90

AVL 트리란?

균형 이진 탐색 트리 (BST)의 한 종류로, 각 노드의 균형을 유지하여 탐색, 삽입, 삭제 연산을 O(log N) 시간에 수행할 수 있는 자료구조

 

균형 이진 탐색 트리이기 때문에 각 노드의 왼쪽 서브 트리와 오른쪽 서브 트리의 높이 차이가 -1, 0, 1 사이로 유지된다.

트리가 한쪽으로 치우치는 것을 방지하여 탐색, 삽입, 삭제 연산의 성능을 보장한다.

 

  • BF = (왼쪽 서브트리의 높이 - 오른쪽 서브 트리의 높이)의 절댓값
  • 모든 노드의 왼쪽, 오른쪽 서브 트리의 높이 차이가 최대 1이다.
  • BF가 2 이상이 되면 회전을 통해 균형을 잡는다.

AVL 트리


AVL 트리 연산, 시간 복잡도

삽입, 삭제 모두 일반적인 BST 삽입, 삭제를 수행한다.

삽입, 삭제 후 BF를 계산하고, BF가 -1, 0, 1 범위를 벗어나면 회전을 수행한다.

 

삽입 : O(log N)

삭제 : O(log N)

탐색 : O(log N)

 

=> AVL 트리는 항상 균형을 유지하므로, 최악의 경우에도 O(log N)을 보장

 


AVL 트리 회전

1. LL 회전

  • 삽입 노드가 왼쪽-왼쪽(LL) 구조를 만들 때 발생
  • 오른쪽으로 회전 수행
30
/
20
/
10

 

회전 후

20
/ \
10 30

 

2. RR 회전

  • 삽입 노드가 오른쪽-오른쪽(RR) 구조를 만들 때 발생
  • 왼쪽으로 회전 수행
10
\
20
\
30

 

회전 후

20
/ \
10 30

 

3. LR 회전

  • 삽입 노드가 왼쪽-오른쪽(LR) 구조를 만들 때 발생
  • 왼쪽으로 회전 후 오른쪽으로 회전 수행
30
/
10
\
20

 

왼쪽으로 회전 후

30
/
20
/
10

 

오른쪽으로 회전 후 

20
/ \
10 30

 

4. RL 회전

  • 삽입 노드가 오른쪽-왼쪽(RL) 구조를 만들 때 발생
  • 오른쪽으로 회전 후 왼쪽으로 회전 수행
10
\
30
/
20

 

오른쪽으로 회전 후

10
\
20
\
30

 

왼쪽으로 회전 

20
/ \
10 30

 

 

 


AVL 트리 구현

 

AVL Node

package avl;
import bst.TreePrinter;
public class AVLNode implements TreePrinter.PrintableNode {
Integer data;
AVLNode left;
AVLNode right;
int height;
public AVLNode(Integer data) {
this.data = data;
height = 0;
}
// 트리 출력
@Override
public TreePrinter.PrintableNode getLeft() {
return left;
}
@Override
public TreePrinter.PrintableNode getRight() {
return right;
}
@Override
public String getText() {
return "["+data+"]";
}
}

 

 

AVL Tree

package avl;
public class AVLTree {
AVLNode root;
int height(AVLNode node) {
if (node == null)
return -1;
return node.height;
}
private int getBalance(AVLNode node) {
if (node == null) {
return 0;
}
return height(node.left) - height(node.right);
}
private AVLNode leftRotate(AVLNode parent) {
AVLNode newParent = parent.right;
AVLNode T2 = newParent.left;
newParent.left = parent;
parent.right = T2;
parent.height = Math.max(height(parent.left), height(parent.right)) + 1;
newParent.height = Math.max(height(newParent.left), height(newParent.right)) + 1;
return newParent;
}
private AVLNode rightRotate(AVLNode parent) {
AVLNode newParent = parent.left;
AVLNode T2 = newParent.right;
newParent.right = parent;
parent.left = T2;
parent.height = Math.max(height(parent.left), height(parent.right)) + 1;
newParent.height = Math.max(height(newParent.left), height(newParent.right)) + 1;
return newParent;
}
public void insert(Integer data) {
this.root = insert(this.root, data);
}
private AVLNode insert(AVLNode node, Integer data) {
if (node == null) {
return new AVLNode(data);
}
if (data < node.data) {
node.left = insert(node.left, data);
} else if (data > node.data) {
node.right = insert(node.right, data);
} else {
return node;
}
node.height = 1 + Math.max(height(node.left), height(node.right));
int balance = getBalance(node);
if (balance > 1 && data < node.left.data)
return rightRotate(node);
if (balance < -1 && data > node.right.data) {
return leftRotate(node);
}
if (balance > 1 && node.left.data < data) {
node.left = leftRotate(node.left);
return rightRotate(node);
}
if (balance < -1 && data < node.right.data) {
node.right = rightRotate(node.right);
return leftRotate(node);
}
return node;
}
}

 

 

AVL Main

package avl;
import bst.TreePrinter;
public class AVLMain {
public static void main(String[] args) {
AVLTree tree = new AVLTree();
// 87 26 34 78 90
tree.insert(87);
tree.insert(26);
tree.insert(34);
tree.insert(78);
tree.insert(90);
TreePrinter.print(tree.root);
System.out.println();
System.out.println();
System.out.println();
System.out.println();
tree.insert(42);
TreePrinter.print(tree.root);
}
}

 

 

82, 26, 34, 78, 90 삽입

 87 26 34 78 90

 

 

42 삽입

 

728x90
저작자표시 비영리 변경금지 (새창열림)

'CS > 자료구조' 카테고리의 다른 글

[자료구조] 최소 힙 트리  (0) 2025.01.24
[자료구조] 이진 탐색 트리  (1) 2025.01.16
  1. AVL 트리란?
  2. AVL 트리 연산, 시간 복잡도
  3. AVL 트리 회전
  4. 1. LL 회전
  5. 2. RR 회전
  6. 3. LR 회전
  7. 4. RL 회전
  8. AVL 트리 구현
  9. AVL Node
  10. AVL Tree
  11. AVL Main
'CS/자료구조' 카테고리의 다른 글
  • [자료구조] 최소 힙 트리
  • [자료구조] 이진 탐색 트리
셰욘
셰욘
셰욘
seiyeon
셰욘
전체
오늘
어제
  • 분류 전체보기 (176)
    • 알고리즘 (46)
      • 프로그래머스 (2)
      • 백준 (37)
      • 문제 유형 (7)
    • CS (41)
      • Linux (6)
      • DB (15)
      • 자료구조 (3)
      • OOP (2)
      • 아키텍처 (0)
    • BE (42)
      • Java (9)
      • Spring Boot (32)
    • FE (6)
      • Next.js (1)
      • JavaScript (5)
      • Vue.js (7)
      • Web (0)
    • 배포 (5)
    • 회고 (19)
      • BEYOND SW 캠프 (19)
    • 기타 (3)

블로그 메뉴

  • 홈
  • 태그
  • 방명록
  • 블로그 관리

공지사항

인기 글

태그

  • Gateway
  • 실습
  • 알고리즘
  • fe
  • 백준
  • 우선순위 큐
  • 구현
  • dfs
  • 백트래킹
  • web
  • be
  • 자료구조
  • 회고
  • cs
  • 리눅스
  • bfs
  • 그리디
  • Java
  • DP
  • vue
  • db
  • 트리
  • 티스토리챌린지
  • js
  • 오블완
  • 주간회고
  • 네트워크
  • spring boot
  • AWS
  • 프로그래머스

최근 댓글

최근 글

250x250
hELLO · Designed By 정상우.v4.2.1
셰욘
[자료구조] AVL 트리
상단으로

티스토리툴바

단축키

내 블로그

내 블로그 - 관리자 홈 전환
Q
Q
새 글 쓰기
W
W

블로그 게시글

글 수정 (권한 있는 경우)
E
E
댓글 영역으로 이동
C
C

모든 영역

이 페이지의 URL 복사
S
S
맨 위로 이동
T
T
티스토리 홈 이동
H
H
단축키 안내
Shift + /
⇧ + /

* 단축키는 한글/영문 대소문자로 이용 가능하며, 티스토리 기본 도메인에서만 동작합니다.