数据结构与算法

Published: 10/1/2023

线性表

栈

队列

树

Trie树

Trie树是一种字符串前缀树，主要用于字符串匹配，其根节点一般为空，其余每个节点持有一个字符，从根节点到每个节点的路径构成一个字符串，每个节点同时持有一个布尔值，表示是否为一个单词的结尾，不同字符串可共享相同前缀存储，从最后相同字符开始分叉。Trie树的优点在于其查找、插入、删除等操作的时间复杂度为O(k)，其中k为字符串长度。

二叉搜索树

递归定义：二叉搜索树BST是一颗二叉树，若非空，则满足每个节点都有一个关键字，左子树的关键字小于根节点的关键字；右子树的关键字都大于根节点的关键字。（若存在等于的情况则为有重复值的二叉搜索树）BST使用中序遍历即可获得树的整个排名。

索引二叉搜索树IBST则在BST的基础上在每个节点增加了leftSize域，表示左子树节点个数。目的是为了实现能够按照名词以O(logn)的复杂度快速搜索（从而不需要遍历整个树）。按名次rank查找时只需比较每个节点leftSize，无外乎三种情况:

rank == leftSize: 找到目标
rank < leftSize : 目标在左子树中，在左子树中搜索
rank > leftSize : 目标在右子树中，将rank减去leftSize+1，在右子树中搜索

BST的ADT如下:

find(k): 返回关键字为k的数对

根据关键字进行比较，若该节点关键字为k则返回，小于k则查找右子树，否则查找左子树

insert(p): 插入数对p

进行查找，若存在对应关键字的节点，则使用新节点的值替换该节点。若不存在，则根据关键字大小作为搜索中断节点的左孩子或右孩子。

erase(k): 删除关键字为k的数对
ascend(): 升序输出所有数对

使用中序遍历即可。

IBST在BST的ADT上增加了如下内容：

get(index): 得到第index个数对

平衡树

平衡树在BST的基础上保持树高度总为O(logn)来确保查找，插入与删除复杂度总为O(logn)。一种流行的平衡树为AVL(Adelson-Velskii与Landis取其首字母)。

AVL定义:非空情况下对于树 $T$ ，其 $T_{L}$ 与 $T_{R}$ 为其左子树， $T$ 为AVL树 iff

$T_{L}$ 与 $T_{R}$ 为AVL树
$∣ h_{L} - h_{R} ∣ \leq 1$ ，其中 $h_{L}$ 与 $h_{R}$ 分别为 $T_{L}$ 与 $T_{R}$ 的高度

红黑树

红黑树是一种自平衡二叉搜索树，

m-叉搜索树

一种m阶多叉树，满足：

每个内部节点最多有m个子节点，m-1个元素
每个含有p个元素的节点都有p+1个子节点
每个节点以其中元素进行分割，子节点中的所有元素都位于该节点对应两元素区间内

数据结构与算法

线性表

栈

队列

树

Trie树

二叉搜索树

平衡树

红黑树

m-叉搜索树

B-树

B+树

图

回溯

动态规划

贪心