Week 6 of Data structures
드디어 자료구조 마지막 강좌이다.
먼저 binary search tree application에 대해 살펴본다.
데이터를 다룰때 위와 같은 문제 상황이 있을 수 있다.
이때 order statistics를 활용하여 k번째 작은 요소를 반환하는 구성을 가지면 될 것이고,
이에 어떤 subtree에 귀속되어있는지 얼마나 많은 요소가 있는지 확인이 필요하다.
이를 위해 N.size라는 개념을 도입하는데 위의 조건을 항상 만족한다.
그리고 이전에 rotation에 관한 내용을 보았을 때 rotation 작업 후 size는 재계산되어야 한다.
재계산하는 Recompute의 pseudo code이다.
OrderStatistic의 pseudo code이고 재귀함수로 구성되어 Size의 조건에 부합할 때까지 반복하는 것을 알 수 있다.
시간복잡도는 O(h)이며 해당 노드까지의 높이가 되겠다.
그렇다면 노드의 랭크는 어떤식으로 계산할지에 대한 논의가 필요한데,
위와 같은 특정 인덱스 x 이후의 색이 모두 뒤집히는 조건을 가진 배열 문제가 있다고 한다.
이때 필요한 동작들을 정의해보면 위의 3가지 정도로 정리할 수 있겠다.
그리고 여기에 tree 구조를 적용하여 문제해결에 한발 더 도움이 될 수 있다고 한다.
우선 퀴즈를 보면 5번째 작은 요소를 찾는 것인데,
아주 쉽게 D인것을 알 수 있다.
자료구조적으로 이 문제를 해결하기 위해서는 위에서 보았듯 배열의 색깔뒤집기 문제로 해석할 수 있겠다.
그리고 3개 중 하나의 동작인 Flip은 위와 같이 merge와 split 동작을 수반한다.
이제 하나씩 살펴보면 NewArray 함수는 위와 같이 배열을 생성하여 각 고유의 색으로 채운다.
Color는 Find 함수와 같이 해당 키(m번째)를 찾게 된다.
Flip은 트리를 분해하고 이를 다시금 조건에 맞도록 합치게 된다.
이로써 트리는 단순히 찾는 용도로 그치지 않는 것을 알 수 있다.
다음은 splay tree에 대해 알아보겠다.
탐색에 가장좋은 트리구조는 시간복잡도가 O(log(n))인 것을 이미 숙지하고 있다.
트리구조상 균형이 맞지 않는 것과 맞는 것을 비교하면 높이부터 차이가 나는 것을 알 수 있다.
게다가 특정 키값을 탐색할 때에도 균형잡힌 트리가 훨씬 시간이 절약되는것을 보았다.
따라서 불균형한 트리를 쿼리를 통해 맞추는 작업을 진행하는 컨셉으로 시작한다.
우선 위와 같이 아주 불균형한 트리가 존재할 때 rotation을 통해,
위와 같이 꺽어주는 작업을 하게되고,
반복하게 되면 무한 루프에 갇힐 위험이 도사리게 된다.
보완법으로 Zig-Zig 구조나,
Zig-Zag,
Zig 구조를 가진 트리들을 splay tree를 통해 개선할 수 있다.
Splay의 동작 pseudo code이다.
바로 퀴즈가 등장하고 4번 노드를 spalying한다면 어떻게 변화하는지에 대한 질문이다.
2, 3, 4의 연속된 Zig-Zig 형태에서는 2와 자리를 바꾸면서 방향이 한번 꺽이게 되고 이후 5, 1, 4의 Zig-Zag 형태에서는 4를 상단으로 올리며 균형을 맞춰주게 되는 간단한 논리이다.
바로 splay tree 시행에 대한 내용으로 넘어간다.
splay tree 동작이 가끔 느린 케이스가 발생한다고 한다.
따라서 Amotize cost 개념을 여기서도 도입하여 연산한다고 한다. 증명은 차후 optional 영상에 있다.
Find를 Splay tree에 적용한 STFind pseudo code이다.
한 노드의 깊이를 D라고 할 때 N을 찾기까지 O(D)의 시간이 걸리며 splaying을 진행하면 Amortized cost는 O(log(n))이 된다.
만약 k를 찾는데 실패하더라고 가장 근접한 노드에서 splaying을 진행하여야 한다.
이번엔 splay tree insert인 STInsert이다.
Delete의 경우 이전 트리에서 삭제와 비슷하게 삭제하고자하는 키값을 최상단으로 올린 뒤 pop하여 날리고 하단의 노드를 올려주면 된다.
STDelete의 pseudo code이다.
Split의 경우도 똑같은 방식으로 진행되며,
STSplit의 pseudo code이다.
이때 CutLeft는 왼쪽의 subtree를 분해할때 사용된다.
Merge또한 같은 방식이며 왼쪽 트리의 최대키값을 루트로 삼으며,
STMerge의 pseudo code이다.
핵심은 Splay tree의 amortized cost(time)은 O(log(n))이다.
드디어 자료구조 마지막 강좌이다.
먼저 binary search tree application에 대해 살펴본다.
데이터를 다룰때 위와 같은 문제 상황이 있을 수 있다.
이때 order statistics를 활용하여 k번째 작은 요소를 반환하는 구성을 가지면 될 것이고,
이에 어떤 subtree에 귀속되어있는지 얼마나 많은 요소가 있는지 확인이 필요하다.
이를 위해 N.size라는 개념을 도입하는데 위의 조건을 항상 만족한다.
그리고 이전에 rotation에 관한 내용을 보았을 때 rotation 작업 후 size는 재계산되어야 한다.
재계산하는 Recompute의 pseudo code이다.
OrderStatistic의 pseudo code이고 재귀함수로 구성되어 Size의 조건에 부합할 때까지 반복하는 것을 알 수 있다.
시간복잡도는 O(h)이며 해당 노드까지의 높이가 되겠다.
그렇다면 노드의 랭크는 어떤식으로 계산할지에 대한 논의가 필요한데,
위와 같은 특정 인덱스 x 이후의 색이 모두 뒤집히는 조건을 가진 배열 문제가 있다고 한다.
이때 필요한 동작들을 정의해보면 위의 3가지 정도로 정리할 수 있겠다.
그리고 여기에 tree 구조를 적용하여 문제해결에 한발 더 도움이 될 수 있다고 한다.
우선 퀴즈를 보면 5번째 작은 요소를 찾는 것인데,
아주 쉽게 D인것을 알 수 있다.
자료구조적으로 이 문제를 해결하기 위해서는 위에서 보았듯 배열의 색깔뒤집기 문제로 해석할 수 있겠다.
그리고 3개 중 하나의 동작인 Flip은 위와 같이 merge와 split 동작을 수반한다.
이제 하나씩 살펴보면 NewArray 함수는 위와 같이 배열을 생성하여 각 고유의 색으로 채운다.
Color는 Find 함수와 같이 해당 키(m번째)를 찾게 된다.
Flip은 트리를 분해하고 이를 다시금 조건에 맞도록 합치게 된다.
이로써 트리는 단순히 찾는 용도로 그치지 않는 것을 알 수 있다.
다음은 splay tree에 대해 알아보겠다.
탐색에 가장좋은 트리구조는 시간복잡도가 O(log(n))인 것을 이미 숙지하고 있다.
트리구조상 균형이 맞지 않는 것과 맞는 것을 비교하면 높이부터 차이가 나는 것을 알 수 있다.
게다가 특정 키값을 탐색할 때에도 균형잡힌 트리가 훨씬 시간이 절약되는것을 보았다.
따라서 불균형한 트리를 쿼리를 통해 맞추는 작업을 진행하는 컨셉으로 시작한다.
우선 위와 같이 아주 불균형한 트리가 존재할 때 rotation을 통해,
위와 같이 꺽어주는 작업을 하게되고,
반복하게 되면 무한 루프에 갇힐 위험이 도사리게 된다.
보완법으로 Zig-Zig 구조나,
Zig-Zag,
Zig 구조를 가진 트리들을 splay tree를 통해 개선할 수 있다.
Splay의 동작 pseudo code이다.
바로 퀴즈가 등장하고 4번 노드를 spalying한다면 어떻게 변화하는지에 대한 질문이다.
2, 3, 4의 연속된 Zig-Zig 형태에서는 2와 자리를 바꾸면서 방향이 한번 꺽이게 되고 이후 5, 1, 4의 Zig-Zag 형태에서는 4를 상단으로 올리며 균형을 맞춰주게 되는 간단한 논리이다.
바로 splay tree 시행에 대한 내용으로 넘어간다.
splay tree 동작이 가끔 느린 케이스가 발생한다고 한다.
따라서 Amotize cost 개념을 여기서도 도입하여 연산한다고 한다. 증명은 차후 optional 영상에 있다.
Find를 Splay tree에 적용한 STFind pseudo code이다.
한 노드의 깊이를 D라고 할 때 N을 찾기까지 O(D)의 시간이 걸리며 splaying을 진행하면 Amortized cost는 O(log(n))이 된다.
만약 k를 찾는데 실패하더라고 가장 근접한 노드에서 splaying을 진행하여야 한다.
이번엔 splay tree insert인 STInsert이다.
Delete의 경우 이전 트리에서 삭제와 비슷하게 삭제하고자하는 키값을 최상단으로 올린 뒤 pop하여 날리고 하단의 노드를 올려주면 된다.
STDelete의 pseudo code이다.
Split의 경우도 똑같은 방식으로 진행되며,
STSplit의 pseudo code이다.
이때 CutLeft는 왼쪽의 subtree를 분해할때 사용된다.
Merge또한 같은 방식이며 왼쪽 트리의 최대키값을 루트로 삼으며,
STMerge의 pseudo code이다.
핵심은 Splay tree의 amortized cost(time)은 O(log(n))이다.
댓글
댓글 쓰기