일정 예약과 이진 탐색 트리(BST)

본 내용은 Deep Into Algorithm from MIT 강의를 들으며 정리한 내용이다.

오늘 해결할 문제는 "활주로 예약 시스템"이다.

활주로 예약 시스템

• 활주로가 매우 혼잡하고 활주로는 단 하나뿐인 공항
• 향후 착륙을 위한 "예약" 필요
• 비행기가 착륙하면 대기 중인 사건 집합에서 제거
• 각각의 착륙 요청에는 "요청 예약 시간" t가 명시되어 있음
• t로부터 k분 전이나 k분 후에 다른 착륙 예약이 없다면, t를 집합에 추가함. k값은 변할 수 있음

이 외의 경우에는 에러로 보고, 예약을 잡지 않는다.

- 예시

활주로 예약 시스템 예시

R(착륙시간) = (41, 46, 49, 56) , k = 3, now = 37 이므로

t = 44 는 허용되지 않는다. (44+3을 하면 46이 겹친다.)

t = 53 은 허용된다.

t = 20 은 허용되지 않는다. (이미 지난 시간)

결국 t가 유효한지 체크하기 위해 R을 탐색해야 하는데 R에 원소가 n개라고 가정하면
일반적인 선형 검색으로는 O(n)이 소요될 것이다.

이번 시간의 목표는 이 시스템을 O(lg n) 시간 안에 효율적으로 운영하는 것이다.

그렇다면 여러 가지 자료구조에 넣어보며 시간 복잡도를 비교해보자.

 

[R이 정렬 되지 않은 배열]

이 리스트에서 주어진 시간 t가 적절한지 확인하기 위해서는 모든 R를 검사해 봐야 한다.

따라서 O(n)의 복잡도를 가진다.

 

[R이 정렬된 배열]

정렬된 리스트이기 때문에 정렬 탐색을 활용하면 주어진 시간 t를 삽입(예약)할 위치를 찾기 위한
복잡도는 Θ(lg n)이 된다.

하지만 여기서 끝나는 것이 아니다. 삽입을 위해 삽입 이후의 값들을 뒤로 옮기는(Shifting) 작업이
필요하기 때문에 여기서 Θ(n)의 시간이 소요된다.

 

[R이 정렬된 리스트]

만약 배열이 아니라 리스트라면 포인터를 옮겨주는 작업만 처리하면
상수 시간 복잡도 내에 삽입이 가능하다.

하지만 일반적인 리스트에서는 이진 탐색도 안되며, 특정 인덱스로 바로 접근하는 것도 힘들다.

결과적으로 추가 및 정렬에는 Θ(n lg n) 시간이 소요된다.

추가와 정렬 과정을 하지 않고 삽입이 가능하지만 이러면 삽입에는 Θ(n) 만큼 시간이 소요된다.

 

[R이 Heap Tree]

힙 트리를 활용하면 O(lg n) 시간 안에 삽입은 가능하다.

만약 힙 트리를 사용하면 이진 탐색을 활용할 수 있을까?

힙 트리에 넣고 싶은 t 값을 체크하기 위해 한쪽(왼쪽 또는 오른쪽) 노드만 고려할 수 없다. 왜냐하면
다른쪽 노드에 t와 k값 이내에 위치한 값이 존재할 수도 있기 때문이다.

따라서 오른쪽 왼쪽 트리를 모두 검사해야 한다.(Root 노드까지 탐색한 후 반대편 노드까지 탐색해 가야 한다.)

즉 이를 위한 시간은 O(n)이 소요된다.

 

[R이 이진 탐색 트리(Binary Search Tree)]

먼저 이진트리의 특성을 살펴볼 필요가 있다.

이진 트리의 각 노드 x에는 key(x)가 존재한다.

기본적으로 이진 탐색 트리는 포인터를 가진 트리라고 생각할 수 있다.

이 포인터는 노드당 부모, 오른쪽, 왼쪽 노드에 대한 총 3개의 포인터로 이루어져 있다. 
즉, 루트가 아닌 다른 노드는 부모인 p(x)가 있다. 노드에는 왼쪽 자식인 left(x)와 오른쪽 자식인 right(x)이 있다.
이것들은 힙과 달리 포인터이다.

 - 이진 탐색 트리의 불변성

