Lecture 6: Binary Trees, Part 1 이진 트리

Lecture 6: Binary Trees, Part 1 이진 트리 

1. Previously and New Goal

 

이전에 배운 자료구조들의 시간 복잡도를 표로 나타낸 것이다. 

 

 

2. How? Binary Trees! 이진 트리 

Pointer-based data structures (like Linked List) can achieve worst-case performance
포인터 기반 자료구조(예: 링크드 리스트)는 최악의 경우 성능이 매우 나쁠 수 있다. 

 

잠깐 이 전에 배운 Linked list 연결 리스트를 복습해보면

Linked list 연결 리스트는 일렬로 쭉 이어진 선형 구조였다. 

각 노드는 값(data) + 다음 노드(next) 에 대한 포인터로 구성되어 있는 자료 구조이다.

이 링크드 리스트에서 탐색은 O(n)이 걸리기 때문에 효율적이지 않았다.

 

하지만 오늘 배울 이진 탐색(Binary Tree)은 다르다. 

어떻게 시간을 단축하는지 차근 차근 알아보도록 하자. 

 

Binary tree is pointer-based data structure with three pointers per node
바이너리 트리도 포인터 기반 자료구조로 되어 있으며, 각 노드는 3개의 포인터를 가진다.

 

Node representation: node.{item, parent, left, right}
노드는 다음과 같이 표현된다: node.{값, 부모 포인터, 왼쪽 자식 포인터, 오른쪽 자식 포인터}

 

 

 

다음은 트리와 각 노드의 아이템(값), 부모, 왼쪽 자식, 오른쪽 자식을 나타낸 테이블이다.

 

 

3. Terminology (용어 설명)

 트리에서 사용하는 기본 용어들을 알아보자 

 

3-1 Root (루트)

The root of a tree has no parent (Ex: <A>)
트리의 루트는 부모 노드가 없다. (예: <A>)
트리 구조에서 맨 꼭대기 노드를 루트(root)라고 하며, 이 노드는 위쪽에 연결된 부모가 없다.

* root 뿌리

3-2 Leaf (리프)

A leaf of a tree has no children (Ex: <C>, <E>, and <F>)
트리의 리프(leaf, 잎 노드)는 자식 노드가 없다. (예: <C>, <E>, <F>)
아래로 더 뻗어나가지 않는 끝 노드들을 리프 노드라고 한다.

* leaf: 잎

 

3-3 Depth of Node  (노드 깊이)

Define depth(<X>) of node <X> in a tree rooted at <R> to be length of path from <X> to <R>
노드 <X>의 깊이(depth)는 <X>에서 <R>까지 가는 경로이다.

 

* <X>: 현 작업 중인 노드 

* <R>: Root 

 

예시] 각 노드의 depth(<X>) - 노드 X에서 루트 A까지의 길이 (depth)

이진 트리 깊이

Node X	X 부터 -> 루트까지	깊이 (depth)
A (R) 일 때	A	0
B  일 때	B → A	1
C  일 때	C → A	1
D  일 때	D → B → A	2
E  일 때	E → B → A	2

 

3-3 Height of Node (노드 높이)

Define height(<X>) of node <X> to be max depth of any node in the subtree rooted at <X>
노드 <X>의 높이(height)는 <X>를 루트로 하는 서브트리에서 가장 깊은 노드의 깊이이다.
* 높이: 노드 x에서 아래로 가장 멀리 떨어진 자식까지의 거리

* 리프 노드의 높이는? 0 자식이 없으니까 

* 전체 트리 높이: root에서 가장 멀리 떨어진 자식까지의 거리 

 

 

Node X	Height
D 일 때	0
E  일 때	0
B  일 때	1
C  일 때	0
A  일 때	2

 

 

Depth vs Height 

depth와 height는 비슷하게 들리지만, 서로 반대 방향으로 간다

