AVL
- 是一棵高度平衡的二叉搜索树, 解决了二叉搜索树退化成链表的问题
- 其性质是, \(BF(balance factor)=左右子树高度差\leq 1\)
- 用f(d)代表深度为d的AVL树的最少节点数,易知:
f(-1)=0,f(0)=1,有递归公式:\(f(d) = f(d-1)+f(d-2)+1\) - 对于高度为h(h = d + 1)的AVL树，其节点数最少为Fibonacci数列中第h+2项减1。
- 1, 2, 4, 7, 12, 20...
-
1, 1, 2, 3, 5, 8, 13...
-
主要用到的操作是旋转
- 参考资料:
splay
- 本质也是一种二叉搜索树
- 为了提高搜索树搜索某些高频率条目的效率, 会在每次查找之后把查找的元素放在根部
- 按照一般搜索树的规则插入元素, 插入之后还要执行splaying操作
- 优势在于不需要记录用于平衡树的冗余信息
均摊分析
- 有势能函数
- 均摊成本 = 实际成本 + 势能变化
这一块深入下去可以很难, 这里不做深究
B树, B+树
- 区别而就是B+树的非叶节点存放的是索引, key都在叶子节点, 而B树的每个节点都是一个key
- 最重要的操作是上溢, 即节点达到了他的阶(order)后将节点拆分, 并且把中间的key向上pop
红黑树
红黑树和AVL树都是高效的平衡二叉树，增删查改的时间复杂度都是\(O(logN)\)，但红黑树和AVL树控制二叉树平衡的方式不同：
- AVL树是通过控制左右高度差不超过1来实现二叉树平衡的，实现的是二叉树的严格平衡。
- 红黑树是通过控制结点的颜色，从而使得红黑树当中最长可能路径不超过最短可能路径的2倍，实现的是近似平衡。
相对于AVL树来说，红黑树降低了插入结点时需要进行的旋转的次数，所以在经常进行增删的结构中性能比AVL树更优，实际运用时也大多用的是红黑树
基本性质: 根节点必须为黑色, 红色节点的父和子必须是黑色, 任何节点到其后代所有叶的简单路径都必须有包含相同数目的黑色节点
- 注意: 从根结点一直走到空位置就算一条路径，而不是从根结点走到左右结点均为空的叶子结点时才算一条路径。
参考资料:
- 
- 红黑树（C++实现）
- 数据结构 - 学习笔记 - 红黑树前传——234树_234树和红黑树_笑虾的博客-CSDN博客
赫夫曼树和赫夫曼编码
每次取频率最小的两个点合并为一个点, 递归得到一个赫夫曼树
从赫夫曼树的root开始, 找到每一个待编码的点
编码规则为:
- 走左路为0走右路为1
- 如: 从根节点开始, 先走左再走右再走右, 编码为
011
左堆, 斜堆
npl: null path length, 到不满节点的最短路径长度
为了解决二叉搜索树的合并操作困难问题, 有以下几点性质:
- npl=子节点最小npl+1
- 左npl >= 右npl
- null节点的npl为-1, 因此叶子节点的npl为0
合并规则:
- 大进小右, 是一个递归调用的过程
- 若合并的过程中不满足性质2, 则左右互换(斜堆则没有npl, 无论如何都要交换左右儿子)
参考资料:
- https://blog.csdn.net/changyuanchn/article/details/14647297
二项队列
有点类似二进制数
一般考查*DeleteMin操作
回溯
- 可能会考$\alpha -\beta $剪枝, 感觉不是很难, 不理解可以看看这个Alpha-Beta剪枝算法（人工智能）_哔哩哔哩_bilibili
分治
一图以蔽之:
NP问题
来自bing的搜索结果:
NP问题是指能在多项式时间内验证得出一个正确解的问题，例如旅行商问题，哈密顿回路问题等。NP问题和P问题的关系是，P问题是NP问题的子集，即所有能在多项式时间内解决的问题，也能在多项式时间内验证。但是是否存在一个多项式时间的算法，能够解决所有的NP问题，这是一个未解决的千年难题3。为了研究这个难题，科学家引入了NP完全问题和NP难问题的概念。NP完全问题是指满足两个条件的NP问题：一是它本身是一个NP问题；二是所有的NP问题都可以在多项式时间内约化到它。约化的意思是，如果能用一个问题B的算法来解决一个问题A，那么就说A可以约化到B。如果存在一个NP完全问题有多项式时间的算法，那么就证明了P=NP。NP难问题是指满足第二个条件但不一定满足第一个条件的问题，即所有的NP问题都可以约化到它，但它不一定是一个NP问题。NP难问题比NP完全问题更广泛，也更难解决。