[자료구조]AVL트리

• 순서
  1. 트리란?
  2. 트리에 사용되는 용어
  3. AVL트리란?
  4. 레드-블랙트리란?
  5. 이진탐색트리(BST)
  6. 레드-블랙트리와 AVL트리 비교
  7. AVL트리가 STL 컨테이너로부터 간택받을 수 없는 이유
• 트리란?
  1. 트리란 계층적인 자료구조이다.
  2. 하나의 루트(root)노드에서 시작하여 자식 노드로 나눠짐
  3. 그래프의 한 종류지만 사이클이 없는 형태
  4. 트리의 용도
     • 계층적 데이터 표현
     • 탐색 및 정렬
     • 우선순위 큐(힙)
     • 파싱 등
    
•  
• 트리에 사용되는 용어
  1. 루트 노드: 트리의 가장 위에 있는 노드를 뜻함
  2. 리프 노드: 자식이 없는 노드
  3. 부모/자식: 연결된 두 노드의 관계를 뜻함
  4. 서브트리: 트리의 일부로서 하나의 노드와 그 하위 노드들
  5. 높이: 루트에서 가장 깊은 리프까지의 거리
• AVL트리란?
  1. 각 노드의 왼쪽, 오른쪽 서브트리 높이 차이가 1 이하가 되도록 자동으로 균형을 유지하는 이진 탐색 트리
  2. 밸런스 팩터 ∈ {-1, 0, 1} : 밸런스팩터는 -1, 0 1 중 하나여야한다는 뜻
     • AVL트리에서 각 노드가 얼마나 균형이 잡혀있는지 나타내는 값이다.
     • 각  노드에 밸런스 팩터 = 왼쪽 서브트리 높이 - 오른쪽 서브트리 높이
     • 해당 범위라면 트리가 균형상태
  3. 삽입/삭제 후 밸런스 팩터를 벗어나면 회전으로 균형을 맞춤
     • LL, RR, LR, RL 4가지 회전 패턴이 있음

     

     

  4. 높이 O(long n)
• 레드-블랙트리란?
  1. 각 노드가 레드 혹은 블랙으로 색칠해 느슨한 균형을 유지하는 이진 탐색 트리.
  2. 레드-블랙트리의 균형규칙
     • 루트와 모든 리프는 블랙이다.
     • 레드는 연속될 수 없다. - 레드 노드의 자식은 블랙
     • 루트에서 리프까지 모든 경로의 블랙 노드 수는 동일함.
  3. 삽입/삭제 시 색 변경과 회전으로 균형이 유지됨
  4. 높이 O(log n)
• 이진 탐색트리(BST)
  1. 한 노드를 기준으로 왼쪽으로 갈수록 값이 작고, 오른쪽으로 갈수록 값이 큰 규칙을 가진 트리
  2. 각 노드의 왼쪽 서브트리 값 < 현재 노드 값 < 오른쪽 서브트리 값
  3. 탐색, 삽입, 삭제가 O(h)(h = 높이)
  4. 문제점: 한쪽으로 치우치면 O(n)까지 성능이 저하됨 => 균형잡힌 트리가 필요함
• 레드-블랙트리와 AVL트리 비교
  1. 균형 유지방식: 레드-블랙트리는 느슨한 균형이지만 AVL트리는 엄격한 균형을 유지함
  2. 삽입/삭제 비용: 레드-블랙트리는 적은 재구성을 함(최대 3회 회전), AVL트리는 삭제 시 재구성 비용이 큼(최대 O(log n)회 회전)
  3. 검색 속도: 레드-블랙트리는 약간 느림, AVL 트리는 빠름
  4. 회전 발생 빈도: 레드-블랙트리는 빈도가 적지만 AVL 트리는 많음
  5. 용도: 레드-블랙트리는 STL에 사용됨, AVL트리는 데이터베이스 인덱스 등 검색 최적화
  6. 높이: 레드-블랙트리는 최대 2 * log₂(n+1) - 1이고 AVL트리는 약 log₁.₆₁₈(n)이다.
• AVL트리가 STL컨테이너로부터 간택받을 수 없는 이유
  1. 삽입/삭제 성능 면에서 AVL이 많은 회전으로 인해 느리기 때문
  2. 전체적인 효율로 검색은 AVL이 조금 빠르지만 삽입/삭제가 상대적으로 느리기 때문이다.
  3. 구현 난이도면에서 AVL은 삭제 시 복잡도가 높아짐