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

\geometry{left=2.5cm,right=2.5cm,headsep=1cm,bottom=2cm,footnotesep=2cm,headheight=13pt}
\pagestyle{fancy}
\fancyfoot[C]{\thepage}
\fancyhead[L]{计算机科学与技术系}
\fancyhead[C]{\ \ \ \ \ \ \ \ }
\fancyhead[R]{\ \ \ \ \ \ \ \ \ \ \ \ 2023年3月31日}

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

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

\parindent0mm
%\pagestyle{empty}

\usetikzlibrary{automata, positioning, arrows}

\newcounter{aufgc}
\newenvironment{example}[1]%
{\refstepcounter{aufgc}\textbf{例题1.\arabic{aufgc}} \emph{#1} \\}
{\vspace{0.2cm}}%

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

\lstset{basicstyle=\ttfamily}

\begin{document}

\section*{堆}

堆：优先队列，几乎完全二叉树，

\section*{二叉搜素树}

最大堆不能支持查找或寻找第$k$大的元素，而我们希望找到一种数据结构支持动态的功能，如查找。

BST，二叉搜索树，一棵二叉树，每个节点满足其值大于等于左子树上所有节点，其值小于等于右子树上所有节点

相比于堆来说，其不限制形状，可能与完全二叉树相差很大

使用中序遍历可以做到将所有节点值按照从小到大的顺序输出，时间复杂度$O(n)$

二叉搜索树支持在$O(h)$时间复杂度内实现查找，其中$h$为树的高度

查找一个节点的后继节点，如果其有右孩子，则其后继节点为右子树最小的节点，否则为其第一个比其大的祖先节点

类似的，也可以在$O(h)$时间复杂度实现查找前继节点

\begin{algorithm}
    \caption{\textsc{Successor} (x)}
    \SetKwFunction{tm}{Tree-Minimum}
    \eIf{$x.right\neq NIL$}{
        \KwRet{\tm{$x.right$}}}{
        $y=x.parent$\\
        \While{$y\neq NIL$ {\bf and} $ y.right==x$}{
            $x=y$\\
            $y=y.parent$}
        \KwRet{$y$}
    }
\end{algorithm}

删除节点操作，分为三种情况：

1. 被删除节点没有孩子节点，直接删除即可

2. 被删除节点只有一个孩子节点，将其孩子节点替换被删除节点即可

3. 被删除节点有两个孩子节点，将其后继节点替换被删除节点，然后删除后继节点

在执行了大量的插入和删除之后，BST的高度可能会变得很难确定

\begin{theorem}
    一棵由$n$个不同元素随机建立的二叉搜索树 (随机插入$n$个元素)的高度的期望为$O(\log n)$.
\end{theorem}

令$H_n$为一棵由$n$个不同元素随机建立的二叉搜索树的高度，目标即为$EH_n=O(\log n)$

一种方式是归纳，有\[EH_n=\frac{1}{n}\sum_{i=1}^n(E\max\{H_{i-1},H_{n-i}\}+1)\]
其中最大值$\max$比较难处理，如果直接放缩成\[EH_n\leqslant\frac{1}{n}\sum_{i=1}^n(EH_{i-1}+EH_{n-i}+1)=\frac{2}{n}\sum_{i=1}^n{EH_{i-1}}+1\]
这是线性的，即$O(n)$，并不是理想的答案，需要做额外的处理

考虑证明$E[2^{H_n}]\leqslant n^{O(2)}$

有\[E[2^{H_n}]=E[\frac{1}{n}\sum_{i=1}^n2^{\max\{H_{i-1},H_{n-i}\}+1}]\leqslant \frac{4}{n}\sum_{i=1}^{n}E[2^{H_{i-1}}]\]

则有$E[2^{H_n}]\leqslant n^3$

\section*{红黑树}

红黑树是对二叉搜索树的改进，保证树高度为$O(\log n)$

根节点是黑色的，叶节点是黑色的，红色节点的孩子节点都是黑色的，从任何一个节点出发到其子叶经过的黑色节点的个数相同

\begin{theorem}
    以上红黑树的性质保证了一棵$n$个节点的树高$\leqslant 2\log_2(n+1)$
\end{theorem}

性质保证一个节点有$bh(x)$即黑色节点高度，则节点子树上至少为$2^{bh(x)}-1$个节点，至多为$2bh(x)$个节点

\end{document}
