1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
|
\documentclass[11pt]{article}
\usepackage{../intro}
\lhead{\color{gray} \small \textit{Шарафатдинов Камиль 192}}
\rhead{\color{gray} \small \textit{аисд-2}}
\title{Алгоритмы и структуры данных 2}
\usepackage{ctable}
% -- Here bet dragons --
\begin{document}
\maketitle
\drawcat{50pt}
\clearpage
\newcommand{\funcname}[1]{
{\incons
\textbf{#1}}
}
\newcommand{\len}[1]{\mathrm{len}\!\left( #1 \right)}
\dmquestion{1}
Посчитаем минимальное количество вершин, которое может иметь дерево с таким свойством, назовем это число $n(h)$. У корня есть левое и правое поддеревья, высота которых отличается не более, чем на $1$, поэтому в них вершин не меньше $n(h - 1)$ и $n(h - 2)$ то есть всего вершин не меньше $n(h - 1) + n(h - 2) + 1$.
Теперь нам нужна какая-то база для $n$, пусть она будет такая: $n(1) = 1, \ \ n(2) = 2$. Тогда видно, что $n(h) > F_h$, где $F_k$ - k-тое число Фибоначчи. Но так как $F_k = \Theta(\phi^k)$, то, логарифмируя, получаем, что $\log_\phi n(h) \geqslant h$, где $\phi$ - некоторая константа.
\dmquestion{2}
Так как $E$ и $H$ соединены ребром, то хотя бы одна из них черная, а значит, чтобы не нарушать черной высоты, $D$ должна быть черной. $A$ также должна быть черной всегда. Для все остальных вершин есть раскраски, в которых они как черного, так и красного цвета:
\medskip
\center \includegraphics[scale=0.25]{rbt.jpg}
{ \color{lightgray} Я бы честно нарисовал в tikz, но нет времени :(}
\end{document}
|