depth(X)	노드 X에서 루트까지 가는 경로의 길이 depth는 "노드가 트리에서 얼마나 깊숙이 박혀 있는지"	아래 → 위
height(X)	노드 X에서 가장 깊은 자식까지 가는 경로의 길이 (서브트리 기준) height는 "노드에서 얼마나 멀리 내려갈 수 있는지"	위 → 아래

 

 

Idea: Design operations to run in O(h) time for root height h, and maintain h = O(log n)
아이디어: 연산을 O(h) 시간에 수행하도록 만들고, 높이 h는 O(log n)으로 유지하자.
트리의 높이를 너무 높지 않게(logarithmic) 유지하면 효율적인 연산이 가능하다.

 

1. 균형 잡힌 이진 탐색 트리 (Binary Search Tree(BST))인 경우 

• 노드 수 n = 7
• 트리 높이 h = 2 (루트 4에서 리프까지 최대 2단계)
• log₂(7) ≈ 2.8 → O(log n)에 해당
• 탐색/삽입/삭제 모두 O(log n) 시간에 가능

 

2. 균형 잡히지 않은 이진 탐색 트리 (Binary Search Tree(BST))인 경우  

• 노드 수 n = 7
• 트리 높이 h = 6
• 예: 값 7을 찾으려면 1부터 차례대로 7번 내려가야 해서
• O(h) = O(n) → 매우 느림
• 사실상 한 줄로 쭉 늘어선 선형 구조인 연결 리스트와 같아짐
• 삽입 순서가 정렬된 데이터이면 BST가 한쪽으로 쏠려버려서 비효율적임

 

3-4 traversal order 순회 순서 

A binary tree has an inherent order: its traversal order
이진 트리는 고유한 순서를 가지고 있다: 그것은 트리 순회(traversal) 순서이다.
트리의 노드를 어떤 순서로 방문할지가 이미 정해져 있다.

* traversal: 모든 노드를 하나씩 방문하는 것. 순회 

 

every node in node <X>’s left subtree is before <X>
노드 <X>의 왼쪽 서브트리에 있는 모든 노드는 <X>보다 작다

 

every node in node <X>’s right subtree is after <X>
노드 <X>의 오른쪽 서브트리에 있는 모든 노드는 <X>보다 크다

 

예를 들어 Node x가 30 일 때 

왼쪽으로는 30보다 작은 수, 오른 쪽으로 30보다 큰 수가 있다

바이너리 트리 왼쪽, 오른쪽

 

List nodes in traversal order via a recursive algorithm starting at root:
루트에서 시작하는 재귀 알고리즘으로 순회 순서대로 노드를 나열하자

 

Recursively list left subtree, list self, then recursively list right subtree
왼쪽 서브트리 -> 자기 자신 -> 오른 쪽 서브트리 순으로 지나간다

B -> A -> C

이 규칙을 traversal order 중에서 구체적으로 중위 순회(in-order traversal)라고 하지만

여기서는  traversal order라 하면 이 중위 순회를 말한다 

 

* In-order traversal

• 방문 순서: 왼쪽 → 자기 자신 → 오른쪽
• 이진 탐색 트리(BST)에서 in-order 순회 결과는 정렬된 순서

Runs in O(n) time, since O(1) work is done to list each node
각 노드 하나를 탐색하는데 O(1) 시간이 걸리지만, 전체 노드를 다 탐색하려면 시간은 O(n)이 걸린다
트리에 n개의 노드가 있을 때 전체 순회 시간은 선형이다

 

Example: Traversal order is (<F>, <D>, <B>, <E>, <A>, <C>)

데이터 <A>, <B>, <C>, <D>, <E>, <F> 가 다음과 같은 트리 구조로 있을 때 

 

순회 결과는 F에서 시작해서 F → D → B → E → A → C 가 된다 

 

Right now, traversal order has no meaning relative to the stored items
지금은 순회 순서가 저장된 아이템의 의미와 아무 관련이 없다.
지금은 단순히 구조에 따라 방문할 뿐이며, 정렬이나 검색 목적은 아니다.

 

