Week 5 of Data structures - AVL trees
이번 강의에서는 AVL tree에 관한 내용을 습득했다.
이번 강의의 목표는 노드의 높이를 이해하고 AVL 특성을 아는 것이다. AVL tree는 Adelson-Velskii, Landis가 제안한 모형이라고 한다.
이전 강좌에서 배운 Balance라는 개념에 대해 상기하는데 항상 balance를 맞추는 것이 복잡도를 낮추는 효과적인 방법이다.
Balance를 맞출 때 가장 쉽게 판단할 수 있는 근거는 높이로 이제까지 보아왔듯 자기자신의 높이를 1로 두고 자식노드로 뻗어나갈 때마다 높이가 1씩 증가하게 된다.
위와 같이 표시된 노드의 높이를 계산하는 퀴즈가 나왔고,
쉽게 계산할 수 있겠지만 6이 될 것이다.
그리고 높이를 계산하는 정의로는 위와 같이 표기할 수 있겠으며,
이제 노드에는 parent, key, left, right 뿐만아니라 높이에 해당하는 height 정보까지 저장하게된다.
이제 한 노드에서 subtree들의 높이가 동일하도록 balance를 맞추는 것이 목적이되며,
이를 맞추기위한 AVL 특성을 정의하게 된다. 한 노드에서 자식노드들의 높이 차이가 1 이내일 때 balance가 확보되었다라고 할 수 있겠다.
AVL 특성에 따라 높이의 복잡도는 O(log(n))이 된다.
N 노드가 AVL 특성을 만족하는 binary tree에 존재할 때 높이 h 는 N.height으로 표기하고 이때 N의 subtree의 높이는 적어도 피보나치 수인 Fh이다.
Fn 수열을 표시하면 위와 같고,
증명은 위와 같이 가능하다.
아주 큰 subtree의 높이는 최소 2^h/2가 된다.
결론적으로 AVL 특성을 유지하려면 이를 시행하는 시간 복잡도는 O(log(n))이 된다.
다음은 AVL 특성을 만족하는 또는 만족하도록 rebalancing을 통해 완성한 AVL tree를 다뤄본다.
우선 위와 같은 AVL 특성을 만족하는 tree가 존재할때,
최우측 자식노드아래에 자식노드가 추가된다면 AVL 특성을 파괴하게 되는 문제가 발생한다. (노드 내 숫자는 높이)
추가가 되었을 때 높이가 갱신된 모습.
새로 추가된 노드축에 속한 노드들만 높이가 갱신된 것을 확인할 수 있다.
이 때 동일한 문제의 퀴즈가 등장하는데 AVL 특성에 맞도록 rebalnce가 필요한 상태가 되는 곳은 어디인가? 라는 문제이며 A, B, C는 재조정이 필요없지만 D의 경우 위와 같이 재조정이 필요해진다.
따라서 AVL 특성을 유지할 수 있도록 재조정이 가능해지게 노드를 삽입하는 알고리즘을 알아본다.
AVLInsert는 위와 같은 pseudo code를 가지며,
Rebalancing은 자식노드들의 높이 차이가 1 이하일 때는 일어나지 않으며,
높이 차이가 2이상일 때 수행된다.
Rebalance의 pseudo code이며,
AdjustHeight은 rebalance가 된 후 재조정 된 높이값을 다시 넣어주게 된다.
다시 Rebalancing의 메카니즘으로 돌아와서 만약 왼쪽 노드의 높이가 더 무거울 경우 오른쪽으로 회전시킨다는 개념으로 보면된다.
Bad case는 이와 같은 경우에 동작하지 않는 것을 보여주고,
위와 같은 순서로 rotation이 진행 될 수 있다.
RebalanceRight의 pseudo code는 위와 같다.
이전 Delete에 대해 상기시키자면 간단히 삭제하는 키값을 최상단으로 보내면서 동시에 자식노드를 상위로 올리면 됐었다.
AVLDelete도 비슷하게 동작하며 위와 같은 pseudo code 형식을 보인다.
마지막으로 merging과 splitting이 AVL tree에서 어떻게 동작하는지 보겠다.
Merge는 두개의 트리는 하나로 합치는 것이고 split는 하나의 트리를 두개로 쪼개는 것이다.
먼저 Merge를 살펴보면 입력은 R1, R2를 루트로 가지는 트리가 있고 R1의 키가 R2보다 작을 경우 출력은 새로운 루트를 통해 두개의 트리가 합쳐진다.
바로 퀴즈가 등장하며 위에 등장한 트리와 병합이 가능한 트리를 고르는 것인데,
위의 정의에 부합하는 것은 A밖에 없다. B, C에서 하나씩 조건에 맞지않는 키값들이 있다.
이제 새로는 루트는 위와 같이 두개의 루트를 연결하는 모습이되겠으며,
MergeWithRoot의 pseudo code는 위와 같은 모습이 된다.
Get Root는 위처럼 왼쪽루트의 가장 큰 값을 가진 노드를 루트로 올리게 된다.
따라서 Merge는 위와 같은 순서로 진행이 됨을 알 수 있다.
Merge가 진행되는 순서를 다시금 도식화하여 보여주게 된다.
하지만 balance가 맞지 않을 수 있다는 단점이 나타나는데,
이를 해결하기 위해 병합하고자 하는 트리와 높이가 같은 subtree에서 병합을 진행하면 쉽게 해결된다.
이를 고려한 AVLTreeMergeWithRoot의 pseudo code이며,
병합의 내용은 여기까지이다.
각 스텝은 높이를 변경할 때 시간복잡도가 O(lR1.Height - R2.Heightl + 1)이 된다.
이번엔 Split이며 단순히 분리하고자하는 기준점에서 subtree를 분리할 수 있겠다.
정의를 보면 key x 인 Root R이 입력일 때 x보다 작은 원소들로 이루어진 트리하나와 보다 큰 원소들로 이루어진 트리 하나가 출력된다.
x값을 찾아나서서 subtree들을 병합한 것에 반대되는 순서라고 생각하면 될 듯하다.
Split의 pseudo code이며,
AVLMergeWithRoot로 균형을 유지하며 이에 대한 시간 복잡도는 위와 같다.
결론에서 볼 수 ㅇ씨듯 Merge와 Split의 동작을 알고 시간복잡도를 확인하였다.
이번 강의에서는 AVL tree에 관한 내용을 습득했다.
이번 강의의 목표는 노드의 높이를 이해하고 AVL 특성을 아는 것이다. AVL tree는 Adelson-Velskii, Landis가 제안한 모형이라고 한다.
이전 강좌에서 배운 Balance라는 개념에 대해 상기하는데 항상 balance를 맞추는 것이 복잡도를 낮추는 효과적인 방법이다.
Balance를 맞출 때 가장 쉽게 판단할 수 있는 근거는 높이로 이제까지 보아왔듯 자기자신의 높이를 1로 두고 자식노드로 뻗어나갈 때마다 높이가 1씩 증가하게 된다.
위와 같이 표시된 노드의 높이를 계산하는 퀴즈가 나왔고,
쉽게 계산할 수 있겠지만 6이 될 것이다.
그리고 높이를 계산하는 정의로는 위와 같이 표기할 수 있겠으며,
이제 노드에는 parent, key, left, right 뿐만아니라 높이에 해당하는 height 정보까지 저장하게된다.
이제 한 노드에서 subtree들의 높이가 동일하도록 balance를 맞추는 것이 목적이되며,
이를 맞추기위한 AVL 특성을 정의하게 된다. 한 노드에서 자식노드들의 높이 차이가 1 이내일 때 balance가 확보되었다라고 할 수 있겠다.
AVL 특성에 따라 높이의 복잡도는 O(log(n))이 된다.
N 노드가 AVL 특성을 만족하는 binary tree에 존재할 때 높이 h 는 N.height으로 표기하고 이때 N의 subtree의 높이는 적어도 피보나치 수인 Fh이다.
Fn 수열을 표시하면 위와 같고,
증명은 위와 같이 가능하다.
아주 큰 subtree의 높이는 최소 2^h/2가 된다.
결론적으로 AVL 특성을 유지하려면 이를 시행하는 시간 복잡도는 O(log(n))이 된다.
다음은 AVL 특성을 만족하는 또는 만족하도록 rebalancing을 통해 완성한 AVL tree를 다뤄본다.
우선 위와 같은 AVL 특성을 만족하는 tree가 존재할때,
최우측 자식노드아래에 자식노드가 추가된다면 AVL 특성을 파괴하게 되는 문제가 발생한다. (노드 내 숫자는 높이)
추가가 되었을 때 높이가 갱신된 모습.
새로 추가된 노드축에 속한 노드들만 높이가 갱신된 것을 확인할 수 있다.
이 때 동일한 문제의 퀴즈가 등장하는데 AVL 특성에 맞도록 rebalnce가 필요한 상태가 되는 곳은 어디인가? 라는 문제이며 A, B, C는 재조정이 필요없지만 D의 경우 위와 같이 재조정이 필요해진다.
따라서 AVL 특성을 유지할 수 있도록 재조정이 가능해지게 노드를 삽입하는 알고리즘을 알아본다.
AVLInsert는 위와 같은 pseudo code를 가지며,
Rebalancing은 자식노드들의 높이 차이가 1 이하일 때는 일어나지 않으며,
높이 차이가 2이상일 때 수행된다.
Rebalance의 pseudo code이며,
AdjustHeight은 rebalance가 된 후 재조정 된 높이값을 다시 넣어주게 된다.
다시 Rebalancing의 메카니즘으로 돌아와서 만약 왼쪽 노드의 높이가 더 무거울 경우 오른쪽으로 회전시킨다는 개념으로 보면된다.
Bad case는 이와 같은 경우에 동작하지 않는 것을 보여주고,
위와 같은 순서로 rotation이 진행 될 수 있다.
RebalanceRight의 pseudo code는 위와 같다.
이전 Delete에 대해 상기시키자면 간단히 삭제하는 키값을 최상단으로 보내면서 동시에 자식노드를 상위로 올리면 됐었다.
AVLDelete도 비슷하게 동작하며 위와 같은 pseudo code 형식을 보인다.
마지막으로 merging과 splitting이 AVL tree에서 어떻게 동작하는지 보겠다.
Merge는 두개의 트리는 하나로 합치는 것이고 split는 하나의 트리를 두개로 쪼개는 것이다.
먼저 Merge를 살펴보면 입력은 R1, R2를 루트로 가지는 트리가 있고 R1의 키가 R2보다 작을 경우 출력은 새로운 루트를 통해 두개의 트리가 합쳐진다.
바로 퀴즈가 등장하며 위에 등장한 트리와 병합이 가능한 트리를 고르는 것인데,
위의 정의에 부합하는 것은 A밖에 없다. B, C에서 하나씩 조건에 맞지않는 키값들이 있다.
이제 새로는 루트는 위와 같이 두개의 루트를 연결하는 모습이되겠으며,
MergeWithRoot의 pseudo code는 위와 같은 모습이 된다.
Get Root는 위처럼 왼쪽루트의 가장 큰 값을 가진 노드를 루트로 올리게 된다.
따라서 Merge는 위와 같은 순서로 진행이 됨을 알 수 있다.
Merge가 진행되는 순서를 다시금 도식화하여 보여주게 된다.
하지만 balance가 맞지 않을 수 있다는 단점이 나타나는데,
이를 해결하기 위해 병합하고자 하는 트리와 높이가 같은 subtree에서 병합을 진행하면 쉽게 해결된다.
이를 고려한 AVLTreeMergeWithRoot의 pseudo code이며,
병합의 내용은 여기까지이다.
각 스텝은 높이를 변경할 때 시간복잡도가 O(lR1.Height - R2.Heightl + 1)이 된다.
이번엔 Split이며 단순히 분리하고자하는 기준점에서 subtree를 분리할 수 있겠다.
정의를 보면 key x 인 Root R이 입력일 때 x보다 작은 원소들로 이루어진 트리하나와 보다 큰 원소들로 이루어진 트리 하나가 출력된다.
x값을 찾아나서서 subtree들을 병합한 것에 반대되는 순서라고 생각하면 될 듯하다.
Split의 pseudo code이며,
AVLMergeWithRoot로 균형을 유지하며 이에 대한 시간 복잡도는 위와 같다.
결론에서 볼 수 ㅇ씨듯 Merge와 Split의 동작을 알고 시간복잡도를 확인하였다.
댓글
댓글 쓰기