
 \documentclass[12pt, leqno]{article}
\usepackage[T2A]{fontenc}
\usepackage[utf8]{inputenc}        % Кодировка входного документа;
                                    % при необходимости, вместо cp1251
                                    % можно указать cp866 (Alt-кодировка
                                    % DOS) или koi8-r.

\usepackage[english,russian]{babel} % Включение русификации, русских и
                                    % английских стилей и переносов
%%\usepackage{a4}
%%\usepackage{moreverb}
\usepackage{amsmath,amsfonts,amsthm,amssymb,amsbsy,amstext,amscd,amsxtra,multicol}
\usepackage{verbatim}
\usepackage{listings}
\usepackage{algorithm2e}


\usepackage{float}
\usepackage{tabto} %Табуляция
\usepackage{tikz} %Рисование автоматов
\usetikzlibrary{automata,positioning,trees,shapes.geometric}  

\usetikzlibrary{trees,arrows,positioning, calc, shadows, spy, backgrounds} 

\pgfdeclarelayer{back}
	\pgfdeclarelayer{front}
	\pgfsetlayers{back,main,front}

\tikzstyle{redVertex}  =[draw,fill=red,     circle,minimum size=18pt,inner sep=0pt, text=white]
\tikzstyle{blackVertex}=[draw,fill=black,   circle,minimum size=18pt,inner sep=0pt, text=white]
\tikzstyle{genVertex}= [draw,fill=gray!25, right color=gray!15, left color=gray!45,   circle,minimum size=18pt,inner sep=0pt, text=black]
\tikzstyle{nil}        =[draw,fill=black,rectangle,minimum size=15pt,inner sep=0pt, text=white, font=\tiny]
\tikzstyle{seg}        = [fill=blue!20, regular polygon, regular polygon sides=3,inner sep=1pt, outer sep=0pt] 
\tikzstyle{segedge} =[edge from parent path={(\tikzparentnode\tikzparentanchor) edge  (\tikzchildnode.north)}]

\definecolor{darkblue}{rgb}{0.2,0.2,0.6}
\definecolor{darkred}{rgb}{0.6,0.1,0.1}
\definecolor{darkgreen}{rgb}{0.2,0.6,0.2}

\def\arrow{
  (10.75:1.1) -- (6.5:1) arc (6.25:120:1) [rounded corners=0.5] --
  (120:0.9) [rounded corners=1] -- (130:1.1) [rounded corners=0.5] --
  (120:1.3) [sharp corners] -- (120:1.2) arc (120:5.25:1.2)
  [rounded corners=1] -- (10.75:1.1) -- (6.5:1) -- cycle
}

\tikzset{
  ashadow/.style={opacity=.25, shadow xshift=0.05, shadow yshift=-0.05},
}    
 
\tikzstyle{myarrows}=[line width=1mm,draw=gray!30,-triangle 60,postaction={draw, line width=2mm, shorten >=4mm, -}]

\def\bh{\mathbf{bh}}

%\newcommand{segedge}{}


   %[regular polygon, regular polygon sides=3,minimum size=15pt,inner sep=0pt, text=black] 
% triangle/.style = {fill=blue!20, regular polygon, regular polygon sides=3 }
\usepackage{multicol} %Несколько колонок
\usepackage{graphicx}
\usepackage[colorlinks,urlcolor=blue]{hyperref}
\usepackage[stable]{footmisc}
\usepackage{indentfirst}  % абзацный отступ после заголовка
\usepackage{enumitem} %Item tricks


%% \voffset-5mm
%% \def\baselinestretch{1.44}
\renewcommand{\theequation}{\arabic{equation}}
\def\hm#1{#1\nobreak\discretionary{}{\hbox{$#1$}}{}}
\newtheorem{Lemma}{Лемма}
\theoremstyle{definiton}
\newtheorem{Remark}{Замечание}
%%\newtheorem{Def}{Определение}
\newtheorem{Claim}{Утверждение}
\newtheorem{Cor}{Следствие}
\newtheorem{Theorem}{Теорема}
\newtheorem*{known}{Теорема}
\def\proofname{Доказательство}
\theoremstyle{definition}
\newtheorem{Def}{Определение}
\theoremstyle{definition}
\newtheorem{Example}{Пример}

%% \newenvironment{Example} % имя окружения
%% {\par\noindent{\bf Пример.}} % команды для \begin
%% {\hfill$\scriptstyle\qed$} % команды для \end






