数据结构三要素

1. 数据结构的逻辑结构

逻辑结构是指数据元素之间的逻辑关系，即从逻辑关系上描述数据。它与数据的存储无关，是独立于计算机的。数据的逻辑结构分为线性结构和非线性结构。

微信截图_20210527175721.png

2. 数据的存储结构

存储结构是指数据结构在计算机中的表示，也称物理结构。它包括数据元素的表示和关系的表示。数据的存储结构是逻辑结构用计算机语言的实现，它依赖于计算机语言。

3. 数据的运算

施加在数据上的运算包括运算的定义和实现。运算的定义是针对逻辑结构的，指出运算的功能；运算的实现是针对存储结构的，指出运算的具体操作步骤。

算法和算法评价

1. 算法的基本概念

算法是对特定问题求解步骤的一种描述，它是指令的有限序列，其中每一条指令表示一个或多个操作。

2. 算法效率的度量

算法效率的度量是通过时间复杂度和空间复杂度来描述的。

1) 时间复杂度

一个语句的频度是指该语句在算法中被重复执行的次数。算法中所有语句的频度之和记作T(n)，它是该算法问题规模n的函数，时间复杂度主要分析T(n)的数量级。算法中的基本运算（最深层循环内的语句）的频度与T(n)同数量级，所以通常采用算法中基本运算的频度f(n)来分析算法的时间复杂度。因此算法的时间复杂度记为：

T(n)=O(f(n))

"O"的含义是T(n)的数量级，其严格的数学定义是：若T(n)和f(n)是定义在正整数集合上的两个函数，则存在正常数C和n₀，使得当n>=n₀时，都满足0<=T(n)<=C×f(n)。

2）空间复杂度

算法的空间复杂度S(n)，定义为该算法所耗费的存储空间，它是问题规模n的函数。渐近空间复杂度也常称为空间复杂度，记作S(n)=O(g(n))。

线性表

线性表的定义

线性表是具有相同数据类型的n(n>=0)个数据元素的有限序列。其中n为表长，当n=0时该线性表是一个空表。

线性表的顺序表示（数组）

顺序表的定义

线性表的顺序存储又称为顺序表。它是用一组地址连续的存储单元，依次存储线性表中的数据元素，从而使得逻辑上相邻的两个元素在物理位置上也相邻。

微信截图_20210527175851.png

顺序表的特点

• 顺序表最主要的特点是随机访问，即通过首地址和元素序号可以在O(1)的时间内找到指定的元素。

• 顺序表的存储密度高，每个节点至存储数据元素。

• 顺序表逻辑上相邻的元素物理上也相邻，所以插入和删除需要移动大量元素。

  微信截图_20210527180029.png

线性表的链式表示（链表）

单链表的定义

线性表的链式存储又称为单链表，它是通过一组任意的存储单元来存储线性表中的数据元素。为了建立起数据元素之间的线性关系，对每个链表结点，除了存放元素自身的信息之外，还需要存放一个指向其后继的指针。

    typeof struct LNode {
        ElementType data;
        struct LNode *next;
    }LNode, *LinkList;

通常用"头指针"来标识一个单链表，如单链表L,头指针为"NULL"时则表示一个空表。

微信截图_20210527180201.png

链表的特点

• 对于随机访问，链表的平均时间复杂度为O(n)。

• 链表的插入、删除操作，只需要修改相关结点的指针域即可。

  微信截图_20210527180401.png

• 由于链表每个结点带有指针域，因而在存储空间上比顺序存储要付出比较大的代价，存储密度不够大。

二分查找

仅适用于有序的顺序表。基本思路是：首先将给定值key与表中中间位置元素的关键字比较，若相等，则查找成功，返回该元素的存储位置；若不等，则所需查找的元素只能在中间元素以外的前半部分或后半部分中。然后在缩小的范围内继续进行同样的查找，如此重复直到找到为止，或者确定表中没有所需查找的元素，则查找不成功，返回查找失败的信息。

int Binary_Search(SeqList L, ElemType key) {
    int low = 0; high = L.TableLen - 1; mid;
    while(low <= high) {
        mid = (low + high) / 2;
        if(L.elem[mid] == key)
            return mid;
        else if(L.elem[mid] > key)
            high = mid - 1;
        else
            low = mid + 1;
    }

    return -1;
}

例如要查找值为11的元素:

现在推导一下二分查找的时间复杂度：

我们知道二分查找每次都是查找原来列表长度的一半，在最坏的情况下最后只剩一个值。假设要进行k此查找，则有

树

树是N（N>=0）个结点的有限集合，N=0时，称为空树，这是一种特殊情况。在任意一颗非空树中英满足：

1. 有且仅有一个特定的称为根的结点

2. 当N>1时，其余结点可分为m（m>0）个互不相交的有限集合T₁, T₂, ...T_m,其中每一个集合本身又是一棵树，并且称为根结点的子树。

微信截图_20210527210255.png

二叉排序树

二叉排序树或者是一颗空树，或者是一颗具有下列特性的非空二叉树：

1. 若左子树非空，则左子树上所有结点关键字值均小于根结点的关键字值。
2. 若右子树非空，则右子树上所有结点关键字值均大于根结点的关键字值。
3. 左、右子树本身也是一颗二叉排序树。

微信截图_20210527210531.png

平衡二叉树

平衡二叉树可以定义为它后者是一颗空树，或者是具有下列性质的二叉树：它的左子树和右子树都是平衡二叉树，且左子树和右子树的高度差的绝对值不超过1。

微信截图_20210527210641.png

平衡二叉树的查找

微信截图_20210527211004.png

在查找的过程中和给定值进行比较的关键字个数不超过树的深度。可以证明，含有n个结点的平衡二叉树的最大深度为O(log₂ⁿ)。

平衡二叉树的插入

二叉树保证平衡的基本思想：每当再二叉排序树中插入（或删除）一个结点时，首先要检查其插入路近上的结点是否因为此次操作而导致了不平衡。如果导致了不平衡，则先找到插入路径上离插入结点最近的平衡因子绝对值大于1的结点A，再对以A为根的子树，在保持二叉排序树特性的前提下，调整各结点的位置关系，使之重新达到平衡。

微信截图_20210527214700.png

在新结点插入后，如果造成了查找路径上某个结点不再平衡，需要做出相应的调整。一般可将失去平衡后进行调整的规律归纳为下列4种情况：

1. LL平衡旋转

在结点A的左孩子(L)的左子树(L)上插入了新结点。

微信截图_20210527213127.png

2. RR平衡旋转

在结点A的右孩子(R)的右子树(R)上插入了新结点。

微信截图_20210527213322.png

3. LR平衡旋转(先左后右双旋转)

在A的左孩子(L)的右子树(R)上插入新的结点。先将A结点的左孩子B的右子树的根结点C向左上旋转提升到B结点的位置，然后再把该C结点向右上旋转提升到A结点的位置。

微信截图_20210527213736.png

4. RL平衡旋转(先右后左双旋转)

在A的右孩子(R)的左子树(L)上插入新结点。先将A结点的右孩子B的左子树的根结点C向右上旋转提升到B结点的位置，然后再把该C结点向左上旋转提升到A结点的位置。

微信截图_20210527214012.png

跳跃表

跳跃表的定义如下：

• 跳跃表由多条分层的链表组成。
• 每条链表中的元素都是有序的。
• 每条链表都有两个元素+∞和-∞，分别表示链表的头部和尾部。
• 从上到下，上层链表元素集合是下层链表元素集合的子集。
• 跳跃表的高度定义为水平链表的层数。

微信截图_20210527214909.png

跳跃表的查找

微信截图_20210527215119.png

以左上角作为起点(currentNode)：

• 如果currentNode后继结点的值小于等于待查询值，则沿着这条链表向后查询，否则，切换到当前结点的下一层链表。
• 继续查询，直到找到待查询值为止（或者currentNode为空结点）为止。

微信截图_20210527215026.png

跳跃表的插入

微信截图_20210527215635.png

首先，需要按照上述查找流程找到待插入元素的前驱和后继；然后，按照如下随机算法生成一个高度值：

// p是一个(0, 1)之间的常数，一般取p = 1/4或者1/2
public void randomHeight(double p) {
    int height = 0;
    while(random.nextDouble() < p) {
        height++;
    }
    return height+1;
}

最后，将待插入结点按照高度值生成一个垂直节点（这个节点的层数正好等于高度值），之后插入到跳跃表的多条链表中去。假设height=randomHeight(p)，这里需要分两种情况讨论：

• 如果height大于跳跃表的高度，那么跳跃表的高度被提升为height，同时需要更新头部节点和尾部节点的指针指向。
• 如果height小于等于跳跃表的高度，那么需要更新待插入元素前驱和后继的指针指向。

复杂度分析

跳跃表具有如下几条性质：

• 一个节点落在第k层的概率为p^k-1：如果randomHeight(p)返回的高度为k，那么必须要求前面(k-1)个随机树都小于p，(k-1)个概率为p的独立事件概率相乘，因此高度为k的概率为p^k-1。
• 一个最底层链表有n个元素的跳跃表，总共元素个数为：

其中k为跳跃表的高度。由于上一个性质，一个元素落在第k层概率为p^k-1，则第k层插入的元素个数为n×p^k-1，所有k相加得到上述公式。当p<=1/2时，上述公式小于O(2n)，所以空间复杂度为O(n)。

• 跳跃表的高度为O(logn)：考虑第1+3×log_1/pⁿ层，落在这层的期望节点数为

,当n较大时，该层节点数为0，所以层数在1+3×log_1/pⁿ=O(logⁿ)这个数据级上。

• 跳跃表的查询时间复杂度为O(log^N)：

查询时间复杂度关键取决于从最左上角到达最底层走过的横向步数和纵向步数之和。我们反过来考虑这个过程，也就是从最底层达到最左上角s走过的期望布数（包括横向步数）。对第k层第j列节点来说，它只可能从下面两种情况跳过来：

1. 第k-1层第j列节点往上走，跳到第k层第j列节点。根据randomHeight(p)函数定义，往上走的概率为p。
2. 第k层第j+1列节点往左走，跳到第k层第j列节点。这种情况，第k层第j+1列节点已经时垂直节点的最高点，也就是说，这个节点已经不能往上走，只能往左走。根据randomHeight(p)函数定义，往左走的概率为(1-p)。

设C_k为往上跳k层的期望步数（包括纵向步数和横向步数），那么有：

C₀=0;

C_k=(1-p)×(1+C_k) + p×(1+ C_k-1)

根据递推式，推出：

由于高度k为O(logN)级别，所以，查询走过的期望步数也为O(logN)。

微信截图_20210527222902.png

微信截图_20210527222951.png

• 跳跃表的插入/删除时间复杂度为O(logN)：由于插入/删除的实现可以看出，插入/删除的时间复杂度和查询时间复杂度相等。

因此，跳跃表的查找、删除、插入的复杂度都是O(logN)。

copy from：

《王道2019年数据结构考研复习指导》

《HBase原理与实践》

《Skip Lists: A Probabilistic Alternative to Balanced Trees》

https://www.cnblogs.com/yellowgg/p/11272908.html