7.1 基本概念

查找的基本概念.pdf

查找：在数据集合中寻找满足某种条件的数据元素的过程称为查找。
查找表（查找结构）：用于查找的数据集合称为查找表，它由同一类型的数据元素（或记录）组成。
- 对查找表的常见操作：
  - 查找符合条件的数据元素
  - 插入、删除某个数据元素
- 只进行查找操作最好使用静态查找表，若需要进行大量插入删除操作可使用动态查找表。
关键字：数据元素中唯一标识该元素的某个数据项的值，使用基于关键字的查找，查找结果应该是唯一的
查找长度：在查找运算中，需要对比关键字的次数称为查找长度。
平均查找长度(ASL, Average Search Length)：所有查找过程中进行关键字的比较次数的平均值 $A S L = i = 1 \sum n p_{i} C_{i}$ ， $p_{i}$ 为查找第 $i$ 个元素的概率， $C_{i}$ 为第 $i$ 个元素的查找长度
- 评价一个查找算法的效率时，通常考虑查找成功/查找失败两种情况的ASL，ASL的数量级反映了查找算法的时间复杂度

7.2 顺序查找和折半查找

7.2.1. 顺序查找

有序数组顺序查找演示

顺序查找.pdf

顺序查找：又叫“线性查找”，通常用于线性表。

顺序查找

算法思想：从头到尾挨个找（或者从尾到头）。

\begin{document}
	\begin{tikzpicture}[scale=2, ultra thick]
	\tikzstyle{every node}=[font=\huge, draw=black, very thick, rectangle, minimum width=1cm, minimum height=1cm]
		\def\myNum{33,10,13,29,16,19,32,7,43,41,37}
		\foreach \num [count=\i] in \myNum {
			\pgfmathtruncatemacro{\idx}{\i-1};%整数结果
			\node[fill=gray!20] at (\idx,0) {\num};
			\node[font=\Large, draw=none] at(\idx,-0.5) (\idx){\idx};
		}
 
		\draw[-latex] (0,-1.2) -- (0);
	\end{tikzpicture}
\end{document}

//个人理解：从头到尾依次对比，直到匹配成功或越界
 
typedef struct{				//查找表的数据结构（顺序表）
	ElemType *elem;			//动态数组起始地址
	int TableLen;			//表的长度
}SSTable;
 
//顺序查找
int Search_Seq(SSTable ST,ElemType key){
	int i;
	for(i=0; i<ST.TableLen && ST.elem[i]!=key; ++i);
	return i==ST.TableLen? -1 : i;
	// 查找成功返回数组下标，否则返回-1
}

顺序查找 - 哨兵方式

哨兵方式：引入哨兵 ST.elem[0] 来使得循环不必判断数组是否会越界

\begin{document}
	\begin{tikzpicture}[scale=2, ultra thick]
	\tikzstyle{every node}=[font=\huge, draw=black, very thick, rectangle, minimum width=1cm, minimum height=1cm]
		\def\myNum{33,10,13,29,16,19,32,7,43,41,37}
		\foreach \num [count=\idx] in \myNum {
			\node[fill=gray!20] at (\idx,0) {\num};
			\node[font=\Large, draw=none] at(\idx,-0.5) (\idx) {\idx};
		}
		\node[fill=green!20] at (0,0) {};
		\node[font=\Large, draw=none] at(0,-0.5) (0) {0};
 
		\draw[-latex] (11,-1.2) -- (11);
	\end{tikzpicture}
\end{document}

//个人理解：elem[0]存放哨兵，从尾到头查找。
//如果查找到elem[0]还没有成功的话，自动返回0，不需要判断数组越界
 
typedef struct{				//查找表的数据结构（顺序表）
	ElemType *elem;			//动态存储空间基址，建表时按照实际长度分配，0号位置留空
	int TableLen;			//表的长度
}SSTable;
 
//顺序查找
int Search_Seq(SSTable ST,ElemType key){
	ST.elem[0]=key;			//0号位置存哨兵，不需要判断i是否越界
	int i;
	for(i=ST.TableLen; ST.elem[i]!=key; --i)
		// 查找成功返回数组下标，否则返回0
		return i;
}

$A S L_{成功} = \frac{1 + 2 + \dots + n}{n} = \frac{n + 1}{2}$ ， $A S L_{失败} = n + 1$

顺序查找优化 - 元素有序

当查找表中元素有序排放（递增/递减）时，利用查找判定树分析ASL，一共 $n + 1$ 个失败结点

一个成功结点的查找长度=自身所在层数
一个失败结点的查找长度=父结点所在层数（失败结点是虚构的，实际上不存在）

\begin{document}
	\begin{tikzpicture}[scale=2, ultra thick,
	true/.style={draw=black, circle, fill=green!20, very thick, font =\huge, minimum size=3em},
	false/.style={draw=black, rectangle, fill=gray!10, very thick, font =\large, minimum width=5em, minimum height=2.5em},
	level 1/.style={sibling distance=4em, level distance=3em},%横向距离与纵向距离
	level 2/.style={sibling distance=4em, level distance=3em},
	level 3/.style={sibling distance=4em, level distance=3em},
	]
	\node [true]{7}
		child {node[false] {$(-\infty,7)$}}
		child {node[true] {13}
			child {node[false] {$(7,13)$}}
			child {node[true] {19}
				child {node[false] {$(13,19)$}}
				child {node[true] {29}
					child {node[false] {$(19,29)$}}
					child {node[true] {37}
						child {node[false] {$(29,37)$}}
						child {node[true] {43}
							child {node[false] {$(37,43)$}}
							child {node[false] {$(43,+\infty$)}}
						}
					}
				}
			}
		};
	\end{tikzpicture}
\end{document}

降低了查找失败时的ASL： $A S L_{失败} = \frac{1 + 2 + \dots + n + n}{n + 1} = \frac{n}{n + 1} + \frac{n}{2}$

顺序查找优化 - 被查概率不等

当查找表中元素被查概率不相等时，可以把被查概率大的元素放在靠前位置

缺点：降低了查找成功的ASL

7.2.2. 折半查找

LeetBook二分查找

LeetCode704. 二分查找

折半查找演示

折半查找.pdf

折半查找：又称“二分查找”，仅适用于有序的顺序表。（顺序表拥有随机访问的特性，链表没有）

折半查找

基本思想：将给定值 key 与顺序表中间位置的元素比较，若相等，则查找成功，返回该元素的存储位置；若不等，则所需查找的元素只能在中间元素以外的前半部分或后半部分，然后在缩小的范围内继续进行同样的查找……

\begin{document}
	\begin{tikzpicture}[scale=2, ultra thick]
	\tikzstyle{every node}=[font=\huge, draw=black, very thick, rectangle, minimum width=1cm, minimum height=1cm]
		\node[fill=green!20] at(-1.5,0){33};
		\node[font=\Large, draw=none] at(-2.2,0){key:};
 
		\def\myNum{7,10,13,16,19,29,32,33,37,41,43, , , }
		\foreach \num [count=\i] in \myNum {
			\pgfmathtruncatemacro{\idx}{\i-1};%整数结果
			\node[fill=gray!20] at (\idx,0) {\num};
			\node[font=\Large, draw=none] at(\idx,-0.5) (\idx){\idx};
		}
 
		\node[font=\large, draw=none] at(0,-1.5)(low){low};
		\draw[-latex] (low) -- (0);
		\node[font=\large, draw=none, red] at(5,-1.5)(mid){mid};
		\draw[-latex, red] (mid) -- (5);
		\node[font=\large, draw=none] at(10,-1.5)(high){high};
		\draw[-latex] (high) -- (10);
	\end{tikzpicture}
\end{document}

\begin{document}
	\begin{tikzpicture}[scale=2, ultra thick]
	\tikzstyle{every node}=[font=\huge, draw=black, very thick, rectangle, minimum width=1cm, minimum height=1cm]
		\node[fill=green!20] at(-1.5,0){33};
		\node[font=\Large, draw=none] at(-2.2,0){key:};
 
		\def\myNum{7,10,13,16,19,29,32,33,37,41,43, , , }
		\foreach \num [count=\i] in \myNum {
			\pgfmathtruncatemacro{\idx}{\i-1};%整数结果
			\node[fill=gray!20] at (\idx,0) {\num};
			\node[font=\Large, draw=none] at(\idx,-0.5) (\idx){\idx};
		}
 
		\node[font=\large, draw=none] at(6,-1.5)(low){low};
		\draw[-latex] (low) -- (6);
		\node[font=\large, draw=none, red] at(8,-1.5)(mid){mid};
		\draw[-latex, red] (mid) -- (8);
		\node[font=\large, draw=none] at(10,-1.5)(high){high};
		\draw[-latex] (high) -- (10);
	\end{tikzpicture}
\end{document}

\begin{document}
	\begin{tikzpicture}[scale=2, ultra thick]
	\tikzstyle{every node}=[font=\huge, draw=black, very thick, rectangle, minimum width=1cm, minimum height=1cm]
		\node[fill=green!20] at(-1.5,0){33};
		\node[font=\Large, draw=none] at(-2.2,0){key:};
 
		\def\myNum{7,10,13,16,19,29,32,33,37,41,43, , , }
		\foreach \num [count=\i] in \myNum {
			\pgfmathtruncatemacro{\idx}{\i-1};%整数结果
			\node[fill=gray!20] at (\idx,0) {\num};
			\node[font=\Large, draw=none] at(\idx,-0.5) (\idx){\idx};
		}
 
		\node[font=\large, draw=none][xshift=-1em] at(6,-1.5)(low){low};
		\draw[-latex] (low) -- ([xshift=-0.5em]6.south);
		\node[font=\large, draw=none, red][xshift=1em] at(6,-1.5)(mid){mid};
		\draw[-latex, red] (mid) -- ([xshift=0.5em]6.south);
		\node[font=\large, draw=none] at(7,-1.5)(high){high};
		\draw[-latex] (high) -- (7);
	\end{tikzpicture}
\end{document}

\begin{document}
	\begin{tikzpicture}[scale=2, ultra thick]
	\tikzstyle{every node}=[font=\huge, draw=black, very thick, rectangle, minimum width=1cm, minimum height=1cm]
		\node[fill=green!20] at(-1.5,0){33};
		\node[font=\Large, draw=none] at(-2.2,0){key:};
 
		\def\myNum{7,10,13,16,19,29,32,33,37,41,43, , , }
		\foreach \num [count=\i] in \myNum {
			\pgfmathtruncatemacro{\idx}{\i-1};%整数结果
			\node[fill=gray!20] at (\idx,0) {\num};
			\node[font=\Large, draw=none] at(\idx,-0.5) (\idx){\idx};
		}
		\node[fill=green!20] at(7,0){33};
 
		\node[font=\large, draw=none][xshift=-1em] at(7,-1.5)(low){low};
		\draw[-latex] (low) -- ([xshift=-0.5em]7.south);
		\node[font=\large, draw=none, red] at(7,-2)(mid){mid};
		\draw[-latex, red] (mid) -- (7);
		\node[font=\large, draw=none][xshift=1em] at(7,-1.5)(high){high};
		\draw[-latex] (high) -- ([xshift=0.5em]7.south);
	\end{tikzpicture}
\end{document}

折半查找算法题

//个人理解：把查找值和数组中间的元素对比，一样就返回下标，大了往左找，小了往右找
//当low>high时查找失败
 
typedef struct{					//查找表的数据结构（顺序表）（升序）
	ElemType *elem;				//动态数组基址
	int TableLength;			//表的长度
}SSTable;
 
// 折半查找
int Binary_Search(SSTable L,ElemType key){
	int low = 0, high = L.TableLenth - 1, mid;
	while(low <= high){			//low>high时查找失败
		mid = (low + high) / 2;		//取中间位置（向下取整）
		if(L.elem[mid] == key)
			return mid;
		else if(L.elem[mid] > key)
			high = mid - 1;			//从前半部分继续查找
		else
			low = mid + 1;			//从后半部分继续查找
	}
	return -1;					//查找失败，返回-1
}

折半查找判定树

\begin{document}
	\begin{tikzpicture}[scale=2, ultra thick]
	\tikzstyle{every node}=[font=\huge, draw=black, very thick, rectangle, minimum width=1cm, minimum height=1cm]
		\def\myNum{7,10,13,16,19,29,32,33,37,41,43}
		\foreach \num [count=\i] in \myNum {
			\pgfmathtruncatemacro{\idx}{\i-1};%整数结果
			\node[fill=gray!20] at (\idx,0) {\num};
			\node[font=\Large, draw=none] at(\idx,-0.5) (\idx){\idx};
		}
	\end{tikzpicture}
\end{document}

\begin{document}
	\begin{tikzpicture}[scale=2, ultra thick,
	true/.style={draw=black, circle, fill=green!20, very thick, font =\huge, minimum size=3em},
	false/.style={draw=black, rectangle, fill=gray!10, very thick, font =\large, minimum width=5em, minimum height=2.5em},
	level 1/.style={sibling distance=16em, level distance=3em},%横向距离与纵向距离
	level 2/.style={sibling distance=16em/2, level distance=3em},
	level 3/.style={sibling distance=16em/4, level distance=3em},
	]
	\node [true]{29}
		child {node[true] {13}
			child {node[true] {7}
				child {node[false] {$(-\infty,7)$}}
				child {node[true] {10}
					child {node[false] {$(7,10)$}}
					child {node[false] {$(10,13)$}}
				}
			}
			child {node[true] {16}
				child {node[false] {$(13,16)$}}
				child {node[true] {19}
					child {node[false] {$(16,19)$}}
					child {node[false] {$(19,29)$}}
				}
			}
		}
		child {node[true] {37}
			child {node[true] {32}
				child {node[false] {$(29,32)$}}
				child {node[true] {33}
					child {node[false] {$(32,33)$}}
					child {node[false] {$(33,37)$}}
				}
			}
			child {node[true] {41}
				child {node[false] {$(37,41)$}}
				child {node[true] {43}
					child {node[false] {$(41,43)$}}
					child {node[false] {$(43,+\infty)$}}
				}
			}
		};
	\end{tikzpicture}
