Lecture 7: Binary Trees, Part 2: AVL
7강 : Binary Trees II: AVL
1. Last Time and Today’s Goal
2. Height Balance
• How to maintain height h = O(log n) where n is number of nodes in tree?
트리의 노드 수가 n일 때, 높이 h를 O(log n)으로 유지하려면 어떻게 해야 할까요?
즉, 삽입이나 삭제가 있어도 트리가 너무 한쪽으로 치우쳐 깊어지지 않도록 높이를 로그 수준으로 유지하는 방법이 없을까요?
• A binary tree that maintains O(log n) height under dynamic operations is called balanced
삽입, 삭제 등 동적 연산이 일어나도 높이가 O(log n)으로 유지되는 이진 트리를 ‘균형 잡힌 트리(balanced tree)’라고 부릅니다.
– There are many balancing schemes (Red-Black Trees, Splay Trees, 2-3 Trees, . . . )
이러한 균형을 유지하기 위해 여러 가지 트리 구조 및 기법들이 존재합니다.
예를 들면 레드-블랙 트리, 스플레이 트리, 2-3 트리 등이 있습니다. 각각은 균형을 유지하는 방식이 다르며, 상황에 따라 선택됩니다.
– First proposed balancing scheme was the AVL Tree (Adelson-Velsky and Landis, 1962)
이런 균형 트리들 중에서 최초로 제안된 것은 AVL 트리이며, 이는 1962년에 Adelson-Velsky와 Landis라는 두 사람이 제안했습니다. AVL 트리는 삽입/삭제 후에도 노드 간의 높이 차이를 엄격히 제한하여 균형을 유지합니다.
3. Rotations
Need to reduce height of tree without changing its traversal order, so that we represent the same sequence of items
트리의 높이를 줄이되, 중위 순회를 했을 때 아이템들의 순서는 바뀌지 않아야 합니다.
How to change the structure of a tree, while preserving traversal order? Rotations!
트리의 구조는 바꾸되 순서는 유지하려면 어떻게 해야 할까? 해답은 회전(Rotation) 을 하는 것입니다.
A rotation relinks O(1) pointers to modify tree structure and maintains traversal order
4. Rotations Suffice 회전으로 충분하다
• Claim: O(n) rotations can transform a binary tree to any other with same traversal order.
주장: 같은 중위 순서를 가진 이진 트리라면, 최대 O(n)번의 회전으로 서로 변환 가능합니다
노드의 순서만 같다면 구조는 회전으로 얼마든지 바꿀 수 있습니다
• Proof: Repeatedly perform last possible right rotation in traversal order; resulting tree is a canonical chain.
증명: 중위 순서를 기준으로 마지막 가능한 오른쪽으로 회전을 계속 수행하면,
결과적으로 트리는 일렬로 연결된 케노니컬 체인 형태가 됩니다
* canonical: 표준의, 정형화된, 규범적인, (수학, 컴퓨터 과학에서는 "가장 단순하고 표준적인 형태" 의미)
* canonical chain 케노니컬 체인: 모든 노드가 오른쪽 자식만 가지는 일렬 구조의 트리.
노드들이 한 줄로 늘어선 형태라서 중위 순서대로 정렬은 되어 있지만, 트리 구조로서 비효율적인 형태입니다
• Each rotation increases depth of the last node by 1.
Depth of last node in final chain is n − 1, so at most n − 1 rotations are performed.
각 회전은 마지막 노드의 깊이를 1씩 증가시킵니다
최종적으로 마지막 노드의 깊이는 n−1이 되고, 따라서 최대 n−1번의 회전만 필요합니다
• Reverse canonical rotations to reach target tree.
이렇게 만든 크로니컬 체인에서 다시 거꾸로 회전하면 원하는 트리 구조로 다시 만들 수 있습니다.
트리 A → 크로니컬 체인 → 트리 B 순서로 변형 가능.
• Can maintain height-balance by using O(n) rotations to fully balance the tree, but slow :(
전체 트리를 완전히 균형 잡힌 형태로 만들기 위해 O(n)번의 회전을 해야 할 수 있습니다.
하지만 그렇게 하면 속도가 느립니다, 성능이 좋지 않네요 :(
(그래서 단순하게 O(n)회전으로 항상 균형 잡는 방식은 쓰기 어려움)
• We will keep the tree balanced in O(log n) time per operation!
대신 우리는 각 연산마다 O(log n) 시간만에 트리를 균형 있게 유지할 것입니다.
AVL 트리나 Red-Black 트리처럼, 동적이고 효율적으로 균형을 맞추는 방법을 알아보도록 하겠습니다
5. AVL Trees: Height Balance
• AVL trees maintain height-balance (also called the AVL Property)
AVL 트리는 높이 균형(height-balance)을 유지하는 트리이며, 이것을 AVL 속성이라고도 합니다
– A node is height-balanced if heights of its left and right subtrees differ by at most 1
노드가 height-balanced 상태라는 것은, 그 노드의 왼쪽 서브트리와 오른쪽 서브트리의 높이 차이가 1 이하라는 의미입니다
– Let skew of a node be the height of its right subtree minus that of its left subtree
노드의 불균형도(skew)을 정의할 때, 오른쪽 서브트리의 높이에서 왼쪽 서브트리의 높이를 뺀 값으로 정의합니다.
예: 오른쪽이 3, 왼쪽이 2면 불균형도는 1
* skew: 불균형도. 보통 왼쪽 서브트리와 오른쪽 서브트리의 높이 차
– Then a node is height-balanced if its skew is −1, 0, or 1
그래서 불균형도 값이 -1, 0, 1 중 하나일 때 그 노드는 높이 균형이 잡힌 상태입니다
• Claim: A binary tree with height-balanced nodes has height h = O(log n) (i.e., n = 2^Ω(h))
주장: 모든 노드가 높이 균형을 갖춘 이진 트리는 전체 높이 h가 O(log n)입니다
• Proof: Suffices to show fewest nodes F(h) in any height h tree is F(h) = 2^Ω(h)
증명: 높이가 h인 AVL 트리에서 최소 노드 수를 F(h)라 하면, 이것이 2^Ω(h)임을 보이면 충분합니다
F(0) = 1,
F(1) = 2,
F(h) = 1+F(h−1)+F(h−2) ≥ 2F(h−2) ⇒ F(h) >= 2^h/2
- F(0)는 노드 하나짜리 트리이므로 1
- F(1)은 높이 1, 즉 루트와 하나의 자식이 있는 최소 구조이므로 2
- 재귀식 F(h) = 1 + F(h-1) + F(h-2)
→ 루트 1개 + 왼쪽 서브트리(h-1 높이) + 오른쪽 서브트리(h-2 높이) - 이것은 점점 커져서 F(h) ≥ 2F(h−2)
- 이 식으로부터 F(h) ≥ 2^(h/2)이라는 하한 도출 가능
• Suppose adding or removing leaf from a height-balanced tree results in imbalance
높이 균형이 맞춰진 트리에 리프 노드를 추가하거나 삭제하면 균형이 깨질 수 있다고 가정합니다
– Only subtrees of the leaf’s ancestors have changed in height or skew
이 경우 영향을 받는 것은 그 리프 노드의 조상 노드들의 서브트리뿐입니다
루트까지 올라가는 경로에서만 변화가 있습니다.
– Heights changed by only ±1, so skews still have magnitude ≤ 2
변화는 높이 ±1로만 생기므로 skew 값도 -2 ~ 2 범위를 넘지 않습니다
– Idea: Fix height-balance of ancestors starting from leaf up to the root
생긴 불균형은 리프에서 루트 방향으로 올라가며 조상들을 하나씩 재조정하면서 해결할 수 있습니다.
– Repeatedly rebalance lowest ancestor that is not height-balanced, wlog assume skew 2
불균형도가 +2(오른쪽으로 치우침)인 경우, 가장 낮은(leaf에 가까운) 불균형 노드부터 하나씩 균형을 복구하며 올라갑니다
* wlog: without loss of generality 일반성을 잃지 않고, 일반성을 해치지 않고
Local Rebalance
• Local Rebalance: Given binary tree node :
전체 트리 전체를 고치는 것이 아니라, 특정 노드를 중심으로 균형을 잡기
– whose skew 2 and
노드 의 불균형도가 2이고
불균형도(skew)는 보통 왼쪽 서브트리와 오른쪽 서브트리의 높이 차를 의미하며, 이 경우는 높이 차가 2
한쪽 서브트리가 다른 쪽보다 두 레벨 더 깊다
– every other node in <B>’s subtree is height-balanced,
<B>의 서브트리에 있는 다른 모든 노드들은 균형이 잡혀 있다면
즉, <B> 만이 유일하게 불균형 상태인 상황이라면
– then ’s subtree can be made height-balanced via one or two rotations
그러면 의 서브트리는 회전(rotation) 한 번이나 두 번으로 균형 상태로 만들 수 있습니다
AVL 트리에서 사용하는 대표적인 방식입니다.
– (after which <B>’s height is the same or one less than before)
그 결과 <B>의 높이는 이전과 같거나 하나 줄어듭니다
균형을 맞춘 후에는 노드의 높이가 그대로이거나, 서브트리 전체가 더 평평해져서 높이가 1 감소할 수도 있습니다
이는 트리의 전체적인 높이 증가를 억제하는 효과가 있습니다.
Proof
- since skew of <B> is 2, <B>'s right child <F> exists
<B>의 불균형도가 2이므로, <B>의 오른쪽 자식 <F>는 존재한다
불균형도가 +2라는 것은 오른쪽 서브트리가 왼쪽보다 2만큼 더 높다는 뜻이고, 따라서 오른쪽에 최소한 하나 이상의 노드가 있어야 하므로 <F>는 존재합니다.
- Case 1: skew of <F> is 0 or Case 2: skew of <F> is 1
- Case 1: <F>의 높이 차가 없는 균형 상태
- Case 2: <F>가 오른쪽으로 한 단계 더 깊은 상태
* Perform a left rotation on <B>
<B>에 대해 왼쪽 회전을 수행한다
이 말은 <B>가 중심이 되어 회전하며, 오른쪽 자식 <E>가 새로운 부모가 되는 구조로 회전이 일어남
목적: <B>의 오른쪽으로 치우친 균형을 바로잡아 트리를 전체적으로 평평하게 만드는 것
* Let h = height(<A>). Then height(<G>) = h + 1 and height(D) is h + 1 in Case 1, h in Case 2
h를 <A>의 높이라고 하자. 그러면 <G>의 높이는 h + 1이고, <D>의 높이는 Case 1에서는 h + 1이며, Case 2에서는 h이다
* After rotation:
회전 후의 상태
• the skew of <B> is either 1 in Case 1 or 0 in Case 2, so <B> is height balanced
Case 1 에서는 <B>의 불균형도(skew)가 1이고, Case 2에서는 0이 된다. 따라서 <B>는 회전 후 균형 상태이다.
— Case 1: 왼쪽과 오른쪽 자식 간 높이 차가 1
— Case 2: 왼쪽과 오른쪽 자식의 높이가 같아 균형 완벽
→ 둘 다 AVL 조건(불균형도 ≤ 1)을 만족하므로 <B>는 height-balanced
• the skew of <F> is -1, so <F> is height balanced
– <F>의 불균형도는 -1이므로, 왼쪽이 오른쪽보다 한 단계 더 깊지만 여전히 균형 상태이다."
— AVL에서 skew -1은 균형 조건에 부합함
— 이는 회전으로 인해 <B>가 <F>의 자식이 되면서 생긴 자연스러운 구조 변화
• the height of <B> before is h + 3, then after is h + 3 in Case 1, h + 2 in Case 2
– 회전 전 <B>의 높이는 h + 3이었고, 회전 후에는 Case 1에서는 h + 3으로 그대로이고, Case 2에서는 h + 2로 줄어든다.
— Case 1: 구조상 회전은 일어났지만 전체 높이에는 변화가 없음
— Case 2: 균형이 더 잘 맞춰지며, 전체 트리 높이가 1 줄어드는 결과
→ 즉, Case 2가 더 깊은 최적화를 이룸 (AVL 트리의 장점 중 하나)
Global Rebalance
Global Rebalance: Add or remove a leaf from height-balanced tree to produce tree T'.
전역 균형 재조정: 높이 균형이 맞는 트리 T에서 리프(leaf) 노드를 하나 추가하거나 제거하여 새로운 트리 T'을 만든다."
— AVL 트리 같은 균형 트리에서 노드를 삽입하거나 삭제할 때 전체 트리 구조가 바뀔 수 있음
— 이 과정에서 일시적으로 균형이 깨진 트리 T'가 만들어짐
Then T' can be transformed into a height-balanced tree T" using at most O(log n) rotations.
그러면 T'은 최대 O(log n)번의 회전만으로 균형 잡힌 트리 T"으로 변환될 수 있다.
— AVL 트리의 핵심 성질: 삽입이나 삭제 이후, 트리의 깊이에 비례하는 소수의 회전만으로 전체 균형을 회복 가능
— 트리의 높이는 O(log n)이므로 회전의 수도 그에 비례해 제한적임
— 이 덕분에 탐색, 삽입, 삭제 연산의 시간 복잡도를 log n으로 유지할 수 있음
Proof
– Only ancestors of the affected leaf have different height in T₀ than in T
영향을 받은 리프(leaf) 노드의 조상들만이 T와 T' 사이에서 높이에 변화가 있다.
— 삽입 또는 삭제는 리프 쪽에서만 발생하므로, 그 위의 조상 노드들만 높이 변화의 영향을 받습니다.
– Affected leaf has at most h = O(log n) ancestors whose subtrees may have changed
– 해당 리프 노드는 많아야 O(log n)개의 조상을 가지며, 이 조상들의 서브트리가 변경되었을 수 있다.
— 트리의 높이는 O(log n)이므로, 조상 노드 개수도 그 정도입니다. 따라서 영향을 받는 범위는 제한적입니다.
– Let be lowest ancestor that is not height-balanced (with skew magnitude 2)
– 를 균형이 깨진(불균형도가 2인) 가장 낮은 조상 노드라고 하자."
— 가장 먼저 균형이 깨지는 지점부터 로컬 회전을 통해 문제를 해결해나갈 수 있다는 접근입니다.
– If a leaf was added into T:
– 만약 리프 노드가 T에 삽입되었다면
∗ Insertion increases height of <X>, so in Case 2 or 3 of Local Rebalancing
삽입으로 인해 <X>의 높이가 증가하므로, 로컬 리밸런싱의 Case 2 또는 Case 3이 발생한다.
— 삽입은 서브트리의 높이를 증가시키므로, 보통 오른쪽 또는 왼쪽으로 2단계 치우친 불균형이 생김
∗ Rotation decreases subtree height: balanced after one rotation
회전을 통해 서브트리 높이가 줄어들고, 한 번의 회전으로 균형을 회복할 수 있다.
– If a leaf was removed from T:
– 만약 리프 노드가 T에서 제거되었다면:
∗ Deletion decreased height of one child of <X>, not <X>, so only imbalance
삭제는 자신의 높이가 아니라 자식 하나의 높이를 줄였기 때문에 균형이 깨진다
— 이 경우 는 높이는 그대로지만 자식 간의 높이 차가 2가 되어 불균형 발생
∗ Could decrease height of <X> by 1; parent of <X> may now be imbalanced
<X>의 높이가 1 감소할 수 있으며, 그로 인해 <X>의 부모 노드가 불균형 상태가 될 수 있다.
— 삭제의 경우, 자식 노드가 사라지면 <X>의 서브트리 높이가 감소함
— 그 결과 <X>의 부모 노드 입장에서는 자식들 간의 높이 차이가 2가 되어 불균형 발생 가능
∗ So may have to rebalance every ancestor of <X>, but at most h = O(log n) of them
– 따라서 <X>의 모든 조상 노드에 대해 균형을 다시 맞춰야 할 수도 있지만, 그 수는 많아야 O(log n)개에 불과하다.
— 최악의 경우 루트까지 영향을 받을 수 있음
— 하지만 트리 높이는 O(log n)이기 때문에, 재조정이 필요한 노드 수도 그 정도로 제한됨
• So can maintain height-balance using only O(log n) rotations after insertion/deletion!
– 결과적으로, 삽입이나 삭제 이후에도 O(log n)번의 회전만으로 전체 트리의 균형을 유지할 수 있다!
— AVL 트리의 핵심 성질: 균형이 깨져도 고작 로그 개수의 회전만 필요
— 이는 탐색, 삽입, 삭제 모두 O(log n) 보장에 필수
• But requires us to evaluate whether possibly O(log n) nodes were height-balanced
– 하지만 O(log n)개의 노드가 실제로 균형을 이루고 있는지를 일일이 평가해야 한다.
— 회전을 하든 안 하든, 각 조상 노드가 균형 상태인지 확인은 필수
— 이 확인 작업도 로그 수준의 시간이 걸림
6. Computing Height 높이 계산하기
• How to tell whether node is height-balanced? Compute heights of subtrees!
– 노드 가 높이 균형 상태인지 어떻게 알 수 있을까? → 왼쪽과 오른쪽 서브트리의 높이를 계산하면 된다!
— AVL 트리는 좌우 서브트리 높이 차이가 1 이하여야 균형 상태
— 즉, 높이 정보가 있어야 판단 가능
• How to compute the height of node ? Naive algorithm:
– 노드 의 높이를 어떻게 계산할까? → 가장 단순한 방법은 다음과 같다:
- Recursively compute height of the left and right subtrees of
– 왼쪽과 오른쪽 서브트리의 높이를 재귀적으로 계산한다.
- Add 1 to the max of the two heights
– 둘 중 더 큰 높이에 1을 더한다 (자기 자신 포함).
- Runs in S(n) time, since we recurse on every node :(
– 하지만 이 방식은 모든 노드에 대해 재귀 호출을 하므로 S(n) 시간(=트리 전체 크기)이나 걸린다 😞
— 트리 조작이 많아질수록 너무 비효율적
• Idea: Augment each node with the height of its subtree! (Save for later!)
– 아이디어: 각 노드에 자신의 서브트리 높이를 저장해 놓자! (즉, 캐싱!)
— 서브트리 높이를 미리 저장해두면 계산 시간 절약 가능
• Height of <X> can be computed in O(1) time from the heights of its children:
– <X> 의 높이는 자식 노드들의 높이 정보를 이용해 O(1) 시간에 계산할 수 있다.
- Look up the stored heights of left and right subtrees in O(1) time
– 왼쪽과 오른쪽 자식에 저장된 높이를 O(1) 시간에 조회하고,
- Add 1 to the max of the two heights
– 둘 중 더 큰 값에 1을 더한다.
• During dynamic operations, we must maintain our augmentation as the tree changes shape
– 동적 연산(삽입, 삭제, 회전 등)이 발생할 때 트리 구조가 바뀌므로 이 높이 정보도 갱신해 줘야 한다.
• Recompute subtree augmentations at every node whose subtree changes:
– 서브트리가 바뀐 노드마다 저장된 높이 정보를 재계산해야 한다.
- Update relinked nodes in a rotation operation in O(1) time (ancestors don't change)
– 회전 연산에서는 연결이 바뀐 몇 개의 노드만 O(1) 시간에 갱신하면 된다 (조상 노드는 그대로 유지되므로).
- Update all ancestors of an inserted or deleted node in O(h) time by walking up the tree
– 삽입 또는 삭제의 경우, 루트까지 조상 노드를 따라 올라가면서 O(h) 시간에 모두 업데이트 가능하다 (h는 트리 높이).
— 트리 높이는 O(log n) 이므로 이 작업도 효율적으로 처리 가능
트리의 높이를 빠르게 계산하려면 각 노드에 서브트리 높이 정보를 저장하고, 삽입/삭제/회전 시 변경된 부분만 갱신하면 됩니다.
이렇게 하면 트리 균형 여부를 빠르게 판단할 수 있고, AVL 트리의 효율성을 유지할 수 있습니다.
7. Steps to Augment a Binary Tree
이진 트리에 어떤 추가 정보를 넣고 싶을 때(예: 서브트리의 크기, 높이 등), 그걸 어떻게 설계할지 설명하는 단계입니다.
• In general, to augment a binary tree with a subtree property P, you must:
일반적으로, 이진 트리에 서브트리의 어떤 속성 P(예: 높이, 크기 등)를 추가하려면 다음과 같은 절차를 따라야 합니다.
* augment: 강화하다, 확장하다, 추가하다
– State the subtree property P() you want to store at each node
각 노드 에 저장하고자 하는 서브트리의 속성 P()를 명확히 정의해야 합니다.
예: 각 노드에 자신을 루트로 하는 서브트리의 크기 또는 최대값을 저장하고 싶다고 선언
– Show how to compute P() from the augmentations of ’s children in O(1) time
그리고 자식 노드들의 속성 값을 기반으로 P()를 상수 시간 안에 계산할 수 있어야 합니다.
예: P(X) = max(P(left), P(right)) + 1 같이 자식 노드의 값만 참조해서 한 번에 계산 가능해야 합니다.
* augmentations: augmentation 복수형, 각 노드에 추가된 보조 정보, 이진 트리를 augment(강화)하면서 각 노드에 저장한 부가적인 값들 전체
• Then stored property P() can be maintained without changing dynamic operation costs
이렇게 하면 트리에 삽입/삭제 같은 동적 연산을 할 때도 시간 복잡도를 증가시키지 않고 P() 값을 유지할 수 있습니다.
즉, 원래 연산들(삽입, 삭제)이 O(log n)이라면 P를 추가해도 여전히 O(log n)을 유지합니다.
8. Application: Sequence
For sequence binary tree, we needed to know subtree sizes
순서 정보를 표현하는 이진 트리(예: 순위 트리, order-statistics tree)에서는 각 노드의 서브트리 크기(자기 자신을 포함해 왼쪽 + 오른쪽 서브트리까지 몇 개의 노드가 있는지)를 알아야 했습니다.
예: “이 노드는 전체 중 몇 번째 원소인가?” 같은 순서를 빠르게 계산하려면 서브트리 크기를 알아야 합니다.
• For just inserting/deleting a leaf, this was easy, but now need to handle rotations
단순히 리프 노드를 삽입하거나 삭제할 때는 서브트리 크기만 잘 업데이트하면 되었지만,
이제는 트리 균형을 위해 회전(rotation)을 할 경우도 고려해야 합니다.
회전은 트리의 구조를 바꾸므로, 서브트리 크기 정보도 같이 조정해줘야 합니다.
• Subtree size is a subtree property, so can maintain via augmentation
서브트리 크기는 서브트리 전체에 대한 정보이기 때문에,
augmentation(노드에 보조 정보를 저장하는 방식)을 통해 유지 관리할 수 있습니다.
즉, 각 노드에 서브트리 크기를 저장해두면 됩니다.
– Can compute size from sizes of children by summing them and adding
자식 노드들의 서브트리 크기를 더하고 자기 자신(1)을 더하면, 현재 노드의 서브트리 크기를 O(1) 시간에 계산할 수 있습니다.
→ size(X) = 1 + size(X.left) + size(X.right)
이 계산은 회전이나 삽입/삭제 후에도 빠르게 처리 가능하므로 트리 연산의 성능에 영향을 주지 않습니다.
9. Conclusion
결론적으로, 아래는 AVL 트리의 두 가지 용도(집합/순서)에서 연산들의 시간 복잡도 요약입니다.
• Set AVL trees achieve O(lg n) time for all set operations,
except O(n log n) time for build and O(n) time for iter
Set AVL 트리(예: 중복 없는 정렬된 데이터 저장)는
삽입, 삭제, 검색 같은 일반적인 집합 연산(set operations)을 O(log n) 시간에 처리할 수 있습니다.
단 build: 트리를 처음 만들 때는 정렬되지 않은 데이터를 삽입하고 정렬해야 하므로 O(n log n)
iter (iteration): 트리 전체를 순회하는 데는 모든 노드를 한 번씩 방문해야 하므로 O(n) 시간 소요됩니다.
• Sequence AVL trees achieve O(lg n) time for all sequence operations, except O(n) time for build and iter
Sequence AVL 트리(예: 리스트처럼 순서가 중요한 구조)는
삽입, 삭제, k번째 원소 조회, 순위 계산 등 순서 기반 연산(sequence operations)을 O(log n) 시간에 처리할 수 있습니다.
단, build: 초기 트리 생성 시 왼쪽/오른쪽 균형을 맞춰 트리를 구성해야 하므로 O(n)
iter: 모든 노드를 순서대로 순회하는 데는 마찬가지로 O(n) 시간 필요합니다.
요약 비교
용도 일반 연산 Build 시간 Iter 시간
| Set AVL | O(log n) | O(n log n) | O(n) |
| Sequence AVL | O(log n) | O(n) | O(n) |
즉, Set AVL은 검색이 우선일 때, Sequence AVL은 순서가 중요한 데이터에 적합합니다.
10. Application: Sorting
응용: 이진 탐색 트리(특히 Set 구조)를 이용하면 정렬 알고리즘을 만들 수 있습니다.
• Any Set data structure defines a sorting algorithm: build (or repeatedly insert) then iter
어떤 Set(집합) 자료구조든, 다음 두 단계를 거치면 정렬된 결과를 얻을 수 있습니다:
- build 또는 하나씩 insert 해서 데이터를 트리에 넣고
- iter(중위 순회 등)로 트리 전체를 방문하면 → 자동으로 정렬된 순서로 출력됩니다.
즉, Set 트리는 내부적으로 항상 정렬된 구조이기 때문에 별도의 정렬 없이도, 이렇게 두 단계를 거치면 정렬이 되는 셈입니다.
• For example, Direct Access Array Sort from Lecture 5
예를 들어, 5강에서 배운 직접 접근 배열 정렬(Direct Access Array Sort)도
데이터를 키에 따라 배열에 바로 넣고
배열을 앞에서부터 순회(iterate)하면 정렬된 결과를 얻는다는 점에서 위 개념과 같습니다.
• AVL Sort is a new O(n lg n)-time sorting algorithm
AVL 트리를 사용한 정렬 방식도 존재합니다:
- 데이터를 AVL 트리에 하나씩 insert (O(log n)씩 n번 → O(n log n))
- 중위 순회(iter)로 정렬된 결과 출력 (O(n))
이렇게 하면 AVL Sort라는 정렬 알고리즘이 되고, 이는 O(n log n) 시간 복잡도를 가집니다.
AVL 트리를 이용한 정렬도 효율적인 정렬 알고리즘이 될 수 있습니다