Later, assign semantic meaning to traversal order to implement Sequence/Set interfaces
나중에는 순회 순서에 의미를 부여해서 Sequence(순서 리스트)나 Set(집합) 인터페이스를 구현하게 된다.

 

4. Tree Navigation (트리 안에서 탐색)

 

• A 기준으로 왼쪽: B
• B 기준으로 왼쪽: D
• D 기준으로 왼쪽: F → 방문 F

 

Find first node in the traversal order of node <X>’s subtree (last is symmetric)
노드 <X>의 서브트리에서 순회 순서상 가장 첫 번째 노드를 찾는다.

(마지막 노드를 구하는 방법은 같은 논리를 이용해 반대로 적용하면 된다)

 

- If <X> has left child, recursively return the first node in the left subtree
<X>에 왼쪽 자식이 있다면, 그 왼쪽 서브트리에서 재귀적으로 첫 번째 노드를 찾아 반환한다.
왼쪽이 계속 있다면 가장 왼쪽까지 계속 내려가는 방식이다. 

root 노드에서 시작해서 왼쪽에 노드가 있으면 계속 타고 내려간다

 

- Otherwise, <X> is the first node, so return it
그렇지 않다면, <X> 자신이 첫 번째 노드이므로 그것을 반환한다.
왼쪽 자식이 없으면, 자신이 해당 서브트리의 최소 노드이다.

 

- Running time is O(h) where h is the height of the tree
이 연산의 시간 복잡도는 트리의 높이 h에 비례하여 O(h)이다.

 

- Example: first node in <A>’s subtree is <F>
예시: <A>의 서브트리에서 순회 순서상 첫 번째 노드는 <F>이다.
<A>의 왼쪽 → <B>의 왼쪽 → <D>의 왼쪽 → <F> 와 같이 가장 왼쪽까지 간다.

 

Find successor of node <X> in the traversal order (predecessor is symmetric)
노드 <X>의 순회 순서에서 자식 노드를 찾는다.

(Predecessor는 Successor와 아이템 순서가 같지만 대칭적으로 방향이 반대)

 

Successor 방향: F → D → B → E → A → C

Predecessor 방향: F ← D ← B ← E ← A ← C

 

- If <X> has right child, return first of right subtree
<X>에 오른쪽 자식이 있다면, 오른쪽 서브트리의 첫 번째 노드를 반환한다.
오른쪽 자식이 있으면, 그쪽에서 가장 왼쪽 노드를 찾아야 한다.

F -> D -> B -> G -> E

• F → 자식 없음 -> 부모 D로
• D 방문 → D의 오른쪽 자식 없음 → 부모 B로
• B 방문 → B의 오른쪽 자식 -> E, 방문 안하고 E의 왼쪽 자식 G로 바로 감
• G 방문 -> G의 자식 없음 -> 부모 E로
• E 방문 

 

- Otherwise, return lowest ancestor of <X> for which <X> is in its left subtree
그렇지 않다면, <X>가 왼쪽 자식으로 있는 가장 위의 조상을 리턴한다.
이제 아래에 있는 자식들은 다 방문했으니 위쪽으로 올라가며 아직 방문 안한 부모를 찾는다

F -> D-> B-> G -> E 까지 왔고 

이제 노드 X가 E 자리에 있다

이 다음은 어디로 가야할까?

부모 B?, 부모 B는 이미 읽었음.

올라가서 B의 부모 → A 

참고로 A는 E의 가장 가까운 왼쪽 서브트리에 E를 포함하는 조상이다

 

- Running time is O(h) where h is the height of the tree
이 연산의 시간 복잡도도 트리의 높이 h에 따라 O(h)이다.

 

- Example: Successor of: <B> is <E>, <E> is <A>, and <C> is None

 

Successor (후속노드) 방향: F → D → B → E → A → C

Predecessor (이전 노드) 방향: F ← D ← B ← E ← A ← C

 

 

5.  Dynamic Operations

