스플레이 트리는 자체 균형 또는 자체 조정 이진 검색 트리입니다. 즉, 스플레이 트리는 이진 검색 트리의 변형이라고 말할 수 있습니다. 이진 검색 트리에 대해 알아야 할 스플레이 트리의 전제 조건입니다.
우리가 이미 알고 있듯이 모든 경우에 이진 검색 트리의 시간 복잡도가 있습니다. 평균적인 경우 이진 검색 트리의 시간 복잡도는 다음과 같습니다. 오(로그인) 최악의 경우 시간복잡도는 O(n)이다. 이진 검색 트리에서 왼쪽 하위 트리의 값은 루트 노드보다 작고 오른쪽 하위 트리의 값은 루트 노드보다 큽니다. 그러한 경우 시간 복잡도는 다음과 같습니다. 오(로그인) . 이진 트리가 왼쪽으로 치우치거나 오른쪽으로 치우쳐 있는 경우 시간 복잡도는 O(n)입니다. 왜도를 제한하려면, AVL 및 레드-블랙 트리 사진 속으로 들어와서 O(로그인 ) 모든 경우의 모든 작업에 대한 시간 복잡도. 또한 보다 실용적인 구현을 수행하여 이러한 시간 복잡성을 개선할 수 있으므로 새로운 트리 스플레이 트리란 무엇입니까?
스플레이 트리는 스스로 균형을 잡는 나무이지만, AVL 및 Red-Black 트리도 자체 균형 트리입니다. 두 그루의 나무를 독특하게 만드는 것은 무엇입니까? 이 제품을 독특하게 만드는 또 하나의 추가 속성은 바로 스플레잉(splaying)입니다.
전개 트리에는 다음과 동일한 작업이 포함됩니다. 이진 검색 트리 , 즉 삽입, 삭제 및 검색이지만 여기에는 또 다른 작업, 즉 재생이 포함됩니다. 그래서. 스플레이 트리의 모든 작업 뒤에는 스플레이가 이어집니다.
스플레이 트리는 엄격하게 균형 잡힌 나무는 아니지만 대략적으로 균형 잡힌 나무입니다. splay-tree에서의 검색 작업을 이해해 봅시다.
아래와 같이 트리에서 7개 요소를 검색한다고 가정해 보겠습니다.
스플레이 트리의 요소를 검색하려면 먼저 표준 이진 검색 트리 작업을 수행합니다. 7은 10보다 작으므로 루트 노드의 왼쪽에 올 것입니다. 검색 작업을 수행한 후에는 스플레잉(splaying)을 수행해야 합니다. 여기서 스플레잉(splaying)은 요소에 대해 수행하는 작업이 일부 재배열을 수행한 후 루트 노드가 되어야 함을 의미합니다. 트리의 재배열은 회전을 통해 이루어집니다.
참고: 확산 트리는 요소에 수행된 모든 작업이 트리를 재정렬하여 작업이 수행된 요소가 트리의 루트 노드가 되는 자체 조정 트리로 정의할 수 있습니다.
회전
스플레잉에 사용되는 회전에는 6가지 유형이 있습니다.
- 지그회전(우회전)
- 재그 회전(왼쪽 회전)
- 지그재그(지그 다음에 재그가 이어짐)
- Zag zig(Zag 다음에 zig가 옴)
- Zig zig(우회전 2회)
- 재그재그(왼쪽 2회전)
회전 유형 선택에 필요한 요소
회전 유형을 선택하는 데 사용되는 요소는 다음과 같습니다.
- 회전하려는 노드에 조부모 노드가 있습니까?
- 노드는 부모의 왼쪽 자식입니까, 오른쪽 자식입니까?
- 노드는 조부모의 왼쪽 자식입니까, 오른쪽 자식입니까?
순환 사례
사례 1: 노드에 조부모가 없고 부모의 오른쪽 자식이면 왼쪽 회전을 수행합니다. 그렇지 않으면 오른쪽 회전이 수행됩니다.
사례 2: 노드에 상위 노드가 있는 경우 다음 시나리오를 기반으로 합니다. 회전이 수행됩니다.
시나리오 1: 노드가 부모의 오른쪽이고 부모도 부모의 오른쪽인 경우 지그지그 오른쪽 오른쪽 회전 수행됩니다.
시나리오 2: 노드가 부모의 왼쪽에 있지만 부모가 부모의 오른쪽에 있는 경우 지그재그 오른쪽 왼쪽 회전 수행됩니다.
시나리오 3: 노드가 부모의 오른쪽에 있고 부모가 부모의 오른쪽에 있는 경우 지그 지그 왼쪽 왼쪽 회전 수행됩니다.
시나리오 4: 노드가 부모의 오른쪽에 있지만 부모가 부모의 왼쪽에 있는 경우 지그재그 좌우 회전 수행됩니다.
이제 예시를 통해 위의 회전을 이해해 보겠습니다.
트리를 재배열하려면 몇 가지 회전을 수행해야 합니다. 다음은 전개 트리의 회전 유형입니다.
지그 회전은 검색할 항목이 루트 노드이거나 루트 노드의 자식(즉, 왼쪽 또는 오른쪽 자식)일 때 사용됩니다.
검색 중 스플레이 트리에 존재할 수 있는 경우는 다음과 같습니다.
사례 1: 검색 항목이 트리의 루트 노드인 경우.
사례 2: 검색 항목이 루트 노드의 하위 항목인 경우 다음 두 가지 시나리오가 있습니다.
- 자식이 왼쪽 자식이면 지그 오른쪽 회전이라고 알려진 오른쪽 회전이 수행됩니다.
- 자식이 오른쪽 자식이면 지그 왼쪽 회전이라고 하는 왼쪽 회전이 수행됩니다.
예제를 통해 위의 두 가지 시나리오를 살펴보겠습니다.
아래 예를 고려하십시오.
위의 예에서는 트리에서 7개의 요소를 검색해야 합니다. 우리는 아래 단계를 따를 것입니다:
1 단계: 먼저 7을 루트 노드와 비교합니다. 7은 10보다 작으므로 루트 노드의 왼쪽 자식입니다.
2 단계: 요소가 발견되면 스플레잉(splaying)을 수행합니다. 아래와 같이 7이 트리의 루트 노드가 되도록 오른쪽 회전이 수행됩니다.
또 다른 예를 생각해 봅시다.
위의 예에서는 트리에서 20개의 요소를 검색해야 합니다. 우리는 아래 단계를 따를 것입니다:
1 단계: 먼저 20을 루트 노드와 비교합니다. 20은 루트 노드보다 크므로 루트 노드의 오른쪽 자식입니다.
2 단계: 요소가 발견되면 스플레잉(splaying)을 수행합니다. 20개의 요소가 트리의 루트 노드가 되도록 왼쪽 회전을 수행합니다.
검색 대상이 조부모뿐만 아니라 부모도 있는 경우가 가끔 발생합니다. 이 경우 스플레이를 위해 4번의 회전을 수행해야 합니다.
이 경우를 예를 통해 이해해 보겠습니다.
아래와 같이 트리에서 요소 1개를 검색해야 한다고 가정합니다.
1 단계: 먼저, 1번째 요소를 검색하기 위해 표준 BST 검색 작업을 수행해야 합니다. 1은 10과 7보다 작으므로 노드 7의 왼쪽에 있게 됩니다. 따라서 요소 1에는 상위 요소(7)와 조부모 요소(10)가 있습니다.
2 단계: 이 단계에서는 스플레잉(splaying)을 수행해야 합니다. 몇 가지 회전을 사용하여 노드 1을 루트 노드로 만들어야 합니다. 이 경우 단순히 지그재그 회전을 수행할 수는 없습니다. zig zig 회전을 구현해야 합니다.
노드 1을 루트 노드로 만들려면 지그지그 회전이라는 두 번의 오른쪽 회전을 수행해야 합니다. 오른쪽 회전을 수행하면 아래 그림과 같이 10이 아래로 이동하고 노드 7이 위로 올라옵니다.
다시 한번 오른쪽으로 지그 회전을 수행하면 아래와 같이 노드 7이 아래로 이동하고 노드 1이 위로 올라갑니다.
위 그림에서 알 수 있듯이 노드 1이 트리의 루트 노드가 되었습니다. 따라서 검색이 완료됩니다.
아래 트리에서 20을 검색한다고 가정해 보겠습니다.
20을 검색하려면 왼쪽 회전을 두 번 수행해야 합니다. 20개의 노드를 검색하는 데 필요한 단계는 다음과 같습니다.
1 단계: 먼저 표준 BST 검색 작업을 수행합니다. 20은 10과 15보다 크므로 노드 15의 오른쪽에 있게 됩니다.
2 단계: 두 번째 단계는 스플레잉을 수행하는 것입니다. 이 경우 두 번의 왼쪽 회전이 수행됩니다. 첫 번째 회전에서는 아래와 같이 노드 10이 아래로 이동하고 노드 15가 위로 이동합니다.
두 번째 왼쪽 회전에서는 아래와 같이 노드 15가 아래쪽으로 이동하고 노드 20이 트리의 루트 노드가 됩니다.
우리가 관찰한 바와 같이 두 번의 왼쪽 회전이 수행됩니다. 그래서 그것은 지그 지그 왼쪽 회전으로 알려져 있습니다.
지금까지 우리는 부모와 조부모 모두 RR 또는 LL 관계에 있다는 것을 읽었습니다. 이제 부모와 조부모 사이의 RL 또는 LR 관계를 살펴보겠습니다.
이 경우를 예를 통해 이해해 보겠습니다.
아래 표시된 트리에서 13개의 요소를 검색한다고 가정합니다.
1 단계: 먼저 표준 BST 검색 작업을 수행합니다. 13은 10보다 크고 15보다 작으므로 노드 13은 노드 15의 왼쪽 자식이 됩니다.
2 단계: 노드 13은 15의 왼쪽에 있고 노드 15는 노드 10의 오른쪽에 있으므로 RL 관계가 존재합니다. 먼저 노드 15에서 오른쪽 회전을 수행하면 아래와 같이 15가 아래로 이동하고 노드 13이 위로 올라갑니다.
그래도 노드 13은 루트 노드가 아니고, 13은 루트 노드의 오른쪽에 있으므로 재그 회전이라고 하는 왼쪽 회전을 수행하겠습니다. 아래와 같이 노드 10이 아래로 이동하고 13이 루트 노드가 됩니다.
위의 트리에서 볼 수 있듯이 노드 13이 루트 노드가 되었습니다. 따라서 검색이 완료됩니다. 이 경우 먼저 지그 회전을 수행한 다음 재그 회전을 수행했습니다. 그래서 지그재그 회전이라고 합니다.
이 경우를 예를 통해 이해해 보겠습니다.
아래와 같이 트리에서 9개 요소를 검색한다고 가정해 보겠습니다.
1 단계: 먼저 표준 BST 검색 작업을 수행합니다. 9는 10보다 작고 7보다 크므로 노드 7의 오른쪽 자식이 됩니다.
2 단계: 노드 9는 노드 7의 오른쪽에 있고 노드 7은 노드 10의 왼쪽에 있으므로 LR 관계가 존재합니다. 먼저 노드 7에서 왼쪽 회전을 수행합니다. 아래와 같이 노드 7은 아래로 이동하고 노드 9는 위로 이동합니다.
여전히 노드 9는 루트 노드가 아니고, 9는 루트 노드의 왼쪽에 있으므로 지그 회전이라는 오른쪽 회전을 수행하겠습니다. 오른쪽 회전을 수행한 후 아래와 같이 노드 9가 루트 노드가 됩니다.
위의 트리에서 볼 수 있듯이 노드 13은 루트 노드입니다. 따라서 검색이 완료됩니다. 이 경우에는 먼저 재그 회전(왼쪽 회전)을 수행한 후 지그 회전(오른쪽 회전)을 수행하므로 이를 재그 지그 회전이라고 합니다.
스플레이트리의 장점
- 스플레이 트리에서는 추가 정보를 저장할 필요가 없습니다. 대조적으로, AVL 트리에서는 추가 공간이 필요한 각 노드의 균형 요소를 저장해야 하며, Red-Black 트리도 노드의 색상(Red 또는 Black)을 나타내는 추가 정보 1비트를 저장해야 합니다.
- 다양한 실제 응용을 위한 가장 빠른 유형의 이진 검색 트리입니다. 그것은에서 사용됩니다 Windows NT 및 GCC 컴파일러 .
- 자주 액세스하는 노드가 루트 노드에 더 가깝게 이동하므로 플레이 트리에서 요소에 빠르게 액세스할 수 있으므로 더 나은 성능을 제공합니다. 최근에 접근한 데이터를 캐시에 저장하기 때문에 캐시 구현에 사용되는데, 데이터에 접근하기 위해 메모리로 갈 필요가 없고 시간도 덜 걸린다.
스플레이 트리의 단점
스플레이 트리의 주요 단점은 트리가 엄격하게 균형을 이루지 않는다는 것입니다. 즉, 대략적으로 균형이 잡혀 있다는 것입니다. 때로는 스플레이 트리가 선형이므로 O(n) 시간 복잡도가 소요됩니다.
Splay 트리에 삽입 작업
에서 삽입 작업을 수행하려면 먼저 트리에 요소를 삽입한 다음 삽입된 요소에 대해 splaying 작업을 수행합니다.
15, 10, 17, 7
1 단계: 먼저 트리에 노드 15를 삽입합니다. 삽입 후에는 스플레잉(splaying)을 수행해야 합니다. 15는 루트 노드이므로 스플레이를 수행할 필요가 없습니다.
2 단계: 다음 요소는 10입니다. 10은 15보다 작으므로 아래와 같이 노드 10이 노드 15의 왼쪽 자식이 됩니다.
이제 우리는 공연을 합니다 튀는 . 10을 루트 노드로 만들기 위해 아래와 같이 오른쪽 회전을 수행합니다.
3단계: 다음 요소는 17입니다. 17은 10과 15보다 크므로 노드 15의 오른쪽 자식이 됩니다.
이제 스플레잉을 해보겠습니다. 17에는 조부모와 부모가 있으므로 지그지그 회전을 수행합니다.
위 그림에서 17이 트리의 루트 노드가 되는 것을 볼 수 있습니다. 따라서 삽입이 완료되었습니다.
4단계: 다음 요소는 7입니다. 7은 17, 15, 10보다 작으므로 노드 7은 10의 자식이 됩니다.
이제 트리를 펼쳐야 합니다. 7에는 조부모와 부모가 있으므로 아래와 같이 두 번의 오른쪽 회전을 수행합니다.
여전히 노드 7은 루트 노드가 아니며 루트 노드의 왼쪽 자식, 즉 17입니다. 따라서 노드 7을 루트 노드로 만들려면 아래와 같이 오른쪽 회전을 한 번 더 수행해야 합니다.
삽입 연산을 위한 알고리즘
Insert(T, n) temp= T_root y=NULL while(temp!=NULL) y=temp if(n->data data) temp=temp->left else temp=temp->right n.parent= y if(y==NULL) T_root = n else if (n->data data) y->left = n else y->right = n Splay(T, n)
위의 알고리즘에서 T는 트리이고 n은 삽입하려는 노드입니다. 루트 노드의 주소를 포함하는 임시 변수를 만들었습니다. temp 값이 NULL이 될 때까지 while 루프를 실행합니다.
삽입이 완료되면 스플레잉(splaying)이 수행됩니다.
스플레잉 작업을 위한 알고리즘
Splay(T, N) while(n->parent !=Null) if(n->parent==T->root) if(n==n->parent->left) right_rotation(T, n->parent) else left_rotation(T, n->parent) else p= n->parent g = p->parent if(n=n->parent->left && p=p->parent->left) right.rotation(T, g), right.rotation(T, p) else if(n=n->parent->right && p=p->parent->right) left.rotation(T, g), left.rotation(T, p) else if(n=n->parent->left && p=p->parent->right) right.rotation(T, p), left.rotation(T, g) else left.rotation(T, p), right.rotation(T, g) Implementation of right.rotation(T, x) right.rotation(T, x) y= x->left x->left=y->right y->right=x return y
위 구현에서 x는 회전이 수행되는 노드이고 y는 노드 x의 왼쪽 자식입니다.
left.rotation(T, x) 구현
left.rotation(T, x) y=x->right x->right = y->left y->left = x return y
위 구현에서 x는 회전이 수행되는 노드이고 y는 노드 x의 오른쪽 자식입니다.
Splay 트리에서 삭제
스플레이 트리는 이진 검색 트리의 변형이므로 스플레이 트리의 삭제 작업은 BST와 유사하지만 유일한 차이점은 스플레이 트리에서 삭제 작업 뒤에 스플레잉 작업이 수행된다는 점입니다.
삭제 유형:
표시 트리에는 두 가지 유형의 삭제가 있습니다.
- 상향식 스플레잉
- 하향식 스플레이
상향식 스플레잉
상향식 스플레이에서는 먼저 트리에서 요소를 삭제한 다음 삭제된 노드에서 스플레잉을 수행합니다.
Splay 트리에서의 삭제를 이해해 봅시다.
아래 표시된 트리에서 12, 14를 삭제한다고 가정합니다.
자바는 같다
- 먼저 표준 BST 삭제 작업을 수행하여 12개 요소를 삭제합니다. 12는 리프 노드이므로 간단히 트리에서 노드를 삭제합니다.
아직 삭제가 완료되지 않았습니다. 삭제된 노드의 상위 노드(예: 10)를 표시해야 합니다. 스플레이(10) 나무에. 위의 트리에서 볼 수 있듯이 10은 노드 7의 오른쪽에 있고 노드 7은 노드 13의 왼쪽에 있습니다. 따라서 먼저 노드 7에서 왼쪽 회전을 수행한 다음 노드에서 오른쪽 회전을 수행합니다. 13, 아래와 같이 :
하지만 노드 10은 루트 노드가 아닙니다. 노드 10은 루트 노드의 왼쪽 자식입니다. 따라서 아래와 같이 노드 10을 루트 노드로 만들기 위해 루트 노드, 즉 14에서 오른쪽 회전을 수행해야 합니다.
- 이제 아래와 같이 트리에서 14개 요소를 삭제해야 합니다.
우리는 내부 노드를 단순히 삭제할 수 없다는 것을 알고 있습니다. 우리는 다음 중 하나를 사용하여 노드의 값을 대체합니다. 중위 선행자 또는 후임자 . 값을 오른쪽 하위 트리에 존재하는 가장 낮은 값으로 바꾸는 중위 후속자를 사용한다고 가정합니다. 노드 14의 오른쪽 하위 트리에서 가장 낮은 값은 15이므로 값 14를 15로 바꿉니다. 노드 14가 리프 노드가 되므로 아래와 같이 간단히 삭제할 수 있습니다.
그래도 삭제가 완료되지 않았습니다. 삭제된 노드의 상위 노드를 루트 노드로 만드는 스플레이(splaying) 작업을 하나 더 수행해야 합니다. 삭제하기 전에는 노드 14의 상위 노드가 루트 노드(예: 10)였으므로 이 경우에는 스플레이를 수행해야 합니다.
하향식 스플레이
하향식 스플레이에서는 먼저 삭제가 수행될 스플레이를 수행한 다음 트리에서 노드를 삭제합니다. 요소가 삭제되면 결합 작업을 수행합니다.
예를 통해 하향식 확장을 이해해 보겠습니다.
아래 표시된 트리에서 16개를 삭제한다고 가정합니다.
1 단계: 하향식 스플레이에서는 먼저 노드 16에서 스플레이를 수행합니다. 노드 16에는 상위 노드와 조부모 노드가 모두 있습니다. 노드 16은 상위 노드의 오른쪽에 있고 상위 노드도 상위 노드의 오른쪽에 있으므로 이는 재그재그 상황입니다. 이 경우 먼저 아래와 같이 노드 13과 14에서 왼쪽 회전을 수행합니다.
노드 16은 아직 루트 노드가 아니며 루트 노드의 오른쪽 자식이므로 노드 16을 루트 노드로 만들기 위해 노드 12에 대해 왼쪽 회전을 수행해야 합니다.
노드 16이 루트 노드가 되면 노드 16을 삭제하고 아래와 같이 두 개의 서로 다른 트리, 즉 왼쪽 하위 트리와 오른쪽 하위 트리를 얻게 됩니다.
우리가 알고 있듯이 왼쪽 하위 트리의 값은 항상 오른쪽 하위 트리의 값보다 작습니다. 왼쪽 하위 트리의 루트는 12이고 오른쪽 하위 트리의 루트는 17입니다. 첫 번째 단계는 왼쪽 하위 트리에서 최대 요소를 찾는 것입니다. 왼쪽 하위 트리에서 최대 요소는 15이며, 15에 대해 확장 작업을 수행해야 합니다.
위의 트리에서 볼 수 있듯이 요소 15에는 조부모뿐만 아니라 부모도 있습니다. 노드는 상위 노드의 오른쪽에 있고 상위 노드도 상위 노드의 오른쪽에 있으므로 아래와 같이 노드 15를 루트 노드로 만들기 위해 두 번의 왼쪽 회전을 수행해야 합니다.
트리에서 두 번의 회전을 수행한 후 노드 15가 루트 노드가 됩니다. 보시다시피 15의 오른쪽 자식은 NULL이므로 아래와 같이 15의 오른쪽 부분에 노드 17을 연결하고 이 작업을 가입하다 작업.
참고: 삭제할 요소가 표시 트리에 없으면 표시가 수행됩니다. NULL에 도달하기 전에 마지막으로 액세스한 요소에서 스플레잉이 수행됩니다.
삭제 작업의 알고리즘
If(root==NULL) return NULL Splay(root, data) If data!= root->data Element is not present If root->left==NULL root=root->right else temp=root Splay(root->left, data) root1->right=root->right free(temp) return root
위의 알고리즘에서는 먼저 루트가 Null인지 여부를 확인합니다. 루트가 NULL이면 트리가 비어 있음을 의미합니다. 트리가 비어 있지 않으면 삭제할 요소에 대해 확산 작업을 수행합니다. 확장 작업이 완료되면 루트 데이터를 삭제할 요소와 비교합니다. 둘 다 같지 않으면 해당 요소가 트리에 존재하지 않는다는 의미입니다. 동일하면 다음과 같은 경우가 발생할 수 있습니다.
사례 1 : 루트의 왼쪽이 NULL이고, 루트의 오른쪽이 루트 노드가 됩니다.
사례 2 : 왼쪽과 오른쪽이 모두 존재하면 왼쪽 하위 트리에 최대 요소를 표시합니다. 스플레잉이 완료되면 최대 요소가 왼쪽 하위 트리의 루트가 됩니다. 오른쪽 하위 트리는 왼쪽 하위 트리 루트의 오른쪽 하위 트리가 됩니다.