AVL tree란 Adelson-Velskii와 Landis에 의해 1962년에 제안된 트리로, 모든 노드의 왼쪽과 오른쪽 서브트리의 높이 차가 1이하인 이진탐색트리를 의미한다.
AVL tree의 연산과정은 다음과 같다.
탐색 연산 : 이진 탐색 트리와 동일하다. 값들을 비교하며 내려가는 구조이다.
삽입,삭제 연산: 삽입-삭제 위치에서 루트까지의 경로에 있는 조상 노드들의 균형 인수에 영향을 받는다. LL type 혹은 RR type을 맞추기 위해 rotation을 진행한다.
반응형
'Computer Science' 카테고리의 다른 글
| [정보보안] AES(Advanced Encryption Standard)에 대하여 (0) | 2023.12.10 |
|---|---|
| [정보보안] DES(Data Encryption Standard)에 대하여 (0) | 2023.12.09 |
| [자료구조] 이진 탐색 트리에서의 연산(탐색 연산, 삽입 연산, 삭제 연산) (1) | 2023.12.07 |
| [선형대수] python으로 행렬의 성분을 부분 출력하기, 행렬 성분의 일부를 변경하는 방법 (1) | 2023.12.06 |
| [선형대수] 파이썬으로 여러 행렬과 단위행렬 출력하기 (0) | 2023.12.05 |