\documentclass[UTF8]{ctexart}
\usepackage[ruled, linesnumbered]{algorithm2e}
\usepackage{amsmath}
\usepackage{amsfonts}
\usepackage{amssymb}
\usepackage{amsthm}
\usepackage{boxedminipage}
\usepackage{circuitikz}
\usepackage{fancyhdr}
\usepackage{float}
\usepackage{fullpage}
\usepackage{gensymb}
\usepackage{geometry}
\usepackage{graphicx}
\usepackage[hidelinks]{hyperref}
\usepackage{listings}
\usepackage{mflogo}
\usepackage{multirow}
\newcommand{\nop}[1]{}
\usepackage{siunitx}
\usepackage{subfigure}
\usepackage{texnames}
\usepackage{textcomp}
\usepackage{tikz}
\usepackage{titlesec}
\usepackage{wrapfig}
\usepackage{xcolor}
\usepackage{xltxtra}

\setlength{\headheight}{0pt}
\geometry{left=2.5cm,right=2.5cm,headsep=2cm,bottom=2cm,footnotesep=2cm}
\pagestyle{fancy}
\fancyfoot[C]{\thepage}
\fancyhead[L]{计算机科学与技术系}
\fancyhead[C]{
    \begin{huge}
        \textbf{}
    \end{huge}\\
    \vspace{0.4cm}
    \ \ \ \ \ \ \ \ }
\fancyhead[R]{\ \ \ \ \ \ \ \ \ \ \ \ 2023年10月21日}

\ctexset{
    section={
      format+ = \Large \raggedright,
     }
}

\newtheorem{theorem}{定理}
\newtheorem{lemma}{引理}
\newtheorem{definition}{定义}

\parindent0mm
%\pagestyle{empty}

\usetikzlibrary{arrows, positioning}

