CS/자료구조 (Data Structure)

[자료구조] 12. AVL 트리(AVL Tree)

2023. 7. 28. 13:33
목차
  1. AVL 트리
  2. AVL트리의 효율 증명
  3. ADT
  4. 구현
  5. 삽입
  6. 제거
  7. 효율
728x90

이전 시간에 살펴보았던 이진탐색트리는 O(h)의 시간 복잡도를 가지기에, 높이의 균형을 유지하여야 O(log n)의 효율을 유지할 수 있었다. 이렇게 밸런스를 유지하는 방법으로는 height-balanced와 weight-balanced의 방식이 있는데 그중 height-balanced 트리는 대표적으로 AVL 트리와 레드-블랙 트리가 존재한다. 이번 글에서는 이 중 AVL 트리에 대해서 다루어 보려 한다.

 

AVL 트리

AVL 트리의 정의는 모든 노드 v에 대하여 v 양옆의 자식들의 높이(height) 차이가 1 이하인 이진탐색트리를 의미한다.

AVL트리의 효율 증명

이러한 방식으로 AVL트리를 제작했을 때 이 효율이 O(log n)인 것의 증명을 서술...나중에 한다.


ADT

search(key)
insert(key)
delete(key)

이진탐색트리와 같다.


구현

힙이 삽입과 삭제 후에 heapify를 하듯이 삽입/삭제 후 규칙에 맞게 restructing 해주는 것이 핵심이다.

삽입

삽입은 삽입 후 AVL 트리에 맞게 restructing 해주는 방식으로 진행된다. 삽입 자체는 이진탐색트리와 동일하게 진행된다.

1. 이진탐색트리 규칙에 맞게 삽입한다.

2. AVL 트리 규칙에 맞는지 확인 후 맞다면 넘어가고, 규칙에서 벗어나면 restructing 해준다.

Trinode Restructing

Restructing의 과정을 설명한다. 노드 삽입시에 AVL 트리 규칙에 벗어나는 경우는 크게 2가지 경우가 있다.

~~~ 작성 중

제거

제거는 삽입과 유사하나 하나의 경우의 수가 더 늘어난다.

~~~ 작성 중


효율

작업 시간 복잡도
find() O(log n)
put() O(log n)
erase() O(log n)

AVL트리는 이진탐색트리의 효율을 따라가는데 이진탐색트리는 O(h)의 시간 복잡도를 가진다. 이때 AVL트리는 h = log n 수준으로 맞춰주는 작업을 추가한 특수한 이진탐색트리임으로, O(log n)의 시간 복잡도를 가진다.

728x90

'CS > 자료구조 (Data Structure)' 카테고리의 다른 글

[자료구조] 13. 그래프(Graph)  (0) 2023.08.02
[자료구조] 12. 해시 테이블(Hash table)  (0) 2023.07.31
[자료구조] 11. 이진탐색트리(Binary search tree)  (0) 2023.07.26
[자료구조] 10. 맵 & 딕셔너리(Map & Dictionary)  (0) 2023.07.24
[자료구조] 9. 힙(Heap)  (0) 2023.07.21
  • AVL 트리
  • AVL트리의 효율 증명
  • ADT
  • 구현
  • 삽입
  • 제거
  • 효율
Wibaek
생쥐 개발자
Wibaek
총 방문
오늘
어제
  • 전체보기 (111)
    • 서버(Server) (4)
      • 장고 (Django) (20)
      • 스프링 (Spring) (0)
    • 프론트엔드 (Frontend) (4)
    • 파이썬 (Python) (8)
    • 자바 (Java) (1)
    • 인프라 (Infra) (10)
    • 알고리즘 (Algorithm), PS (4)
      • Leetcode (0)
      • Baekjoon Online Judge (3)
    • CS (20)
      • 자료구조 (Data Structure) (19)
    • Troubleshooting (10)
    • 회고 & 기록 (10)
    • 기타 (Other) (12)
    • TIL (1)
    • 하나도 안 중요함 (6)

인기 글

250x250
hELLO · Designed By 정상우.
Wibaek
[자료구조] 12. AVL 트리(AVL Tree)
상단으로

티스토리툴바

단축키

내 블로그

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

블로그 게시글

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

모든 영역

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

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