%\date{22 июня 2011 г.}
\let\leq\leqslant
\let\geq\geqslant
\def\MT{\mathrm{MT}}
%Обозначения ``ажуром''
\def\BB{\mathbb B}
\def\CC{\mathbb C}
\def\RR{\mathbb R}
\def\SS{\mathbb S}
\def\ZZ{\mathbb Z}
\def\NN{\mathbb N}
\def\FF{\mathbb F}
%греческие буквы
\let\epsilon\varepsilon
\let\es\varnothing
\let\eps\varepsilon
\let\al\alpha
\let\sg\sigma
\let\ga\gamma
\let\ph\varphi
\let\om\omega
\let\ld\lambda
\let\Ld\Lambda
\let\vk\varkappa
\let\Om\Omega
\def\first{\mathrm{ FIRST} }
\def\follow{\mathrm{ FOLLOW} }
\let\yield\Rightarrow
\def\abstractname{}

\def\R{{\cal R}}
\def\A{{\cal A}}
\def\B{{\cal B}}
\def\C{{\cal C}}
\def\D{{\cal D}}
\let\w\omega

%классы сложности
\def\REG{{\mathsf{REG}}}
\def\CFL{{\mathsf{CFL}}}
\def\PP{{\mathsf{P}}}
\def\NP{{\mathsf{NP}}}
\def\NPc{{\mathsf{NP}}\text{-}{\rm c}}
\def\coNP{{\rm co}\text{-}{\mathsf{NP}}}
\def\DTIME{{\mathsf{DTIME}}}
\def\NTIME{{\mathsf{NTIME}}}
\def\HALT{{\rm{HALT}}}
\def\SAT{{\rm{SAT}}}
\def\3SAT{{\rm{3\text{-}SAT}}}
\def\2SAT{{\rm{2\text{-}SAT}}}
\def\UNSAT{{\rm{UNSAT}}}
\def\LL{{\mathrm{LL}}}
\def\poly{{\rm{poly}}}
\newcounter{problem}
\newcounter{uproblem}
\newcounter{subproblem}
\def\pr{\medskip\noindent\stepcounter{problem}{\bf \theproblem .  }\setcounter{subproblem}{0} }
\def\prp{\medskip\noindent\stepcounter{problem}{\bf Задача \theproblem.\;}\setcounter{subproblem}{0}}
\def\prstar{\medskip\noindent\stepcounter{problem}{\bf Задача $\bf{\theproblem^*}\negmedspace .$  }\setcounter{subproblem}{0}}
\def\prdag{\medskip\noindent\stepcounter{problem}{\bf Задача $\mathbf\theproblem^\dagger$.\;}\setcounter{subproblem}{0}}
\def\upr{\medskip\noindent\stepcounter{uproblem}{\bf Упражнение \theuproblem .  }\setcounter{subproblem}{0} }
%\def\prp{\vspace{5pt}\stepcounter{problem}{\bf Задача \theproblem .  } }
%\def\prs{\vspace{5pt}\stepcounter{problem}{\bf \theproblem .*   }
\def\prsub{\medskip\noindent\stepcounter{subproblem}{\rm \thesubproblem .  } }
%прочее
\def\quotient{\backslash\negthickspace\sim}
           



\begin{document}
\centerline{\LARGE Задание 7}

\medskip

\begin{center}
	{\Large Структуры данных }
\end{center}

\bigskip

{\bf Литература: }
\begin{enumerate}

	\item {\bf [Кормен 1]} {\em Кормен Т., Лейзерсон Ч., Ривест Р.}\\
	Алгоритмы: Построение и Анализ.\\ М.: МЦНМО, 2002.

	\item {\bf [Кормен 2]} {\em Кормен Т., Лейзерсон Ч., Ривест Р., Штайн К.}\\
	Алгоритмы: Построение и Анализ. (2-е изд.)\\ М.: Вильямс, 2005.

%\item {\bf [ДПВ]} {\em  Дасгупта С., Пападимитриу Х., Вазирани У.}\\ Алгоритмы.\\ М.: МЦНМО, 2014.  


\end{enumerate}
 

\section*{Домашнее задание}

\medskip
\noindent\textbf{Задачи 32-34} из КДЗ-2017.
\medskip

\prp Изучите алгоритм удаления вершины из двоичного дерева поиска, описанный в \textbf{[Кормен 2]}. Докажите корректность данной процедуры.

\prp Известно, что в структуре данных потребуется хранить $k$-элементное подмножество $A$ $n$-элементного множества. После того как в структуру данных будет загружено множество $A$, с помощью неё будет нужно проверить принадлежит ли $A$ элемент $x$. Для этого можно совершить не более $t$ запросов к структуре: каждый запрос $q$ представляет собой конечную строку битов, ответ на каждый запрос -- $1$ бит. 

Структура данных представляет собой таблицу с двумя столбцами: первый столбец состоит из всевозможных запросов $q$ (известных заранее), а правый из битов-ответов на запрос -- правый столбец формируется после загрузки в структуру множества $A$.  Пусть $s(n,k,t)$ -- минимальное количество строк в такой таблице которое достаточно отвести под такую структуру данных.

\prsub Чему равно $s(n,k,1)$?

\prsub Найдите $\min\limits_t( s(n,k,t))$, при каком $t$ он достигается?

\section*{Красно-чёрные деревья}

 

\begin{figure}[h]
\hspace*{-4em}	
 \begin{tikzpicture}[font=\sffamily,very thick,level/.style={sibling distance=80mm/#1}]
\node [blackVertex] (r){8}
  child {
    node [blackVertex] {4}
    child {
      node  [blackVertex] {3}
     child {node [redVertex] {1}
		 child {node [nil] {NIL}}
	        child {node [nil] {NIL}}
	 }
	child {node [nil] {NIL}}    
    }
    child {
      node [blackVertex] {6}
      child {
        node [redVertex] {5}
        child {node [nil] {NIL}}
        child {node [nil] {NIL}}
      }
      child {
        node [redVertex] {7}
        child {node [nil] {NIL}}
        child {node [nil] {NIL}}
      }
    }
  }
  child {
    node [blackVertex] {17}
    child {
      node [blackVertex] {9}
      child {node [nil] {NIL}}
	  child {node [nil] {NIL}}
    }
    child {
      node [redVertex] {19}
      child {
        node [blackVertex] {18}
         child {node [nil] {NIL}}
		 child {node [nil] {NIL}}
      }
      child {
        node [blackVertex] {20}
        child {node [nil] {NIL}}
        child {node [nil] {NIL}}
      }
    }
  };
\end{tikzpicture}
\caption{Красно-чёрное дерево.}\label{RbTreeExample}     
\end{figure}


 
                 
В данном разделе мы приведём определение красно-чёрного дерева и опишем процедуру добавления в него новой вершины. В конце раздела есть задачи на дом. Изложение ведётся на основе~\textbf{[Кормен 2]}. Здесь я приведу более подробные картинки, опишу алгоритм добавления вершины в красно-чёрное дерево и докажу его корректность. За более формальным изложением алгоритма (псевдокоду) стоит обращаться к~\textbf{[Кормен 1]}(\textbf{[Кормен 2]}).

Красно-чёрное дерево -- это двоичное дерево поиска специального вида.  Во-первых, на него налагается следующее техническое условие: если у вершины двоичного дерева нет дочерней вершины, то тогда мы добавляем к ней соответсвующее ребро в терминальный лист NIL. Мы будем называть листьями красно-чёрного дерева -- листья двоичного дерева поиска, а узлы NIL -- терминальными листьями.
Во-вторых, для красно-чёрного дерева выполнены следующие условия:

\begin{enumerate}
	\item Каждая вершина дерева либо красная, либо чёрная.
	\item Каждый терминальный лист -- чёрный.
	\item Корень -- чёрный.
	\item На пути из корня в каждый терминальный лист находится одинаковое количество чёрных вершин.
	\item Обе дочерних вершины красной вершины -- чёрные.
\end{enumerate}

                                      


\begin{figure}[t]
\begin{tikzpicture}[font=\sffamily,very thick,level/.style={sibling distance=80mm/#1}]
	\node [blackVertex] (r){8}
	  child {
	    node [blackVertex] {4}
	    child [clockwise from=-135] {node [blackVertex] {3}
	     child [clockwise from=-135] {node [redVertex] {1}
			% child {node [nil] {NIL}}
		    % child {node [nil] {NIL}}
		 }
		%child {node [nil] {NIL}}    
	    }	    
	  }
	  child {
	    node [blackVertex] {17}
	    child {
	      node [blackVertex] {9}
	     % child {node [nil] {NIL}}
		 % child {node [nil] {NIL}}
	    }
	    child {
	      node [redVertex] {19}
	      child {
	        node [blackVertex] {18}
	        % child {node [nil] {NIL}}
			 %child {node [nil] {NIL}}
	      }
	      child {
	        node [blackVertex] {20}
	        %child {node [nil] {NIL}}
	        %child {node [nil] {NIL}}
	      }
	    }
	  };
	\end{tikzpicture}
	\caption{Не красно-чёрное дерево.}\label{RbTreeBadExample}     	
\end{figure}

  На рис.~\ref{RbTreeExample} приведён пример красно-чёрного дерева\footnote{Картинки в задании построены на основе стиля~\url{https://github.com/MartinThoma/LaTeX-examples/blob/master/tikz/red-black-tree/red-black-tree.tex}}. Терминальные узлы важны для условия баланса. В частности, на рис.~\ref{RbTreeBadExample}, приведено не красно-чёрное дерево, хотя оно будет удовлетворять определению, если не добавлять терминальные листы и изменить соответственно условие 2. И это отличие существенно: при добавлении вершины со значением~6 в дерево на рис.~\ref{RbTreeBadExample} будет нарушено условие баланса~4.

Первый шаг процедуры добавления вершины в красно-чёрное дерево совпадает с алгоритмом добавления вершины в обычное двоичное дерево поиска: мы находим соответсвующий значению новой вершины терминальный лист и заменяем его на добавляемую вершину. Мы красим новую вершину в красной и добавляем к ней терминальные листья. 

Однако, данное действие может нарушить условие~5, что случится если мы добавим в дерево на рис.~\ref{RbTreeExample} вершину со значением $2$. Это нарушение можно исправить путём перестроения дерева и перекраски его вершин, сохраняющей при этом свойства~1-5. В качестве процедуры перестроения дерева мы используем операцию поворота, приведённую на рис.~\ref{Rotates}.



                                                                  
%%%%%%%%%%%%%%%%%%% Повороты

\begin{figure}

		 \begin{tikzpicture}[font=\sffamily,very thick, level/.style={sibling distance=35mm/#1}   ]
				\draw[color=darkgray, right color=gray, left color=gray!60, %
					    drop shadow={ashadow, color=gray!60!black}] [rotate=-20, yscale=1,xscale=-1, yshift=-1, xshift=-2] \arrow;
		\node [genVertex] (r){x}
		  child  {
		    node [genVertex] {y}
		    child [segedge]   {node [seg] {$\alpha$}}    
		    child [segedge]  {node [seg] {$\beta$}}  
		  } 
		  child [sibling angle=45, clockwise from=0, level distance=25mm, segedge] {node [seg] {$\gamma$}};	  %level distance=35mm,
%%%%%
                                    
		\draw [myarrows] (2.5,-0.25) -- (5,-0.25) ;
		\draw [myarrows] (5,-1) -- (2.5,-1) ;
         
		 \draw[color=darkgray, right color=gray, left color=gray!60, %
				    drop shadow={ashadow, color=gray!60!black}] [rotate=20, yscale=1,xscale=1, yshift=-70, xshift=185] \arrow;
		\node [genVertex] (r2) at (7,0) {y}
		child [clockwise from=235, level distance=25mm,segedge]   {node [seg] {$\alpha$}}
		 child  {
		   node [genVertex] {x}
		    child [segedge]   {node [seg] {$\beta$}}    
		    child [segedge]  {node [seg] {$\gamma$}}    
		 };

		\end{tikzpicture}

	\caption{Повороты}\label{Rotates}
\end{figure}
 

Напомним, что если спроецировать значения всех вершин двоичного дерева поиска на ось $Ox$, то мы получим неубывающую числовую последовательность. Более того, это является необходимым и достаточным условием для того, чтобы двоичное дерево было двоичным деревом поиска. Исходя из этого мы и будем обосновывать корректность операций поворотов.

Обратимся к рис.~\ref{Rotates}. Греческие буквы в треугольниках обозначают на нём поддеревья. Обозначим через $[\alpha]$ отрезок, полученной проекцией значений всех вершин поддерева $\alpha$ на ось $Ox$. Тогда проекции на ось $Ox$ значений вершин левого и правого деревьев будут совпадать: они равны $[\alpha]y[\beta]x[\gamma]$. Значит, эти деревья эквивалентны: одно можно заменить на другое не нарушив при этом порядка на вершинах. Также их можно заменить как поддеревья в некотором двоичном дереве поиска и не нарушить при этом его корректность. Замена левого дерева на правое называется \emph{правым поворотом}, а обратная замена -- \emph{левым поворотом}.  %Значит, можно заменить одно двоичное дерево поиска на другое и получить при этом эквивалентное дерево поиска.

Мы будем использовать повороты вместе с допустимой перекраской вершин, чтобы решать коллизии, возникающие в ходе добавления новой вершины в красно-чёрное дерево. Общий план алгоритма решения коллизий состоит в следующем: мы будем преобразовывать красно-чёрное дерево таким образом, чтобы в результате преобразования конфликтующие вершины поднимались вверх; при этом не будет нарушаться условие~4 о сохранении чёрной высоты. В результате этого процесса коллизия либо разрешится на этапе подъёма, либо достигнет корня. Однако, корень всегда можно перекрасить в чёрный цвет не нарушая ни одного из свойств 1-5! Ведь тогда количество чёрных вершин на каждом пути из корень в терминальный лист лишь возрастёт на 1.

 Для контроля за выполнением условия~4, мы вводим функцию \emph{чёрной высоты} $\bh(u)$ вершины $u$. Она возвращает количество чёрных вершин на пути из $u$ в каждый терминальный лист, считая $u$, если она чёрная. Функция $\bh$ не определена, если из $u$ есть два пути в терминальные листы с разным количеством чёрных вершин.  %В результате этой перекраске возрастёт чёрная высота каждого пути из корня в терминальный лист.
 
%%%%%%%%%%%%%%%%%%% Fix RB

\begin{figure}   
	          
 \hspace*{-2em} \begin{tikzpicture}[font=\sffamily,very thick, level/.style={sibling distance=35mm/#1}   ]
					\node [blackVertex] (r)  {x}
					  child  {%[sibling distance=30mm]
					    node [redVertex] {y}
					    child [sibling distance=22mm]  { node [redVertex] {v} 
					    	 child [segedge]   {node [seg] {$\alpha$}}    
							    child [segedge]  {node [seg] {$\beta$}}	
						}	    
					    child [sibling distance=22mm] { node [blackVertex] {w} 
					    	 child [segedge]   {node [seg] {$\gamma$}}    
							    child [segedge]  {node [seg] {$\delta$}}
						}
					  } 
					 	child {node [redVertex] {z}%[sibling distance=30mm]
					    child [segedge]   {node [seg] {$\eps$}}    
					    child [segedge]  {node [seg] {$\zeta$}} };
					 
						


						\draw [myarrows] %[color=darkblue, right color=blue, left color=blue!60]
						 (2.7,-0.7) -- (5.2,-0.7);  					

	%%%%%%%%%%
					 \node [redVertex] (r2)  at (8,0) {x}
						  child  {%[sibling distance=30mm]
						    node [blackVertex] {y}
						    child [sibling distance=22mm]  { node [redVertex] {v} 
						    	 child [segedge]   {node [seg] {$\alpha$}}    
								    child [segedge]  {node [seg] {$\beta$}}	
							}	    
						    child [sibling distance=22mm] { node [blackVertex] {w} 
						    	 child [segedge]   {node [seg] {$\gamma$}}    
								    child [segedge]  {node [seg] {$\delta$}}
							}
						  } 
						 	child {node [blackVertex] {z}%[sibling distance=30mm]
						    child [segedge]   {node [seg] {$\eps$}}    
						    child [segedge]  {node [seg] {$\zeta$}} };
 

   			\end{tikzpicture} 

	
\begin{comment}
	
  
	  \begin{multicols}{2}
		 \begin{tikzpicture}[font=\sffamily,very thick, level/.style={sibling distance=35mm/#1}   ]
		\node [blackVertex] (r){x}
		  child  {
		    node [redVertex] {y}
		    child [segedge]   {node [seg] {$\alpha$}}    
		    child { node [redVertex] {w} 
		    	 child [segedge]   {node [seg] {$\beta$}}    
				    child [segedge]  {node [seg] {$\gamma$}}
			}
		  } 
		 	child {node [redVertex] {z}
		    child [segedge]   {node [seg] {$\delta$}}    
		    child [segedge]  {node [seg] {$\eps$}} };
		\end{tikzpicture}
%%%%%%%%%%%
		 \begin{tikzpicture}[font=\sffamily,very thick, level/.style={sibling distance=35mm/#1}   ]
		\node [redVertex] (r){x}
		  child  {
		    node [blackVertex] {y}
		    child [segedge]   {node [seg] {$\alpha$}}    
		    child { node [redVertex] {w} 
		    	 child [segedge]   {node [seg] {$\beta$}}    
				    child [segedge]  {node [seg] {$\gamma$}}
			}
		  } 
		 	child { node [blackVertex] {z}
		    child [segedge]   {node [seg] {$\delta$}}    
		    child [segedge]  {node [seg] {$\eps$}} };
		\end{tikzpicture}

	\end{multicols}
\end{comment} 	
	\caption{Первый случай}\label{FirstCase}
\end{figure}

Итак, начнём рассматривать всевозможные случаи, возникающие в результате коллизий. Заметим, что поскольку корень всегда чёрный, то коллизии всегда возникают на глубине не меньшей, чем $3$. При этом, в результате добавления вершины возникает ровно одна коллизия, и мы будем поддерживать этот инвариант. Так, на рис.~\ref{FirstCase} коллизия возникла из-за добавления или подъёма вершины $v$. При этом, чёрная высота вершин $v$ и $w$ одинаковая, также как у $y$ и $z$, а $w$ -- чёрная вершина, иначе в дереве было бы две коллизии. Заметим, что вершина $x$ всегда покрашена в чёрный: иначе была бы коллизия между $x$ и $y$.

Первый случай самый простой: для его решения достаточно перекрасить вершину $y$ и $z$ в чёрный цвет, а $x$ -- в красный. Данная перекраска не меняет чёрную высоту указанных вершин. В результате перекраски $x$, коллизия либо вовсе исчезнет, либо поднимется выше. Если вершина $x$ была корнем дерева, то её можно просто перекрасить в чёрный. 

Также под первый случай попадает симметричный случай, когда вершина $v$ -- чёрная, а $w$ -- красная. Эта симметрия, в отличие от второго и третьего случаев, не играет роли. Также мы будем далее опускать симметричные случаи конфликтов в правых поддеревьях $x$. 


 \begin{figure}[t]
	
    
 \hspace*{-3em} \begin{tikzpicture}[font=\sffamily,very thick, level/.style={sibling distance=35mm/#1}   ]


		
	    \draw[color=darkred, right color=red, left color=red!60, %
			    drop shadow={ashadow, color=red!60!black}] [rotate=20, yshift=-29, xshift=-61] \arrow;			 
\begin{pgfonlayer}{back}  			

	
		\node [blackVertex] (r){x}
		  child  {
		    node [redVertex] {y}
		    child [sibling distance=22mm]  { node [blackVertex] {v} 
		    	 child [segedge]   {node [seg] {$\alpha$}}    
				    child [segedge]  {node [seg] {$\beta$}}	
			}	    
		    child [sibling distance=22mm] { node [redVertex] {w} 
		    	 child [segedge]   {node [seg] {$\gamma$}}    
				    child [segedge]  {node [seg] {$\delta$}}
			}
		  } 
		 	child {node [blackVertex] {z}
		    child [segedge]   {node [seg] {$\eps$}}    
		    child [segedge]  {node [seg] {$\zeta$}} };
\end{pgfonlayer}   		
		              
		\draw [myarrows] %[color=darkblue, right color=blue, left color=blue!60]
		 (3.5,-1) -- (6,-1);
		
		\node [blackVertex] (r2) at (9,0)  {x}
		  child  {%[sibling distance=30mm]
		    node [redVertex] {w}
		    child [sibling distance=22mm]  { node [redVertex] {y} 
		    	 child [segedge]   {node [seg] {$\alpha^\prime$}}    
				    child [segedge]  {node [seg] {$\gamma$}}	
			}	    
		    child [segedge]   {node [seg] {$\delta$}}    
		  } 
		 	child {node [blackVertex] {z}%[sibling distance=30mm]
		    child [segedge]   {node [seg] {$\eps$}}    
		    child [segedge]  {node [seg] {$\zeta$}} };
		
		\end{tikzpicture}

	\caption{Второй случай}\label{SecondCase}
\end{figure}

 
\begin{figure}[H]
	 { \setlength\columnsep{5em} \begin{multicols}{2}
		\begin{tikzpicture}[font=\sffamily,very thick, level/.style={sibling distance=35mm/#1}   ] 
		
		 \draw[color=darkred, right color=red, left color=red!60, %
			    drop shadow={ashadow, color=red!60!black}] [rotate=20, yshift=-1, xshift=-2] \arrow;
		
		\node [redVertex] {y}
		    child { node [blackVertex] {v} 
		    	 child [segedge]   {node [seg] {$\alpha$}}    
				    child [segedge]  {node [seg] {$\beta$}}	
			}	    
		    child { node [redVertex] {w} 
		    	 child [segedge]   {node [seg] {$\gamma$}}    
				    child [segedge]  {node [seg] {$\delta$}}
			};
		  
			\draw [myarrows] %[color=darkblue, right color=blue, left color=blue!60]
			 (3.5,-1) -- (6,-1);
	 
		\node [redVertex] at (9,0) {w}			
		    child { node [redVertex] {y}
		 	   child { node [blackVertex] {v} 
			    	 child [segedge]   {node [seg] {$\alpha$}}    
					    child [segedge]  {node [seg] {$\beta$}}	
				}
				child [segedge]   {node [seg] {$\gamma$}}
			}	    
			child [segedge]  {node [seg] {$\delta$}};


		 
		\end{tikzpicture}
%%%%%%%%%%%
	   

	\end{multicols} }
	\caption{Сведение поворотом к третьему случаю}
\end{figure}
  
Перейдём теперь ко второму случаю, изображённому на рис.~\ref{SecondCase}.  Его анализ довольно короткий: мы преобразуем его к третьему случаю левым поворотом. Поскольку поворот, как мы показали выше, преобразует поддерево двоичного дерева поиска в эквивалентное, то новых коллизий кроме коллизии между $y$ и $w$ не возникнет.

Третий случай, пожалуй, самый содержательный. Заметим, что чёрная высота вершин $v,w,y,z$ совпадает, в то время как $\bh(x)=\bh(y)+1$. Применив правый поворот относительно вершины $x$ мы получаем, что  $\bh(v) = \bh(x)-1$, а значит из $y$ есть два пути в листья с разным количеством чёрных вершин. Исправим это, обменяв цвета вершин $x$ и $y$: теперь чёрная высота вершин $x$ и $v$ выровнялась, а значит свойство $4$ осталось выполненным. Заметим, что при повороте не были нарушены свойство~4 для путей, проходящих через $x$, поскольку $\bh(w) = \bh(z) = \bh(x)-1$.


%%%%%%%%%%%%%%%%%%%%%%%% Третий случай 


\begin{figure}[t!]
%	 { \setlength\columnsep{5em} \begin{multicols}{2}
	% \hspace*{-8em}     \hspace*{-3em}
 \begin{tikzpicture}[font=\sffamily,very thick, level/.style={sibling distance=35mm/#1}   ]
	
		 \draw[color=darkred, right color=red, left color=red!60, %
			    drop shadow={ashadow, color=red!60!black}] [rotate=-20, yscale=1,xscale=-1, yshift=-1, xshift=-2] \arrow;
				\node [blackVertex] (r)  {x}
				  child  {%[sibling distance=30mm]
				    node [redVertex] {y}
				    child [sibling distance=22mm]  { node [redVertex] {v} 
				    	 child [segedge]   {node [seg] {$\alpha$}}    
						    child [segedge]  {node [seg] {$\beta$}}	
					}	    
				    child [sibling distance=22mm] { node [blackVertex] {w} 
				    	 child [segedge]   {node [seg] {$\gamma$}}    
						    child [segedge]  {node [seg] {$\delta$}}
					}
				  } 
				 	child {node [blackVertex] {z}%[sibling distance=30mm]
				    child [segedge]   {node [seg] {$\eps$}}    
				    child [segedge]  {node [seg] {$\zeta$}} };

				 
					
					\begin{comment}
						          \draw[color=darkblue, right color=blue, left color=blue!60, %
						    drop shadow={ashadow, color=blue!60!black}] [rotate=-20, yscale=1,xscale=-1, yshift=-1, xshift=-2] (10.75:1.1) -- (6.5:1) arc (6.25:120:1) [rounded corners=0.5] --
							  (120:0.9) [rounded corners=1] -- (130:1.1) [rounded corners=0.5] --
							  (120:1.3) [sharp corners] -- (120:1.2) arc (120:5.25:1.2)
							  [rounded corners=1] -- (10.75:1.1) -- (6.5:1) -- cycle;
							
							(10.75:1.1) -- (6.5:1) arc (6.25:120:1) [rounded corners=0.5] --
							  (120:0.9) [rounded corners=1] -- (130:1.1) [rounded corners=0.5] --
							  (120:1.3) [sharp corners] -- (120:1.2) arc (120:5.25:1.2)
							  [rounded corners=1] -- (10.75:1.1) -- (6.5:1) -- cycle
					\end{comment}
				   
					
					\draw [myarrows] %[color=darkblue, right color=blue, left color=blue!60]
					 (2.7,-0.7) -- (5.2,-0.7);  					
					
%%%%%%%%%%
				  \node  [redVertex] (r2) at (8,0) {y}
						  child  { node [redVertex] {v} %[sibling distance=30mm]
						    	 child [segedge]   {node [seg] {$\alpha$}}    
								    child [segedge]  {node [seg] {$\beta$}}	
							}
						child{ node [blackVertex] {x}
						  child  { node [blackVertex] {w} %[sibling distance=30mm]
						    	 child [segedge]   {node [seg] {$\gamma$}}    
								    child [segedge]  {node [seg] {$\delta$}}
							}
						 child [sibling distance=22mm] {node [blackVertex] {z}
						    child [segedge]   {node [seg] {$\eps$}}    
						    child [segedge]  {node [seg] {$\zeta$}} }
						}; 

 
              
		\draw [myarrows] %[color=darkblue, right color=blue, left color=blue!60]
		 (7.5,-5.5) -- (5.5,-7);

			\node [blackVertex] (r3) at (4,-7) {y}
			  child  { node [redVertex] {v} %[sibling distance=30mm]
			    	 child [segedge]   {node [seg] {$\alpha$}}    
					    child [segedge]  {node [seg] {$\beta$}}	
				}
			child{ node [redVertex] {x}%[sibling distance=30mm]
			  child [sibling distance=22mm] { node [blackVertex] {w} 
			    	 child [segedge]   {node [seg] {$\gamma$}}    
					    child [segedge]  {node [seg] {$\delta$}}
				}
			 child [sibling distance=22mm] {node [blackVertex] {z}
			    child [segedge]   {node [seg] {$\eps$}}    
			    child [segedge]  {node [seg] {$\zeta$}} }
			}; 

			\end{tikzpicture}
%     	\end{center}
	\caption{Третий случай}
\end{figure}

Итак, алгоритм решения коллизий состоит в применении указанных преобразований, в зависимости от одного из трёх случаев коллизии. Мы показали как в каждом случае либо решить коллизию, либо переместить коллизию выше, не нарушив оставив при этом свойства 1-4 выполненными. Таким образом, либо коллизия исчезнет не достигнув корня, либо корень будет окрашен в красный цвет -- тогда перекрасим корень в чёрный.
  
 

%%%%%%%%%%%%%%%%%%% Задача

\begin{figure}[h]
\hspace*{-2em}	
 \begin{tikzpicture}[font=\sffamily,very thick,level/.style={sibling distance=80mm/#1}]
\node [blackVertex] (r){8}
  child {
    node [blackVertex] {3}
    child {node [nil] {NIL}}    
    child {
      node [redVertex] {6}
      child {node [nil] {NIL}}
      child {node [nil] {NIL}}
    }
  }
  child {
    node [redVertex] {17}
    child {
      node [blackVertex] {9}
      child {node [nil] {NIL}}
	  child {node [nil] {NIL}}
    }
    child {
      node [blackVertex] {19}
     	 child {node [nil] {NIL}}
		 child {node [nil] {NIL}}
    }
  };
\end{tikzpicture}
\caption{К задаче 3.}\label{RbINSproblem}
\end{figure}
  


\prp Вставьте в красно-чёрное дерево с рис.~\ref{RbINSproblem} вершину со значением $5$.

 
\begin{comment}
	
%%%%%%%%%%%%%%%%%%%% Печаль-беда

\begin{figure}
	 { \setlength\columnsep{5em} \begin{multicols}{2}
		\hspace*{-2em}\begin{tikzpicture}[font=\sffamily,very thick, level/.style={sibling distance=35mm/#1}   ]
		\node [blackVertex] (r){x}
		  child  {
		    node [redVertex] {y}
		    child [sibling distance=22mm]  { node [blackVertex] {v} 
		    	 child [segedge]   {node [seg] {$\alpha$}}    
				    child [segedge]  {node [seg] {$\beta$}}	
			}	    
		    child [sibling distance=22mm] { node [redVertex] {w} 
		    	 child [segedge]   {node [seg] {$\gamma$}}    
				    child [segedge]  {node [seg] {$\delta$}}
			}
		  } 
		 	child {node [blackVertex] {z}
		    child [segedge]   {node [seg] {$\eps$}}    
		    child [segedge]  {node [seg] {$\zeta$}} };
		\end{tikzpicture}
%%%%%%%%%%%
		\begin{tikzpicture}[font=\sffamily,very thick, level/.style={sibling distance=35mm/#1}   ]
		\node [redVertex] (r){y}
		  child  { node [blackVertex] {v} 
		    	 child [segedge]   {node [seg] {$\alpha$}}    
				    child [segedge]  {node [seg] {$\beta$}}	
			}
		child{ node [blackVertex] {x}
		  child [sibling distance=22mm] { node [redVertex] {w} 
		    	 child [segedge]   {node [seg] {$\gamma$}}    
				    child [segedge]  {node [seg] {$\delta$}}
			}
		 child [sibling distance=22mm] {node [blackVertex] {z}
		    child [segedge]   {node [seg] {$\eps$}}    
		    child [segedge]  {node [seg] {$\zeta$}} }
		}; 
		   
		\end{tikzpicture}     

	\end{multicols} }  
	    
	 \begin{tikzpicture}[font=\sffamily,very thick, level/.style={sibling distance=35mm/#1}   ]
			 \node [redVertex] {v}  
			 	child [segedge]   {node [seg] {$\alpha$}}			    
			    child { node [redVertex] {y} 
					child [segedge]  {node [seg] {$\beta$}}
			    	child { node [blackVertex] {w} 
					    	 child [segedge]   {node [seg] {$\gamma$}}    
							    child [segedge]  {node [seg] {$\delta$}}
					}
				};
		   
		\end{tikzpicture}
  
	\caption{Плохой второй случай =(}
\end{figure}
\end{comment} 
\begin{comment}
	


\begin{figure}[h]
\hspace*{-2em}	
 \begin{tikzpicture}[font=\sffamily,very thick,level/.style={sibling distance=80mm/#1}]
\node [blackVertex] (r){8}
  child {
    node [blackVertex] {3}
    child {
      node [blackVertex] {1}
     child {node [nil] {NIL}} 
      child {
        node [redVertex] {2}
        child {node [nil] {NIL}}
        child {node [nil] {NIL}}
      }
    }
    child {
      node [blackVertex] {6}
      child {
        node [nil] {NIL}
      }
      child {
        node [redVertex] {7}
        child {node [nil] {NIL}}
        child {node [nil] {NIL}}
      }
    }
  }
  child {
    node [blackVertex] {17}
    child {
      node [blackVertex] {9}
      child {node [nil] {NIL}}
	  child {node [nil] {NIL}}
    }
    child {
      node [redVertex] {19}
      child {
        node [blackVertex] {18}
         child {node [nil] {NIL}}
		 child {node [nil] {NIL}}
      }
      child {
        node [blackVertex] {20}
        child {node [nil] {NIL}}
        child {node [nil] {NIL}}
      }
    }
  };
\end{tikzpicture}
\caption{Красно-чёрное дерево.}\label{RbTreeExample}     
\end{figure}  
 \end{comment}  



\end{document}