\end{document}

折半查找判定树的构造： $mi d = ⌊ (l o w + hi g h) /2 ⌋$
- 如果当前 low 和 high 之间有奇数个元素，则 mid 分隔后，左右两部分元素个数相等；
- 如果当前 low 和 high 之间有偶数个元素，则 mid 分隔后，左半部分比右半部分少一个元素。
折半查找的判定树中，采用 $mi d = ⌊ (l o w + hi g h) /2 ⌋$ 算法时，对于任何一个结点，必有：右子树结点数 - 左子树结点数 = 0 或 1。
折半查找的判定树一定是平衡二叉树。折半查找的判定树中，只有最下面一层是不满的。元素个数为 $n$ 时（不包含失败结点）树高 $h = ⌈ lo g_{2} (n + 1) ⌉$ （参考：完全二叉树的高度）
判定树结点关键字：左<中<右，满足二叉排序树的定义。
失败结点： $n + 1$ 个（等于成功结点的空链域数量）
折半查找的查找效率： $A S L ⩽ h$ ，折半查找的时间复杂度 = $O (lo g_{2} n)$ 。

Example

例题：若 $mi d = ⌊ (l o w + hi g h) /2 ⌋$ ，画出含1个元素、2个元素、3个元素….16个元素的查找表对应的折半查找判定树，注：暂不考虑失败结点，图中编号为当有 $i$ 个元素时，判定树的形态。

注：该树可用于判断给定元素数量的顺序表中，折半查找一个元素的比较次数

 

\begin{document}

\begin{tikzpicture}[scale=2, ultra thick,

true/.style={draw=black, circle, fill=green!20, very thick, font =\huge, minimum size=3em},

false/.style={draw=black, rectangle, fill=gray!10, very thick, font =\large, minimum width=5em, minimum height=2.5em},

level 1/.style={sibling distance=8em/1, level distance=3em},%横向距离与纵向距离

level 2/.style={sibling distance=8em/2, level distance=3em},

level 3/.style={sibling distance=8em/4, level distance=3em},

]

