下面主要是我学习《算法导论》的笔记，发现之前的自己竟然能耐心学了那些证明，原来自己现在变弱了，汇总记录，好以后复习，也分享出来

二叉搜索树

1. 介绍

树中的每个结点X，他的左子树中所有项的值都小于X的值，右子树所有项的值都大于X的值

2. 插入

就像查找树中是否有X结点那样沿着树查找，如果找到X，则做一些 “更新” ，否则就将X插入到遍历的路径上的最后一点
注：对于重复圆的插入可以通过在节点中记录附加字段，以指示此数据出现的频率

浅色节点为插入的路径

//将k插入t树中
void insert(AVLnode *&t,int k)
{if(t==NULL) t=new AVLnode(null,null,k); //设置新节点的左右孩子null，值k的构造函数if(x< value(t)) insert(t->left);if(x< value(t)) insert(t->left);if(x==value(t)) do something
}

3. 删除

发现X结点为树叶，删除X
发现X结点有一个儿子，调整X父亲的链指向X的儿子，删除X
发现X结点有两个儿子，整X父亲的链指向X右子树最小元素（或左子树的最大元素），删除X，这时候就会变成第一种和第二种情况
注：当删除的次数不多时，可以使用懒惰搜索，被删除了的做一个标记

//删除t树的k
bool delete(AVLnode *&t,int k)
{if(t==NULL) return false;//设置新节点的左右孩子null，值k的构造函数if(x< value(t)) delete(t->left,k);if(x> value(t)) delete(t->right,k);if(x==value(t))  deletethis(t);}void deletethis(AVLnode *&t){1. X结点为树叶处理2. X结点有一个儿子处理3. X结点有两个儿子处理}

4. 二叉搜索树优化——随机二叉搜索树

普通版本二叉排序树

BST_Sort(A):
T <- φ
for i <- 1 to nTree_Insert(A[i],T)
Inorder_Tree_Search()

与快速排序是失散多年的兄弟，此处更新中

BST的上的操作和树的高度有很大关系，上面的普通版本构造树假如是n个结点一棵完全二叉树，这些操作最坏的运行时间为Θ(lgn)，而一旦这n个结点是一条线性链，那么同样得操作需要Θ(n)的最坏运行时间，而下面的随机构造的BST的期望高度为O(lgn)【下面证明】，因此基本操作的平均运行时间为Θ(lgn)，这就是为什么需要构造随机BST

Random_BST_Sort(A):均匀随机打乱ABST_Sort(A):

在这里随机选取一个根节点，而快速排序随机选择随机pivot，所以他们最好最坏期望的运行时间都一样

平衡二叉树

1. 介绍

首先说一下树旋转

在数据结构中，树旋转（英语：Tree rotation）是对二叉树的一种操作，不影响元素的顺序（可以理解为旋转操作前后，树的中序遍历结果是一致的，也就是说旋转过程中也始终受二叉搜索树的主要性质约束：右子节点比父节点大、左子节点比父节点小），但会改变树的结构，将一个节点上移、一个节点下移。树旋转会改变树的形状，因此常被用来将较小的子树下移、较大的子树上移，从而降低树的高度、提升许多树操作的效率。

在计算机科学中，AVL树是最早被发明的自平衡二叉查找树。在AVL树中，任一节点对应的两棵子树的最大高度差为1，因此它也被称为高度平衡树。查找、插入和删除在平均和最坏情况下的时间复杂度都是O(lgn)。增加和删除元素的操作则可能需要借由一次或多次树旋转，以实现树的重新平衡。

2. 旋转（重要基础，维护性质的操作）

AVL的插入就像二叉查找树一样，不过为了维护性质，AVL树需要依靠旋转来达到平衡
对一棵树进行旋转时，这棵树的根节点是被旋转的两棵子树的父节点，称为旋转时的根（英语：root）；如果节点在旋转后会成为新的父节点，则该节点为旋转时的转轴（英语：pivot），以下图表以四列表示四种情况，每行表示在该种情况下要进行的操作。在左左和右右的情况下，只需要进行一次旋转操作；在左右和右左的情况下，需要进行两次旋转操作。

注意：下面一开始的四幅图为插入或者删除导致失衡后的状态，三角形为高为h的树，C或者D树是插入或者删除这个节点所在的树，因为插入或者删除都需要从这个点开始向根的方向查找第一个失衡子树（下面的黄色点）

3. 插入

从插入点开始，需要从这个点开始向根的方向查找第一个失衡子树，然后以该失衡节点和他相邻的刚查过的两个节点构成调整子树，使之成为调整子树，使之成为新的平衡子树，当失衡的最小子树被调整成为平衡子树后，又是AVL

4. 删除

1. 查找：现在平衡二叉树中查找到关键字为k的节点q
2. 删除：删除q
   
3. 若删除的是节点q，则从节点q向根的方向查找第一个失衡子树，进行旋转调整

红黑树

1. 介绍

1. 每个节点要么是红色，要么是黑色
2. root和leaves(nil)都是黑色
3. 每一个红色结点有黑色父结点
4. x出发到所有叶子结点的路径都有相等black-height(x)
   black-height(x)：不包括x本身的黑色结点高度

2. 插入

变色-旋转

//color[x]表示x的颜色，root[x]表示X的根，P[x]表示X的父亲结点
RB_Insert(T,x)Tree_Insert(T,x)color[x]<-Redwhile(x!=root[T] and color[x]==red) //不是根结点，或者黑色不断循环{if(p[x]==left[p[p[x]]]) //case A{y=right[p[p[x]]]if(color[y]=red) case 1else if(x=right[p[x]]) case 2case 3}else //case B{上面所有的left与right互换}color[root[t]]<-red	}

下面是case A代码的三种情况

case 1
: 如果y是红色，插入的结点X，一开始与A冲突，然后变颜色把冲突传递给C，逐级上升

case 1

Z字型

case3

直线型,可以看出这是case2的结果，这也是为什么代码这么写的理由

循环的最大次数为lgn

3. 然后我们看一个例子

二叉堆

1. 介绍

二叉堆就是用数组实现的完全二叉树，所以它没有使用父指针或者子指针
①最大堆，除根外,任意父亲节点值≥儿子节点值(性质)，一般用于堆排序
②最小堆，除根外,任意父亲节点值≤儿子节点值(性质)，一般用于优先队列

完全二叉树只要一个数组就可以实现，而不需要链，也就是说如果树有n个结点，存在数组中的下标位为1~n，很容易模拟结点的上下移动：由于位置为j的父节点位置为⌊ j/2 ⌋ ，两个子节点的位置分别为2j，2j+1，比如14的父亲⌊ 2/2 ⌋=1 ，两个子节点 4 与 5
完全二叉树：除最底层外，该树完全充满，而且每层从左至右填充

2. 上滤，下滤（重要基础，维护性质的操作，大根堆为例）

上滤，下滤能够维护除根外任意父亲节点比儿子节点大的性质，堆排序和优先队列都是上滤，下滤来实现

注：下面代码都是 [1~n]，0号下标没有用

2.1 上滤：增大值或者插入操作需要用到

与它的父亲比较大小直到比他父亲小或者到顶了,类似于下

void up(int index, int *heap, int heapsize)
{int i;  int key = heap[index];//compare with his father until failure or reaching the rootfor (i = index; key > heap[i / 2] && i >= 1; i = i / 2)heap[i] = heap[i / 2];if (i == 0) { i++; heap[i] = key; }//防止写入0else heap[i] = key;
}

2.2 下滤：减小值或者删除操作需要用到

与它的儿子比较大小直到比他儿子大或者到底了,类似于下

void down(int index,int *heap,int heapsize)
{int i;  int key = heap[index];for (i = 2 * index; i <= heapsize; i = 2 * i ){if (i + 1 <= heapsize && heap[i] < heap[i + 1]) i ++;if (key < heap[i]) heap[i / 2]= heap[i];else break;}heap[i / 2] = key;
}

3. 如何建立堆

从最下非叶子结点层开始进行下滤down操作直到根结点

void createheap(int *Array,int heapsize)
{for (int  i = heapsize/2; i>=1; i--)down(i, Array, heapsize);
}

3. 应用：堆排序

堆排序是一个优秀的算法，任何时候只需要常数个额外的元素空间存储临时数据，具有空间原址性，复杂度仅为O(nlgn)

1. 首先要在先是堆的前提下进行排序，所以第一步要调用createheap，建立了[1~n]的堆

createheap(Array, 10);

2. 然后不断让第一个结点与最后一个个结点互换，然后将这个结点从堆中去除（可以直接用heapsize–即完成），重复这一步直到堆中没有结点，下面只演示了排好三个，后面同理
   

void heapsort(int *heap)
{int p = heapsize;while (p>=1){//互换int temp = heap[1];heap[1] = heap[p];heap[p] = temp;p--; //从堆中去除down(1, Array, p);}
}

4. 应用：优先队列

优先队列是一种用来维护由一组元素构成的集合S的数据结构，其中每一个元素都有一个相关的值，也就是关键字，优先队列分为最大优先队列和最小优先队列

最大优先队列 （为例）

应用有很多，比如共享计算机系统的作业调用。最大优先队列记录要执行的各个作业以及他们之间的相对优先级。当一个作业完成或被中断后，调度器将调用下面的dequeue，选出优先级最高的作业执行，并去除；调用下面的enqueue，插入新作业到队列中

最小优先队列

可以被用于基于事件驱动的模拟器等等，在此不一 一说了

1.返回最大值

int returnMax(int *heap)
{return heap[1];
}

2. 出队操作

出队的是第一个元素
操作步骤是被最后一个节点覆盖，然后将该结点从堆中去除（可以直接用heapsize–即完成），最后使用down下滤操作维护，如下出队16

void dequeue(int *heap)
{heap[1] = heap[heapsize];heapsize--;//去除down(1, heap, heapsize); //下滤
}

3. 入队操作

将将要插入的数字挂在数组末端且heapsize++ 入队后，使用up上滤来维护

void enqueue(int *heap,int num)
{heapsize++; //入队Array[heapsize] = num;up(heapsize, heap, heapsize); //上滤
}

4. 修改值

检查某个结点的值改动是增大还是变小，分别调用up和down操作

void modifyvalue(int *heap, int index,int num)
{	if (num > heap[index]) { heap[index] = num; up(index, heap, heapsize); }if (num < heap[index]) { heap[index] = num; down(index, heap, heapsize); }
}

B-Tree

1. 磁盘介绍

磁盘构造

如Fig2-20，磁盘是由多个铝盘叠成，每个磁表面有自己的磁头和磁盘臂
如Fig2-21，一个盘片有多个磁道(track，每个圆环)，一个磁道被分为多个扇区(sector)，每个扇区存取512字节的数据区，如Fig2-19，数据区前有前导区（preamble）和纠错码（ECC），连续两个扇区之间有隔离带（intersector gap）

磁盘原理理

磁头中有正或者负电通过时，就可磁化磁头正下方的磁盘表面，使磁性颗粒朝左或者朝右偏转，这就写入了
磁头通过磁性区域时，将被感应出正电路或者负电流，这样就读出了存在磁盘的数据位

读写过程

1. 寻道：寻找磁道，5~10ms（相邻<1ms）
2. 旋转：旋转磁道对应扇区至磁头下，旋转半圈为3~6ms
3. 读写：512字节扇区约3.5us
花费都在寻道和旋转上

数据结构

大规模数据存取，磁盘维护了文件的索引目录，找个文件的索引就可以找个文件在磁盘中正真的位置。
但由于磁盘读取是一个扇区一个扇区的读取，每当读取一个扇区后，我们需要将结点信息读到内存中判断我们要找的文件目录索引是不是在这里。
所以访问扇区数对应了我们I/O操作数，由上面我们已经知道了I/O操作花费的时间是大部分的。

于是我们读取结论：减少访问扇区数，也就是减少了I/O操作，也就节省了时间，所以选择一个合理的数据结构大大帮助我们读取磁盘，B-tree就来了

B树（B-tree）是为磁盘或者其他直接存取辅存而设计的一种平衡搜索树，B树类似于红黑树，但他在降低I/O操作数方面要更好一些，并且许多数据库使用B树或者B树的变种来存储信息

2. B-tree介绍

是一种平衡的多路查找树，文件系统中很有用

m阶B-tree中（m叉）

三个约束

1.树中的每个结点至多有m棵子树 【插入需要用到这个约束】
2.除根之外的所有非终端结点至少有 ⌈m/2⌉棵子树 【删除需要用到这个约束】
3.根节点若不是叶子结点，则至少两棵子树 【根的约束】

关键字与指针的数量关系是

指针=关键字+1,即每个节点关键字个数最多为m-1

K_i-1 < (A_i-1) < K_i

指针(A_i-1)所指的子树的所有结点所有关键字均<K_i
指针(A_i-1)所指的子树的所有结点所有关键字均>K_i-1

叶子F

所有的叶子结点都出现在同一层次，并且不带信息（可以看作是外部结点或查找失败的结点，实际上这些结点不存在，指向这些结点的指针为空）

3. B- tree的查找

假设每个key含有文件的正真位置,且每个节点代表一个扇区

B-树的查找过程与二叉排序树查找类似，一路下去找，上面为演示寻找29，所以我们就找到了29文件的，详细写就是

1. 找到文件目录的根扇区，将结点信息导入内存（29<35 定位左边子树指针）（1次I/O操作）

2. 根据左边子树指针，我们定位到该扇区，将结点信息导入内存（29>27 定位右边子树指针）（2次I/O操作）

3. 根据左边子树指针，我们定位到该扇区，将结点信息导入内存（29=29 找到文件正真位置）（3次I/O操作）

进行正真的I/O操作

4. B- tree的插入

一棵m阶的树，每次添加一个关键字不是在树中添加一个叶子结点，而是首先在最底层的某个非终端结点中添加一个关键字，若该结点关键字个数不超过m-1，则插入完成，否则要产生结点“分裂”

① 直接插入成功：插入30

执行流程

寻找到在哪里插入（定是在最底层的某个非终端结点中），然后按序添加一个关键字

② 需要分裂的插入，在上面插入完30后，插入26

分裂规则（插入第m个元素时需要分裂情况）

第⌈m/2⌉插入到双亲（向上取整，有小数就取1），也就是最中间的是分界点，两边各自形成新节点

执行流程

从动画中可以看出，因为该结点的数量超过2了，需要分裂，关键字37带着前后两个指针走了形成新的结点，关键字26带着前后两个指针走了形成新的结点，剩下的30去插入到双亲结点中，发现该结点没有超过两个，成功。
假如超过2个，关键字30插入过去的结点需要分裂，也就是执行上述类似过程，比如在最左边的叶结点插入10

5. B- tree的删除

一棵m阶的树，删除关键字Ki，首先应该找到该关键字所在结点

①不是最底层的某个非终端结点

则可以使用指针Ai中所指的最小关键字Y代替Ki（K_i的前驱或者后继），然后删除关键字Y，让B-树的删除转化为最底层的某个非终端结点操作，如下图删除45的情况

② 是最底层的某个非终端结点

1. 是最底层的某个非终端结点中，删除后，其中的子树数目不少于⌈m/2⌉，则删除完成，

2. 左(右)兄弟可借：所删关键字结点的子树数目少于⌈m/2⌉，而其相邻的左（或右）两兄弟的子树数目⌈m/2⌉，则需要将其兄弟结点中最小的（或最大）的关键字上移到双亲结点中，而将双亲结点中小于（或大于）且紧贴该上移关键字的关键字下下移至被删除关键字所在结点中。下面是删除50的动画演示【开始图是上一个删除45的图】

3. 左(右)兄弟不可借：所删关键字结点的子树数目少于⌈m/2⌉，而其相邻的左（或右）两兄弟的子树数目等于⌈m/2⌉，假设该结点有右兄弟，且其右兄弟结点地址由双亲结点中的指针Ai，则删去关键字之后，他所在结点剩余的关键字和指针，加上双亲结点的关键字Ki一起，合并到A_i所指的兄弟结点中（若没有右兄弟，则合并到左兄弟结点中）。下面是删除53的动画演示【开始图是上一个删除50的结果】
   

跳跃表

1. 介绍

坐地铁算法

动态搜索结构，一个多层次的链表，且每一层链表中的元素是前一层链表元素的子集，下面是四层层，而且是理想条约表，高概率的可能基本操作为O(lgn) ，L4存储所有的元素，L1存储一些元素，然后L1和L2的元素之间相同元素互联

其中，插入、删除、查找以及迭代输出有序序列这几个操作，红黑树也可以完成，时间复杂度和跳表是一样的。
但是，按照区间查找数据这个操作，红黑树的效率没有跳表高。跳表可以在 O(logn)
时间复杂度定位区间的起点，然后在原始链表中顺序向后查询就可以了，这样非常高效。
此外，相比于红黑树，跳表还具有代码更容易实现、可读性好、不容易出错、更加灵活等优点，因此 Redis 用跳表来实现有序集合

2. 查询

往右走直到走过头，找到比他大的，然后回头一站往下走，直到找到x(到底层找到>x 的话说明没有)

3. 插入

插入与删除对于上面的理想跳跃表很难维护，我们都是选择是大致维护，

下面是wiki上面插入的动图，首先我们查询应该插入在哪里，我们做的是使用硬币来决定x应该存入到哪些表中，如果正面就再上升存储到上面的链表中，直到反面

coinRes=flip_coin(coin);
while(coinRes==head)
{promote(x);coinRes=flip_coin(coin);
}

4. 删除

就是把每个表中的那个元素删除

---

证明专区

1. 红黑树证明：每个基本操作O(lgn)

树的基本操作与树的高度直接相关，证明树高，也就证明了基本操作所耗费的时间

2. 随机BST证明：期望高度为Θ(lgn)

Jenson不等式就不证明了，只证明②

3. 跳表证明：理想跳跃表搜索代价(2层)

下面是求最小代价

类推到多个，k个，lgn个

4. 跳表证明：我们选择掷硬币的方式有没有保证每个操作是O(lgn）

首先证明一个引理

lemma: #levels=O(lgn) w.h.p.
即证明 ：高概率使得跳跃表层数≤clgn

假如我们使用方向走从底部开始走，目标是走到最左边，那么这个路径长度是和正向走路径长度相同，每次走的时候，扔硬币正面为up move 向上走，背面 像左走，高概率的总的代价就是总move数，也就是抛硬币数(而且带有clgn次数为正面)

#up move ≤ #levels ≤ clgn(w.h.p.)
#move ≤ #coin filp till clgn heads
证明 ：#coin filp till clgn heads =O(lgn)

---