Change the tree by a single item (only add or remove leaves):
트리에서 한 번에 하나의 아이템씩 바꾼다. (단, 리프 노드(leaf)만 추가하거나 삭제할 수 있다)
트리의 균형이나 순서를 보존하기 위해서는 중간 노드가 아닌 리프 노드만 다뤄야 한다

 

 - add a node after another in the traversal order (before is symmetric):
순회 순서대로 어떤 노드 다음에 새로운 노드를 추가한다. (앞에 넣는 경우도 같은 방식으로 처리할 수 있음)

원하는 위치가 있으면 앞에서 본 순회 순서를 이용해, 앞에 올 노드를 확인 후 그 뒤에 위치 시킨다 

 

 -  remove an item from the tree
트리에서 노드를 삭제한다 (리프만 삭제 가능)

 

5-1. Insert  노드 삽입하기

그럼 이제 노드를 트리에 삽입하는 방법을 알아보자

 

숫자를 입력하는 경우 예를 살펴보자.

데이터가 [50, 30, 70, 20, 25, 15, 60, 80]이 있는 경우를 바이너리 트리를 만들어보자

• 시작 50
• 30은 50보다 작기에 왼쪽에 놓는다
• 70은 50보다 크기에 오른쪽에 놓는다 
• 25는 50,30 보다는 작아서 왼쪽으로 20보다는 커서 오른쪽에 놓는다
• 15는 50, 30, 20 보다 작아서 왼쪽에 놓는다 
• 60은 50보다 커서 오른쪽, 70보다 작아서 왼쪽에 놓는다 
• 80은 50, 70 보다 커서 오른쪽에 놓는다 
• 이 완성된 트리를 순회하면 [15, 20, 25, 30, 50, 60, 70, 80]순으로 나온다

 

그럼 이제 순회 순서에 맞게 나오도록 데이터를 위치시켜보자 

Insert node <Y> after node <X> in the traversal order
<X> 다음에 <Y> 삽입하기. X 다음으로 오게 하려면 왼쪽? 오른쪽? 

 

– If <X> has no right child, make <Y> the right child of <X>
<X>에 오른쪽 자식이 없는 경우, <Y>를 오른쪽 자식으로 삽입하면 X -> Y 순서로 온다 

 

– Otherwise, make <Y> the left child of <X>’s successor (which cannot have a left child)
만약 <X>에 이미 오른쪽 자식이 있다면, 그 오른쪽 자식의 왼쪽에 <Y>를 삽입한다
이 때 왼쪽 자식이 없어야 함

 

– Running time is O(h) where h is the height of the tree
이 삽입 작업은 트리의 높이만큼 내려가거나 올라가야 하므로 시간 복잡도는 O(h)이다

 

before is symmetric

반대 방향도 같다 

 

 

이제 트리를 삽입하는 몇 가지 예시를 살펴보자

Example: Insert node <G> before <E> in traversal order

E 앞에 G가 오도록 하려면 E의 왼쪽에 삽입 

 

 

E 다음에 I를 넣고 싶으면

<I>를 <E>의 오른쪽 자식으로 삽입

D → B → G -> E → I → A → C

 

 

B 다음에 G가 오게 하려면 

B 오른쪽에 자식이 있으니 그 자식 아래 왼쪽으로 넣는다

D → B → G → E → A → C 순이 된다

B 이 후에 넣는 것이 E 이 전에 넣는 것과 같게 되었다.

 

Example: Insert node <H> after <A> in traversal order

A 다음에 H가 오도록 하려면 A의 오른쪽에 이미 자식이 있으니 그 자식 아래 왼쪽으로 삽입 

 

 

 

 

5-2. Delete 

이제는 노드를 삭제하는 방법에 대해 알아보자 

 

Delete the item in node <X> from <X>’s subtree
노드 <X>에 들어 있는 아이템을, <X>의 서브트리에서 제거해보자

 

– If <X> is a leaf, detach from parent and return
만약 <X>가 리프 노드(자식이 없는 노드)라면, 부모 노드와의 연결을 끊고 리턴하면 된다
부모와 연결 끊으면 끝

 

 

