Odds and Ends
[자료구조] AVL Tree 개념 본문
스스로 균형을 잡는 이진 탐색 트리, AVL Tree
📌 AVL Tree 탄생 이유
아래와 같은 이진 검색 트리에서는 문제점이 발생한다.
위와 같은 트리는 한 쪽으로 쏠려있어서 원하는 자료를 찾으려면 루트부터 끝까지 탐색을 해야 찾을 수 있음
>> 이러한 한계를 극복하고자 AVL 트리가 탄생함
AVL 트리는 이진 검색 트리이면서 동시에 균형을 유지하고 있습니다.
모든 노드의 왼쪽과 오른쪽 서브트리의 높이 차이가 1 이하입니다.
균형이 무너진 유형에는 4가지가 있습니다. LL, RR, LR, RL
📌 균형잡기 이해하기 좋은 글
[Data Structure] AVL(Adelson-Velsky and Landis) 트리란?
안녕하세요 Foma 💻 입니다! 오늘은 저번에 정리했던 이진 탐색 트리를 더 업그레이드(?)한 자료구조인 AVL 트리에 대해서 알아보도록 하겠습니다. (혹시 이진 탐색 트리에 대해 모르시는 분들은
fomaios.tistory.com
LL(Left Left) case
y는 z의 왼쪽 자식 노드이고, x는 y의 왼쪽 자식 노드인 경우 right rotation을 수행하여 균형을 맞춥니다.
RR(Right Right) case
y는 z의 오른쪽 자식 노드이고, x는 y의 오른쪽 자식 노드인 경우 left rotation을 수행하여 균형을 맞춥니다.
LR(Left Right) case
y는 z의 왼쪽 자식 노드이고, x는 y의 오른쪽 자식 노드인 경우 left , right 순으로 총 두 번의 rotation을 수행하여 균형을 맞춥니다.
RL(Right Left) case
y는 z의 오른쪽 자식 노드이고, x는 y의 왼쪽 자식 노드인 경우, right, left 순으로 총 두번의 rotation을 수행하여 균형을 맞춥니다.
'CS 개념 정리' 카테고리의 다른 글
| [자료구조] 트라이(Trie) 개념 정리 (0) | 2022.10.09 |
|---|---|
| [자료구조] Red-Black Tree 개념 (0) | 2022.10.09 |
| [CS 면접 대비] DFS/BFS 개념 & 파이썬 코드 정리 (0) | 2022.10.09 |
| [CS 면접 대비] 자료구조/알고리즘 비선형 자료구조(Graph, Tree, Binary Tree, Full Binary Tree, Complete Binary Tree,Binary Search Tree) 개념 & 질문 정리 (0) | 2022.10.06 |
| [CS 면접 대비] 자료구조/알고리즘 선형 자료구조(Array, List, HashTable, Queue, Stack) 개념 & 질문 정리 (1) | 2022.10.06 |