\node [true]{1}

  child {node[true] {3}

  	child {node[true] {7}

  		child {node[true] {15}}

  		child {node[true] {11}}

  	child {node[true] {5}

  		child {node[true] {13}}

  		child {node[true] {9}}

  child {node[true] {2}

  	child {node[true] {6}

  		child {node[true] {14}}

  		child {node[true] {10}}

  	child {node[true] {4}

  		child {node[true] {12}}

  		child {node[true] {8}

  			child {node[true, xshift=2em] {16}}

};

\end{tikzpicture}

\end{document}

7.2.3. 分块查找

分块查找.pdf

分块查找所针对的情况：块内无序、块间有序。

分块查找又称索引顺序查找，算法过程如下：

在索引表中确定待查记录所属的分块（可顺序，可折半）
在块内顺序查找

\usetikzlibrary{positioning}
\begin{document}
	\begin{tikzpicture}[scale=1.2,line width=1.5pt]
	\tikzstyle{every node}=[font=\huge, draw=black, very thick, rectangle, minimum width=1cm, minimum height=1cm]
		\def \index{10,20,30,40,50}
		\foreach \idx [count=\i] in \index {
			\pgfmathtruncatemacro{\j}{\i-1};
			\node[fill=green!20] at (\j+5,4) (\j){\idx};
		}
 
		\def\mystring{7,10,13,19,16,20,27,22,30,40,36,43,50,48}
		\foreach \num [count=\i] in \mystring {
			\node[fill=gray!20] at (\i-1,0) (\num){\num};
			\pgfmathtruncatemacro{\j}{\i-1};
			\node[draw=none,font=\large,below] at (\j,-0.5){\j};
		}
		\node[fill=gray!20, font=\large] at (14,0) {$\cdots$};
		\foreach \i in {0,2,6,9,11,14}{
			\draw (\i-0.5,-1.5) -- (\i-0.5,1);
		}
 
		\draw[-latex] (0.south) -- (7.north);
		\draw[-latex] (1.south) -- (13.north);
		\draw[-latex] (2.south) -- (27.north);
		\draw[-latex] (3.south) -- (40.north);
		\draw[-latex] (4.south) -- (43.north);
 
		\node[draw=none, font=\large, above of=0]{$[0,1]$};
		\node[draw=none, font=\large, above of=1]{$[2,5]$};
		\node[draw=none, font=\large, above of=2]{$[6,8]$};
		\node[draw=none, font=\large, above of=3]{$[9,10]$};
		\node[draw=none, font=\large, above of=4]{$[11,13]$};
	\end{tikzpicture}
\end{document}

索引表及顺序表代码：

// 索引表
typedef struct{
	ElemType maxValue;
	int low,high;
}Index;
 
// 顺序表存储实际元素
ElemType List[100];

查找目标关键字所在分块可使用顺序查找和折半查找两种方式。
若使用折半查找且索引表中不包含目标关键字，则最终要停在 low > high 的位置，要在 low 所指分块中查找目标关键字。
查找效率分析(ASL)：假设长度为 $n$ 的查找表被均匀地分为 $b$ 块，每块 $s$ 个元素( $b = s / n$ )。设索引查找和块内查找的平均查找长度分别为 $L_{I}$ 、 $L_{S}$ ，则分块查找的平均查找长度为： $A S L = L_{I} + L_{S}$
- 用顺序查找查索引表【重要】，则 $L_{I} = \frac{1 + 2 + \dots + b}{b} = \frac{b + 1}{2}$ ， $L_{S} = \frac{1 + 2 + \dots + s}{s} = \frac{s + 1}{2}$ ， $A S L = L_{I} + L_{S} = \frac{s ^{2} + 2 s + n}{2 s}$ 。故当 $s = n$ 时，ASL 最小，为 $n + 1$
- 用折半查找查索引表，则 $L_{I} = ⌈ lo g_{2} (b + 1) ⌉$ ， $L_{s} = \frac{1 + 2 + \dots + s}{S} = \frac{s + 1}{2}$ 。 $A S L = \frac{s + 1}{2} + ⌈ lo g_{2} (b + 1)⌉$

7.2.4 本节习题精选

选择题：题目、答案

综合题：题目、答案

7.3 树型查找

7.3.1 二叉排序树(BST)

二叉排序树演示

二叉排序树.pdf

二叉排序树的定义：一棵二叉树或是空二叉树，或者是具有以下性质的二叉树：左子树结点值<根结点值<右子树结点值 ^[注意不是左结点值<根结点值<右结点值] 易错
对二叉排序树进行中序遍历，可以得到一个递增的有序序列
二叉排序树可用于元素的有序组织、搜索

二叉排序树的查找

LeetCode700. 二叉搜索树中的搜索

若树非空，将目标值与根结点值进行比较：
- 若相等，则查找成功；
- 若小于根结点，则在左子树上查找；
- 若大于根结点，则在右子树上查找。
查找成功则返回根结点指针，查找失败则返回 NULL

/**
Definition for a binary tree node.
struct TreeNode {
	int val;
	TreeNode *left;
	TreeNode *right;
	TreeNode() : val(0), left(nullptr), right(nullptr) {}
	TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
	TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 };
*/

迭代实现，时间复杂度 $O (n)$ ，空间复杂度 $O (1)$

TreeNode* searchBST(TreeNode* root, int val) {
	while(root!=nullptr){
		if(root->val == val) return root;
		else if(root->val > val) root=root->left;
		else root=root->right;
	}
	return NULL;
}

递归实现，时间复杂度 $O (n)$ ，空间复杂度 $O (h)$

TreeNode* searchBST(TreeNode* root, int val) {
	if(root==nullptr) return NULL;
 
	if(root->val==val) return root;
	else if(root->val > val) return searchBST(root->left, val);
	else return searchBST(root->right, val);
}

二叉排序树的插入

Leetcode701. 二叉搜索树中的插入操作

插入之前先进行查找操作找到要插入的位置

若原二叉排序树为空，则直接插入结点；
若关键字 k 小于根结点值，则插入到左子树；
若关键字 k 大于根结点值，则插入到右子树

//个人理解：二叉排序树为空，则创建结点；若不为空，等于的话查找失败；大于的话往左走；小于的话往右走
 
//在二叉排序树中插入关键字为k的新结点【递归实现】
//最坏空间复杂度：O(h)
int BST_Insert(BSTree &T, int k){
	if(T==NULL){			//若原二叉树为空，直接插入结点
		T = (BSTree)malloc(sizeof(BSTNode));
		T->key = k;
		T->lchild = T->rchild = NULL;
		return 1;			//插入成功
	}
	else if(k == T->key)		//树中存在相同关键字的结点，插入失败
		return 0;
	else if(k < T->key)
		return BST_Insert(T->lchild, k);		//插入到T的左子树
	else
		return BST_Insert(T->rchild, k);		//插入到T的右子树
}

二叉排序树的构造

不断进行插入操作

注意：对于不同顺序的关键字序列，得到的二叉树可能不同

//个人理解：利用二叉排序树的插入，不断将关键字插入到二叉排序树
 
//按照str[ ]中的关键字序列建立二叉排序树
void Crear_BST(BSTree &T, int str[], int n){
	T = NULL;                     //初始时T为空树
	int i=0;
	while(i<n){
		BST_Insert(T,str[i]);     //依次将每个关键字插入到二叉排序树中
	}
}

二叉排序树的删除

LeetCode450. 删除二叉搜索树中的结点

先搜索找到目标结点：

若被删除结点 z 是叶结点，直接删除，不会破坏二叉排序树的性质
若被删除结点 z 只有一棵左子树或右子树，则令 z 的子树称为 z 的父结点的子树，替代 z 的位置
若被删除结点 z 有左右两棵子树，则令 z 的直接后继（或直接前驱）替代 z ，然后从二叉排序树中删去这个直接后继（或直接前驱）。新删去的结点至多只有一棵子树，这样就转换成了第一或第二种情况

\begin{document}
	\begin{tikzpicture}[scale=2, ultra thick,
	every node/.style={draw=black, circle, very thick, font =\huge, minimum size=3em},
	level 1/.style={sibling distance=8em/1, level distance=3em},
	level 2/.style={sibling distance=8em/1.5, level distance=3em},
	level 3/.style={sibling distance=8em/2, level distance=3em},
	level 3/.style={sibling distance=8em/3, level distance=3em},
	]
	\node at (8,0) {19}
		child {node {13}
			child {node[xshift=-8em/1.5] {11}
				child {node[xshift=-4em] {8}}
			}
		}
        child {node[fill=red!30] (50) {50}
			child {node {26}
				child {node {21}}
				child {node[fill=green!30] (30) {30}}
			}
			child {node {66}
				child {node {60}
					child {node[xshift=2em] {63}
						child {node {61}}
						child {node {65}}
					}
				}
				child {node {70}}
			}
		};
		\draw[-latex, dashed] (30) to[out=60, in=-90] (50);
 
		\node at (0,0) {19}
		child {node {13}
			child {node[xshift=-8em/1.5] {11}
				child {node[xshift=-4em] {8}}
			}
		}
        child {node[fill=red!30] (50) {50}
			child {node {26}
				child {node {21}}
				child {node (30) {30}}
			}
			child {node {66}
				child {node[fill=green!30](60) {60}
					child {node[xshift=2em] {63}
						child {node {61}}
						child {node {65}}
					}
				}
				child {node {70}}
			}
		};
		\draw[-latex, dashed] (60) to[out=120, in=-90] (50);
	\end{tikzpicture}
\end{document}

二叉排序树查找效率分析

查找长度：查找运算中，需要对比关键字的次数，反映了查找操作时间复杂度；查找长度 $⩽$ 树高（最小树高 $⌊ lo g_{2} n ⌋ + 1$ ）
查找成功的平均查找长度ASL
查找失败的平均查找长度ASL

7.3.2 平衡二叉树(AVL)

为了降低二叉排序树的高度，从而让查找效率更高，要让左右子树尽可能平衡

LeetCode110. 平衡二叉树的判定

平衡二叉树演示

平衡二叉树.pdf

平衡二叉树的定义

平衡二叉树是二叉排序树：左子树结点值 $⩽$ 根结点值 $⩽$ 右子树结点值
相比于普通二叉排序树：树上任一结点的左子树和右子树的高度之差不超过 1
结点的平衡因子=左子树高-右子树高。平衡二叉树结点的平衡因子的值只可能是 $- 1$ 、 $0$ 或 $1$

\usetikzlibrary{positioning}
\begin{document}
	\begin{tikzpicture}[scale=2, ultra thick,
	every node/.style={draw=black, circle, very thick, font =\huge, minimum size=3em},
	sub/.style={font=\large, draw=none},
	level 1/.style={sibling distance=8em/1, level distance=4em},
	level 2/.style={sibling distance=8em/2, level distance=4em},
	level 3/.style={sibling distance=8em/4, level distance=4em},
	]
	\node(50) {50}
		child {node (26) {26}
			child {node (21) {21}}
			child {node (30) {30}}
		}
        child {node (66) {66}
			child {node (60) {60}}
			child {node (70) {70}
				child {node[xshift=-2em] (68) {68}}
			}
		};
 
	\node [below of=50, sub] {$1$};
	\node [below of=26, sub] {$0$};
	\node [below of=66, sub] {$-1$};
	\node [below of=21, sub] {$0$};
	\node [below of=30, sub] {$0$};
	\node [below of=60, sub] {$0$};
	\node [below of=70, sub] {$1$};
	\node [below of=68, sub] {$0$};
	\end{tikzpicture}
\end{document}

//平衡二叉树结点
typedef struct AVLNode{
	int key;         //数据域
	int balance;     //平衡因子
	struct AVLNode *lchild; *rchild;
}AVLNode, *AVLTree;

平衡二叉树的插入

插入新结点后如何调整“不平衡”问题：只需要调整最小不平衡子树 ^[提示：插入新结点使得最小不平衡子树树高 $+ 1$ ，调整后树高又 $- 1$ ]。做题过程中最好把子树补齐，这样会更直观一点。

LL：在A结点的左孩子的左子树中插入导致不平衡
- 调整： A的左孩子结点(B)右上旋转替代A成为根结点，A结点右下旋转成为B的右孩子，B的原右子树作为A结点的左子树 (BL<B<BR)<A<AR→BL<B<(BR<A<AR)

\usetikzlibrary{positioning}
\begin{document}
	\begin{tikzpicture}[scale=2, ultra thick,
	root/.style={draw=black, circle, font =\Huge, minimum size=3em},
	tree/.style={draw=black, rectangle, font =\Huge, minimum height=2em, minimum width=3em, fill=gray!30},
	sub/.style={font=\large},
	level 1/.style={sibling distance=8em/1.5, level distance=4em},
	level 2/.style={sibling distance=8em/2, level distance=4em},
	]
	\node[root](A) at(0,0) {$A$}
		child {node[root] (B) {$B$}
			child {node[tree, fill=blue!30] (BL) {$BL$}}
			child {node[tree] (BR) {$BR$}}
		}
        child {node[tree] (AR) {$AR$}};
    \node [below of=A, sub]{$2$};
    \node [below of=B, sub]{$1$};
    \node [below of=BL, sub]{$H+1$};
    \node [below of=BR, sub]{$H$};
    \node [below of=AR, sub]{$H$};
 
	\node[root](B) at(5,0) {$B$}
        child {node[tree, fill=blue!30] (BL) {$BL$}}
		child {node[root] (A) {$A$}
			child {node[tree] (BR) {$BR$}}
			child {node[tree] (AR) {$AR$}}
		};
	\node [below of=A, sub]{$0$};
    \node [below of=B, sub]{$0$};
    \node [below of=BL, sub]{$H+1$};
    \node [below of=BR, sub]{$H$};
    \node [below of=AR, sub]{$H$};
    \end{tikzpicture}
\end{document}

RR：在A结点的右孩子的右子树中插入导致不平衡
- 调整： A的右孩子结点(B)左上旋转替代A成为根结点，A结点左下旋转成为B的左孩子，B的原左子树作为A结点的右子树 AL<A<(BL<B<BR)→(AL<A<BL)<B<\BR

\usetikzlibrary{positioning}
\begin{document}
	\begin{tikzpicture}[scale=2, ultra thick,
	root/.style={draw=black, circle, font =\Huge, minimum size=3em},
	tree/.style={draw=black, rectangle, font =\Huge, minimum height=2em, minimum width=3em, fill=gray!30},
	sub/.style={font=\large},
	level 1/.style={sibling distance=8em/1.5, level distance=4em},
	level 2/.style={sibling distance=8em/2, level distance=4em},
	]
	\node[root](A) at(0,0) {$A$}
        child {node[tree] (AL) {$AL$}}
		child {node[root] (B) {$B$}
			child {node[tree] (BL) {$BL$}}
			child {node[tree, fill=blue!30] (BR) {$BR$}}
		};
    \node [below of=A, sub]{$-2$};
    \node [below of=B, sub]{$-1$};
    \node [below of=AL, sub]{$H$};
    \node [below of=BL, sub]{$H$};
    \node [below of=BR, sub]{$H+1$};
 
	\node[root](B) at(6,0) {$B$}
		child {node[root] (A) {$A$}
			child {node[tree] (AL) {$AL$}}
			child {node[tree] (BL) {$BL$}}
		}
        child {node[tree, fill=blue!30] (BR) {$BR$}};
    \node [below of=A, sub]{$0$};
    \node [below of=B, sub]{$0$};
    \node [below of=AL, sub]{$H$};
    \node [below of=BL, sub]{$H$};
    \node [below of=BR, sub]{$H+1$};
	\end{tikzpicture}
\end{document}

LR：在A结点的左孩子的右子树中插入导致不平衡
- 调整： A的左孩子的右孩子(C)，先左上旋转提升到B结点的位置，再右上旋转提升到A结点的位置(BL<B<(CL<C<CR))<A<AR→((BL<B<CL)<C<CR)<A<AR→(BL<B<CL)<C<(CR<A<AR)
- CL与CR中插入情况类似

\usetikzlibrary{positioning}
\begin{document}
	\begin{tikzpicture}[scale=2, ultra thick,
	root/.style={draw=black, circle, font =\Huge, minimum size=3em},
	tree/.style={draw=black, rectangle, font =\Huge, minimum height=2em, minimum width=3em, fill=gray!30},
	sub/.style={font=\large},
	level 1/.style={sibling distance=8em/1.5, level distance=4em},
	level 2/.style={sibling distance=8em/2, level distance=4em},
	level 3/.style={sibling distance=8em/2, level distance=4em},
	]
	\node[root](A) at(0,0) {$A$}
		child {node[root] (B) {$B$}
			child {node[tree] (BL) {$BL$}}
			child {node[root, fill=blue!30] (C) {$C$}
				child {node[tree] (CL) {$CL$}}
				child {node[tree] (CR) {$CR$}}
			}
		}
        child {node[tree, fill=gray!30] (AR) {$AR$}};
    \node [below of=A, font=\large, draw=none]{$2$};
    \node [below of=B, font=\large, draw=none]{$-1$};
    \node [below of=C, font=\large, draw=none]{$-1$};
    \node [below of=BL, font=\large, draw=none]{$H$};
    \node [below of=AR, font=\large, draw=none]{$H$};
    \node [below of=CL, font=\large, draw=none]{$H-1$};
    \node [below of=CR, font=\large, draw=none]{$H$};
 
	\node[root](A) at(5,0){$A$}
		child {node[root, fill=blue!30] (C) {$C$}
			child {node[root] (B) {$B$}
				child {node[tree] (BL) {$BL$}}
				child {node[tree] (CL) {$CL$}}
			}
			child {node[tree] (CR) {$CR$}}
		}
        child {node[tree] (AR) {$AR$}};
    \node [below of=A, font=\large, draw=none]{$2$};
    \node [below of=B, font=\large, draw=none]{$1$};
    \node [below of=C, font=\large, draw=none]{$1$};
    \node [below of=BL, font=\large, draw=none]{$H$};
    \node [below of=AR, font=\large, draw=none]{$H$};
    \node [below of=CL, font=\large, draw=none]{$H-1$};
    \node [below of=CR, font=\large, draw=none]{$H$};
 
	\node(C)[root] at(10,0)[fill=blue!30] {$C$}
		child {node[root] (B)[xshift=-1cm] {$B$}
			child {node[tree] (BL) {$BL$}}
			child {node[tree] (CL) {$CL$}}
		}
		child {node[root] (A)[xshift=1cm] {$A$}
			child {node[tree] (CR) {$CR$}}
	        child {node[tree] (AR) {$AR$}}
		};
    \node [below of=A, font=\large, draw=none]{$0$};
    \node [below of=B, font=\large, draw=none]{$1$};
    \node [below of=C, font=\large, draw=none]{$0$};
    \node [below of=BL, font=\large, draw=none]{$H$};
    \node [below of=AR, font=\large, draw=none]{$H$};
    \node [below of=CL, font=\large, draw=none]{$H-1$};
    \node [below of=CR, font=\large, draw=none]{$H$};
	\end{tikzpicture}
\end{document}

RL：在A结点的右孩子的左子树中插入导致不平衡
- 调整： A的右孩子的左孩子(C)，先右上旋转提升到B结点的位置，再左上旋转提升到A结点的位置 AL<A<((CL<C<CR)<B<BR)→AL<A<(CL<C<(CR<B<BR))→(AL<A<CL)<C<(CR<B<BR)
- CL与CR中插入情况类似

\usetikzlibrary{positioning}
\begin{document}
	\begin{tikzpicture}[scale=2, ultra thick,
	root/.style={draw=black, circle, font =\Huge, minimum size=3em},
	tree/.style={draw=black, rectangle, font =\Huge, minimum height=2em, minimum width=3em, fill=gray!30},
	sub/.style={font=\large},
	level 1/.style={sibling distance=8em/1.5, level distance=4em},
	level 2/.style={sibling distance=8em/2, level distance=4em},
	level 3/.style={sibling distance=8em/2, level distance=4em},
	]
	\node[root](A) at(0,0) {$A$}
        child {node[tree] (AL) {$AL$}}
		child {node[root] (B) {$B$}
			child {node[root, fill=blue!30] (C) {$C$}
				child {node[tree] (CL) {$CL$}}
				child {node[tree] (CR) {$CR$}}
			}
			child {node[tree] (BR) {$BR$}}
		};
    \node [below of=A, font=\large, draw=none]{$-2$};
    \node [below of=B, font=\large, draw=none]{$1$};
    \node [below of=C, font=\large, draw=none]{$1$};
    \node [below of=AL, font=\large, draw=none]{$H$};
    \node [below of=BR, font=\large, draw=none]{$H$};
    \node [below of=CL, font=\large, draw=none]{$H$};
    \node [below of=CR, font=\large, draw=none]{$H-1$};
 
	\node[root](A) at(5,0) {$A$}
        child {node[tree] (AL) {$AL$}}
		child {node[root, fill=blue!30] (C) {$C$}
			child {node[tree] (CL) {$CL$}}
			child {node[root] (B) {$B$}
				child {node[tree] (CR) {$CR$}}
				child {node[tree] (BR) {$BR$}}
			}
		};
    \node [below of=A, font=\large, draw=none]{$-2$};
    \node [below of=B, font=\large, draw=none]{$-1$};
    \node [below of=C, font=\large, draw=none]{$-1$};
    \node [below of=AL, font=\large, draw=none]{$H$};
    \node [below of=BR, font=\large, draw=none]{$H$};
    \node [below of=CL, font=\large, draw=none]{$H$};
    \node [below of=CR, font=\large, draw=none]{$H-1$};
 
	\node[root](C)[fill=blue!30] at(11,0) {$C$}
		child {node[root, xshift=-1cm] (A) {$A$}
	        child {node[tree] (AL) {$AL$}}
			child {node[tree] (CL) {$CL$}}
		}
		child {node[root, xshift=1cm] (B) {$B$}
			child {node[tree] (CR) {$CR$}}
			child {node[tree] (BR) {$BR$}}
		};
    \node [below of=A, font=\large, draw=none]{$0$};
    \node [below of=B, font=\large, draw=none]{$-1$};
    \node [below of=C, font=\large, draw=none]{$0$};
    \node [below of=AL, font=\large, draw=none]{$H$};
    \node [below of=BR, font=\large, draw=none]{$H$};
    \node [below of=CL, font=\large, draw=none]{$H$};
    \node [below of=CR, font=\large, draw=none]{$H-1$};
	\end{tikzpicture}
\end{document}

平衡二叉树的查找与效率分析

若树高为 $h$ ，则最坏情况下，查找一个关键字最多需要对比 $h$ 次，即查找操作的时间复杂度不可能超过 $O (h)$
以 $n_{h}$ 表示深度为 $h$ 的平衡树中含有的最少结点数，则有 $n_{0} = 0$ 、 $n_{1} = 1$ ， $n_{2} = 2$ ，并且有 $n_{h} = n_{h - 1} + n_{h - 2} + 1$ ^[提示：两个子树各自结点数量+根结点数量，两个子树高度差为1，分别至少有 $n_{h - 1}$ 和 $n_{h - 2}$ 个结点，再加上1个根结点]，所以有 $n_{3} = n_{2} + n_{1} + 1 = 4$ ， $n_{4} = 7$ ， $\dots$ 考前记一记
含有 $n$ 个结点的平衡二叉树的最大深度为 $O (lo g_{2} n)$ ，平衡二叉树的平均查找长度为 $O (lo g_{2} n)$

平衡二叉树的删除

平衡二叉树的删除.pdf

对比平衡二叉树的插入与删除

插入
- 插入新结点后，要保持二叉排序树的特性不变（左<中<右）
- 若插入新结点导致不平衡，则需要调整平衡
删除
- 删除结点后，要保持二叉排序树的特性不变（左<中<右）
- 若删除新结点导致不平衡，则需要调整平衡

平衡二叉树删除操作的具体步骤

考前记一记

删除结点（方法同二叉排序树）
一路向上，找到最小不平衡子树，找不到就完结撒花
找最小不平衡子树下，个头最高的儿子、孙子
根据孙子的位置，调整平衡(LL/RR/LR/RL)（方法同平衡二叉树的插入）
如果调整导致不平衡向上传导，继续第2步

Example

 

\usetikzlibrary{fit, backgrounds, shadows}

\begin{document}

\begin{tikzpicture}[scale=2, ultra thick,

every node/.style={draw=black, circle, very thick, font =\huge, minimum size=3em},

level 1/.style={sibling distance=12em/1, level distance=3em},

level 2/.style={sibling distance=12em/2, level distance=3em},

level 3/.style={sibling distance=12em/4, level distance=3em},

level 4/.style={sibling distance=12em/4, level distance=3em},

]

\node {33}

  child {node {10}

  	child {node {5}

  		child {node {4}

  			child {node[xshift=-3em] {1}}

  		child {node {8}

  			child {node[xshift=-3em] {6}}

  	child{node {20}

  		child {node {15}

  			child {node[xshift=-3em] {12}}

  		child {node {25}

  			child {node {23}

  				child {node[xshift=-3em] {21}}

  			child {node {28}}

   child {node[fill=red!20](44) {44}

  	child {node(17) {17}

  		child[dashed] {node[fill=gray!30, xshift=3em] (32) {32}}

  	child {node[fill=orange!20] {78}

  		child {node[fill=blue!20] (50) {50}

  			child {node(48) {48}}

  			child {node(62) {62}}

  		child {node(88) {88}}

};

  \begin{scope}[on background layer]

  	\node [draw, dashed, fit=(17) (44) (88) (62), rectangle, rounded corners, drop shadow={gray!10}] {};

  \end{scope}

\end{tikzpicture}

\end{document}

 

\usetikzlibrary{fit, backgrounds, shadows}

\begin{document}

\begin{tikzpicture}[scale=2, ultra thick,

every node/.style={draw=black, circle, very thick, font =\huge, minimum size=3em},

level 1/.style={sibling distance=12em/1, level distance=3em},

level 2/.style={sibling distance=12em/2, level distance=3em},

level 3/.style={sibling distance=12em/4, level distance=3em},

level 4/.style={sibling distance=12em/4, level distance=3em},

]

\node{33}

  child {node {10}

  	child {node {5}

  		child {node {4}

  			child {node[xshift=-3em] {1}}

  		child {node {8}

  			child {node[xshift=-3em] {6}}

  	child{node {20}

  		child {node {15}

  			child {node[xshift=-3em] {12}}

  		child {node {25}

  			child {node {23}

  				child {node[xshift=-3em] {21}}

  			child {node {28}}

   child {node[fill=blue!20](50) {50}

  	child {node[fill=red!20] (44) {44}

  		child {node(17) {17}}

  		child {node(48) {48}}

  	child {node[fill=orange!20](78) {78}

  		child {node(62) {62}}

  		child {node(88) {88}}

};

  \begin{scope}[on background layer]

  	\node [draw, dashed, fit=(17) (50) (88), rectangle, rounded corners, drop shadow={gray!10}] {};

  \end{scope}

\end{tikzpicture}

\end{document}

 

\usetikzlibrary{fit, backgrounds, shadows}

\begin{document}

\begin{tikzpicture}[scale=2, ultra thick,

every node/.style={draw=black, circle, very thick, font =\huge, minimum size=3em},

level 1/.style={sibling distance=12em/1, level distance=3em},

level 2/.style={sibling distance=12em/2, level distance=3em},

level 3/.style={sibling distance=12em/4, level distance=3em},

level 4/.style={sibling distance=12em/4, level distance=3em},

]

\node[fill=red!20] (33) {33}

  child {node[fill=orange!20] {10}

  	child {node {5}

  		child {node {4}

  			child {node[xshift=-3em](1) {1}}

  		child {node {8}

  			child {node[xshift=-3em] {6}}

  	child{node[fill=blue!20] {20}

  		child {node {15}

  			child {node[xshift=-3em] {12}}

  		child {node {25}

  			child {node {23}

  				child {node[xshift=-3em](21) {21}}

  			child {node {28}}

   child {node {50}

  	child {node {44}

  		child {node {17}}

  		child {node {48}}

  	child {node {78}

  		child {node {62}}

  		child {node(88) {88}}

};

  \begin{scope}[on background layer]

  	\node [draw, dashed, fit=(33) (1) (88) (21), rectangle, rounded corners, drop shadow={gray!10}] {};

  \end{scope}

\end{tikzpicture}

\end{document}

 

\usetikzlibrary{fit, backgrounds, shadows}

\begin{document}

\begin{tikzpicture}[scale=2, ultra thick,

every node/.style={draw=black, circle, very thick, font =\huge, minimum size=3em},

level 1/.style={sibling distance=12em/1, level distance=3em},

level 2/.style={sibling distance=12em/1.5, level distance=3em},

level 3/.style={sibling distance=12em/3, level distance=3em},

level 4/.style={sibling distance=12em/6, level distance=3em},

]

\nodefill=blue!20 {20}

  child {node[fill=orange!20] {10}

  	child {node {5}

  		child {node {4}

  			child {node[xshift=-3em](1) {1}}

  		child {node {8}

  			child {node[xshift=-3em] {6}}

  	child {node {15}

  		child {node[xshift=-3em] {12}}

  child{node [fill=red!20] {33}

  	child {node {25}

  		child {node {23}

  			child {node[xshift=-3em] {21}}

  		child {node {28}}

      child {node {50}

  		child {node {44}

  			child {node {17}}

  			child {node {48}}

  		child {node {78}

  			child {node {62}}

  			child {node(88) {88}}

};

  \begin{scope}[on background layer]

  	\node [draw, dashed, fit=(20) (1) (88), rectangle, rounded corners, drop shadow={gray!10}] {};

  \end{scope}

\end{tikzpicture}

\end{document}

7.3.3. 红黑树(RBT)

红黑树演示

史上最好理解的红黑树讲解，让你彻底搞懂红黑树待补充

红黑树的概念与性质

红黑树的定义和性质.pdf

为什么要发明红黑树

平衡二叉树插入/删除很容易破坏平衡特性，需要频繁调整树的形态（先计算平衡因子，找到最小不平衡子树（时间开销大），再进行LL/RR/LR/RL调整）——适用于以查为主、很少插入/删除的场景
红黑树插入/删除很多时候不会破坏红黑特性，无需频繁调整树的形态，即便需要调整，一般都可以在常数级时间内完成——适用于频繁插入/删除的场景，实用性更强

红黑树的定义

红黑树是二叉排序树：左子树结点值 $⩽$ 根结点值 $⩽$ 右子树结点值（左根右）
相比于普通二叉排序树
- 每个结点是红色或者黑色的
- 根结点是黑色的（根叶黑）
- 叶结点是黑色的（通常是：外部结点、NULL结点、失败结点）（根叶黑）
- 不存在两个相邻的红结点（即红结点的父结点和孩子结点均是黑色）（不红红）
- 对每个结点，从该结点到任一叶结点的简单路径上，所含黑结点的数目相同（黑路同）

\usetikzlibrary{positioning}
\begin{document}
	\begin{tikzpicture}[scale=2, ultra thick,
	rednode/.style={draw=black, circle, fill=red!50, font =\huge, minimum size=3em},
	blacknode/.style={draw=black, circle, fill=gray!50, font =\huge, minimum size=3em},
	leafnode/.style={draw=black, rectangle, label=center:NULL, fill=gray!50, font =\large, minimum width=3em, minimum height=2em},
	level 1/.style={sibling distance=16em/1, level distance=3em},
	level 2/.style={sibling distance=16em/2, level distance=3em},
	level 3/.style={sibling distance=16em/4, level distance=3em},
	level 4/.style={sibling distance=16em/8, level distance=3em},
	]
	\node[blacknode](13){13}
		child {node[rednode] {8}
			child {node[blacknode] {1}
				child {node[leafnode] {}}
				child {node[rednode] {6}
					child {node[leafnode] {}}
					child {node[leafnode] {}}
				}
			}
			child {node[blacknode] {11}
				child {node[leafnode] {}}
				child {node[leafnode] {}}
			}
		}
        child {node[rednode] (17){17}
			child {node[blacknode] {15}
				child {node[leafnode] {}}
				child {node[leafnode] {}}
			}
			child {node[blacknode] (25){25}
				child {node[rednode] {22}
					child {node[leafnode]{}}
					child {node[leafnode] {}}
				}
				child {node[rednode] (27){27}
					child {node[leafnode] {}}
					child {node[leafnode] (null) {}}
				}
			}
		};
		\node[right of=13, font=\large, xshift=2em]{bh=2};
		\node[right of=17, font=\large, xshift=2em]{bh=2};
		\node[right of=25, font=\large, xshift=2em]{bh=1};
		\node[right of=27, font=\large, xshift=2em]{bh=1};
		\node[right of=null, font=\large, xshift=2em]{bh=0};
	\end{tikzpicture}
\end{document}

struct RBnode{	//红黑树的结点定义
	int key;			//关键字的值
	RBnode* parent;		//父结点指针
	RBnode* lChild;		//左孩子指针
	RBnode* rChild;		//右孩子指针
	int color;			//结点颜色，如：可用0/1表示黑/红，也可以使用枚举型或布尔型变量表示
};

结点的黑高bh：从某结点出发（不含该结点）到达任一空叶结点的路径上黑结点总数

根结点黑高为 $h$ 的红黑树，内部结点数（关键字）至少有 $2^{h} - 1$ 个（一共 $h$ 层黑结点的满树形态）

红黑树的性质

从根结点到叶结点的最长路径不大于最短路径的2倍
- 左子树、右子树高度差不超过两倍
若根结点黑高为 $h$ ，则内部结点最少时，为 $h$ 层黑结点的满树形态，此时内部结点数为 $2^{h} - 1$
若红黑色总高度为 $h$ ，则根结点的黑高 $⩽ \frac{h}{2}$ ，所以有 $n$ 个内部结点的高度 $h ⩽ 2 lo g_{2} (n + 1)$
- 红黑树查找操作时间复杂度为 $O (lo g_{2} n)$
红黑树的本质是2-3-4树，即4阶B树
- 黑色节点与它的红色子节点融合在一起，形成1个B树节点
- 红黑树的黑色节点个数与4阶B树的节点总个数相等
- 在所有的B树节点中，永远是黑色节点是父节点，红色节点是子节点。黑色节点在中间，红色节点在两边。

红黑树与2-3-4树的对应关系

红黑树的查找：与二叉排序树以及平衡二叉树相同，从根出发，右小左大，若查找到一个空叶结点，则查找失败

红黑树的插入

红黑树的插入.pdf

先查找，确定插入位置（原理同二叉排序树），插入新结点
新结点是根，染为黑色；新结点非根，染为红色，再判断是否满足不红红 ^[保证黑路同，非根结点只需要判断不红红] 考前记一记
1. 若插入新结点后依然满足红黑树定义，则插入结束
2. 若插入新结点后不满足红黑树定义，需要调整使其重新满足红黑树定义（看新结点的叔叔的脸色）
  - 黑叔叔：旋转（同平衡二叉树） + 染色
    - LL型：右单旋，父换爷+染色（父结点换到爷结点位置，对原来的父结点和爷结点进行染色，染色即为取另一种颜色）
    - RR型：左单旋，父换爷+染色
    - LR型：左右单旋，儿换爷+染色
    - RL型：右左单旋，儿换爷+染色
  - 红叔叔：染色 + 变新
    - 叔父爷染色，爷变为新结点（叔结点、父结点、爷结点染色，将爷结点视为新结点，继续进行调整）

Example

例题：从一棵空的红黑树开始，插入：20,10,5,30,40,57,3,2,4,35,25,18,22,23,24,19,18

插入20，是根结点，直接染黑

 

\begin{document}

\begin{tikzpicture}[scale=2, ultra thick,

rednode/.style={draw=black, circle, fill=red!50, font =\huge, minimum size=3em},

blacknode/.style={draw=black, circle, fill=gray!50, font =\huge, minimum size=3em},

leafnode/.style={draw=black, rectangle, label=center:NULL, fill=gray!50, font =\large, minimum width=3em, minimum height=2em},

level 1/.style={sibling distance=4em/1, level distance=3em},

level 2/.style={sibling distance=4em/2, level distance=3em},

]

\node[blacknode] {20}

  child {node[leafnode] {}}

  child {node[leafnode] {}};

\end{tikzpicture}

\end{document}

插入10，未破坏“不红红”

 

\usetikzlibrary{positioning}

\begin{document}

\begin{tikzpicture}[scale=2, ultra thick,

rednode/.style={draw=black, circle, fill=red!50, font =\huge, minimum size=3em},

blacknode/.style={draw=black, circle, fill=gray!50, font =\huge, minimum size=3em},

leafnode/.style={draw=black, rectangle, label=center:NULL, fill=gray!50, font =\large, minimum width=3em, minimum height=2em},

level 1/.style={sibling distance=4em/1, level distance=3em},

level 2/.style={sibling distance=4em/2, level distance=3em},

]

\node[blacknode] {20}

  child {node[rednode] {10}

  	child {node[leafnode] {}}

  	child {node[leafnode] {}}

  child {node[leafnode] {}};

\end{tikzpicture}

\end{document}

插入5，破坏“不红红”，叔结点为黑色，属于LL型，旋转后将原父结点与爷结点染色

 

\usetikzlibrary{positioning}

\usetikzlibrary{fit, backgrounds, shadows}

\begin{document}

\begin{tikzpicture}[scale=2, ultra thick,

rednode/.style={draw=black, circle, fill=red!50, font =\huge, minimum size=3em},

blacknode/.style={draw=black, circle, fill=gray!50, font =\huge, minimum size=3em},

leafnode/.style={draw=black, rectangle, label=center:NULL, fill=gray!50, font =\large, minimum width=3em, minimum height=2em},

level 1/.style={sibling distance=4em/1, level distance=3em},

level 2/.style={sibling distance=4em/2, level distance=3em},

]

\node[blacknode]at(0,0) {20}

  child {node[rednode] {10}

  	child {node[rednode] {5}

  		child {node[leafnode] {}}

  		child {node[leafnode] {}}

  	child {node[leafnode] {}}

  child {node[leafnode](uncle) {}};

\begin{scope}[on background layer]

  \node [draw, ultra thick,dashed, fit=(uncle), rectangle, rounded corners, drop shadow={gray!10}] {};

\end{scope}

\node[rednode]at(4,0) {10}

  child {node[rednode] {5}

  	child {node[leafnode] {}}

  	child {node[leafnode] {}}

  child {node[blacknode] {20}

  	child {node[leafnode] {}}

  child {node[leafnode] {}}

};

\node[blacknode]at(8,0) {10}

  child {node[rednode] {5}

  	child {node[leafnode] {}}

  	child {node[leafnode] {}}

  child {node[rednode] {20}

  	child {node[leafnode] {}}

  child {node[leafnode] {}}

};

\end{tikzpicture}

\end{document}

插入30，破坏“不红红”，叔结点为红色，将叔结点、父结点与爷结点染色，并将爷结点10视为新结点。

新结点10在根结点，直接染成黑色。

 

\usetikzlibrary{positioning}

\usetikzlibrary{fit, backgrounds, shadows}

\begin{document}

\begin{tikzpicture}[scale=2, ultra thick,

rednode/.style={draw=black, circle, fill=red!50, font =\huge, minimum size=3em},

blacknode/.style={draw=black, circle, fill=gray!50, font =\huge, minimum size=3em},

leafnode/.style={draw=black, rectangle, label=center:NULL, fill=gray!50, font =\large, minimum width=3em, minimum height=2em},

level 1/.style={sibling distance=4em/1, level distance=3em},

level 2/.style={sibling distance=4em/2, level distance=3em},

]

\node[blacknode]at(0,0) {10}

  child {node[rednode] (uncle){5}

  	child {node[leafnode] {}}

  	child {node[leafnode] {}}

  child {node[rednode] {20}

  	child {node[leafnode] {}}

  	child {node[rednode]{30}

  		child {node[leafnode] {}}

  		child {node[leafnode] {}}

};

\begin{scope}[on background layer]

  \node [draw, ultra thick,dashed, fit=(uncle), rectangle, rounded corners, drop shadow={gray!10}] {};

\end{scope}

\node[rednode]at(5,0) {10}

  child {node[blacknode] {5}

  	child {node[leafnode] {}}

  	child {node[leafnode] {}}

  child {node[blacknode] {20}

  	child {node[leafnode] {}}

  	child {node[rednode]{30}

  		child {node[leafnode] {}}

  		child {node[leafnode] {}}

};

\node[blacknode]at(10,0) {10}

  child {node[blacknode] {5}

  	child {node[leafnode] {}}

  	child {node[leafnode] {}}

  child {node[blacknode] {20}

  	child {node[leafnode] {}}

  	child {node[rednode]{30}

  		child {node[leafnode] {}}

  		child {node[leafnode] {}}

};

\end{tikzpicture}

\end{document}

插入40，破坏“不红红”，叔结点为黑色，属于RR型，旋转后就原父结点30与爷结点20染色

 

\usetikzlibrary{positioning}

\usetikzlibrary{fit, backgrounds, shadows}

\begin{document}

\begin{tikzpicture}[scale=2, ultra thick,

rednode/.style={draw=black, circle, fill=red!50, font =\huge, minimum size=3em},

blacknode/.style={draw=black, circle, fill=gray!50, font =\huge, minimum size=3em},

leafnode/.style={draw=black, rectangle, label=center:NULL, fill=gray!50, font =\large, minimum width=3em, minimum height=2em},

level 1/.style={sibling distance=8em/1, level distance=3em},

level 2/.style={sibling distance=8em/2, level distance=3em},

level 3/.style={sibling distance=8em/4, level distance=3em},

]

\node[blacknode]at(0,0) {10}

  child {node[blacknode] {5}

  	child {node[leafnode] {}}

  	child {node[leafnode] {}}

  child {node[blacknode] {20}

  	child {node[leafnode](uncle) {}}

  	child {node[rednode]{30}

  		child {node[leafnode] {}}

  		child {node[rednode] {40}

  			child {node[leafnode] {}}

  			child {node[leafnode] {}}

};

\begin{scope}[on background layer]

  \node [draw, ultra thick,dashed, fit=(uncle), rectangle, rounded corners, drop shadow={gray!10}] {};

\end{scope}

\node[blacknode]at(5,0) {10}

  child {node[blacknode] {5}

  	child {node[leafnode] {}}

  	child {node[leafnode] {}}

  child {node[rednode]{30}

  	child {node[blacknode] {20}

  		child {node[leafnode] {}}

  		child {node[leafnode] {}}

  	child {node[rednode] {40}

  		child {node[leafnode] {}}

  		child {node[leafnode] {}}

};

\node[blacknode]at(10,0) {10}

  child {node[rednode] {5}

  	child {node[leafnode] {}}

  	child {node[leafnode] {}}

  child {node[blacknode]{30}

  	child {node[rednode] {20}

  		child {node[leafnode] {}}

  		child {node[leafnode] {}}

  	child {node[rednode] {40}

  		child {node[leafnode] {}}

  		child {node[leafnode] {}}

};

\end{tikzpicture}

\end{document}

红黑树的删除

红黑树的删除.pdf

红黑树删除的时间复杂度 $= O (lo g_{2} n)$
红黑树中删除结点的处理方式与二叉排序树的删除一致
删除结点后，可能破坏红黑树特性，此时需要调整结点颜色、位置，使其再次满足红黑树性质

7.3.4 本节习题精选

选择题：题目、答案

综合题：题目、答案

7.4 B树、B+树

7.4.1. B树

B树演示

B树.pdf

B树，又称多路平衡查找树，B树中所有结点的孩子个数的最大值称为B树的阶，通常用 $m$ 表示。一棵 $m$ 阶B树或为空树，或为满足如下特性的 $m$ 叉树：（类似二叉查找树）

树中每个结点至多有 $m$ 棵子树，即至多含有 $m - 1$ 个关键字。
若根结点不是终端结点，则至少有 $2$ 棵子树。
规定：除根结点外的所有非叶结点至少有 $⌈ m /2 ⌉$ 棵子树，即至少含有 $⌈ m /2 ⌉ - 1$ 个关键字。（为了保证查找效率，每个结点的关键字不能太少）
规定： $m$ 叉查找树中，对于任意结点，其所有子树的高度均相同，所有的叶结点都出现在同一层次上，并且不带信息（可以视为外部结点或类似于折半查找判定树的查找失败结点，实际上这些结点不存在，指向这些结点的指针为空）。
B树中将失败结点称为叶子结点，将最下层含有实际数据的结点称为终端结点
所有非叶结点的结构如下：

\begin{document}
	\begin{tikzpicture}[scale=1, ultra thick]
	\tikzstyle{every node}=[font=\huge, draw=black, very thick, rectangle, minimum width=2cm, minimum height=1cm]
		\def\mystring{$n$, $P_{0}$, $K_{1}$, $P_{1}$, $K_{2}$, $P_{2}$, $\cdots$, $K_{n}$, $P_{n}$}
		\foreach \char [count=\i] in \mystring {
			\node[fill=gray!20] at (2*\i,0) {\char};
		}
	\end{tikzpicture}
\end{document}

其中， $K_{i} (i = 1, 2, \dots, n)$ 为结点的关键字，且满足 $K_{1} < K_{2} < \dots < K_{n}$ ； $P_{i} (i = 0, 1, \dots, n)$ 为指向子树根结点的指针，且指针 $P_{i - 1}$ 所指子树中所有结点的关键字均小于 $K_{i}$ ， $P_{i}$ 所指子树中所有结点的关键字均大于 $K_{i}$ ， $n (⌈ m /2 ⌉ - 1 \leq n \leq m - 1)$ 为结点中关键字的个数

  \usetikzlibrary{matrix}
\usetikzlibrary{positioning}
\begin{document}
	\begin{tikzpicture}[scale=0.8, ultra thick]
	\tikzstyle{every node}=[font=\huge, draw=black, very thick, rectangle, minimum width=3em, minimum height=3em]
		\matrix at(0,0) (node1)[matrix of nodes, column sep=0.5em]{
			1 & 3 & & \\
		};
		\matrix [right = 4em of node1] (node2)[matrix of nodes, column sep=0.5em]{
			6 & 8 & 9 & \\
		};
		\matrix [right = 4em of node2] (node3)[matrix of nodes, column sep=0.5em]{
			13 & 15 & & \\
		};
		\matrix [right = 4em of node3] (node4)[matrix of nodes, column sep=0.5em]{
			30 & 35 & & \\
		};
		\matrix [right = 4em of node4] (node5)[matrix of nodes, column sep=0.5em]{
			40 & 42 & & \\
		};
		\matrix [right = 4em of node5] (node6)[matrix of nodes, column sep=0.5em]{
			47 & 48 & 50 & 56\\
		};
 
		\matrix at(10,4) (node7)[matrix of nodes, column sep=0.5em]{
			5 & 11 & & \\
		};
		\matrix [right = 16em of node7] (node8)[matrix of nodes, column sep=0.5em]{
			36 & 45 & & \\
		};
		\matrix at(16,8) (node9)[matrix of nodes, column sep=0.5em]{
			22 &  &  & \\
		};
 
		\matrix [below=4em of node1] (null1)[matrix of nodes, column sep=0.5em, draw=none, nodes={font=\small, fill=gray!20}]{
			null & null & null & &\\
		};
		\matrix [below=4em of node2] (null2)[matrix of nodes, column sep=0.5em, draw=none, nodes={font=\small, fill=gray!20}]{
			null & null & null & null & \\
		};
		\matrix [below=4em of node3] (null3)[matrix of nodes, column sep=0.5em, draw=none, nodes={font=\small, fill=gray!20}]{
			null & null & null & & \\
		};
		\matrix [below=4em of node4] (null4)[matrix of nodes, column sep=0.5em, draw=none, nodes={font=\small, fill=gray!20}]{
			null & null & null & & \\
		};
		\matrix [below=4em of node5] (null5)[matrix of nodes, column sep=0.5em, draw=none, nodes={font=\small, fill=gray!20}]{
			null & null & null & & \\
		};
		\matrix [below=4em of node6] (null6)[matrix of nodes, column sep=0.5em, draw=none, nodes={font=\small, fill=gray!20}]{
			null & null & null & null & null\\
		};
 
		\draw[-latex](node9-1-1.south west) -- (node7.north);
		\draw[-latex](node9-1-1.south east) -- (node8.north);
 
		\draw[-latex](node7-1-1.south west) -- (node1.north);
		\draw[-latex](node7-1-1.south east) -- (node2.north);
		\draw[-latex](node7-1-2.south east) -- (node3.north);
 
		\draw[-latex](node8-1-1.south west) -- (node4.north);
		\draw[-latex](node8-1-1.south east) -- (node5.north);
		\draw[-latex](node8-1-2.south east) -- (node6.north);
 
		% 空结点
		\foreach \cnt[count=\i] in{3,4,3,3,3,5}{
			\draw[-latex](node\i-1-1.south west) -- (null\i-1-1.north);
			\foreach \cntj[count=\j] in{2,3,4,5}{
				\ifnum \j<\cnt
					\draw[-latex](node\i-1-\j.south east) -- (null\i-1-\cntj.north);
				\else
				\fi
			}
		}
	\end{tikzpicture}
\end{document}

$m$ 阶B树的核心特性：

根结点的子树数 $\in [2, m]$ ，关键字数 $\in [1, m - 1]$ 。其他结点的子树数 $\in [⌈ m /2 ⌉, m]$ ；关键字数 $\in [⌈ m /2 ⌉ - 1, m - 1]$
对任一结点，其所有子树高度都相同。
关键字的值：子树0 < 关键字1 < 子树1 < 关键字2 < 子树2 < … (类比二叉查找树左<中<右)

B树的高度：含 $n$ 个关键字的 $m$ 叉B树，最小高度、最大高度是多少？（不包括叶子结点）考前记一记

填上叶子结点，m叉B树共 $h + 1$ 层，但注意叶子结点没有关键字

最小高度：让每个结点尽可能的满，有 $m - 1$ 个关键字， $m$ 个分叉，故 $n ⩽ (m - 1) (1 + m + m^{2} + \dots + m^{h - 1}) = m^{h} - 1$
最大高度：让各层的分叉尽可能少，即根结点只有2个分叉，其他结点只有 $⌈ m /2 ⌉$ 个分叉
- 第 $h + 1$ 层共有叶子结点 $2 (⌈ m /2 ⌉)^{h - 1}$ 个，而 $n$ 个关键字的B树必有 $n + 1$ 个叶子结点，则 $n + 1 ⩾ 2 (⌈ m /2 ⌉)^{h - 1}$
- 根结点至少有1个关键字，至少一共有其他结点 $\frac{2 [( ⌈ m /2 ⌉ ) ^{h - 1} - 1 ]}{⌈ m /2 ⌉ - 1}$ 个，每个结点有 $⌈ m /2 ⌉ - 1$ 个关键字，则一共有关键字 $1 + 2 [(⌈ m /2 ⌉)^{h - 1} - 1]$ 个，则 $n ⩾ 1 + 2 [(⌈ m /2 ⌉)^{h - 1} - 1]$
$lo g_{m} (n + 1) ⩽ h ⩽ lo g_{⌈ m /2 ⌉} \frac{n + 1}{2} + 1$

7.4.2. B树的基本操作

B树的插入删除.pdf

B树的查找

B树的查找操作与二叉查找树类似。B树的查找包含两个基本操作：① 在B树中找结点；② 在结点中找关键字。

B树常存储在磁盘上，因此前一个查找操作在磁盘上进行，后一个查找操作在内存中进行。在B树中查找到某个结点后，先在有序表中进行查找，若找到则查找成功，否则按照对应指针信息到所指的子树中去查找。查找到叶子结点（对应指针为空指针），则说明树中没有对应的关键字，查找失败。

B树的插入

将关键字插入到B树的过程：

定位：利用B树的查找算法，找到插入该关键字的最底层中的某个非叶子结点。（插入位置一定是最底层的某个非叶子结点！）
插入：B树中，每个非失败结点的关键字个数都在区间 $[⌈ m /2 ⌉ - 1, m - 1]$ 内。若插入关键字之后结点关键字个数小于 $m$ ，则可以直接插入；否则必须对结点进行分裂
分裂：从结点的中间位置（ $⌈ m /2 ⌉$ ）将其中的关键字分为两部分，左半部分包含的关键字放到原结点中，右半部分包含的关键字放到新结点中，中间位置（ $⌈ m /2 ⌉$ ）的关键字则插入原结点的父结点（注意要保证父结点中关键字顺序）。若此时父结点的关键字也超过了上限，则对父结点继续进行分裂操作，直到这个过程传到根结点为止，进而导致B树的高度增加

Example

如：在下述B树中插入80，原结点将分为两个部分

 

\usetikzlibrary{matrix}

\usetikzlibrary{positioning}

\begin{document}

\begin{tikzpicture}[scale=1, ultra thick]

\tikzstyle{every node}=[font=\huge, draw=black, very thick, rectangle, minimum width=3em, minimum height=3em]

  \matrix at(0,0) (node1)[matrix of nodes, column sep=0.5em]{

  	25 & 38 & 49 & 60\\

};

  \node [right of=node1, xshift=8em, fill=green!20] {80};

  \matrix at(8,0) (node1)[matrix of nodes, column sep=0.5em]{

  	25 & 38 & & \\

};

  \matrix at(16,0) (node2)[matrix of nodes, column sep=0.5em]{

  	60 & 80 & & \\

};

  \matrix at(12,4) (node3)[matrix of nodes, column sep=0.5em]{

  	49 &  &  & \\

};

  \draw[-latex](node3-1-1.south west) -- (node1.north);

  \draw[-latex](node3-1-1.south east) -- (node2.north);

\end{tikzpicture}

\end{document}

插入90

 

\usetikzlibrary{matrix}

\usetikzlibrary{positioning}

\begin{document}

\begin{tikzpicture}[scale=1, ultra thick]

\tikzstyle{every node}=[font=\huge, draw=black, very thick, rectangle, minimum width=3em, minimum height=3em]

  \matrix at(8,0) (node1)[matrix of nodes, column sep=0.5em]{

  	25 & 38 & & \\

};

  \matrix at(16,0) (node2)[matrix of nodes, column sep=0.5em]{

  	60 & 80 & |[fill=green!20]|90 & \\

};

  \matrix at(12,4) (node3)[matrix of nodes, column sep=0.5em]{

  	49 &  &  & \\

};

  \draw[-latex](node3-1-1.south west) -- (node1.north);

  \draw[-latex](node3-1-1.south east) -- (node2.north);

\end{tikzpicture}

\end{document}

插入99

 

\usetikzlibrary{matrix}

\usetikzlibrary{positioning}

\begin{document}

\begin{tikzpicture}[scale=1, ultra thick]

\tikzstyle{every node}=[font=\huge, draw=black, very thick, rectangle, minimum width=3em, minimum height=3em]

  \matrix at(8,0) (node1)[matrix of nodes, column sep=0.5em]{

  	25 & 38 & & \\

};

  \matrix at(16,0) (node2)[matrix of nodes, column sep=0.5em]{

  	60 & 80 & 90 & |[fill=green!20]|99 \\

};

  \matrix at(12,4) (node3)[matrix of nodes, column sep=0.5em]{

  	49 &  &  & \\

};

  \draw[-latex](node3-1-1.south west) -- (node1.north);

  \draw[-latex](node3-1-1.south east) -- (node2.north);

\end{tikzpicture}

\end{document}

插入88

 

\usetikzlibrary{matrix}

\usetikzlibrary{positioning}

\begin{document}

\begin{tikzpicture}[scale=1, ultra thick]

\tikzstyle{every node}=[font=\huge, draw=black, very thick, rectangle, minimum width=3em, minimum height=3em]

  \matrix at(0,0) (node1)[matrix of nodes, column sep=0.5em]{

  	25 & 38 & & \\

};

  \matrix at(8,0) (node2)[matrix of nodes, column sep=0.5em]{

  	60 & 80  & |[fill=green!20]|88 & 90 \\

};

  \matrix at(4,4) (node3)[matrix of nodes, column sep=0.5em]{

  	49 &  &  & \\

};

  \node [right of=node2, xshift=8em] {99};

  \draw[-latex](node3-1-1.south west) -- (node1.north);

  \draw[-latex](node3-1-1.south east) -- (node2.north);

\end{tikzpicture}

\end{document}

 

\usetikzlibrary{matrix}

\usetikzlibrary{positioning}

\begin{document}

\begin{tikzpicture}[scale=1, ultra thick]

\tikzstyle{every node}=[font=\huge, draw=black, very thick, rectangle, minimum width=3em, minimum height=3em]

  \matrix at(0,0) (node1)[matrix of nodes, column sep=0.5em]{

  	25 & 38 & & \\

};

  \matrix at(8,0) (node2)[matrix of nodes, column sep=0.5em]{

  	60 & 80 & & \\

};

  \matrix at(16,0) (node3)[matrix of nodes, column sep=0.5em]{

  	90 & 99 & & \\

};

  \matrix at(8,4) (node4)[matrix of nodes, column sep=0.5em]{

  	49 & 88 &  & \\

};

  \draw[-latex](node4-1-1.south west) -- (node1.north);

  \draw[-latex](node4-1-1.south east) -- (node2.north);

  \draw[-latex](node4-1-2.south east) -- (node3.north);

\end{tikzpicture}

\end{document}

B树的删除

非终端结点的删除：使用直接前驱（最右下）或者直接后继（最左下）来代替被删除的关键字，转换为删除终端结点。
终端结点的删除，具体分为三种情况：
- 直接删除关键字：若删除关键字前所在结点关键字个数 $⩾ ⌈ m /2 ⌉$ ，则可直接删除。
- 兄弟够借：若删除关键字前所在结点关键字个数 $= ⌈ m /2 ⌉ - 1$ ，且与此结点相邻的兄弟结点关键字个数 $⩾ ⌈ m /2 ⌉$ ，则需调整该结点、兄弟结点及双亲结点（父子换位法）以达到新的平衡。即把父结点（后继/前驱）换下来补充，兄弟结点（后继的后继/前驱的前驱）换上去顶替
- 兄弟不够借：若删除关键字前所在结点关键字个数 $= ⌈ m /2 ⌉ - 1$ ，且与此结点相邻的兄弟结点关键字个数 $= ⌈ m /2 ⌉ - 1$ ，则将该结点、兄弟结点及双亲结点中的关键字进行合并。合并过程中，双亲结点的关键字个数会减1，可能需要继续合并
  - 若其双亲结点是根结点且关键字个数减少至0，则直接将根结点删除，合并后的新结点成为根；
  - 若双亲结点不是根结点，且关键字个数减少至 $⌈ m /2 ⌉ - 2$ ，则又要与他的兄弟结点进行调整或合并操作，并重复上述步骤，直至达到要求为止

Example

例：删除结点38，右兄弟够借，用70补充

 

\usetikzlibrary{matrix}

\usetikzlibrary{positioning}

\begin{document}

\begin{tikzpicture}[scale=0.6, ultra thick]

\tikzstyle{every node}=[font=\huge, draw=black, very thick, rectangle, minimum width=3em, minimum height=3em]

  \matrix at(0,0) (node1)[matrix of nodes, column sep=0.5em]{

  	25 & |[fill=gray!20]|38 & & \\

};

  \matrix at(8,0) (node2)[matrix of nodes, column sep=0.5em]{

  	70 & 71 & 72 & \\

};

  \matrix at(16,0) (node3)[matrix of nodes, column sep=0.5em]{

  	74 & 75 & 76 & \\

};

  \matrix at(24,0) (node4)[matrix of nodes, column sep=0.5em]{

  	83 & 86 & 87 & \\

};

  \matrix at(32,0) (node5)[matrix of nodes, column sep=0.5em]{

  	90 & 92 & & \\

};

  \matrix at(40,0) (node6)[matrix of nodes, column sep=0.5em]{

  	94 & 99 & & \\

};

  \matrix at(12,4) (node7)[matrix of nodes, column sep=0.5em]{

  	49 & 73 &  & \\

};

  \matrix at(28,4) (node8)[matrix of nodes, column sep=0.5em]{

  	88 & 93 &  & \\

};

  \matrix at(20,8) (node9)[matrix of nodes, column sep=0.5em]{

  	82 &  &  & \\

};

  \draw[-latex](node9-1-1.south west) -- (node7.north);

  \draw[-latex](node9-1-1.south east) -- (node8.north);

  \draw[-latex](node7-1-1.south west) -- (node1.north);

  \draw[-latex](node7-1-1.south east) -- (node2.north);

  \draw[-latex](node7-1-2.south east) -- (node3.north);

  \draw[-latex](node8-1-1.south west) -- (node4.north);

  \draw[-latex](node8-1-1.south east) -- (node5.north);

  \draw[-latex](node8-1-2.south east) -- (node6.north);

  \draw[-latex, red](node7-1-1.north) [out=90, in=90] to (node1-1-2.north);

  \draw[-latex, red](node2-1-1.north) [out=90, in=-90] to (node7-1-1.south);

\end{tikzpicture}

\end{document}

 

\usetikzlibrary{matrix}

\usetikzlibrary{positioning}

\begin{document}

\begin{tikzpicture}[scale=0.6, ultra thick]

\tikzstyle{every node}=[font=\huge, draw=black, very thick, rectangle, minimum width=3em, minimum height=3em]

  \matrix at(0,0) (node1)[matrix of nodes, column sep=0.5em]{

  	25 & 49 & & \\

};

  \matrix at(8,0) (node2)[matrix of nodes, column sep=0.5em]{

  	71 & 72 & & \\

};

  \matrix at(16,0) (node3)[matrix of nodes, column sep=0.5em]{

  	74 & 75 & 76 & \\

};

  \matrix at(24,0) (node4)[matrix of nodes, column sep=0.5em]{

  	83 & 86 & 87 & \\

};

  \matrix at(32,0) (node5)[matrix of nodes, column sep=0.5em]{

  	90 & 92 & & \\

};

  \matrix at(40,0) (node6)[matrix of nodes, column sep=0.5em]{

  	94 & 99 & & \\

};

  \matrix at(12,4) (node7)[matrix of nodes, column sep=0.5em]{

  	70 & 73 &  & \\

};

  \matrix at(28,4) (node8)[matrix of nodes, column sep=0.5em]{

  	88 & 93 &  & \\

};

  \matrix at(20,8) (node9)[matrix of nodes, column sep=0.5em]{

  	82 &  &  & \\

};

  \draw[-latex](node9-1-1.south west) -- (node7.north);

  \draw[-latex](node9-1-1.south east) -- (node8.north);

  \draw[-latex](node7-1-1.south west) -- (node1.north);

  \draw[-latex](node7-1-1.south east) -- (node2.north);

  \draw[-latex](node7-1-2.south east) -- (node3.north);

  \draw[-latex](node8-1-1.south west) -- (node4.north);

  \draw[-latex](node8-1-1.south east) -- (node5.north);

  \draw[-latex](node8-1-2.south east) -- (node6.north);

\end{tikzpicture}

\end{document}

Example

例：删除结点90，左兄弟够借，用87补充

 

\usetikzlibrary{matrix}

\usetikzlibrary{positioning}

\begin{document}

\begin{tikzpicture}[scale=0.6, ultra thick]

\tikzstyle{every node}=[font=\huge, draw=black, very thick, rectangle, minimum width=3em, minimum height=3em]

  \matrix at(0,0) (node1)[matrix of nodes, column sep=0.5em]{

  	25 & 49 & & \\

};

  \matrix at(8,0) (node2)[matrix of nodes, column sep=0.5em]{

  	71 & 72 & & \\

};

  \matrix at(16,0) (node3)[matrix of nodes, column sep=0.5em]{

  	74 & 75 & 76 & \\

};

  \matrix at(24,0) (node4)[matrix of nodes, column sep=0.5em]{

  	83 & 86 & 87 & \\

};

  \matrix at(32,0) (node5)[matrix of nodes, column sep=0.5em]{

  	|[fill=gray!20]|90 & 92 & & \\

};

  \matrix at(40,0) (node6)[matrix of nodes, column sep=0.5em]{

  	94 & 99 & & \\

};

  \matrix at(12,4) (node7)[matrix of nodes, column sep=0.5em]{

  	70 & 73 &  & \\

};

  \matrix at(28,4) (node8)[matrix of nodes, column sep=0.5em]{

  	88 & 93 &  & \\

};

  \matrix at(20,8) (node9)[matrix of nodes, column sep=0.5em]{

  	82 &  &  & \\

};

  \draw[-latex](node9-1-1.south west) -- (node7.north);

  \draw[-latex](node9-1-1.south east) -- (node8.north);

  \draw[-latex](node7-1-1.south west) -- (node1.north);

  \draw[-latex](node7-1-1.south east) -- (node2.north);

  \draw[-latex](node7-1-2.south east) -- (node3.north);

  \draw[-latex](node8-1-1.south west) -- (node4.north);

  \draw[-latex](node8-1-1.south east) -- (node5.north);

  \draw[-latex](node8-1-2.south east) -- (node6.north);

  \draw[-latex, red](node8-1-1.north) [out=90, in=90] to (node5-1-1.north);

  \draw[-latex, red](node4-1-3.north) [out=90, in=-90] to (node8-1-1.south);

\end{tikzpicture}

\end{document}

 

\usetikzlibrary{matrix}

\usetikzlibrary{positioning}

\begin{document}

\begin{tikzpicture}[scale=0.6, ultra thick]

\tikzstyle{every node}=[font=\huge, draw=black, very thick, rectangle, minimum width=3em, minimum height=3em]

  \matrix at(0,0) (node1)[matrix of nodes, column sep=0.5em]{

  	25 & 49 & & \\

};

  \matrix at(8,0) (node2)[matrix of nodes, column sep=0.5em]{

  	71 & 72 & & \\

};

  \matrix at(16,0) (node3)[matrix of nodes, column sep=0.5em]{

  	74 & 75 & 76 & \\

};

  \matrix at(24,0) (node4)[matrix of nodes, column sep=0.5em]{

  	83 & 86 &  & \\

};

  \matrix at(32,0) (node5)[matrix of nodes, column sep=0.5em]{

  	88 & 92 & & \\

};

  \matrix at(40,0) (node6)[matrix of nodes, column sep=0.5em]{

  	94 & 99 & & \\

};

  \matrix at(12,4) (node7)[matrix of nodes, column sep=0.5em]{

  	70 & 73 &  & \\

};

  \matrix at(28,4) (node8)[matrix of nodes, column sep=0.5em]{

  	87 & 93 &  & \\

};

  \matrix at(20,8) (node9)[matrix of nodes, column sep=0.5em]{

  	82 &  &  & \\

};

  \draw[-latex](node9-1-1.south west) -- (node7.north);

  \draw[-latex](node9-1-1.south east) -- (node8.north);

  \draw[-latex](node7-1-1.south west) -- (node1.north);

  \draw[-latex](node7-1-1.south east) -- (node2.north);

  \draw[-latex](node7-1-2.south east) -- (node3.north);

  \draw[-latex](node8-1-1.south west) -- (node4.north);

  \draw[-latex](node8-1-1.south east) -- (node5.north);

  \draw[-latex](node8-1-2.south east) -- (node6.north);

\end{tikzpicture}

\end{document}

Example

例：删除结点49，兄弟不够借，将兄弟结点与父结点中的关键字进行合并。

 

\usetikzlibrary{matrix}

\usetikzlibrary{positioning}

\begin{document}

\begin{tikzpicture}[scale=0.6, ultra thick]

\tikzstyle{every node}=[font=\huge, draw=black, very thick, rectangle, minimum width=3em, minimum height=3em]

  \matrix at(0,0) (node1)[matrix of nodes, column sep=0.5em]{

  	25 & |[fill=gray!20]|49 & & \\

};

  \matrix at(8,0) (node2)[matrix of nodes, column sep=0.5em]{

  	71 & 72 & & \\

};

  \matrix at(16,0) (node3)[matrix of nodes, column sep=0.5em]{

  	74 & 75 & 76 & \\

};

  \matrix at(24,0) (node4)[matrix of nodes, column sep=0.5em]{

  	83 & 86 &  & \\

};

  \matrix at(32,0) (node5)[matrix of nodes, column sep=0.5em]{

  	88 & 92 & & \\

};

  \matrix at(40,0) (node6)[matrix of nodes, column sep=0.5em]{

  	94 & 99 & & \\

};

  \matrix at(12,4) (node7)[matrix of nodes, column sep=0.5em]{

  	70 & 73 &  & \\

};

  \matrix at(28,4) (node8)[matrix of nodes, column sep=0.5em]{

  	87 & 93 &  & \\

};

  \matrix at(20,8) (node9)[matrix of nodes, column sep=0.5em]{

  	82 &  &  & \\

};

  \draw[-latex](node9-1-1.south west) -- (node7.north);

  \draw[-latex](node9-1-1.south east) -- (node8.north);

  \draw[-latex](node7-1-1.south west) -- (node1.north);

  \draw[-latex](node7-1-1.south east) -- (node2.north);

  \draw[-latex](node7-1-2.south east) -- (node3.north);

  \draw[-latex](node8-1-1.south west) -- (node4.north);

  \draw[-latex](node8-1-1.south east) -- (node5.north);

  \draw[-latex](node8-1-2.south east) -- (node6.north);

\end{tikzpicture}

\end{document}

合并后父结点中的关键字个数不够，将父结点的关键字与其兄弟结点进行调整

 

\usetikzlibrary{matrix}

\usetikzlibrary{positioning}

\begin{document}

\begin{tikzpicture}[scale=0.6, ultra thick]

\tikzstyle{every node}=[font=\huge, draw=black, very thick, rectangle, minimum width=3em, minimum height=3em]

  \matrix at(6,0) (node1)[matrix of nodes, column sep=0.5em]{

  	25 & 70 & 71 & 72\\

};

  %\matrix at(8,0) (node2)[matrix of nodes, column sep=0.5em]{

  %	71 & 72 & & \\

%};

  \matrix at(16,0) (node3)[matrix of nodes, column sep=0.5em]{

  	74 & 75 & 76 & \\

};

  \matrix at(24,0) (node4)[matrix of nodes, column sep=0.5em]{

  	83 & 86 &  & \\

};

  \matrix at(32,0) (node5)[matrix of nodes, column sep=0.5em]{

  	88 & 92 & & \\

};

  \matrix at(40,0) (node6)[matrix of nodes, column sep=0.5em]{

  	94 & 99 & & \\

};

  \matrix at(12,4) (node7)[matrix of nodes, column sep=0.5em]{

  	73 & &  & \\

};

  \matrix at(28,4) (node8)[matrix of nodes, column sep=0.5em]{

  	87 & 93 &  & \\

};

  \matrix at(20,8) (node9)[matrix of nodes, column sep=0.5em]{

  	82 &  &  & \\

};

  \draw[-latex](node9-1-1.south west) -- (node7.north);

  \draw[-latex](node9-1-1.south east) -- (node8.north);

  \draw[-latex](node7-1-1.south west) -- (node1.north);

  %\draw[-latex](node7-1-1.south east) -- (node2.north);

  \draw[-latex](node7-1-1.south east) -- (node3.north);

  \draw[-latex](node8-1-1.south west) -- (node4.north);

  \draw[-latex](node8-1-1.south east) -- (node5.north);

  \draw[-latex](node8-1-2.south east) -- (node6.north);

\end{tikzpicture}

\end{document}

 

\usetikzlibrary{matrix}

\usetikzlibrary{positioning}

\begin{document}

\begin{tikzpicture}[scale=0.6, ultra thick]

\tikzstyle{every node}=[font=\huge, draw=black, very thick, rectangle, minimum width=3em, minimum height=3em]

  \matrix at(6,0) (node1)[matrix of nodes, column sep=0.5em]{

  	25 & 70 & 71 & 72\\

};

  \matrix at(16,0) (node3)[matrix of nodes, column sep=0.5em]{

  	74 & 75 & 76 & \\

};

  \matrix at(24,0) (node4)[matrix of nodes, column sep=0.5em]{

  	83 & 86 &  & \\

};

  \matrix at(32,0) (node5)[matrix of nodes, column sep=0.5em]{

  	88 & 92 & & \\

};

  \matrix at(40,0) (node6)[matrix of nodes, column sep=0.5em]{

  	94 & 99 & & \\

};

  \matrix at(20,4) (node7)[matrix of nodes, column sep=0.5em]{

  	73 & 82 & 87 & 93\\

};

  \draw[-latex](node7-1-1.south west) -- (node1.north);

  \draw[-latex](node7-1-1.south east) -- (node3.north);

  \draw[-latex](node7-1-2.south east) -- (node4.north);

  \draw[-latex](node7-1-3.south east) -- (node5.north);

  \draw[-latex](node7-1-4.south east) -- (node6.north);

\end{tikzpicture}

\end{document}

7.4.3. B+树

B+树是应数据库所需出现的一种B树的变形树，用于数据库索引和操作系统文件索引

B+树演示

B+树.pdf

一棵 $m$ 阶的B+树需满足以下条件（类似分块查找）

每个分支结点最多有 $m$ 棵子树（孩子结点）。
非叶根结点至少有两颗子树，其他每个分支结点至少有 $⌈ m /2 ⌉$ 棵子树。
结点的子树个数与关键字个数相同
所有叶子结点包含所有关键字及指向相应记录的指针，叶子结点中将关键字按大小排列，并且相邻叶子结点按大小顺序相互链接起来。（说明B+树支持顺序查找）
所有分支结点仅包含它的各个结点中关键字的最大值及指向其子结点的指针。

\usetikzlibrary{matrix}
\usetikzlibrary{positioning}
\begin{document}
	\begin{tikzpicture}[scale=0.8, ultra thick]
	\tikzstyle{every node}=[font=\huge, draw=black, very thick, rectangle, minimum width=3em, minimum height=3em]
		\matrix at(0,0) (node1)[matrix of nodes, column sep=0.5em]{
			1 & 3 & & \\
		};
		\matrix [right = 4em of node1] (node2)[matrix of nodes, column sep=0.5em]{
			6 & 8 & 9 & \\
		};
		\matrix [right = 4em of node2] (node3)[matrix of nodes, column sep=0.5em]{
			13 & 15 & & \\
		};
		\matrix [right = 4em of node3] (node4)[matrix of nodes, column sep=0.5em]{
			30 & 35 & & \\
		};
		\matrix [right = 4em of node4] (node5)[matrix of nodes, column sep=0.5em]{
			40 & 42 & & \\
		};
		\matrix [right = 4em of node5] (node6)[matrix of nodes, column sep=0.5em]{
			47 & 48 & 50 & 56\\
		};
 
		\matrix at(12,4) (node7)[matrix of nodes, column sep=0.5em]{
			3 & 9 & 15 & \\
		};
		\matrix [right = 4em of node7] (node8)[matrix of nodes, column sep=0.5em]{
			35 & 42 & 56 & \\
		};
		\matrix at(16,8) (node9)[matrix of nodes, column sep=0.5em]{
			15 & 56 &  & \\
		};
 
		\matrix [below=4em of node1] (data1)[matrix of nodes, column sep=0.5em, draw=none, nodes={font=\small, fill=gray!20}]{
			data & data &  & \\
		};
		\matrix [below=4em of node2] (data2)[matrix of nodes, column sep=0.5em, draw=none, nodes={font=\small, fill=gray!20}]{
			data & data & data & \\
		};
		\matrix [below=4em of node3] (data3)[matrix of nodes, column sep=0.5em, draw=none, nodes={font=\small, fill=gray!20}]{
			data & data &  & \\
		};
		\matrix [below=4em of node4] (data4)[matrix of nodes, column sep=0.5em, draw=none, nodes={font=\small, fill=gray!20}]{
			data & data &  & \\
		};
		\matrix [below=4em of node5] (data5)[matrix of nodes, column sep=0.5em, draw=none, nodes={font=\small, fill=gray!20}]{
			data & data &  & \\
		};
		\matrix [below=4em of node6] (data6)[matrix of nodes, column sep=0.5em, draw=none, nodes={font=\small, fill=gray!20}]{
			data & data & data & data \\
		};
 
		\draw[-latex](node9-1-1.south) -- (node7.north);
		\draw[-latex](node9-1-2.south) -- (node8.north);
 
		\draw[-latex](node7-1-1.south) -- (node1.north);
		\draw[-latex](node7-1-2.south) -- (node2.north);
		\draw[-latex](node7-1-3.south) -- (node3.north);
 
		\draw[-latex](node8-1-1.south) -- (node4.north);
		\draw[-latex](node8-1-2.south) -- (node5.north);
		\draw[-latex](node8-1-3.south) -- (node6.north);
 
		\node[left=4em of node1, draw=none] (p) {p};
		\draw[-latex](p)--(node1);
		\draw[-latex](node1)--(node2);
		\draw[-latex](node2)--(node3);
		\draw[-latex](node3)--(node4);
		\draw[-latex](node4)--(node5);
		\draw[-latex](node5)--(node6);
 
		% 空结点
		\foreach \cnt[count=\i] in{3,4,3,3,3,5}{
			\foreach \j in{1,2,3,4}{
				\ifnum \j<\cnt
					\draw[-latex](node\i-1-\j.south) -- (data\i-1-\j.north);
				\else
				\fi
			}
		}
	\end{tikzpicture}
\end{document}

对比 B树：

m阶B树	m阶B+树
结点中 $n$ 个关键字对应 $n + 1$ 棵子树	结点中 $n$ 个关键字对应 $n$ 棵子树
根结点关键字数 $n \in [1, m - 1]$ 其他结点关键字数 $n \in [⌈ m /2 ⌉ - 1, m - 1]$	根结点关键字数 $n \in [1, m]$ 其他结点关键字数 $n \in [⌈ m /2 ⌉, m]$
各结点包含的关键字是不重复的	叶子结点包含全部关键字，非叶结点出现过的关键字也会出现在叶子结点中
结点中包含了关键字对应的记录的存储地址	叶子结点包含信息，非叶结点只起索引作用。非叶结点中的每个索引项只含有对应子树的最大关键字和指向该字树的指针，不含有该关键字对应记录的存储地址
不支持顺序查找。查找成功时可能停在任何一层结点，查找速度不稳定	支持顺序查找。查找成功或失败一定会达到最下一层结点，查找速度稳定

在B+树中，非叶结点不含有该关键字对应记录的存储地址，这使得一个磁盘块中可以包含更多个关键字，使得B+树的阶更大，分枝数更多，树更矮，读磁盘次数更少，查找更快

7.4.4 本节习题精选

选择题：题目、答案

综合题：题目、答案

7.5. 散列查找及其性能分析

7.5.1. 散列表的基本概念

散列表的基本概念.pdf

散列函数：一个把查找表中的关键字映射成该关键字对应的地址的函数，记作 $H a s h (k ey) = A dd r$ 。
散列表：又称哈希表，一种根据关键字而直接进行访问的数据结构。散列表建立了数据元素关键字和存储地址之间的一种直接映射关系。
理想情况下，对散列表进行查找的时间复杂度为 $O (1)$
冲突：散列函数可能会把两个或两个以上的不同关键字映射到同一地址，称这种情况为冲突。发生冲突的不同关键字称为同义词。
用拉链法（又称链接法、链地址法）处理冲突，把所有同义词存储在一个链表中
散列查找是典型的“用空间换时间”的算法，只要散列函数设计合理，散列表越长，冲突的概率越低

7.5.2. 散列函数的构造方法

设计目标：让不同关键字的冲突尽可能少

散列函数的构造.pdf

散列函数的要求

定义域必须涵盖所有可能出现的关键字
值域不能超出散列表的地址范围
尽可能减少冲突，散列函数计算出来的地址应该尽可能均匀的分布在整个地址空间
散列函数应该尽可能简单，能够快速计算出任意一个关键字对应的散列地址

常见散列函数

直接定址法：直接取关键字的某个线性函数值为散列地址，散列函数为 $H (k ey) = k ey$ 或 $H (k ey) = a \times k ey + b$ 考前记一记
- 这种方法计算简单，不会产生冲突，适合关键字的分布基本连续的情况，若关键字不连续，空位较多，则会造成存储空间的浪费
除留余数法：假定散列表表长 $m$ ，取一个不大于但最接近 $m$ 的质数 $p$ ，利用散列函数 $H (k ey) = k ey % p$ 将关键字转换为散列地址。
- $p$ 取质数是因为这样可以使关键字通过散列函数转换后等概率地映射到散列空间上的任一地址。
数字分析法：选取数码分布较为均匀的若干位作为散列地址
- 假设关键字是 $r$ 进制数，而 $r$ 个数码在各位上出现的频率不一定相同，可能在某些位上分布的均匀一些，而在某些位分布的不均匀。此时应选数码分布均匀的若干位作为散列地址。
平方取中法：取关键字平方值的中间几位作为散列地址，具体取多少位视具体情况而定。
- 这种方法得到的散列地址与关键字的每一位都有关系，因此使得散列地址分布比较均匀。适用于关键字每位取值都不够均匀或均小于散列地址所需的位数。

7.5.3. 处理冲突的方法

开放定址法

如果发生冲突，就给新元素另找一个空闲位置。

线性探测法演示

平方探测法演示

双散列法演示

处理冲突的方法_开放定址法.pdf

指可存放新表项的空闲地址既向它的同义词表项开放，又向它的非同义词表项开放。其数学递推公式为： $H_{i} = (H (k ey) + d_{i}) % m$ 其中， $H (k ey)$ 为散列函数， $i = 0, 1, 2, \dots, k (k ⩽ m - 1)$ 为冲突的次数， $m$ 表示散列表表长， $d_{i}$ 为增量序列。增量序列通常有以下几种取法：

线性探测法： $d_{i} = 0, 1, 2, ..., m - 1$ 。使用方法发生冲突时，顺序查看下一个单元，直到找到一个空闲单元或查遍全表
- 使用这种方法可能造成大量元素在相邻的散列地址上堆积（或聚集）起来，大大降低了查找效率。（查找需要查找到空位置为止）
- 发生聚集的主要原因是解决冲突的方式选择不当
平方探测法：也称二次探测法， $d_{i} = 0^{2}, 1^{2}, - 1^{2}, 2^{2}, - 2^{2}, \dots, k^{2}, - k^{2}$ 。其中 $k ⩽ m /2$ 。使用这种方法可以避免堆积问题
- 散列表长度 $m$ 必须是一个可以表示为 $4 j + 3$ 的质数（符合这个条件才能够探测到所有位置）
双散列法： $d_{i} = i \times ha s h_{2} (k ey)$ ，
- 若 $ha s h_{2} (k ey)$ 计算得到的值与散列表表长 $m$ 互质，就能保证双散列法可以探测所有单元
伪随机序列法： $d_{i}$ 是一个伪随机序列。

元素的操作

插入操作：根据散列函数算出初始散列地址，若发生冲突，就“探测”下一个地址，直到找到一个空闲地址，即可插入元素
查找：根据散列函数算出初始散列地址，对比关键字。若关键字不匹配，就“探测”下一个地址，直到关键字匹配(成功)或探测到一个空位置(失败)
删除操作：在开放地址的情形下，不能简单地把被删除结点置为空，否则会截断其他具有相同散列地址的元素的查找地址。因此要删除一个元素时，可以给它做一个删除标记，进行逻辑删除。但这样做的副作用是：执行多次删除后，表面上看起来散列表很满，但实际上有许多位置没有利用，因此需要定期维护散列表，把删除标记的元素物理删除

Example

例题：散列表长度为13，散列函数 $H (k ey) = k ey %13$ ，依次插入关键字 $19, 14, 23, 1, 68, 20, 84, 27, 55, 11, 10, 79$ ，采用线性探测法解决冲突，构造散列表。

13的倍数有：13,26,39,52,65,78,91

因此各个关键字的散列函数值如下

| 关键字 | 19 | 14 | 23 | 1 | 68 | 20 | 84 | 27 | 55 | 11 | 10 | 79 |

|:----------:|:---:|:---:|:---:|:---:|:---:|:---:|:---:|:---:|:---:|:---:|:---:|:---:|

| 散列函数值 | 6 | 1 | 10 | 1 | 3 | 7 | 6 | 1 | 3 | 11 | 10 | 1 |

| 查找长度 | 1 | 1 | 1 | 2 | 1 | 1 | 3 | 4 | 3 | 1 | 3 | 9 |

所以构造的散列表如下：

 

\newcommand{\drawMyVar}[2]{

\pgfmathsetmacro{\myvar}{#1}

\def\keys{#2}

\foreach \num [count=\i] in \keys {

  \pgfmathtruncatemacro{\idx}{\i-1};%整数结果

  \ifnum\num=-1

  	\node[draw=black] at (\idx,\myvar*2) { };

  \else

  	\node[fill=gray!20, draw=black] at (\idx,\myvar*2) {\num};

\fi

  \node[font=\Large] at(\idx,\myvar*2-0.8) (\idx){\idx};

}

\begin{document}

\begin{tikzpicture}[scale=1.5, ultra thick]

\tikzstyle{every node}=[font=\huge, very thick, rectangle, minimum width=1.2cm, minimum height=1.2cm]

  \drawMyVar{0}{-1,14,1,68,27,55,19,20,84,79,23,11,10,-1,-1,-1}

\end{tikzpicture}

\end{document}

$A S L_{成功} = \frac{1}{12} (1 + 1 + 1 + 2 + 1 + 1 + 3 + 4 + 3 + 1 + 3 + 9) = \frac{30}{12} = 2.5$

$A S L_{失败} = \frac{1}{13} (1 + 13 + 12 + 11 + 10 + 9 + 8 + 7 + 6 + 5 + 4 + 3 + 2) = \frac{91}{13} = 7$

拉链法

LeetCode705. 设计哈希集合

拉链法演示

处理冲突的方法_拉链法.pdf

对于不同的关键字通过散列函数映射到同一地址时，为了与避免非同义词发生冲突，可以把所有的同义词存储到一个线性链表中。拉链法适用于经常进行插入和删除的方法。

Example

例：散列表长度为13，散列函数 $H (k ey) = k ey %13$ ，依次插入关键字 $19, 14, 23, 1, 68, 20, 84, 27, 55, 11, 10, 79$ ，采用拉链法解决冲突

13的倍数有：13,26,39,52,65,78,91

因此各个关键字的散列函数值如下

| 关键字 | 19 | 14 | 23 | 1 | 68 | 20 | 84 | 27 | 55 | 11 | 10 | 79 |

|:----------:|:---:|:---:|:---:|:---:|:---:|:---:|:---:|:---:|:---:|:---:|:---:|:---:|

| 散列函数值 | 6 | 1 | 10 | 1 | 3 | 7 | 6 | 1 | 3 | 11 | 10 | 1 |

| 查找长度 | 1 | 1 | 1 | 2 | 1 | 1 | 2 | 3 | 2 | 1 | 2 | 4 |

所以构造的散列表如下：

 

\usetikzlibrary{positioning}

\newcommand{\drawMyVar}[2]{

\pgfmathsetmacro{\myvar}{#1}

\def\keys{#2}

\foreach \num [count=\i] in \keys {

  \node[fill=gray!20, minimum width=3em, minimum height=3em] at(\myvar,-\i*1.5) (\myvar-\i){\num};

  \pgfmathtruncatemacro{\pre}{\i-1}

  \draw[-latex] (\myvar-\pre) -- (\myvar-\i);

}

\begin{document}

\begin{tikzpicture}[scale=1.5, ultra thick]

\tikzstyle{every node}=[font=\huge, draw=black, very thick, rectangle, minimum width=1.2cm, minimum height=1.2cm]

  \def\myChar{null, ,null, ,null,null, , ,null,null, , ,null}

  \foreach \char [count=\i] in \myChar {

  	\pgfmathtruncatemacro{\idx}{\i-1};%整数结果

  	\node[font=\Large] at (\idx,0) (\idx-0){\char};

  	\node[font=\large, draw=none, above = -1em of \idx-0] {\idx};

  \drawMyVar{1}{79,27,1,14};

  \drawMyVar{3}{55,68};

  \drawMyVar{6}{84,19};

  \drawMyVar{7}{20};

  \drawMyVar{10}{10,23};

  \drawMyVar{11}{11};

\end{tikzpicture}

\end{document}

$A S L_{成功} = \frac{1}{12} (1 \times 6 + 2 \times 4 + 3 \times 1 + 4 \times 1) = 1.75$

$A S L_{失败} = \frac{1}{13} (0 + 4 + 0 + 2 + 0 + 0 + 2 + 1 + 0 + 0 + 2 + 1 + 0) = \frac{12}{13}$

插入操作：根据散列函数计算新元素的散列地址，将新元素插入到散列地址对应的链表(头插法、尾插法)
查找操作：根据散列函数计算目标元素的散列地址，顺序查找散列地址对应的链表，直到查找成功或失败
- 分析查找长度时，通常只统计关键字对比次数，而不计入空指针对比次数
- 在插入新元素时，保持关键字有序，可微微提高查找效率
删除操作：根据散列函数计算目标元素的散列地址，顺序查找散列地址对应的链表，若查找成功则将目标元素从链表中删除

再散列法

当通过第一个散列函数 $H (k ey)$ 得到的地址发生冲突时，则利用下一个散列函数再次计算该关键字的地址，直到不冲突为止。其散列函数为： $H_{i} = R H_{i} (k ey)$

7.5.4. 散列查找及性能分析

散列查找执行步骤如下：

①初始化：根据散列函数 $A dd r = H a s h (k ey)$ 计算目标元素存储地址
②检测查找表中地址为 Addr 的位置上是否有记录，若无记录，返回查找失败；若有记录，比较它和 key 的值，若相等则返回查找成功，否则执行步骤③。
③用给定的处理冲突方式计算“下一个散列表地址”，并把 Addr 置为此地址，转入步骤②。

平均查找长度（ASL）

散列表查找成功的平均查找长度即找到表中已有表项的平均比较次数；
散列表查找失败的平均查找长度即找不到待查的表项但能找到插入位置的平均比较次数。（装填因子）
装填因子：一般记为 $α$ ，即一个表的装满程度。 $α = \frac{表中记录数 n}{散列表长度 m}$

Example

例：现有长度为11且初始为空的散列表HT，散列函数 H(key)=key%7 ，采用线性探测法解决冲突。将关键字序列87，40，30，6，11，22，98，20 ，38依次插入HT后，HT的查找失败的平均长度是多少？查找成功的平均查找长度又是多少？

答：关键字序列依次插入后，散列表HT如下所示：

| 散列地址 | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |

| :------: | :—: | :—: | :—: | :—: | :—: | :—: | :—: | :—: | :—: | :—: | :—: |

| 关键字 | 98 | 22 | 30 | 87 | 11 | 40 | 6 | 20 | 38 | | |

| 冲突次数 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 1 | 5 | | |

$A S L_{查找成功} = (1 + 1 + 1 + 1 + 1 + 1 + 1 + 2 + 6) /9 = 5/3$

$A S L_{查找失败} = (10 + 9 + 8 + 7 + 6 + 5 + 4) /7 = 7$ （需要查找到空位置为止）

7.5.5 本节习题精选

选择题：题目、答案

综合题：题目、答案

易错

注意区分折半查找判定树和平衡二叉树
找机会汇总一下各种树，对比一下

我的 Obsidian 知识库

探索

第7章 查找

7.1 基本概念

7.2 顺序查找和折半查找

7.2.1. 顺序查找

顺序查找

顺序查找 - 哨兵方式

顺序查找优化 - 元素有序

顺序查找优化 - 被查概率不等

7.2.2. 折半查找

折半查找

折半查找判定树

7.2.3. 分块查找

7.2.4 本节习题精选

7.3 树型查找

7.3.1 二叉排序树(BST)

二叉排序树的查找

二叉排序树的插入

二叉排序树的构造

二叉排序树的删除

二叉排序树查找效率分析

7.3.2 平衡二叉树(AVL)

平衡二叉树的插入

平衡二叉树的查找与效率分析

平衡二叉树的删除

7.3.3. 红黑树(RBT)

红黑树的概念与性质

红黑树的插入

红黑树的删除

7.3.4 本节习题精选

7.4 B树、B+树

7.4.1. B树

7.4.2. B树的基本操作

B树的查找

B树的插入

B树的删除

7.4.3. B+树

7.4.4 本节习题精选

7.5. 散列查找及其性能分析

7.5.1. 散列表的基本概念

7.5.2. 散列函数的构造方法

7.5.3. 处理冲突的方法

开放定址法

拉链法

再散列法

7.5.4. 散列查找及性能分析

7.5.5 本节习题精选

易错

关系图谱

目录

反向链接

第7章查找