AVL 트리에서 노드를 삭제하는 것은 이진 검색 트리에서와 유사합니다. 삭제는 AVL 트리의 균형 요소를 교란할 수 있으므로 AVL 특성을 유지하려면 트리의 균형을 다시 조정해야 합니다. 이를 위해서는 회전을 수행해야 합니다. 회전에는 L회전과 R회전이 있습니다. 여기서는 R 회전에 대해 설명하겠습니다. L 회전은 그 거울상입니다.

삭제할 노드가 임계 노드의 왼쪽 하위 트리에 있으면 L 회전을 적용하고, 그렇지 않으면 삭제할 노드가 임계 노드의 오른쪽 하위 트리에 있으면 L 회전을 적용해야 합니다. , R 회전이 적용됩니다.

A는 임계 노드이고 B는 왼쪽 하위 트리의 루트 노드라고 가정해 보겠습니다. A의 오른쪽 하위 트리에 있는 노드 X가 삭제되는 경우 세 가지 상황이 있을 수 있습니다.

R0 회전(노드 B의 균형 요소는 0 )

노드 B의 균형 인자가 0이고 노드 X 삭제 시 노드 A의 균형 인자가 교란되면 R0 회전을 사용하여 트리를 회전시켜 트리의 균형을 재조정합니다.

임계 노드 A는 오른쪽으로 이동하고 노드 B는 T1이 왼쪽 하위 트리인 트리의 루트가 됩니다. 하위 트리 T2와 T3는 노드 A의 왼쪽 및 오른쪽 하위 트리가 됩니다. R0 회전과 관련된 프로세스는 다음 이미지에 표시됩니다.

예:

다음 이미지에 표시된 AVL 트리에서 노드 30을 삭제합니다.

해결책

이 경우 노드 B의 균형 요소는 0이므로 다음 그림과 같이 R0 회전을 사용하여 트리가 회전됩니다. 노드 B(10)가 루트가 되고, 노드 A는 오른쪽으로 이동합니다. 이제 노드 B의 오른쪽 자식이 노드 A의 왼쪽 자식이 됩니다.

둥근 수학 자바

R1 회전(노드 B의 균형 요소는 1임)

R1 회전은 노드 B의 균형 요소가 1인 경우 수행됩니다. R1 회전에서 임계 노드 A는 하위 트리 T2 및 T3을 각각 왼쪽 및 오른쪽 자식으로 사용하여 오른쪽으로 이동합니다. T1은 노드 B의 왼쪽 하위 트리로 배치됩니다.

R1 회전과 관련된 프로세스는 다음 이미지에 표시됩니다.

예

다음 이미지에 표시된 AVL 트리에서 노드 55를 삭제합니다.

해결책 :

AVL 트리에서 55를 삭제하면 노드 50, 즉 임계 노드가 되는 노드 A의 균형 요소가 교란됩니다. 이는 노드 A가 오른쪽으로 이동하는 R1 회전 조건입니다(아래 이미지 참조). 이제 B의 오른쪽이 A의 왼쪽이 됩니다(예: 45).

솔루션과 관련된 프로세스는 다음 이미지에 나와 있습니다.

R-1 회전(노드 B의 균형 계수는 -1임)

R-1 회전은 노드 B의 균형 인자가 -1인 경우 수행됩니다. 이 경우는 LR 회전과 동일한 방식으로 처리됩니다. 이 경우 노드 B의 오른쪽 자식인 노드 C는 트리의 루트 노드가 되며 각각 왼쪽과 오른쪽 자식인 B와 A를 갖습니다.

하위 트리 T1, T2는 B의 왼쪽 및 오른쪽 하위 트리가 되고, T3, T4는 A의 왼쪽 및 오른쪽 하위 트리가 됩니다.

문자열.java의 값

R-1 회전과 관련된 프로세스는 다음 이미지에 표시됩니다.

예

다음 이미지에 표시된 AVL 트리에서 노드 60을 삭제합니다.

해결책:

이 경우 노드 B의 균형 요소는 -1입니다. 노드(60)를 삭제하면 노드(50)의 균형 요소가 교란되므로 R-1 회전이 필요합니다. 노드 C, 즉 45는 노드 B(40)와 A(50)를 왼쪽 및 오른쪽 자식으로 갖는 트리의 루트가 됩니다.