查找
- 静态查找：集合中记录是固定的，没有插入和删除操作，只有查找
- 方法1：顺序查找；时间复杂度为O(n)。
- 方法2：二分查找；时间复杂度O(logN)——可采用递归实现
- 动态查找：集合中记录是动态变化的，除查找，还可能发生插入和删除
树的定义
基本定义
- 子树是不相交的；
- 除了根结点外，每个结点有且仅有一个父结点；
- 一棵N个结点的树有N-1条边。
树的基本术语
- 基本术语
- 父结点（Parent）
- 子结点（Child）
- 兄弟结点（Sibling）
- 路径和路径长度
- 祖先结点(Ancestor)
- 子孙结点(Descendant)
- 结点的层次（Level）
- 树的深度（Depth）
- 结点的度（Degree）：结点的子树个数
- 树的度：树的所有结点中最大的度数
- 叶结点（Leaf）：度为0的结点
树的表示
链表表示法
- 将全部子结点都存入父结点点结构体中
- 缺点：子结点个数不一，难以形成统一的结构体，若以最大结点数，为统一结构体的结点数，又太浪费空间
儿子-兄弟表示法（转化为二叉树）
结构体中仅存两个结点，一个是兄弟结点，一个是“长子”结点。
二叉树
特殊二叉树
- 斜二叉树：一种另类链表
- 完美二叉树（满二叉树）：完全对称，除了叶结点，每个结点都有两个儿子
- 完全二叉树：完美二叉树有最底层缺少右侧缺少一部分，而且左侧必须连续
几个重要性质
一个二叉树第 i 层的最大结点数为：2^(i-1)，i >= 1。
对任何非空二叉树 T，若n0表示叶结点的个数、n2是度为2的非叶结点个数，那么两者满足关系n0= n2+1。
深度为k的二叉树有最大结点总数为： (2^k)-1，k >= 1。
存储结构
顺序存储结构
- 用完全二叉树存，结点序号即为数组下标。
- 一般二叉树，可采用伪完全二叉树存，即留空位，但浪费空间。
链表存储：略
遍历方法
可采用递归实现，不同的方法read的位置不同
- 先序——根、左子树、右子树；
- 中序—左子树、根、右子树；
- 后序—左子树、右子树、根；
- 层次遍历，从上到下、从左到右
二叉搜索树
查找
寻找特定值：二分法
寻找最大、最小值：
- 最大元素一定是在树的最右分枝的端结点上
- 最小元素一定是在树的最左分枝的端结点上
插入
寻找到到对应的空位，直接插入——类查找
删除
情况一：叶节点，直接删
情况二：单子结点，子结点代替
情况三：双子结点，用另一结点替代被删除结点：右子树的最小元素或者 左子树的最大元素
平衡二叉树（AVL树）
概念
平衡因子：左、右子树的高度差。
平衡二叉树：空树，平衡因子≤ 1
平衡二叉树的高度：(log2n)。
调整
RR 旋转
LL 旋转
LR 旋转
RL 旋转
“3+4”重构
调整的最终结果就是三个节点，四个子树
直接把调整结果付给这个模板就可以了，不需要乱七八糟的过程
堆（Heap）
概念
优先队列（Priority Queue）：取出元素的顺序是依照元素的关键字的大小
优势特点：
- 表的效率比树低；
- 二叉树多次删除后会单边倾斜；
两个特性
结构性：用数组表示的完全二叉树；
有序性：任一结点是其子树所有结点的最大值（最大堆）或最小值（最小堆）
堆的操作
堆的插入：从最后面开始，逐级比较；直到找到合适的位置；比不过的下沉一级
堆的删除：删除最顶端的，用最后面的元素替换；然后逐级比较；直到找到合适的位置；比过的位置交替
堆的创建：一个个插效率太低，可以先按输入顺序输入完全二叉树，然后调整位置实现有序性，从倒数第二层开始按层次调；逐级向上；每次只考虑当前结点及其子结点。
哈夫曼树（Huffman Tree）
概念
带权路径长度(WPL)：每个叶子结点带有权值 Wk，从根结点到每个叶子结点的长度为Lk，则WPL等于所有叶节点Wk*Lk的和；
最优二叉树或哈夫曼树: WPL最小的二叉树
构造与实现
构造
两个权值最小合并构成一个结点，父结点的权值为为两个子结点的和；
父结点再次进入排序；最终构成了一个树。
排序的实现
用最小堆排序，删除两结点，合并成新节点，插入堆，重复n（叶节点数为n）次。
特点
没有度为1的结点
n个叶子结点的哈夫曼树共有2n-1个结点
哈夫曼树的任意非叶节点的左右子树交换后仍是哈夫曼树
对同一组权值，存在不同构的两棵哈夫曼树
哈夫曼编码
- 目的：节省编码的空间
- 根据字符出现的频率设置字符权重，
- 为了避免二义性，所有的字符都在叶节点上
集合
概念
并查集：集合并；查某元素属于什么集合
用树结构表示集合，树的每个子结点代表一个集合元素
用数组存储：每个元素有data，parent构成，parent为负数表示根结点；为非负数表示双亲结点的下标。
集合的运算
查找：在数组中找x;通过x向上遍历，找到根节点
并：
找到两个集合的树根；把其中一个树根的parent设置为另一个树根的下标。即把一个集合挂到另一个集合上。
为了改善合并以后的查找性能，可以采用小的集合合并到相对大的集合中。
- 为体现集合的大小，修改根节点的parent的表示规则。根节点的parent如果为-3。表示集合有3个元素。
伸展树
动机
局部性：把刚访问的放在树根，方便下次访问
意外收获：动态自平衡性
意外收获：常访问的会堆积在树根
实现思路
尝试：逐层调整，无平衡性，效率低，尝试失败
双层伸展（可用）：
子孙异侧：RL旋转或LR旋转
子孙同侧：祖父与父先调整，父与子再调整
- 在顶层若无祖父
分析
单层在找到最高层时没有消层的作用，双层在做每一次比较时，如果最高层是自己的子树，会自动消去一层。
B树
概念
- B树意义：扩大子树范围，减少树的层数，以符合存储器读写要求
- 结点：称为超级结点，每个结点可以视为一颗二叉树，有2^d分支，和2^d-1个关键码
- 阶数m：m阶B树，即为m路平衡搜索树，
- 外部结点：与叶节点一一对应，所有叶结点都在最后一层上
- 高度：一般的树不同，B树的高度对应的是外部结点的深度
- 实际分支数n：
- 上限：m-1
- 下限：树根：2<=n+1，其余m/2<=n+1
- 因故称为（m/2，m）树
插入
找到位置插入
若溢出，则以中位数为父，分裂，分裂出来的父关键字放入上一层
若仍溢出，则再分裂，直到不溢出，或者到达根
若根溢出，则根分裂，树增高，形成新根
删除
- 找到改关键字
- 若非叶结点，则被删点的右子树的最左结点的第一个关键字进行替换，然后删除
- 若发生下溢，则先尝试旋转，旋转不成，再合并
- 旋转,向兄弟借结点，借来的放父，父下来合并
- 合并，兄弟，父，自己三个合并，同分裂
红黑树
动机
快速插入或删除（log n级别）
定义
树根：必为黑色
外部结点：均为黑色
其余节点：若为红，则只能有黑孩子
外部节点到根：途中黑色节点数目相等
红黑树=4阶B树
将所有红节点，与其父结点构成一个超级节点
红黑树的高度h，h<=2H（H为B树的高度，同时也为黑节点的高度）
插入
插入的节点默认是红节点
找到插入的位置，将该节点插入，若该节点的父节点为黑，红黑树性质继续保持，操作完成。
若父节点为红色，则红黑树性质被破坏，需要进行调整。
- case 1：当叔父节点为红时，执行B树上溢出缺陷即可
- case 2：叔父节点为黑，交换一下中间和旁边的颜色
- case 1：当叔父节点为红时，执行B树上溢出缺陷即可
删除
概念
最多做O（log n）重染色、一次“3+4”重构，一次单旋
可较好实现持久性（保存历史状态）
思路：
- 是不是真“兄弟”，不是就自己找一个真兄弟
- 是真“兄弟”，“兄弟”有没有钱
- “兄弟”有没有钱，爸爸没有钱
执行过程
执行BST常规算法：在被删节点x的子树找一个节点r替代x
Case 1：黑s有红子t（兄弟有钱可借，旋转）
- Case 2：黑s无红子t，红p（兄弟没钱，爸爸有钱，不会下溢，单次合并)
Case 3：黑s无红子t，黑p（兄弟没钱，爸爸也没钱，会下溢，多次合并）
Case 4：红s
- 解析：假兄弟，真“叔叔”
- 做法：“叔叔”和爸爸换颜色，变为Case 2
总结
