AVL 나무는 1962년 GM Adelson, Velsky 및 EM Landis에 의해 발명되었습니다. 이 나무는 발명가를 기리기 위해 AVL로 명명되었습니다.
100개 중 10개
AVL 트리는 각 노드가 왼쪽 하위 트리의 높이에서 오른쪽 하위 트리의 높이를 빼서 계산되는 균형 인자와 연관된 높이 균형 이진 검색 트리로 정의될 수 있습니다.
각 노드의 균형 요소가 -1에서 1 사이에 있으면 트리가 균형을 이룬다고 하며, 그렇지 않으면 트리가 불균형하므로 균형을 맞춰야 합니다.
균형 요소(k) = 높이(왼쪽(k)) - 높이(오른쪽(k))
임의의 노드의 균형 인자가 1이면 왼쪽 하위 트리가 오른쪽 하위 트리보다 한 수준 높다는 의미입니다.
임의의 노드의 균형 인자가 0이면 왼쪽 하위 트리와 오른쪽 하위 트리의 높이가 동일하다는 의미입니다.
어떤 노드의 균형 요소가 -1이면 왼쪽 하위 트리가 오른쪽 하위 트리보다 한 수준 낮다는 의미입니다.
AVL 트리는 다음 그림에 나와 있습니다. 각 노드와 관련된 균형 요소는 -1과 +1 사이에 있음을 알 수 있습니다. 따라서 이는 AVL 트리의 예입니다.
복잡성
| 연산 | 평균 사례 | 최악의 경우 |
|---|---|---|
| 공간 | 에) | 에) |
| 찾다 | 오(로그 n) | 오(로그 n) |
| 끼워 넣다 | 오(로그 n) | 오(로그 n) |
| 삭제 | 오(로그 n) | 오(로그 n) |
AVL 트리 작업
AVL 트리는 이진 검색 트리이기도 하므로 모든 작업은 이진 검색 트리에서 수행되는 것과 동일한 방식으로 수행됩니다. 검색 및 순회는 AVL 트리의 속성 위반으로 이어지지 않습니다. 그러나 삽입과 삭제는 이 속성을 위반할 수 있는 작업이므로 다시 검토할 필요가 있습니다.
| SN | 작업 | 설명 |
|---|---|---|
| 1 | 삽입 | AVL 트리에 대한 삽입은 이진 검색 트리에서 수행되는 것과 동일한 방식으로 수행됩니다. 그러나 AVL 트리 속성에 위반이 발생할 수 있으므로 트리 균형 조정이 필요할 수 있습니다. 회전을 적용하여 트리의 균형을 맞출 수 있습니다. |
| 2 | 삭제 | 삭제 역시 이진 탐색 트리에서와 동일한 방식으로 수행될 수 있다. 삭제는 트리의 균형을 방해할 수도 있으므로 트리의 균형을 재조정하기 위해 다양한 유형의 회전이 사용됩니다. |
왜 AVL 트리인가?
AVL 트리는 이진 검색 트리가 기울어지지 않도록 하여 높이를 제어합니다. 높이 h의 이진 검색 트리에서 모든 작업에 소요되는 시간은 다음과 같습니다. 오) . 그러나 다음으로 확장될 수 있습니다. 에) BST가 왜곡되는 경우(즉, 최악의 경우) 이 높이를 log n으로 제한함으로써 AVL 트리는 각 작업에 상한을 부과합니다. O(로그 n) 여기서 n은 노드 수입니다.
AVL 회전
Balance Factor가 다음과 다른 경우에만 AVL 트리에서 회전을 수행합니다. -1, 0, 1 . 기본적으로 다음과 같은 네 가지 유형의 회전이 있습니다.
- L L 회전: 삽입된 노드는 A의 왼쪽 하위 트리의 왼쪽 하위 트리에 있습니다.
- R R 회전 : 삽입된 노드는 A의 오른쪽 하위 트리의 오른쪽 하위 트리에 있습니다.
- L R 회전 : 삽입된 노드는 A의 왼쪽 하위 트리의 오른쪽 하위 트리에 있습니다.
- R L 회전 : 삽입된 노드는 A의 오른쪽 하위 트리의 왼쪽 하위 트리에 있습니다.
여기서 노드 A는 균형 요소가 -1, 0, 1이 아닌 노드입니다.
처음 두 회전 LL과 RR은 단일 회전이고 다음 두 회전 LR과 RL은 이중 회전입니다. 나무가 불균형하려면 최소 높이가 2 이상이어야 합니다. 각 회전을 이해해 봅시다.
1. RR 로테이션
BST가 불균형 상태가 되면 A의 오른쪽 하위 트리의 오른쪽 하위 트리에 노드가 삽입되어 RR 회전을 수행합니다. RR 회전은 반시계 방향 회전으로 균형 인자가 -2인 노드 아래의 가장자리에 적용됩니다.
위의 예에서 노드 C는 A 오른쪽 하위 트리의 오른쪽 하위 트리에 삽입되었으므로 노드 A의 균형 계수는 -2입니다. A 아래 가장자리에서 RR 회전을 수행합니다.
2. LL 회전
BST가 불균형 상태가 되면 C의 왼쪽 하위 트리의 왼쪽 하위 트리에 노드가 삽입되어 LL 회전을 수행합니다. LL 회전은 시계 방향 회전이며 이는 균형 인자 2를 갖는 노드 아래의 가장자리에 적용됩니다.
위의 예에서 노드 C는 노드 A가 C 왼쪽 하위 트리의 왼쪽 하위 트리에 삽입되었으므로 균형 요소 2를 갖습니다. A 아래 가장자리에서 LL 회전을 수행합니다.
3. LR 회전
이중 회전은 위에서 이미 설명한 단일 회전보다 약간 더 어렵습니다. LR 회전 = RR 회전 + LL 회전, 즉 첫 번째 RR 회전은 하위 트리에서 수행되고 그 다음 LL 회전은 전체 트리에서 수행됩니다. 전체 트리란 삽입된 노드의 경로에서 균형 요소가 -1이 아닌 첫 번째 노드를 의미합니다. , 0 또는 1.
strsep
각 단계를 매우 명확하게 이해해 보겠습니다.
| 상태 | 행동 |
|---|---|
 | 노드 B가 C의 왼쪽 하위 트리인 A의 오른쪽 하위 트리에 삽입되었습니다. 이로 인해 C는 균형 인자 2를 갖는 불균형 노드가 되었습니다. 이 경우는 L R 회전입니다. 삽입된 노드는 왼쪽 하위 트리의 오른쪽 하위 트리에 있습니다. 씨 |
 | LR 회전 = RR + LL 회전이므로 A에 루트가 있는 하위 트리의 RR(시계 반대 방향)이 먼저 수행됩니다. RR 회전을 함으로써 노드 ㅏ , 의 왼쪽 하위 트리가 되었습니다. 비 . |
 | RR 회전을 수행한 후에도 노드 C는 여전히 불균형 상태입니다. 즉, 삽입된 노드 A가 왼쪽에 있기 때문에 균형 요소 2를 갖습니다. 씨 |
 | 이제 전체 트리, 즉 노드 C에서 LL 시계 방향 회전을 수행합니다. 씨 이제 노드 B의 오른쪽 하위 트리가 되고, A는 B의 왼쪽 하위 트리가 됩니다. |
 | 각 노드의 균형 요소는 이제 -1, 0 또는 1입니다. 즉, 이제 BST가 균형을 이루고 있습니다. |