– Otherwise, <X> has a child
만약 <X>가 자식이 있는 경우를 보자 

 

∗ If <X> has a left child, swap items with the predecessor of <X> and recurse
<X>가 왼쪽 자식이 있으면 <X>와 왼쪽 자식의 아이템을 서로 바꾼다

이제 삭제 대상이 자식으로 이동했으므로, 그 노드의 연결을 끊는다 

이렇게 하면 트리 구조는 유지되면서도 삭제가 이루어진다

 

∗ Otherwise <X> has a right child, swap items with the successor of <X> and recurse
왼쪽 자식이 없고, 오른쪽 자식이 있다면 <X>와 그 자식의 아이템을 바꾸고, 자식을 대상으로 다시 삭제 작업을 수행한다.

E 지우기

 

 

– Running time is O(h) where h is the height of the tree
이 작업은 노드를 따라 내려가야 하기 때문에, 최악의 경우에는 트리의 높이만큼 걸린다.
따라서 시간 복잡도는 O(h)

 

– Example: Remove <F> (a leaf)
예시: <F>는 리프 노드이므로, 위 첫 번째 규칙대로 그냥 부모 노드에서 분리하면 된다.
간단한 삭제

 

 

 

– Example: Remove <A> (not a leaf, so first swap down to a leaf)

 

 

6. Application: Set  - BST(Binary Search Tree) 

Binary Search Tree 구조를 사용해 Set과 Sequence를 각각 구현할 수 있다

Set을 BST로 구현하면 key 순서대로 정렬된 트리 형태가 되며,

중위 순회(in-order traversal)을 하면 key 값이 오름차순 정렬된 순서로 출력한다

이번엔 BST를 순서가 중요한 시퀀스로 사용시 트리 순회 순서 = 시퀀스 순서이다

 

Set BST vs Sequence BST

트리 구조	값의 크기 순으로 결정됨	삽입 순서에 따라 트리 모양이 달라짐
중복 가능 여부	보통 허용하지 않음 (집합)	허용 가능 (리스트니까)
주된 연산	search(key) 등	get(i), insert(i, val), delete(i)
값 순서	정렬된 순서 유지	사용자가 넣은 순서 유지
사용 예	정렬된 데이터 저장, 탐색 최적화	문서 편집기, undo/redo, 순서 기반 데이터 처리

 

일단 Set에 대해 먼저 알아보자. 

 

Idea! Set Binary Tree (a.k.a. Binary Search Tree / BST):
아이디어! Set을 구현할 때 Set Binary Tree, 즉 이진 탐색 트리 (Binary Search Tree, BST)를 사용한다.
키 값을 기준으로 정렬된 구조를 가지는 트리가 만들어진다

 

Set Binary Tree 

• 중복 없이 값을 저장하는 Set의 역할
• 정렬된 순서 유지 - 키 값(여기서는 숫자) 기준으로 오름차순 정렬된 순서를 가짐
• 빠르게 탐색/삽입/삭제 (보통 O(log n) 시간)

이진 탐색 트리(BST)를 Set처럼 사용하는 예시

데이터 {50, 30, 70, 20, 40, 60, 80} 을 BST로 저장하기

• 중위 순회(in-order traversal)로 탐색하면 값은 이렇게 정렬된 상태로 나온다 
  20 → 30 → 40 → 50 → 60 → 70 → 80

탐색 예시) 60이 있는지 확인 (Set.contains(60)): 

• 60 < 50? ❌ → 오른쪽으로
• 60 < 70? ✔️ → 왼쪽으로
• 도착한 노드 = 60 ✔️→ 존재함!

 

Traversal order is sorted order increasing by key
키 값이 오름차순으로 정렬된 순서로 순회하여 노드가 나온다.
즉, 트리 탐색 순서 = 정렬된 순서

 

Equivalent to BST Property: for every node, every key in left subtree ≤ node’s key ≤ every key in right subtree
이 구조는 BST의 핵심 속성과 같다: 모든 노드는 

