\documentclass[twoside,a4paper,12pt]{book}
%%%%%%%%%%%%%برای رنگی کردن شماره section و ....
\usepackage{color}
\usepackage[indentafter]{titlesec}

\definecolor{mycolor}{rgb}{0,0,1}
%\definecolor{booloo}{cmyk}{1,0,0,0}
\titleformat{\chapter}[display]
{\normalfont\huge\bfseries }{\chaptertitlename \  {\color{mycolor}\thechapter}}{20pt}{\Huge}
 
 \titleformat{\section}[block]
{\normalfont \Large \bfseries }{\sectiontitle {\color{mycolor}\thesection}}{1em}{}

 \titleformat{\subsection}[block]
{ \normalfont \large \bfseries }{{\color{mycolor}\thesubsection}}{1em}{}
%دستور سطر بعد را خودم اضافه کرده ام و جلیل ننوشته است
 \titleformat{\subsubsection}[block]
{ \normalfont \normalsize \bfseries }{{\color{mycolor}\thesubsubsection}}{1em}{}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\usepackage{geometry}
\geometry{
   left=25mm,
  right=25mm,
 %  top=25mm, bottom=25mm,
 }
\usepackage{amsmath}\usepackage{mathrsfs}\usepackage{color}
\usepackage{setspace}\usepackage{amssymb}\usepackage{setspace}
\usepackage{amsthm}\usepackage{fancyhdr}
\usepackage{graphicx}\usepackage[all]{xy}\usepackage{makeidx}
\usepackage{xecolour}\usepackage{xepersian}
%\usepackage{fmultico}\usepackage{fancybox}\usepackage{tocbibind}



\settextfont[Scale=1]{Yas}
\setlatintextfont[Scale=1]{Yas}
\setdigitfont[Scale=1]{PGaramond}


%%%%%%%%%%%%%%%%%%%%برای خط آبی در سربرگ
\makeatletter
\def\thickhrulefill{\leavevmode \leaders \hrule height 1pt \hfill \kern \z@}
\makeatother

\makeatletter
\def\@oddhead{\rightmark\quad {\color{booloo}\thickhrulefill} \quad \thepage }
\def\@evenhead{\thepage \quad {\color{booloo}\thickhrulefill} \quad \leftmark}
\makeatother
\cfoot{}
%%%%%%%%%%%%%%%%%%%%
%رنگی کردن آیتم بندی
\renewcommand\labelenumi{\textcolor{booloo}{\theenumi .}}
\def\ds#1{\displaystyle{#1}}
%\def\Dom{\text{ Dom }}
\def\mfi{\mathop{\forall}^\infty}

%\pagestyle{headings}

%\pagestyle{fancy}
%\pagestyle{headings}
\doublespacing
\renewcommand{\baselinestretch}{1.69}
\setcounter{secnumdepth}{4}
\setcounter{tocdepth}{3}
\defpersianfont\nastaliq[Scale=2]{IranNastaliq}
\defpersianfont\nastaliqq[Scale=2.5]{IranNastaliq}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%برای حذف یک شماره از شماره بندی بخش و زیربخش و ...
\renewcommand{\thesection}{\arabic{section}}
\renewcommand{\thesubsection}{\arabic{subsection}.\thesection}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\definecolor{booloo}{cmyk}{1,0,0,0}