4. RL 회전
이미 논의한 바와 같이, 그 이중 회전은 이미 위에서 설명한 단일 회전보다 조금 더 어렵습니다. R L 회전 = LL 회전 + RR 회전, 즉 첫 번째 LL 회전은 하위 트리에서 수행되고 그 다음 RR 회전은 전체 트리에서 수행됩니다. 전체 트리란 삽입된 노드의 경로에서 균형 요소가 -1이 아닌 첫 번째 노드를 의미합니다. , 0 또는 1.
| 상태 | 행동 |
|---|---|
 | 노드 비 왼쪽 하위 트리에 삽입되었습니다. 씨 오른쪽 하위 트리 ㅏ , 이로 인해 A는 균형 요소 - 2를 갖는 불균형 노드가 되었습니다. 이 경우는 RL 회전입니다. 삽입된 노드는 A의 오른쪽 하위 트리의 왼쪽 하위 트리에 있습니다. |
 | RL 회전 = LL 회전 + RR 회전이므로 루트에 있는 하위 트리의 LL(시계 방향) 씨 먼저 수행됩니다. RR 회전을 함으로써 노드 씨 의 올바른 하위 트리가 되었습니다. 비 . |
 | LL 회전을 수행한 후 노드 ㅏ 즉, 오른쪽 하위 트리 노드 A의 오른쪽 하위 트리로 인해 균형 요소가 -2입니다. |
 | 이제 전체 트리, 즉 노드 A에서 RR 회전(반시계 방향 회전)을 수행합니다. 씨 이제 노드 B의 오른쪽 하위 트리가 되고 노드 A는 B의 왼쪽 하위 트리가 됩니다. |
 | 각 노드의 균형 요소는 이제 -1, 0 또는 1입니다. 즉, 이제 BST가 균형을 이루고 있습니다. |