\newcounter{aufgc}
\newenvironment{exercise}[1]%
{\refstepcounter{aufgc}\textbf{问题 \arabic{aufgc}} \emph{#1} \\}
{\vspace{0.2cm}}%

\renewcommand{\labelenumi}{(\alph{enumi})}

\begin{document}

\textbf{Q1.}

1. 最大树高 $H_{\max}=7$，最小树高 $H_{\min}=3$，分别如下

\begin{tikzpicture}
    \node[draw, circle](1) at (0,0) {-3};
    \node[draw, circle](2) at (1,-1) {2};
    \node[draw, circle](3) at (2,-2) {3};
    \node[draw, circle](4) at (3,-3) {4};
    \node[draw, circle](5) at (4,-4) {5};
    \node[draw, circle](6) at (5,-5) {6};
    \node[draw, circle](7) at (6,-6) {9};
    \node[draw, circle](8) at (7,-7) {13};
    \draw (1)--(2)--(3)--(4)--(5)--(6)--(7)--(8);

    \node[draw, circle] (11) at(10,0) {5};
    \node[draw, circle] (12) at(8.5,-1) {3}
    child{node[draw, circle] (13) {2}}
    child{node[draw, circle] (15) {4}};
    \node[draw, circle] (16) at(11.5,-1) {9}
    child{node[draw, circle] (17) {6}}
    child{node[draw, circle] (18) {13}};
    \node[draw, circle] (14) at(7,-4) {-3};
    \draw (11) -- (12)
    (11)--(16)
    (13)--(14);
\end{tikzpicture}

2. 如下，两棵红黑树的黑高分别为3和4.

\begin{tikzpicture}
    \node[draw, circle, fill, text=white] (1) at(0,0) {5};
    \node[draw, circle] (2) at(-1.5,-1) {3}
    child{node[draw, circle, fill, text=white] (3) {2}}
    child{node[draw, circle, fill, text=white] (5) {4}};
    \node[draw, circle] (6) at(1.5,-1) {9}
    child{node[draw, circle, fill, text=white] (7) {6}}
    child{node[draw, circle, fill, text=white] (8) {13}};
    \node[draw, circle] (4) at(-3,-4) {-3}
    child{node[draw, circle, fill, text=white] (9) {nil}}
    child{node[draw, circle, fill, text=white] (10) {nil}};
    \node[draw, circle, fill, text=white] (11) at(-2,-4) {nil};
    \node[draw, circle, fill, text=white] (12) at(-1.2,-4) {nil};
    \node[draw, circle, fill, text=white] (13) at(-0.4,-4) {nil};
    \node[draw, circle, fill, text=white] (14) at(0.4,-4) {nil};
    \node[draw, circle, fill, text=white] (15) at(1.2,-4) {nil};
    \node[draw, circle, fill, text=white] (16) at(2,-4) {nil};
    \node[draw, circle, fill, text=white] (17) at(2.8,-4) {nil};
    \draw (1) -- (2)
    (1) -- (6)
    (3) -- (4)
    (3) -- (11)
    (5) -- (12)
    (5) -- (13)
    (7) -- (14)
    (7) -- (15)
    (8) -- (16)
    (8) -- (17);

    \node[draw, circle, fill, text=white] (21) at(8,0) {5};
    \node[draw, circle, fill, text=white] (22) at(6.5,-1) {3}
    child{node[draw, circle, fill, text=white] (23) {2}}
    child{node[draw, circle, fill, text=white] (25) {4}};
    \node[draw, circle, fill, text=white] (26) at(9.5,-1) {9}
    child{node[draw, circle, fill, text=white] (27) {6}}
    child{node[draw, circle, fill, text=white] (28) {13}};
    \node[draw, circle] (24) at(5,-4) {-3}
    child{node[draw, circle, fill, text=white] (29) {nil}}
    child{node[draw, circle, fill, text=white] (30) {nil}};
    \node[draw, circle, fill, text=white] (31) at(6,-4) {nil};
    \node[draw, circle, fill, text=white] (32) at(6.8,-4) {nil};
    \node[draw, circle, fill, text=white] (33) at(7.6,-4) {nil};
    \node[draw, circle, fill, text=white] (34) at(8.4,-4) {nil};
    \node[draw, circle, fill, text=white] (35) at(9.2,-4) {nil};
    \node[draw, circle, fill, text=white] (36) at(10,-4) {nil};
    \node[draw, circle, fill, text=white] (37) at(10.8,-4) {nil};
    \draw (21) -- (22)
    (21) -- (26)
    (23) -- (24)
    (23) -- (31)
    (25) -- (32)
    (25) -- (33)
    (27) -- (34)
    (27) -- (35)
    (28) -- (36)
    (28) -- (37);
\end{tikzpicture}

\hrulefill\medskip

\textbf{Q2.}

1. 见算法~\ref{algo:1}.

\begin{algorithm}[htbp]
    \caption{\textsc{InorderTreeWalk-Leaf} ($x$)}\label{algo:1}
    \uIf{$x\neq$ NIL}{
        \textsc{InorderTreeWalk-Leaf} ($left[x]$)\;
        \uIf{$left[x]=$ NIL and $right[x]=$ NIL}{
            print $x$\;
        }
        \textsc{InorderTreeWalk-Leaf} ($right[x]$)\;
    }
\end{algorithm}

2. 见算法~\ref{algo:2}.

\begin{algorithm}[htbp]
    \caption{\textsc{TreeSearch-Set} ($x,k$)}\label{algo:2}
    \SetKwProg{Fn}{Function}{:}{}
    \SetKwFunction{ts}{TreeSearch-Add}
    \SetKwFunction{tsc}{TreeSearch-Closure}
    $S_{path}=S_{left}=S_{right}=\Phi$\;
    \Fn{\ts{$x,k$}}{
    \uIf{$x=$ NIL}{\Return{}\;}
    $S_{path}.add(key[x])$\;
    \uIf{$k=key[x]$}{
    \Return{}\;
    }
    \eIf{$k<key[x]$}{
        $S_{right}.add(right[x])$\;
        \Return{\ts{$left[x],k$}}\;
    }{
        $S_{left}.add(left[x])$\;
        \Return{\ts{$right[x],k$}}\;
    }}
    \Fn{\tsc{$x,S$}}{
        \uIf{$x\neq$NIL}{
            \tsc{$left[x],S$}\;
            $S.add(key[x])$\;
            \tsc{$right[x], S$}\;
        }
    }
    \ts{$x,k$}\;
    \ForEach{$y\in S_{left}$}{\tsc{$y,S_{left}$}\;}
    \ForEach{$y\in S_{right}$}{\tsc{$y,S_{right}$}\;}
\end{algorithm}

3. 时间复杂度分析：算法~\ref{algo:2} 实质上是在搜索到 $k$ 的过程
中将另一半子树上的节点加入到 $S_{left}$ 或是 $S_{right}$，其中
搜索的时间复杂度为 $O(h)=O(n)$，而再将 $S_{left}$ 和 $S_{right}$
上节点所在子树全部节点加入到对应集合中的时间复杂度为叶节点数的两
倍加树上所有节点数，这个值是 $O(n)$，因此总的时间复杂度为 $O(n)$.

4. 前两条正确.只需证明 \[\forall a\in S_{left},\forall b\in S_{right},a\leqslant k\leqslant b.\]

\begin{proof}
    $\forall a\in S_{left}$，总存在 $a'\in S_{path}$，$a'$ 是
    $a$ 的祖先，则 $a$ 在 $a'$ 的左子树上，而 $a'$ 左子树上的所
    有节点都比 $a'$ 键值小，同时 $k$ 对应键值节点在 $a'$ 的右子
    树上，也就是 $a\leqslant a'\leqslant k$，同理有
    $\forall b\in S_{right},k\leqslant b$.
\end{proof}

第三条反例如下，$k=6$ 时，$S_{path}=\{2,7,5,6\},S_{left}=\{1,3\},S_{right}=\Phi$，
但对于 $2\in S_{path},3\in S_{left}$，有 $2<3$.

\begin{tikzpicture}
    \node[draw, circle] (1) {2}
    child{node[draw, circle] (2) {1}}
    child{node[draw, circle] (3) {7}
            child{node[draw, circle] (4) {5}
                    child{node[draw, circle] (5) {3}}
                    child{node[draw, circle] (6) {6}}}
            child[missing]{}};
\end{tikzpicture}

\hrulefill\medskip

\textbf{Q3.}

\begin{proof}
    首先，对于任何一棵二叉搜索树，可以通过 $O(n)$ 次旋转，转变为
    一条链状的二叉搜索树，可以如下操作：首先将根节点加入这条链，
    然后对链上节点的左孩子节点 $x$，只要对其双亲节点做一次右旋
    操作，即可将 $x$ 加入到链中，同时不会移除链上的节点，这样直到
    根节点上左子树上节点全加入到链中之后，再递归对根节点右子树做
    如上操作. 这样就可以最多进行 $n-1$ 次操作即可得到 $n$ 个节点
    的链状二叉搜索树.

    然后对于两棵包含相同节点的二叉搜索树，对第一棵树做 $O(n)$ 次
    旋转操作得到链状二叉搜索树，对第二棵树也可以做 $O(n)$ 次旋转
    操作得到相同的链状二叉搜索树，则只需在第一棵树做了 $O(n)$ 次
    旋转操作得到的链状二叉搜索树的基础上做 $O(n)$ 次逆操作即可得
    到第二棵树，因此总的操作数为 $O(n)$.
\end{proof}

\hrulefill\medskip

\textbf{Q4.}

不一样.

反例如下，在插入节点1后，右旋得到合法的红黑树，再删除节点1，得到
的红黑树和原本的不一样.

\begin{tikzpicture}
    \node[draw, circle, fill, text=white] (1) at(0,0) {3}
    child{node[draw, circle] (2) {2}
            child{node[draw, circle, fill, text=white] (3) {nil}}
            child{node[draw, circle, fill, text=white] (4) {nil}}}
    child{node[draw, circle, fill, text=white] (5) {nil}};

    \node[draw, circle, fill, text=white] (11) at(3,0) {3}
    child{node[draw, circle] (12) {2}
            child{node[draw, circle] (13) {1}
                    child{node[draw, circle, fill, text=white] (14) {nil}}
                    child{node[draw, circle, fill, text=white] (15) {nil}}}
            child{node[draw, circle, fill, text=white] (16) {nil}}}
    child{node[draw, circle, fill, text=white] (17) {nil}};

    \node[draw, circle, fill, text=white] (21) at(6,-2) {2}
    child{node[draw, circle] (22) {1}}
    child{node[draw, circle] (23) {3}};
    \node[draw, circle, fill, text=white] (24) at(4.5,-5) {nil};
    \node[draw, circle, fill, text=white] (25) at(5.5,-5) {nil};
    \node[draw, circle, fill, text=white] (26) at(6.5,-5) {nil};
    \node[draw, circle, fill, text=white] (27) at(7.5,-5) {nil};
    \draw(22) -- (24) (22) -- (25) (23) -- (26) (23) -- (27);

    \node[draw, circle, fill, text=white] (31) at(8,0) {2}
    child{node[draw, circle, fill, text=white] (32) {nil}}
    child{node[draw, circle] (33) {3}
            child{node[draw, circle, fill, text=white] (34) {nil}}
            child{node[draw, circle, fill, text=white] (35) {nil}}};

\end{tikzpicture}

\hrulefill\medskip

\newpage

\textbf{Q5.}

结果见下图.

\begin{tikzpicture}
    \node[draw, circle] (1) {17}
    child{node[draw, circle] (2) {38}
            child{node[draw, circle] (3) {41}}}
    child{node[draw, circle] (4){30}}
    child[missing]{};
    \node[draw, circle, right=20pt of 1] (5) {24};
    \node[draw, circle, left=70pt of 1, fill, text=white] (6) {18}
    child{node[draw, circle] (7) {25}
            child{node[draw, circle, fill, text=white] (8) {26}
                    child{node[draw, circle] (9) {34}}}
            child{node[draw, circle] (10) {46}}
            child[missing]{}}
    child{node[draw, circle] (11) {20}
            child{node[draw, circle] (12) {55}}}
    child{node[draw, circle, fill, text=white] (13) {39}}
    child[missing]{}
    child[missing]{};
    \node[above=of 1] (label) {H.min};

    \draw[->] (label) -- (1);
    \draw[dotted] (6) -- (1) -- (5);

\end{tikzpicture}

\end{document}