• 왼쪽 서브트리의 모든 키 ≤ 그 노드의 키
• 오른쪽 서브트리의 모든 키 ≥ 그 노드의 키
  → 그래서 중위 순회(Traversal order)를 하면 자동으로 정렬된다

Then can find the node with key k in node <X>’s subtree in O(h) time like binary search:
그러면 노드 <X>의 서브트리 안에서 키 k를 가진 노드를 찾는 작업을
이진 탐색(binary search)처럼 O(h) 시간 안에 수행할 수 있다.
* h: 트리의 높이

 

If k is smaller than the key at <X>, recurse in left subtree (or return None)

만약 찾고자 하는 키 k가 <X>의 키보다 작다면
→ 왼쪽 서브트리에서 재귀적으로 탐색하고, 
→ 만약 왼쪽 서브트리가 없다면 None을 리턴한다 

 

If k is larger than the key at <X>, recurse in right subtree (or return None)

키 k가 <X>의 키보다 크다면
→ 오른쪽 서브트리에서 재귀 탐색한 후 
→ 없으면 None 리턴한다 

 

Otherwise, return the item stored at <X>

그렇지 않고 k와 <X>의 키가 같다면 해당 노드의 아이템을 리턴한다 

 

Other Set operations follow a similar pattern; see recitation

Set의 다른 연산들 (삽입, 삭제 등)도 이와 비슷한 재귀 패턴을 따른다
추가 설명은 보충 수업(Recitation)을 참고하라

 

 

7. Application: Sequence

Sequence BST는 삽입한 순서가 유지되는 트리입니다.

일반적으로 AVL, Splay, 또는 Treap 같은 self-balancing 트리로 구현하고,

각 노드에 서브트리 크기(size)를 저장합니다.

예를 들어, "B"를 루트로 만들고, "A"를 왼쪽, "C"를 오른쪽에 순서대로 삽입하면 다음과 같습니다:

여기까지는 Set BST와 비슷해 보이지만, 

차이는 "B가 0번째, A가 1번째, C가 2번째"라는 삽입된 순서 정보를 유지하고 있다는 점입니다.

 

 

하지만 예를 들어, 삽입 순서가 "A" → "C" → "B" 로 다르면?

다음과 같은 다른 모양의 트리가 만들어집니다.

• 이 구조는 삽입 순서를 유지하는 Sequence BST에서 나올 수 있는 형태입니다.
• 이 트리에서 subtree_at(1) 연산을 하면 → "C"를 반환합니다.

 

이 시퀀스 트리는 언제 사용될까? 

• "i번째 원소"를 빠르게 찾거나 수정하고 싶을 때
• 텍스트 편집기처럼 중간 삽입/삭제가 많은 환경

 

7-2. i 번째 원소 찾기 알고리즘

Sequence 구현에서는 각 노드에 서브트리 크기 정보를 저장(augmentation) 하여

i번째 원소 찾기 같은 연산을 빠르게 수행하는 방법을 사용합니다

 

Idea! Sequence Binary Tree: Traversal order is sequence order
아이디어! 이진 트리의 순회 순서를 시퀀스의 순서로 실행해보자 

트리의 순회 순서 = 시퀀스의 순서

 

How do we find i-th node in traversal order of a subtree?

Call this operation subtree_at(i)
서브트리의 순회 순서 하다가 i번째 노드를 어떻게 찾을까? 이 연산을 subtree_at(i)라고 부른다

 

Could just iterate through entire traversal order, but that’s bad, O(n)
단순히 순회 순서를 다 돌면 되긴 하지만, 그렇게 하면 시간복잡도가 O(n)이라 비효율적이다

 

However, if we could compute a subtree’s size in O(1), then can solve in O(h) time
하지만 만약 각 서브트리의 크기를 O(1) 시간에 계산할 수 있다면, 전체 연산을 O(h) 시간에 해결할 수 있다
h: 트리의 높이

 