Q: 다음 요소를 포함하는 AVL 트리를 구성합니다.
H, I, J, B, A, E, C, F, D, G, K, L
1. H, I, J 삽입
위의 요소를 삽입하면, 특히 H의 경우 H의 Balance Factor가 -2이므로 BST가 불균형해집니다. BST는 오른쪽으로 치우쳐 있으므로 노드 H에서 RR 회전을 수행합니다.
결과 잔액 트리는 다음과 같습니다.
자바 문자열 클래스
2. B, A 삽입
위의 요소를 삽입할 때, 특히 A의 경우 H의 Balance Factor가 2이고 I가 2이므로 BST가 불균형해집니다. 마지막으로 삽입된 노드의 첫 번째 노드인 H를 고려합니다. H의 BST는 왼쪽으로 치우쳐 있으므로, 노드 H에서 LL 회전을 수행합니다.
결과 잔액 트리는 다음과 같습니다.
3. E를 삽입하세요
E를 삽입하면 I의 균형 요소가 2이므로 BST는 불균형이 됩니다. E에서 I로 이동하면 I의 오른쪽 하위 트리의 왼쪽 하위 트리에 삽입되어 노드 I에서 LR 회전을 수행하기 때문입니다. LR = RR + LL 회전
3 a) 먼저 노드 B에서 RR 회전을 수행합니다.
RR 회전 후 결과 트리는 다음과 같습니다.
3b) 먼저 노드 I에서 LL 회전을 수행합니다.
LL 회전 후 결과 균형 트리는 다음과 같습니다.
4. C, F, D 삽입
C, F, D를 삽입하면 B와 H의 균형 요소가 -2이므로 BST는 불균형이 됩니다. D에서 B로 이동하면 B의 왼쪽 하위 트리의 오른쪽 하위 트리에 삽입된 것을 발견하므로 다음을 수행합니다. 노드 I의 RL 회전. RL = LL + RR 회전.
4a) 먼저 노드 E에서 LL 회전을 수행합니다.
LL 회전 후 결과 트리는 다음과 같습니다.
컴퓨터의 종류
4b) 그런 다음 노드 B에서 RR 회전을 수행합니다.
RR 회전 후 결과 균형 트리는 다음과 같습니다.
5. G 삽입
G를 삽입할 때 H의 Balance Factor가 2이므로 BST는 불균형이 됩니다. G에서 H로 이동하면 H의 오른쪽 하위 트리의 왼쪽 하위 트리에 삽입되어 노드 I에서 LR 회전을 수행하기 때문입니다. LR = RR + LL 회전.
VLC 유튜브 비디오 다운로드
5 a) 먼저 노드 C에서 RR 회전을 수행합니다.
RR 회전 후 결과 트리는 다음과 같습니다.
5 b) 그런 다음 노드 H에서 LL 회전을 수행합니다.
LL 회전 후 결과 균형 트리는 다음과 같습니다.
6. K를 삽입하세요
K를 삽입하면 I의 균형 요소가 -2이므로 BST가 불균형해집니다. BST는 I에서 K로 오른쪽으로 치우쳐 있으므로 노드 I에서 RR 회전을 수행합니다.
RR 회전 후 결과 균형 트리는 다음과 같습니다.
7. L 삽입
L 트리를 삽입하면 각 노드의 균형 요소가 이제 -1, 0, +1이므로 여전히 균형이 유지됩니다. 따라서 트리는 균형 잡힌 AVL 트리입니다.
