[자료구조] AVL트리

[자료구조] AVL트리

1. 정의

• 스스로 균형을 잡는 이진 탐색 트리
  • 왼쪽과 오른쪽의 높이 차가 1이하여야 함.
• 항상 O(logN)의 시간복잡도를 보장

2. 구현

• //AVL트리의 생성자
  public AVLTree() {
    root = null;
    currentSize = 0;
  }
  
  //기본 노드
  class Node<T> {
    T data;
    Node<T> left;
    Node<T> right;
    Node<T> parent;
  
    public Node(T obj) {
      data = obj;
      parent = null;
      left = null;
      right = null;
    }
  }

• //추가 메서드
  public void add(E obj) {
    Node<E> node = new Node<>(obj);
  
    if (root == null) {
      root = node;
      currentSize++;
      return;
    }
    add(root, node);
  }
  
  public void add(Node<E> parent, Node<E> newNode) {
    if(((comparable<E>) newNode.data.compareTo(parent.data)) > 0) { //기준값보다 크면 오른쪽
      if (parent.right == null) {
        parent.right = newNode;
        newMode.parent = parent;
        currentSize++;
      } else {
        add(parent.right, newNode);
      }
    } else { //기준값보다 작으면 왼쪽
      if (parent.left == null) {
        parent.left = newNode;
        newMode.parent = parent;
        currentSize++;
      } else {
        add(parent.left, newNode);
      }
    }
    checkBalence(newNode);
  }

• //균형 확인 메서드
  public void checkBalance(Node<E> node) {
    int diff = height(node.left) - hight(node.right);
  
    if (diff > 1 || diff < -1) {
        rebalance(node);  
    }
  
    if (node.parent == null) {
      return;
    }
  
    checkBalance(node.parent);
  }

• //rebalance 메서드
  public void reBalance(Node<E> node) {
    int diff = height(node.left) - hight(node.right);
  
    if (diff > 1) { //왼쪽이 더 길 때
      if (height(node.left.left) > height(node.left.right)){ //왼쪽 자식 노드의 왼쪽 오른쪽 자식 노드 비교
        node = rightRotate(node);
      } else {
        node = leftRotate(node);
      }
    } else { //오른쪽이 더 길 때
      if (height(node.right.left) > height(node.right.right)){ //오른쪽 자식 노드의 왼쪽 오른쪽 자식 노드 비교
        node = rightRotate(node);
      } else {
        node = leftRotate(node);
      }
    }
  
    if (node.parent == null) {
      root = node;
    }
  }

---

※ 참조

• 자바로 구현하고 배우는 자료구조 - 네이버 부스트 코스

• Interview_Question_for_Beginner