树
树的表示方法
通过在连续的存储空间中标注每个节点的父节点，兄弟节点，子节点等，来达到索引的目的
双亲表示法
在每个节点后面指明父节点所在位置（结构体就可以表示）
孩子表示法
在每个节点后面链接上子节点的下表（数组+链表来表示）
双亲孩子表示法
以上两种方式的结合，每个节点后面既指明父节点的位置，也同时链接上各个子节点
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16#define MAX_TREE_SIZE 50
typedef CTNode{
int index;
CTNode *next ;
}NodePtr;
typedef struct{
ElementType elem ;
int parent_index ;
NodePtr *firstChild ;
}CTBox;
typedef struct{
CTBox nodes[MAX_TREE_SIZE]
}CTree;
二叉树
二叉树，顾名思义，最多有两个子节点。在递归定义的情况下，它有五种形态：空二叉树，只有根节点，只有左子树，只有右子树，左右子树都有。
比如说，对于一棵二叉树，有三个节点，那它有几种情况呢？答案是五种！
特殊二叉树
斜二叉树（斜成一条线），满二叉树（最圆满的情况），完全二叉树（最后一层最右边的节点从右往左缺失）
二叉树性质
二叉树的第i层最多有2^(i-1)个节点 （化作等比数列，二叉树的第i层相当于数列的第i-1项）
深度为k的二叉树至多有2^k-1个节点
任何一棵二叉树，如果其叶子节点数为n0，度为二的节点数为n2,则n0 = n2 + 1
推导：设总结点数为n,度为1的节点数为n1,n=n0+n1+n2,树枝数目为n-1=n1+2*n2,结合这两个公式有n0=n2+1
具有n个节点的完全二叉树的深度是$$ \lfloor \log n \rfloor+1$$
推导：设该二叉树深度为k,则它的节点数量位于深度为k-1和深度为k的满二叉树中间，即有
$ 2^{k-1} -1 < n \leq2^{k}-1$ 化简得 $k-1\leq \log n<k$ 所以有$k=\lfloor \log n\rfloor+1$
- 如果一棵有n个节点的完全二叉树其节点按层序编号，对任一节点i(1<=i<=n)有如下性质
- 如果i=1,则i是根节点
- 如果2i>n,则i没有左孩子，否则其左孩子是2i
- 如果2i+1>n,则i没有右孩子，否则其右孩子是2i+1
二叉树存储结构
数组或者链表，用数组存储的话遇到极端情况（如斜树）比较浪费空间，所以一般用链表来存储
1
2
3
4
5typedef BiNode{
ElemType elem;
BiNode *lchild ;
Binode *rchild ;
}BiTree二叉树的遍历
前序遍历
根，左，右
中序遍历
左，根，右
后序遍历
左，右，根
层序遍历
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37//define bitree
typedef struct BiTree{
char data ;
struct BiTree * lchild ;
struct BiTree * rchild ;
}BiTree;
//create bitree
void createBiTree(BiTree* &T){
char c ;
//cin >> c ;
if(' '==(c=getchar()))
T = NULL;
else{
T = new BiTree ;
T -> data = c ;
createBiTree(T->lchild) ;
createBiTree(T->rchild) ;
}
}
void visit(BiTree* T,int level){
cout << "node " << T-> data << " in level " << level << endl ;
}
//traverse bitree
void preOrderTraverse(BiTree* T,int level){
if(T){
visit(T,level) ;
preOrderTraverse(T->lchild,level+1) ;
preOrderTraverse(T -> rchild,level+1) ;
}
}
Huffman Tree
背景
有n个带权重的叶子节点，我们想构造一棵二叉树，使得带权路径长度最小
方法
不断的将两棵权值最小的树合并成一棵更大的树，新树的根节点权值为之前两棵树的根节点权值之和。
Huffman Code
综合考虑，我们认为Huffman Tree中每一个节点都有权值（其中非叶子节点权值为0），左右孩子。且哈夫曼树的节点要么为0要么为2，没有度为1的节点，则有n个叶子节点的哈夫曼树共有2n-1个节点（这点可由二叉树性质推出），我们考虑将其存储在长度为2n的一维数组中（选择长度为2n而不是2n-1是为了下边从1开始计算）
存储结构
1
2
3
4typedef struct{
unsigned int weight ;
unsigned int parent,lchild,rchild ; //这里我们存储的都是下标
}HTNode,*HuffmanCode哈夫曼编码主要分为一下几个步骤：
初始化
初始化时给叶子节点权重，非叶子节点权重为0（也就是第一行和第二行for循环的意思）
构建哈夫曼树
构建时我们就从前面n个叶子节点找到权值最小的两个，将他俩合并成一个新的节点，放在n+1的位置，以此类推（对应第三个for循环）
求哈夫曼编码
求哈夫曼编码就是从根节点到叶子节点游走下去，如果是左孩子则编码为0，如果是右孩子，则编码为1，然后将编码以此存入相应数组里。但是，如果从根节点开始寻找，那么我们必须遍历这棵树，这是很麻烦的，我们可以考虑从叶子节点回溯到根节点，对于每个节点，从结构体我们可以知道它是有指向父节点的指针的，那我们就从叶子节点开始回溯，如果当前节点是父节点的左孩子，则当前编码为0，如果是右孩子，则编码为1，同时我们设置一个数组cd[…]来存储编码，因为是从叶子到根节点这样回溯的，所以我们得到的编码肯定是反着的，所以如果我们把这个编码从数组cd的的屁股开始放，就可以解决这个问题了。
图
关键路径
在AOE网（Activity On Edge）中，弧表示活动，顶点表示事件，权值表示活动持续时间，它是一个有向无环图。通常情况下，AOE网可以用来估算工程的完成时间。它的两个主要问题是：
1. 完成整项工程需要多长时间
2. 哪些活动是影响工程进度的关键
对于第一个问题，完成整项工程的需要多长时间，我们只需要考虑完成它所需要的最短时间即可。对于一个有向无环图所表示的工程来说，完成工程的最短时间是从开始点到结束点的最长路径的长度，我们把这个最长路径叫做关键路径（这里有人可能会疑问为什么不是最短路径的长度，你想，如果是在最短路径长度所表示的时间内就能完成工程，那么那些耗时较长的工序咋整，假设最长长度是8，最短是5，如果有个工序需要在时间为6时进行，如果选择5作为完成工程的最短时间，那这个工序岂不是没有时间进行了）
对于第二个问题，哪些活动是影响工程进度的关键，我们引入下图来说明问题，因为途中有些活动是并行进行的，所以有些顶点事件的开始时间其实是不唯一的，拿v5来说，v1 -> v2 -> v5 这条路径执行的话，v5要到7这个时间点才能执行，按照v1 -> v3 -> v5 这条路径执行的话，到5这个时间点就可以执行了，那么问题来了，v5处的事件真的能在时间为5时执行么，答案是不能！如果此时执行的话，时间为5时v2还没有被执行，v5的先决条件还不满足呢，这也是我们上述中最短时间为什么选的是最长路径的原因。这里我们提出事件的最早开始时间ei这一概念
事件Vi的最早开始时间就是从V1到Vi的最长距离。最早开始时间，顾名思义就是这个事件最早能被执行的时间，上述的V5的最早开始时间就是7，也就是说V7不能比时间7更早执行了，不然它的先决事件没有被执行完。也即V5的执行时间应该大于等于7，那是不是可以无限大呢？显然是不能的，因为无限延迟肯定会延误工期啊，所以V5的执行时间再怎么延迟，也要在工期（也就是我们说的项目的最短时间即关键路径）结束前走到V9啊。因此我们又提出了最迟开始时间li，顾名思义也就是这个开始时间的选择很精准，刚好到工期结束，它也刚好走到V9.
拿上图来分析，这里我们以知从v1到v9的最长路径是（v1,v2,v5,v8,v9）,路径长度18，即v9的最早发生时间是18.我们来看活动a6(注意这里看的是活动不是事件哦),它的最早开始时间是5（从v1到v4）,最晚开始时间是8，怎么算的呢，总长是18，它如果要赶在刚好工期结束的时候赶到v9,那它应该从时间 18-a11-a9-a6 = 8 处开始，这样工期结束时就刚好赶到v9。
上述我们计算了时间的最早开始时间和最迟开始时间，你会发现，在l-e之间有个差值，这个差值表示我们工期可以延迟的一个幅度，那么就一种特殊情况，差值为零，它表示这个活动一秒钟都延期不得，不然会影响整个工期进度，我们把这种活动叫做关键活动。
排序
插入排序
插入排序的核心思想：认为最初的一个元素是有序的，
然后从第二个元素往后，开始和已经有序的元素进行逆向比较，
如果比有序的倒数第一个元素大是最好的，这种情况下不用移动有序元素可以直接插入末尾
否则就是把有序部分向后移动，直到遇见某个元素，它刚好小于我们的待比较元素，
查找
二叉排序树
左孩子比父亲小，右孩子比父亲大。正常情况，用n个节点随机构造的二叉排序树，高度为log(n),所以查找的时间复杂度也是log(n)，没问题。但怕就怕在这个二叉排序树走极端，万一它只有左孩子或者只有右孩子，那么它就会变成个链表，这时候查找的时间复杂度就变成了n了。
所以，为了避免上述情况的发生，我们需要薛微制裁一下二叉排序树，使它不要偏科严重，于是就有了平衡二叉树。
平衡二叉树（AVL树）
因为二叉排序树偏科严重，所以我们教会了AVL树雨露均沾，在保证二叉排序树的特点上，我们又要求AVL树左右子树高度差不能超过1，这样一来，整棵树就显得很均衡了。每当插入或者删除节点使得树失衡的时候，我们都要通过旋转去调节。
但是！虽然它很严格的平衡了，但是每次这种调节确实很费时的，这对于频繁的删除和插入的场景来说，并不是个好消息。所以人们又想，能不能弱化一下它的平衡，让它可以偏科，但是不要太严重就行，于是，就有了红黑树。
红黑树
红黑树的定义是这样的：
- 每个节点要么红要么黑
- 根节点是黑色的
- 每个叶节点都是空节点，是黑的
- 如果一个节点是红的，那么它的两个儿子是黑的
- 对于每个节点，到叶子节点的任意一条路径上，黑色节点数目都一样多
它的查找，插入，删除时间复杂度为O(log n),它的统计性能比AVL数更好。
插入
插入只能是插入红色节点，因为插入黑节点，违背性质五，需要大规模调整。
- 插入的节点是根节点
直接涂黑
- 插入的节点的父亲是黑节点
没毛病，直接插
父亲是红节点
现象说明 处理策略 Case 1 当前节点的父节点是红色，且当前节点的祖父节点的另一个子节点（叔叔节点）也是红色。 (01) 将“父节点”设为黑色。 (02) 将“叔叔节点”设为黑色。 (03) 将“祖父节点”设为“红色”。 (04) 将“祖父节点”设为“当前节点”(红色节点)；即，之后继续对“当前节点”进行操作。 Case 2 当前节点的父节点是红色，叔叔节点是黑色，且当前节点是其父节点的右孩子 (01) 将“父节点”作为“新的当前节点”。 (02) 以“新的当前节点”为支点进行左旋。 Case 3 当前节点的父节点是红色，叔叔节点是黑色，且当前节点是其父节点的左孩子 (01) 将“父节点”设为“黑色”。 (02) 将“祖父节点”设为“红色”。 (03) 以“祖父节点”为支点进行右旋。 叔叔是红色
- 叔叔是黑色，当前是右孩子
处理策略：
将“父节点”作为“新的当前节点”；
以“新的当前节点”为支点进行左旋。
- 叔叔是黑色，当前是左孩子
处理策略
(01) 将“父节点”设为“黑色”。
(02) 将“祖父节点”设为“红色”。
(03) 以“祖父节点”为支点进行右旋。
删除
普通二叉树的删除规则：
1、如果删除的是叶节点，可以直接删除；
2、如果被删除的元素有一个子节点，可以将子节点直接移到被删除元素的位置；
3、如果有两个子节点，这时候就可以把被删除元素的右支的最小节点（被删除元素右支的最左边的节点）和被删除元素互换，我们把被删除元素右支的最左边的节点称之为后继节点（后继元素），然后在根据情况1或者情况2进行操作。
对于红黑树的删除，首先要满足普通二叉树的删除规则，其次，删除还不能影响到上述的红黑树的五条特性。
大意就是：红色的，直接删；根节点，直接删；
这个我已经写不动了，有时间再写吧，
总结
总之，无论是插入还是删除，在满足普通二叉排序数的规则之上，还需要考虑配色问题，要使得颜色满足红黑树的定义。
感悟
为什么今天突然看这个呢，因为在看源码的时候渐渐发现除了HashMap, TreeMap也用到了红黑树去达到一个有序的Map的效果的，所以就看了下，虽然挺复杂的，我也没看完，但是大概懂它的工作原理以及设计哲学了，也是不错的收获啦，起码以后再看源码的时候碰到它就不会很陌生了。
参考文献：
