체육공대생

Amortized Runtime Analysis: 분할 상환 런타임 분석 알고리즘 A는 아래와 같은 규칙적인 런타임 패턴을 보인다고 하자.각 루프에서는 $\Theta(1)$의 시간이 걸린다.마지막 루프에서는 $\Theta(n)$의 시간이 걸린다.그렇다면 알고리즘 A의 전체 런타임은 얼마일까? $\Theta(n)$이다.마지막 루프에서 발생하는 시간 $\Theta(n)$이 이전 모든 루프에 고르게 분배된다고 가정하면, 각 루프의 평균적인 시간은 여전히 $\Theta(n)$이 된다. 이러한 방식의 런타임 분석을 분할 상환 분석이라 부른다. 하지만, 알고리즘 B는 알고리즘 A와 다소 다르다.대부분의 루프는 $\Theta(1)$의 시간이 걸린다.가끔 드물게 $\Theta(n)$의 시간이 걸리는 루프가 발생한다.이..

레드-블랙 트리는 이진 탐색 트리에 1비트 속성을 추가한 구조로, 각 노드는 빨강 또는 검정색으로 색칠된다. 모든 리프 노드는 NIL이며, 검정색으로 칠해져 있다.이를 레드-블랙 트리 T의 모든 리프에 대해 single sentinel 노드 nil[T] 라고 한다.color[nil[T]]는 항상 검은색이며, 루트 노드의 부모도 nil[T]다. 레드-블랙 트리는 이진 탐색 트리의 모든 속성을 상속받고, nil[T]에 저장된 키 값은 중요하지 않으므로 무시한다.Properties of red-black trees 레드-블랙 트리는 트리의 균형을 유지하기 위해 다음 다섯 가지 속성을 만족한다.모든 노드는 빨강 또는 검정이다.트리의 루트 노드는 항상 검정색이다.모든 리프 노드(센티널 nil[T])는 항상 검정색..