[자료구조] 탐색트리 -4

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

AVL트리 삽입연산

AVL트리에서 삽입은 2단계로 수행
1. 이진탐색트리의 삽입과 동일하게 새로운 노드 삽입
2. 새로 삽입한 노드부터 루트로 거슬러 올라가며 각 노드의 서브트리 높이 차이를 갱신
  - 이때 가장 먼저 불균형이 발생한 노드를 발견하면, 이 노드를 기준으로 새 노드가 어디에 삽입되었는지에 따라 적절한 회전연산을 수행

AVL 트리 Node 클래스

public class Node {
 private Key id;
 private Value name;
 private int height;
 private Node left, right;
 public Node(Key newID, Value newName, int newHt) {
     id = newID;
     name = newName;
     height = newHt;
     left = right = null;
 }
}

삽입 연산

public void put(Key k, Value v) { root = put(root, k, v); }
private Node put(Node n, Key k, Value v) {
 if(n==null) {
     return new Node(k, v, 1);
 }
 int i = k.compareTo(n.id);
 if(t<0) {
     n.left = put(n.left, k, v);
 } else if (t>0) {
     n.right = put(n.right, k, v);
 } else {
     n.name = v;
     return n;
 }
 n.height = tallerHeight(height(n.left), height(n.right))+1;
 return balance(n);
}

회전연산 수행 메소드

private Node balance(Node n) {
 if(bf(n)>1) {
     if(bf(n.left)<0) {
         n.left = rotateLeft(n.left);
     }
     n = rotateRight(n);
 } else if (bf(n)<-1) {
     if(bf(n.right)>0) {
         n.right = rotateRight(n.right);
     }
     n.rotateLeft(n);
 }
 return n;
}

삽입연산에 사용되는 메소드

좌우 노드 높이차 계산

private int bf(Node n) {
 return height(n.left) - height(n.right);
}

지정노드 높이 계산

private int height(Node n) {
  if(n==null) { return 0; }
  return n.height;
}

지정노드 중 더 깊은노드 찾기

private int tallerHeight(int x, int y) {
  if(x>y) { return x; }
  else { return y; }
}

AVL트리 삭제 연산

AVL트리에서 삭제는 2단계로 진행

이진탐색트리에서와 동일한 삭제 연산 수행

삭제된 노드로부터 루트노드 방향으로 거슬러 올라가며 불균형이 발생한 경우 적절한 회전연산 수행

회전연산 수행 후에 부모노드에서 불균형이 발생할 수 있고, 이러한 일이 반복되어 루트노드에서 회전연산을 수행해야 하는 경우도 발생

public void delete(Key k) { root = delete(root, k); }
  public Node delete(Node n, Key k) {
 int t = n.id.compareTo(k);
 if(t>0) {
  n.left = delete(n.left, k);
 } else if (t<0) {
  n.right = delete(n.right, k);
 } else {
  if(n.right==null) {
      return n.left;
  }
  if(n.left==null) {
      return n.right;
  }
  Node target = n;
  n = min(target.right);
  n.right = deleteMin(target.right);
  n.left = target.left ;
 }
 n.height = tallerHeight(height(n.left), height(n.right))+1;
 return balance(n);
  }

정리

AVL 트리에서의 탐색, 삽입, 삭제 연산은 공통적으로 루트노드부터 탐색을 시작하여 최악의 경우에 이파리노드까지 내려가고, 삽입이나 삭제 연산은 다시 루트까지 거슬러 올라가야 함
트리를 1층 내려갈 때는 재귀호출하며, 1층을 올라갈 때 불균형이 발생하면 적절한 회전연산을 수행하는데, 이들 각각은 O(1)시간 밖에 걸리지 않음
탐색, 삽입, 삭제 연산의 수행시간은 각각 AVL의 높이에 비례하므로 각 연산의 수행시간은 O(logN)
다양한 실험결과에 따르면 AVL트리는 거의 정렬된 데이터를 삽입한 후에 랜덤 순서로 데이터를 탐색하는 경우 가장 좋은 성능을 보임
이진탐색트리는 랜덤 순서의 데이터를 삽입한 후에 랜덤 순서로 데이터를 탐색하는 경우 가장 좋은 성능을 보임

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

IM

AVL트리 삽입연산

AVL트리 삭제 연산

정리