IM

작지만 단단하게

본문과 관련하여 실습한 전체코드는 리파지토리에 별도 작성하였습니다.
https://github.com/ejImDev/data_structure_study.git

AVL 트리

  • 균형 탐색 트리
  • 트리가 한쪽으로 치우쳐져 자라나는 현상을 방지하여 트리 높이의 균형을 유지하는 이진탐색트리
  • 균형 이진트리를 만들면 N개의 노드를 가진 트리의 높이가 O(logN)이 되어 탐색, 삽입, 삭제 연산의 수행시간이 O(logN)으로 보장

  • 삽입이나 삭제로 인해 균형이 깨지면 회전 연산을 통해 트리의 균형을 유지함

  • A(h)를 높이가 h인 AVL트리를 구성하는 최소의 노드 수로 정의
    • A(3)를 재귀적으로 표현하면 : A(h) = A(2) + A(2) + 1 로 표현할 수 있음

AVL트리의 회전 연산

  • AVL트리에서 삽입 또는 삭제 연산을 수행할 때 트리의 균형을 유지하기 위해 LL-회전, RR-회전, LR-회전, RL-회전연산 사용
  • 회전연산은 2개의 기본적인 연산으로 구현

  1. rotateRight()
    • 왼쪽 방향의 서브트리가 높아서 불균형이 발생할 때 서브트리를 오른쪽 방향으로 회전하기 위한 메소드
    • 노드 n의 왼쪽 자식노드 x를 노드 n의 자리로 옮기고, 노드 n을 노드 x의 오른쪽 자식노드로 만들며, 이 과정에서 서브트리 t가 노드 n의 왼쪽 서브트리로 이동
      private Node rotateRight(Node n) {
 Node x = n.left;
 n.left = x.right;
 x.right = n;
 n.height = tallerHeight(height(n.left), height(n.right)) +1;
 x.height = tallerHeight(height(x.left), height(x.right)) +1;
 return x;
}
  2. rotateLeft()
    • 오른쪽 방향의 서브트리가 높아서 불균형이 발생했을 때 왼족방향으로 회전하기 위한 메소드
    • 노드 n의 오론쪽 자식노드 x를 노드 n의 자리로 옮기고 노드 n를 노드 x의 왼쪽 자식노드로 만들며, 이 과정에서 서브트리 t가 노드 n의 오른쪽 서브트리로 이동
      private Node rotateLeft(Node n) {
 Node x = n.right;
 n.right = x.left;
 x.left = n;
 n.height = tallerHeight(height(n.left), height(n.right)) +1;
 x.height = tallerHeight(height(x.left), height(x.right)) +1;
 return x;
}
  3. 4가지 회전연산
    1) LL 유형
    - t.left.left가 가장 깊음
    - 우회전 필요
    2) LR 유형
    - t.left.right가 가장 깊음
    - 좌회전 후 우회전 필요
    3) RR 유형
    - t.right.right가 가장 깊음
    - 좌회전 필요
    4) RL 유형
    - t.right.left가 가장 깊음
    - 우회전 후 좌회전 필요

  • 4가지 유형 모두 회전 후의 트리들이 모두 동일 (단, 기존 값도 동일해야 함)
    - 각 값이 어디에 위치하든지 중간값을 가진 노드가 위로 이동하면서 나머지 값이 좌우 자식노드가 되기 때문
    • 각 회전연산의 수행시간이 O(1)
      • 변경된 노드 레퍼런스 수가 O(1)개이기 때문

참고 자료 : ‘경기대학교 소프트웨어중심대학사업단 - JAVA 자료구조’ https://youtu.be/UBZSn1ioNO8

Updated: