二叉树

• 二叉树定义
  • n个结点的有限集合，该集合为空集，或者一个根节点和两棵互不相交的、分别称为根节点的左子树和右子树的二叉树组成
• 满二叉树
  • 一棵二叉树中所有分支结点都存在左子树和右子树，并且所有叶子都在同一层上
• 完全二叉树
  • 一棵有n个结点的二叉树按层序编号，编号为i的结点与同样深度的满二叉树中编号为i的结点在二叉树中位置完全相同
• 二叉树的性质
  • 非空二叉树第 i 层最多 2^(i-1) 个结点 （i >= 1）
  • 深度为 k 的二叉树最多 2^k - 1 个结点 （k >= 1）
  • 度为 0 的结点数为 n0，度为 2 的结点数为 n2，则 n0 = n2 + 1
  • 有 n 个结点的完全二叉树深度 k = ⌊ log2(n) ⌋ + 1
  • 对于含 n 个结点的完全二叉树中编号为 i （1 <= i <= n） 的结点
    • 若 i = 1，为根，否则双亲为 ⌊ i / 2 ⌋
    • 若 2i > n，则 i 结点没有左孩子，否则孩子编号为 2i
    • 若 2i + 1 > n，则 i 结点没有右孩子，否则孩子编号为 2i + 1

最大堆和最小堆

堆是完全二叉树，根据结点和左右孩子的大小关系，分为最大堆和最小堆

• 最大堆
  • 每个结点的值都大于或等于其左右孩子结点的值
• 最小堆
  • 每个结点的值都小于或等于其左右孩子结点的值

二分查找

二分查找适用于有序数组

• 查找时间复杂度O(logn)

二叉搜索树：

• 若它的左子树不空，则左子树上所有结点的值均小于它的根结构的值
• 若它的右子树不空 ，则右子树上所有结点的值均大于它的根结点的值
• 它的左、右子树也分别为二叉搜索树。

通过中序遍历即可得出有序的序列， 构造一棵二叉搜索树的目的:为了提高查找和插入删除关键字的速度

平衡二叉树(AVL树)：

• 平衡二叉树是二叉搜索树的一种，其特点：左右子树的高度之差的绝对值不超过1，左右子树高度之差被称为平衡因子，每次插入一个新的值的时候，都要检查二叉树的平衡，也就是平衡调整

• 将二叉树上结点的左子树深度减去右子树深度的值称为平衡因子BF (Balanoe Factor)，平衡因乎只可能是-1、0和 1

红黑树

• 查找时间复杂度O(logn)，插入和删除时间复杂度O(logn)

• 红黑树(red-black tree) 是一棵满足下述性质的二叉查找树：

• 每个结点非红即黑
• 根结点为黑色
• 每个叶结点（叶结点即实际叶子结点的NULL指针或NULL结点）都是黑的;
• 若结点为红色，其子节点一定是黑色（没有连续的红结点）
• 对于每个结点，从该结点到其后代叶结点的简单路径上，均包含相同数目的黑色结点（叶子结点要补充两个NULL结点）
• 有了五条性质，才有一个结论：通过任意一条从根到叶子简单路径上颜色的约束，红黑树保证最长路径不超过最短路径的二倍，因而近似平衡。

应用场景主要是STL中map，set的实现，优点在于支持频繁的修改，因为查询删除插入时间复杂度都是logN

• 平衡树和红黑树的区别

  • AVL树是高度平衡的，频繁的插入和删除，会引起频繁的调整以重新平衡，导致效率下降
  • 红黑树不是高度平衡的，算是一种折中，插入最多两次旋转，删除最多三次旋转，调整时新插入的都是红色。

• 为什么红黑树的插入、删除和查找如此高效？

  • 插入、删除和查找操作与树的高度成正比，因此如果平衡二叉树不会频繁的调整以重新平衡，那它肯定是最快的，但它需要频繁调整以保证平衡
  • 红黑树算是一种折中，保证最长路径不超过最短路径的二倍，这种情况下插入最多两次旋转，删除最多三次旋转，因此比平衡二叉树高效。

• 红黑树为什么要保证每条路径上黑色结点数目一致？

  • 为了保证红黑树保证最长路径不超过最短路径的二倍
  • 假设一个红黑树T，其到叶节点的最短路径肯定全部是黑色节点（共B个），最长路径肯定有相同个黑色节点（性质5：黑色节点的数量是相等），另外会多几个红色节点。性质4（红色节点必须有两个黑色儿子节点）能保证不会再现两个连续的红色节点。所以最长的路径长度应该是2B个节点，其中B个红色，B个黑色。

基于磁盘IO角度来看二叉树、B-tree树、B+树

参考：

B-树就是B树，都是 B-tree 的翻译，里面不是减号-，是连接符-

B树的时间复杂度与二叉树一样，均为O(logN)

相关概念

磁盘读取依靠的是机械运动，分为寻道时间、旋转延迟、传输时间三个部分，这三个部分耗时相加就是一次磁盘IO的时间，大概9ms左右。这个成本是访问内存的十万倍左右；

正是由于磁盘IO是非常昂贵的操作，所以计算机操作系统对此做了优化：预读；每一次IO时，不仅仅把当前磁盘地址的数据加载到内存，同时也把相邻数据也加载到内存缓冲区中。因为局部预读原理说明：当访问一个地址数据的时候，与其相邻的数据很快也会被访问到。每次磁盘IO读取的数据我们称之为一页（page）。一页的大小与操作系统有关，一般为4k或者8k。这也就意味着读取一页内数据的时候，实际上发生了一次磁盘IO。

B-Tree与二叉查找树的对比

数据库索引是存储在磁盘上，当表中的数据量比较大时，索引的大小也跟着增长，达到几个G甚至更多。当我们利用索引进行查询的时候，不可能把索引全部加载到内存中，只能逐一加载每个磁盘页，这里的磁盘页就对应索引树的节点。每个结点加载一次磁盘io，减少磁盘IO的次数就必须要压缩树的高度，让瘦高的树尽量变成矮胖的树。平衡二叉树由于树深度过大而造成磁盘IO读写过于频繁，进而导致效率低下。为了减少磁盘ＩＯ的次数，就你必须降低树的深度

B树这种数据结构常常用于实现数据库索引，查找效率比较高。

B树

m阶B-Tree满足以下条件：

• 每个节点最多拥有m个子树

• 根节点至少有2个子树

• 分支节点至少拥有m/2颗子树（除根节点和叶子节点外都是分支节点）

• 所有叶子节点都在同一层、每个节点最多可以有m-1个key，并且以升序排列

如：一个3阶的B树

在本例中每一个父节点都出现在子节点中，是子节点最大或者最小的元素

每个叶子节点都有一个指针，指向下一个数据，形成一个有序链表。

B+树

B+树是B树的一个升级版，相对于B树来说B+树更充分的利用了节点的空间，让查询速度更加稳定，其速度完全接近于二分法查找。

为什么说B+树查找的效率要比B树更高、更稳定；我们先看看两者的区别

• B+树的非叶子节点不保存关键字记录的指针，只进行数据索引，使得B+树每个非叶子节点所能保存的关键字大大增加；
• B+树叶子节点保存了父节点的所有关键字记录的指针，所有数据地址必须要到叶子节点才能获取到。所以每次数据查询的次数都一样；
• B+树叶子节点的关键字从小到大有序排列，左边结尾数据都会保存右边节点开始数据的指针。
• 非叶子节点的子节点数=关键字数

• 完B树，再来说说B+树，B+树和结构很类似，但查询性能上更高，具有如下的特性：

  • 有k个子树的中间节点包含有k个元素（B树中是k-1个元素），每个元素不保存数据，只用来索引，所有数据都保存在叶子节点；

  • 叶子节点中包含了全部元素的信息，按照关键字的大小从左到右排序；

从图中可以看出，B+树中间节点和叶子节点有重复的数据，这里声明一下，中间节点保存的只是子树数据的子针，并不是真实的数据，所以中间节点的存储占用空间较少。

同时，叶子节点之间用指针连在一起，换句话说，叶子节点形成了一个链表，把所有的数据都存储了进来。

为什么这样设计，比起B树有什么好处呢？

首先，因为B+树的中间节点只是保存子树的最大数据和子树的子针，本身的占用空间较小，因此可以容纳更多节点元素，也就是说同样数据情况下，B+ 树会 B 树更加“矮胖”，因此查询效率更快。

其次，查找某个范围的数据，只需在B+树的叶子节点链表中遍历即可，不需要像B 树那样挨个中序遍历比较大小。总结来说，B+树的优点就是：

1. 层级更低，IO 次数更少；
2. 每次都需要查询到叶子节点；
3. 查询性能稳定叶子节点形成有序链表，范围查询方便

总结

插入或者删除元素都会导致节点发生裂变反应，有时候会非常麻烦，但正因为如此才让B树能够始终保持多路平衡，这也是B树自身的一个优势：自平衡；B树主要应用于文件系统以及部分数据库索引，如MongoDB，所以目前大部分关系型数据库索引是使用B+树实现。

B树：有序数组+平衡多叉树；

B+树：有序数组链表+平衡多叉树；

哈希表

哈希表是一种以键-值(key-indexed) 存储数据的结构，我们只要输入待查找的值即key，即可查找到其存储位置，在该位置上存储着对应的数据

哈希表的实现

• 主要包括构造哈希和处理哈希冲突
  • 使用哈希函数将被查找的键转换为数组的索引。方法有直接地址法、平方取中法、除留余数法等。理想的情况下，不同的键会被转换为不同的索引值，但是在有些情况下我们需要处理多个键被哈希到同一个索引值的情况。所以哈希查找的第二个步骤就是处理冲突。
  • 处理哈希碰撞冲突。有很多处理哈希碰撞冲突的方法，如拉链法(哈希桶)、线性探测法(开放定址法)、再哈希法、公共溢出区法。

构造哈希

• 直接地址法
  • 直接用key或key的线性函数值作为索引
  • 如果所有的键都是整数，那么就可以使用一个简单的无序数组来实现：将键作为索引，值即为其对应的值，这样就可以快速访问任意键的值。
• 平方取中法
  • 将key平方后取中间的几位数作为索引，可以是3位或4位
• 除留余数法
  • 最常用的构造哈希函数的方法，直接对key取模，也可以平方后取模。
  • 获取正整数哈希值最常用的方法是使用除留余数法，即对于大小为素数M的数组，对于任意正整数k，计算k除以M的余数。M一般取素数。

字符串哈希值

• 将字符串作为键的时候，可以将它作为一个大的整数，将组成字符串的每一个字符取ASCII值然后进行哈希，采用Horner计算字符串哈希值。
• 如果对每个字符去哈希值可能会比较耗时，所以可以通过间隔取N个字符来获取哈西值来节省时间

int hash = 0;
char *str = "abcdef";
for(int i = 0;i < strlen(str);i++){
	hash = 31*hash + (int)str[i];
}
cout<<hash<<endl;

处理哈希冲突

1.拉链法（哈希桶法）

• 基本思想
  • 将大小为M的数组的每一个元素指向一个链表，链表中的每一个结点都存储散列值为该索引的键值对。注意选择足够大的M，使得所有的链表都尽可能的短小，以保证查找的效率
• 拉链法查找
  • 根据散列值找到索引对应的链表，
  • 沿着链表顺序找到相应的键

2.线性探测法（开放定址法）

基本思想：f(key) = (f(key) + d) MOD M

• 线性探测
  • 当碰撞发生时即一个键的散列值被另外一个键占用时，直接检查散列表中的下一个位置即将索引值加1
• 二次探测
  • 索引值位移量不为1，为1，-1，2，-2…的平方
• 随机探测
  • 索引值位移量采用随机函数计算得到。随机种子产生伪随机数，每次得到的随机序列相同

3.再哈希法

使用哈希函数去散列一个输入的时候，输出是同一个位置就再次散列，直至不发生冲突位置，但每次冲突都要重新散列，计算时间增加，另外需要准备多个哈希函数

4.公共溢出区法

建立一个公共溢出区域，把hash冲突的元素都放在该溢出区里。查找时，如果发现hash表中对应桶里存在其他元素，还需要在公共溢出区里再次进行查找。

为什么哈希桶的长度和除留余数法的M为质数？

设有一个哈希函数：H( c ) = c % N;
当N取一个合数时，最简单的例子是取2^{n，比如说取2}3=8,这时候
H(11100(二进制)) = H(28) = 4
H(10100(二进制)) = H(20) = 4

• c的二进制**第4位（从右向左数）就“失效”**了，也就是说，无论第c的4位取什么值，都会导致H( c )的值一样．这时候c的第四位就根本不参与H( c )的运算，这样H( c )就无法完整地反映c的特性，增大了导致冲突的几率．
• 取其他合数时，都会不同程度的导致c的某些位”失效”，从而在一些常见应用中导致冲突．
• 取质数，基本可以保证c的每一位都参与H( c )的运算，从而在常见应用中减小冲突几率．

跳表

跳表全称为跳跃列表，它允许快速查询，插入和删除一个有序连续元素的数据链表。跳跃列表的平均查找和插入时间复杂度都是O(logn)。快速查询是通过维护一个多层次的链表，且每一层链表中的元素是前一层链表元素的子集（见右边的示意图）。一开始时，算法在最稀疏的层次进行搜索，直至需要查找的元素在该层两个相邻的元素中间。这时，算法将跳转到下一个层次，重复刚才的搜索，直到找到需要查找的元素为止

• 查找时间复杂度O(logn)，插入、删除时间复杂度O(logn)
• 用于有序链表的查找，类似二分查找操作的链表

跳表的效率比链表高了，但是跳表需要额外存储多级索引，所以需要的更多的内存空间

• 跳表的空间复杂度为 o(n)
• 插入和删除的时间复杂度也为 O(longn)

基本思想

对于单链表来说，即使数据是已经排好序的，想要查询其中的一个数据，只能从头开始遍历链表，这样效率很低，时间复杂度很高，是 O(n)

把链表中的一些节点提取出来作为索引，为了提高效率可以逐级提取作为索引

• 原始链表

  • 14 → 23 → 34 → 43 → 50 → 59 → 66 → 72
  • 原始链表查找复杂度O(n)

• 跳表

  • 性质

    • 由很多层结构组成
    • 每一层都是一个有序的链表
    • 最底层(Level 1)的链表包含所有元素
    • 如果一个元素出现在 Level i 的链表中，则它在 Level i 之下的链表也都会出现。
    • 每个节点包含两个指针，一个指向同一链表中的下一个元素，一个指向下面一层的元素。

  • 原始链表转换成跳表

  14       →     50

   ↓           ↓

  14  →  34  →  50  →  66

   ↓     ↓     ↓     ↓

  14  → 23  → 34  → 43  → 50  → 59  → 66  →  72

  第二级索引 - 第一级索引 - 原始链表

跳表的查找、插入和删除

• 查找

  • 查找时间复杂度为O(logn)
  • 如果链表中总共有 n 个结点，那么第一级索引就有 n/2 个结点，第二级索引就有 n/4 个结点，以此类推，那么第 k 级索引就有 n/(2^k) 个结点。如果最高级索引有 2 个结点，那总的索引级数 k=log2n−1，如果我们算上原始链表的话，那也就是总共有 log2n 级。

• 插入

  • 先查找再插入，插入时间复杂度O(logn)
  • 当我们不停地往跳表中插入数据的时候，如果我们不更新索引，就有可能出现某两个结点之间数据非常多的情况。极端情况下，跳表还会退化为单链表。
  • 我们需要某种手段来维护索引与原始链表大小之间的平衡，也就是说，如果链表结点变多了，索引值就相应地增加一些
  • 可以选择同时也将这个数据插入到部分索引层中。而插入到哪些索引层中，则由一个随机函数生成一个随机数字来决定

跳表和红黑树的对比

• 插入、删除、查找以及迭代输出有序序列这几个操作，红黑树也可以完成，时间复杂度和跳表是一样
• 跳表的优点
  • 代码相对简单
  • 按照区间查找数据这个操作，红黑树的效率没有跳表高。跳表可以在 O(logn) 时间复杂度定位区间的起点，然后在原始链表中顺序向后查询就可以了，这样非常高效。
  • 删除一段区间的数据，相对于红黑树容易

void mergeSort(vector<int> &q, int l, int r){
    if(l >= r)
        return;
    int mid = l + r >> 1;
    mergeSort(q, l, mid);
    mergeSort(q, mid + 1, r);
    static vector<int> w;
    w.clear();
    int i = l, j = mid + 1;
    while(i <= mid && j <= r){
        if(q[i] > q[j])
            w.push_back(q[j++]);
        else
            w.push_back(q[i++]);
    }
    while(i <= mid)
        w.push_back(q[i++]);
    while(j <= mid)
        w.push_back(q[j++]);
    for(int i : w)
        q[l++] = i;
}

int Partition(vector<int> &v,int low ,int high)
{
    int pivot;
    pivot=v[low];//用子表的第一个记录作枢轴记录
    while(low<high)
    {

        while(low<high && v[high]>=pivot)
            high--;
        swap(v[low],v[high]);//high指示的值小于pivot，交换
        while(low<high && v[low]<=pivot)
            low++;
        swap(v[low],v[high]);//low指示的值大于pivot，交换


    }

    return low;
}

void quickSort(vector<int> &v,int low ,int high)
{
    int i;
    if(low<high)
    {
        i=Partition(v,low,high);
        quickSort(v,low,i-1);
        quickSort(v,i+1,high);

    }

}

void push_down(vector<int>& heap, int size, int u){
    int t = u, left = u * 2, right = u * 2 + 1;
    if(left <= size && heap[left] > heap[t])
        t = left;
    if(right <= size && heap[right] > heap[t])
        t = right;
    if(u != t){
        swap(heap[u], heap[t]);
        push_down(heap, size, t);
    }
}

void push_up(vector<int>& heap, int u){
    while(u / 2 && heap[u / 2] < heap[u]){
        swap(heap[u / 2], heap[u]);
        u /= 2;
    }
}

void heapSort(vector<int> &q, int n){
    int size = n;
    for(int i = 1; i <= n; i++)
        push_up(q, i);
    for(int i = 1; i <= n; i++){
        swap(q[1], q[size]);
        size--;
        push_down(q, size, 1);
    }
}

树和图的区别

• 树是图的子集,树是没有环的图（在图里面，环的路线是开始和结束都是一样的点）
• 树可以递归遍历，图要看情况
• 树是一种“层次”关系，图是“网络”关系
• 树有一个根节点，图没有,树的非根节点必定有一个父节点，图不一定