\begin{document}
\chapter{طراحی الگوریتم}
همچنین کد عملیات‌های Rotation و Combine وقتی $p$ فرزند چپ $r$ است به صورت زیر می‌باشد:
\begin{latin}
\begin{flushleft}
//Rotation when p is the left child of r and q is the middle child of r.\\
p $\to$  dataL= r $\to$  dataL;\\
p $\to$  MiddleChild = q $\to$  LeftChild;\\
r $\to$  dataL = q $\to$  dataL;\\
q $\to$  dataL = q $\to$  dataR;\\
q $\to$  LeftChild = q $\to$  MiddleChild;\\
q $\to$  MiddleChild = q $\to$  RightChild;\\
q $\to$  dataR.Key = MAXKEY;\\
...............................................................\\
//Combine when p is the left child of r and q is the right sibling of p.\\
p $\to$  dataL= r $\to$  dataL;\\
p $\to$  dataR= q $\to$  dataL;\\
p $\to$  MiddleChild = q $\to$  LeftChild;\\
q $\to$  RightChild = q $\to$  MiddleChild;\\
if(r $\to$  dataR.Key = MAXKEY)// r was a 2-node\\
$\qquad$ r $\to$  dataL.Key = MAXKEY;\\
else \{\\
$\qquad$ r $\to$  dataL= r $\to$  dataR;\\
$\qquad$ r $\to$  dataR.Key = MAXKEY ;\\
$\qquad$ r $\to$  MiddleChild = r $\to$  RightChild;\\
$\qquad$ \}
\end{flushleft}
\end{latin}
\subsubsection{تجزیه و تحلیل عملکرد حذف از یک درخت 2-3}
مشخص است که یک عملکرد ترکیب یا چرخش به تنهایی در زمانی برابر با $O(1)$ انجام می‌گیرد. اگر یم چرخش انجام شود، عمل حذف کامل می‌گردد. اگر یک ترکیب صورت گیرد، $p$ در درخت 2-3 به یک سطح بالاتر منتقل می‌شود. بنابراین تعداد ترکیباتی که در خلال یک حذف می‌توانند صورت گیرند از ارتفاع درخت 2-3 تجاوز نخواهد کرد و در نتیجه عمل حذف از یک درخت 2-3 با $n$ عنصر به زمانی برابر با $O(\log n)$ نیاز دارد.
%p83
\subsection{درخت قرمز - سیاه Red-Black}
یک درخت قرمز - سیاه به صورت زیر می‌باشد: \RTLfootnote{مطالب این قسمت برگرفته از جزوه دکتر محمد قدسی می‌باشد.}
\subsubsection{خواص درخت قرمز - سیاه}
\begin{itemize}
\item 
هر گره یا قرمز و یا سیاه است.
\item 
هر برگ nil سیاه است.
\item 
دو فرزند یک گره قرمز، سیاه هستند. (در یک گره قرمز، فرزند قرمز نمی‌تواند باشد)
\item 
هر مسیر ساده از یک گره به برگ فرزند (نه لزوماً فرزند مستقیم) شامل تعداد یکسانی گره سیاه است.
\item 
ریشه درخت سیاه است. (این شرط از شروط اساسی نمی‌باشد)
\end{itemize}
مانند مثال زیر:
\subsubsection{تعاریف و قضایای ابتدایی}
Black-Height(x) : بنابر تعریف Black-Height(x) یا $bh(X)$ برابر است با تعداد گره‌های سیاه از $x$ تا یک برگ فرزند\RTLfootnote{رنگ خود $x$ بی‌تأثیر است و آنرا نمی‌شماریم}.

uncle(x) :
\begin{latin}
\begin{flushleft}
if parent[x]=right[parent[parent[x]]] then\\
$\qquad$ uncle[x]:=left[parent[parent[x]]]\\
else uncle[x]:=right[parent[parent[x]]]
\end{flushleft}
\end{latin}
قضیه ۱: حداکثر ارتفاع یک درخت RB که دارای $n$ گره داخلی است، برابر  $2\log_2^{(n+1)}$ است.

اثبات: برای اثبات قضیه فوق ابتدا نشان می‌دهیم که یک زیردرخت به ریشه دلخواه $x$ حداقل دارای $2^{bh(x)}-1$ گره داخلی است. برای اثبات از استقرا بر روی ارتفاع گره داخلی $x$ در درخت استفاده می‌شود.

پایه استقراء:

اگر ارتفاع $x$ صفر باشد، $x$ حتماً برگ و در نتیجه nil است. بنابراین زیردرخت به ریشه $x$ حداقل $2^{bh(x)}-1$ یعنی $2^0-1=0$ گره داخلی دارد.

گام استقرائی:

گره داخلی $x$ را در نظر بگیرید. $bh(x)$ عددی مثبت می‌باشد و $x$ دارای دو فرزند می‌باشد. هر کدام از فرزندان بر حسب آنکه قرمز باشند یا سیاه، Height - Black آنها برابر $bh(x)$ یا $bh(x)-1$ خواهد بود. به علت آنکه هر فرزند $x$ ارتفاعی کمتر از خود $x$ دارد می‌توانیم با استفاده از فرض استقرا نتیجه بگیریم که هر زیردرخت به ریشه یک فرزند $x$ حداقل $2^{bh(x)-1}-1$ گره داخلی دارد. بنابراین زیردرخت به ریشهٔ $x$ حداقل $2^{bh(x)-1}-1+2^{bh(x)-1}-1+1=2^{bh(x)}-1$ گره داخلی خواهد داشت.

از طرف دیگر می‌دانیم که در درخت به ارتفاع $h$ حداقل نیمی از گره‌ها (بدون در نظر داشتن ریشه) بر روی هر مسیر ساده از ریشه به برگ، سیاه هستند. زیرا در غیر این صورت خاصیت ۳ از خواص درخت نقض خواهد شد. در نتیجه Black-Height ریشه حداقل $\frac{h}{2}$ خواهد بود.
$$n\geq 2\frac{h}{2} -1 \Rightarrow 2^\frac{h}{2} \leq n+1 \Rightarrow h \leq 2 \log _2^{(n+1)}$$
نتیجه: ارتفاع درخت RB، $O(\log n)$ hsj.
%p85
\subsubsection{دوران}
برای بازیابی خواص درخت RB بعد از عملیات درج و حذف در بعضی شرایط مجبور خواهیم شد که رنگ بعضی از گره‌ها را عوض کنیم یا تغییراتی در ساختار اشاره‌گرها اعمال نماییم. به همین منظور دو عمل دوران (راستگرد و چپگرد) تعریف می‌نماییم. با توجه به شکل زیر واضح است که این دو عمل هیچ اشکالی در خواص یک درخت دودویی ایجاد نخواهد کرد.

نکته: هنگامی که یک دوران چپگرد انجام می‌شود فرض می‌نماییم که فرزند راست گره مورد نظر nil نباشد.

واضح است که دروان از $O(1)$ باشد زیرا تنها اشاره‌گرها در اثر یک دوران تغییر می‌نمایند و سایر اجزا بدون تغییر می‌ماند.
\begin{latin}
\begin{flushleft}
Left-Rotate(T,x)\\
$\qquad $1. y  $\leftarrow$  right[x] $\qquad$ // SET y\\
$\qquad $2. right[x]   $\leftarrow$  left[y] $\quad$ // Turn y’s left subtree into x’s right subtree\\
$\qquad $3. if left[y] $\neq$ = NIL then\\
$\qquad $4. p[left[y]]   $\leftarrow$  x\\
$\qquad $5. p[y]  $\leftarrow$   p[x] $\qquad$ // Link x’s parent to y\\
$\qquad $6. if p[x] =Nil then\\
$\qquad $7. $\qquad$ root[T]   y\\
$\qquad $8. $\qquad$ else if x= left[p[x]]then\\
$\qquad $9. $\qquad \quad $left[p[x]]  $\leftarrow$   y\\
$\qquad $10. $\qquad \quad$ else right[p[x]]  $\leftarrow$  y\\
$\qquad $11. left[y]  $\leftarrow$   x $\qquad$ // Put x on y’s left\\
$\qquad $12. p[x]  $\leftarrow$  y
\end{flushleft}
\end{latin}
%p86
\subsubsection{درج}






\end{document}