– How? Check the size nL of the left subtree and compare to i
방법은? 왼쪽 서브트리의 크기(nL)을 보고, i와 비교한다

 

– If i < nL, recurse on the left subtree
i < nL이면, 왼쪽 서브트리로 재귀 호출한다

 

– If i > nL, recurse on the right subtree with i′ = i − nL − 1
i > nL이면, 오른쪽 서브트리로 가되, 새로운 인덱스 i′ = i − nL − 1로 재귀 호출한다
(왼쪽 서브트리 + 현재 노드 하나는 건너뛰어야 하므로)

 

– Otherwise, i = nL, and you’ve reached the desired node!
그 외에는 i == nL이므로, 지금 노드가 원하는 노드이다

 

어떤 노드 X에서 i번째 원소를 찾고자 할 때,

일단 왼 쪽에 있는

• nL = X.left.size (왼쪽 서브트리 크기)
• 세 경우로 나뉨

조건	의미	조치
i < nL	i번째 원소는 왼쪽에 있다	왼쪽으로 가서 i 그대로 전달
i == nL	i번째 원소는 현재 노드다	현재 노드를 반환
i > nL	i번째 원소는 오른쪽에 있다	오른쪽으로 가되, i′ = i - nL - 1로 전달

 

연습) 다음 트리에서 subtree_at(3) 호출 해보자

중위 순회 순서 = 시퀀스 리스트 순서 

A → B → C → D → E

 

왼쪽 서브트리: A (index 0), B (index 1)
현재 노드: C (index 2)
오른쪽 서브트리: D (index 3), E (index 4)

 

각 노드 (value, size)를 적은 형태는 다음과 같다 

• A(2)는 자기 자신과 B를 포함한 서브트리 크기
• E(2)는 자기 자신과 D를 포함한 서브트리 크기
• C(5)는 전체 크기 = 5

subtree_at(3) 을 찾으려면 

1. 루트 노드 C에서 시작 

 

C의 왼쪽 크기(nL) 과 i를 비교 

C의 왼쪽 크기(nL) 2 < 3

 

왼쪽에 있는 size보다 i가 더 크기 때문에 오른쪽으로 이동

E에서 확인. E가 subtree_at(3)

 

단계	현재 노드	왼쪽 크기 (nL)	i	다음 단계
1	C	2	1	왼쪽 서브트리로 이동
2	A	0	1	오른쪽 서브트리로 이동, i′ = 0
3	B	0	0	i == nL → 현재 노드가 정답 !!

 

 

 

• Maintain the size of each node’s subtree at the node via augmentation
각 노드에 해당 서브트리의 크기를 보조 정보(augmentation)로 저장합니다.

 

– Add node.size field to each node
각 노드에 size 필드를 추가해서 그 노드를 루트로 하는 서브트리의 크기를 저장합니다.

– When adding new leaf, add +1 to a.size for all ancestors a in O(h) time
새 리프 노드를 추가할 때는, 그 리프의 모든 조상 노드 a에 대해 a.size를 +1씩 해주며 업데이트합니다. 시간은 O(h)

– When deleting a leaf, add −1 to a.size for all ancestors a in O(h) time
리프를 삭제할 때는 모든 조상 노드의 size에서 −1씩 빼주며 갱신합니다. 이것도 O(h)

 

• Sequence operations follow directly from a fast subtree at(i) operation
이제 빠른 subtree at(i) 연산이 가능하므로, 시퀀스 기반의 다양한 연산들도 쉽게 구현할 수 있습니다.

 

• Naively, build(X) takes O(nh) time, but can be done in O(n) time; see recitation
단순하게 구현하면 시퀀스를 이 트리로 만드는 데 O(nh) 시간이 걸릴 수 있지만, 사실은 O(n)에 가능합니다. (자세한 건 recitation 참고)

 

 

8. So Far 

 

 

9. Next Time 

• Keep a binary tree balanced after insertion or deletion

• Reduce O(h) running times to O(log n) by keeping h = O(log n)