• 모든 노드 x와 x의 왼쪽 하위 트리에 있는 모든 노드 y에 대해서 key(y) ≤ key(x)이다.
• x의 오른쪽 하위 트리에 있는 모든 노드 y에 대해서 key(y) ≥ key(x)이다.

 

이진 탐색 트리의 삽입 : insert(val) → O(h) (h : 트리의 높이)

알맞은 위치를 찾을 때까지 루트 노드에서부터 왼쪽 및 오른쪽 포인터를 따라 내려간다.
내려가는 도중 삽입을 원하는 값의 k값 내에 있는 다른 요소를 발견하게 되면 과정을 중단하고 삽입하지 않는다.

이진 탐색 트리

 

이진 탐색 트리에 값이 존재하는 경우, 그 값 찾기 : find(val) → O(h)

값을 찾거나 NIL에 도달할 때까지 왼쪽과 오른쪽 포인터들을 따라간다.

 

이진 탐색 트리에서 최소 요소 찾기 : findmin() → O(h)

더 이상 왼쪽으로 갈 수 없을 때까지 왼쪽으로 간다.

이를 활용해 최솟값을 제거하는 것을 예로 들면, 왼쪽 끝까지 가서 그 값을 지운다.

최솟값 제거

 

이진 탐색 트리에서 다음으로 큰 요소 찾기 : next-larger(x) → O(h)

먼저 x는 값이 아니라 노드라는 것에 주의하자.

1. 오른쪽 자식이 NIL이 아닐 경우, minimum(right)을 리턴
2. NIL인 경우, y = parent(x)
3. y가 NIL이 아니고 x = right(y)인 경우, x=y; y=parent(y)
   return(y);

예시를 살펴보자.

예제 BST

next-larger(find(46))을 하면

1. 오른쪽 자식이 NIL이므로 y =parent(x) (41)
2. y가 NIL이 아니고 x = right(y)이므로 x=y; y=parent(y) (49)
3. return(y); (49)

 

[새로운 요구조건]

이진 탐색 트리에 우리의 시스템의 새로운 요구 조건을 적용시켜 보자.

Rank(t) : 시간 ≤ t에 착륙 예정인 비행기는 몇 대일까? 새로운 요구 조건은 설계도의 수정을 필요로 한다.  

현재 우리가 설계한 이진 탐색 트리로는 이를 효율적으로 해결할 수 없기 때문에 새로운 요소를 추가한다.

이진 탐색 트리 구조 보완

각 노드마다 해당 노드를 포함해 아래에 총 몇 개의 노드가 존재하는지 사이즈를 저장한다.

삽입마다 사이즈를 유지하는 방법은 새롭게 들어오는 노드가 지나가는 노드마다 1씩 추가해주는 방식이다.

만약 42가 들어오게 되면 49, 46, 43을 걸쳐 43의 왼쪽 자식으로 노드가 생성되는데
각 노드마다 size가 1씩 늘어나면 되는 것이다.

이를 활용해 Rank(t)를 구하는 알고리즘은 다음과 같다.

1. 원하는 시간을 찾기 위해 트리를 따라 내려오기
2. 노드의 값이 찾는 값보다 작거나 같으면 1 더하기
3. 왼쪽 서브 트리의 크기만큼 더하기

전체적으로, 이 알고리즘은 O(h)만큼의 시간이 소요된다.

위 그림 예제에서 만약 Rank(79)를 구한다면 

1. 49는 찾는 값보다 작다. (+1)
2. 49의 왼쪽 서브 트리인 46의 사이즈를 더한다. (+2)
3. 오른쪽 자식 노드로 간다.
4. 79는 찾는 값과 같다. (+1)
5. 79의 왼쪽 서브트리인 64의 사이즈를 더한다. (+1)

Rank(79)

위 알고리즘에 따라 연산을 하게 되면 5라는 값이 나오게 된다.

이진 탐색 트리를 활용한 알고리즘은 잘 동작하는 것 같지만 문제점이 존재한다.

정렬된 순서로 삽입된 경우

이와 같은 트리가 구성되면 리스트와 같은 구조가 된다. 이는 O(lg n)이 아닌 O(n)의 시간을 걸리게 한다.

따라서 다음 시간에는 이진 탐색 트리에 균형이 맞도록 조정할 수 있는 균형 이진 탐색 트리에 대해 배울 것이다.

이를 통해 이 문제점을 해결해보자.