\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}