数据结构

树

概念

• 高度(Height):节点到叶子节点的最长路径(边数)
• 深度(Depth):根节点到这个节点所经历的边的个数
• 层(Level):节点的深度+1
• 树的高度:根节点的高度

二叉树(Binary Tree)

• 定义:每个节点最多有两个子节点

• 存储

  • 链式存储法(基于指针):每个节点有三个字段,一个存储数据,另外两个分别指向左右子节点的指针
  • 顺序存储法(基于数组):根节点存储在下标i=1的位置,左子节点存储在下标2i=2的位置,右子节点存储在2i+1=3的位置

• 遍历

  • 前序遍历:对于树中的任意节点,先打印这个节点,然后再打印它的左子树,最后打印它的右子树
  • 中序遍历:对于树中的任意节点,先打印它的左子树,然后再打印它本身,最后打印它的右子树
  • 后序遍历:对于树中的任意节点,先打印它的左子树,然后再打印它的右子树,最后打印它本身

• 类型

  • 满二叉树:除了叶子节点外,每个节点都有两个子节点

  • 完全二叉树:叶子节点都在最底下两层,最后一层叶子节点都靠左排列,并且除了最后一层,其它层的节点个数都要达到最大

  • 二叉查找树(Binary Search Tree)

    • 定义:树中的任意一个节点,其左子树中每个节点的值,都小于这个节点的值,而右子树节点的值都大于这个节点的值

    • 特点:支持动态数据的快速插入/删除/查找操作

    • 操作

      • 查找:先取根节点,若它等于查找的数据,直接返回.若要查找的数据比根节点小,那就在左子树中递归查找;若要查找的数据比根节点大,就在右子树中递归查找

      • 插入:从根节点开始,依次比较要插入的数据和节点大小的关系

      • 删除

        • 要删除的节点没有子节点:只需将父节点中指向删除节点的指针置为null
        • 要删除的节点只有一个子节点:只需将父节点中指向删除节点的指针,让它指向要删除节点的子节点即可
        • 要删除的节点有两个子节点:找到这个节点右子树中的最小节点,把它替换到要删除的节点上,然后再删除掉这个最小节点

      • 其他操作

        • 快速查找最大节点和最小节点,前驱节点和后继节点
        • 中序遍历二叉查找树,输出有序的数据序列,O(n)

    • 支持重复数据的二叉查找树

      • 方法一:通过链表和支持动态扩容的数组等数据结构,把值相同的数据存储在同一个节点上

      • 方法二:每个节点仍然只存储一个数据

        • 插入时,若一个节点的值与要插入数据的值相同,就将这个要插入的数据放到这个节点的右子树
        • 查找时,遇到值相同节点,继续在右子树查找,直到遇到叶子节点才停止
        • 删除时,找到每个要删除的节点按照前面删除方法删除

    • 时间复杂度分析

      • 最坏情况:退化成链表,O(n)
      • 最好情况:一棵完全二叉树,时间复杂度与树的高度成正比O(height)

  • 平衡二叉查找树

    • 设计初衷:解决二叉查找树因动态更新导致的性能退化问题

    • 定义:二叉树中任意一个节点的左右子树的高度相差不能大于1

    • 类型

      • AVL树:严格意义上的平衡二叉查找树

      • 红黑树(R-B Tree)

        • 定义

          • 根节点是黑色的
          • 每个叶子节点都是黑色的空节点,也就是说叶子节点不存储数据
          • 任何相邻节点都不能同为红色,也就是说红色节点被黑色节点隔开
          • 每个节点,从该节点到达其可达叶子节点的所有路径,都包含相同数量的黑色节点

        • 时间复杂度O(logn)

        • 实现

          • 左旋
          • 右旋
          • 插入或删除时的平衡调整

  • 堆

    • 定义

      • 一个完全二叉树
      • 每个节点值都必须大于等于(或小于等于)其子树中每个节点的值

    • 存储

      • 完全二叉树使用数组存储.数组下标为i的节点的左子节点就是下标为i2的节点,右子节点就是下标为i2+1的节点,父节点就是下标为i/2的节点

    • 操作

      • 插入
      • 删除堆顶元素
      • 堆化:插入或删除元素,为满足堆的特性,需要调整,这个过程称为堆化.顺着节点所在路径,向上或者向下,对比然后交换

散列表

定义

• 键:参赛选手编号
• 散列函数(哈希函数):把参赛选手编号转换为数组下标的映射方法
• 散列值(哈希值):由散列函数计算得到的值
• 装载因子:表示空位的多少,装载因子越大,说明空闲位越少,冲突越多,散列表性能下降.装载因子=填入表中元素/散列表长度

原理

• 利用数组支持随机访问的特性.通过散列函数把元素的键值映射为下标,将数据存储在数组中对应下标的位置.当按照键查询时,利用同样散列函数将键值转换成数组下标,从对应的数组下标位置获取数据

散列函数

• 散列函数计算得到的散列值必须是一个非负整数(数组下标从0开始)
• 若key1=key2,则hash(key1)=hash(key2)
• 若key1≠key2,则hash(key1)≠hash(key2)

解决散列冲突

• 开放寻址法:出现散列冲突,重新探测一个空闲位置,将其插入

  • 线性探测
  • 二次探测
  • 双重散列

• 链表法:散列值相同的元素都放在相同槽位对应的链表中

跳表

链表加多级索引的结构,甚至可以替代红黑树

队列

定义

• 想象成现实的排队买票
• 先进者先出

实现

• 数组(顺序队列)
• 链表(链式队列)

操作

• 入队:放一个数据在队列尾部
• 出队:在队列头部取一个元素

应用

• 阻塞队列:队列为空,队头取数据阻塞.队列满,队尾插入数据阻塞
• 并发队列:线程安全的队列,在入队和出队方法上加锁

手撕队列

• 数组实现队列
• 链表实现队列

栈

定义

• 只允许在一端插入和删除数据
• 后进者先出,先进者后出

实现

• 数组(顺序栈)

  • 支持动态扩容的顺序栈,与ArrayList动态扩容原理一致

• 链表(链式栈)

操作

• 入栈(push):在栈顶插入一个数据
• 出栈(pop):在栈顶删除一个数据

应用

• 函数调用栈(栈帧入栈出栈)

手撕栈

• 数组实现栈
• 链表实现栈

链表

定义

• 通过指针将零散的内存块串联起来
• 内存块称为链表结点

类型

• 单链表

  • 定义

    • 头结点:记录链表基地址
    • 尾结点:指针指向一个空地址NULL
    • 后继指针next:记录下个结点地址的指针

  • 操作

    • 查询:依次遍历,O(n)
    • 插入:只考虑相邻结点的指针改变,O(1)
    • 删除:只考虑相邻结点的指针改变,O(1)

• 循环链表

  • 与单链表唯一区别:尾结点指针指向头结点

• 双向链表

  • 定义

    • 每个结点不只有后继指针,还存在一个前驱指针prev指向前面的结点

  • LinkedHashMap实现原理

  • 插入和删除比单链表更高效,空间换时间

• 双向循环链表

手撕链表

• 单链表反转
• 链表中环检测
• 两个有序链表合并
• 删除链表倒数第n个结点
• 求链表的中间结点

数组

定义

• 线性表
• 连续的内存空间
• 存储一组具有相同类型的数据

操作

• 随机访问

  • a[i]_address = base_address + i * data_type_size

• 插入

  • 数组有序,插入第k个数据,需搬移k~n之间的数据,最坏O(n),平均O(n)
  • 数组无序,将第k个位置数据搬移至数组最后,把新元素放置第k个位置.时间复杂度O(1)

• 删除

  • 删除与插入类似,最坏O(n),平均O(n),最好O(1)
  • 不追求数据数据连续性,将多次删除操作集中一起执行,提升删除效率

问题

• 警惕数组访问越界

• 容器能否完全替代数组

  • ArrayList最大优势将数组操作细节封装起来,支持动态扩容.动态扩容即存储空间不够时,自动扩容为1.5倍大小,将原来数据复制过去,再将新数据插入
  • 数组优于容器,比容器更快

图(Graph)

定义

• 顶点

• 边

• 度:跟顶点相连接的边的条数

  • 入度:有多少条边指向这个顶点
  • 出度:有多少条边是以这个顶点为起点指向其他顶点

• 有向图:边有方向的图

• 无向图

• 带权图:每条边都有一个权重

存储

• 邻接矩阵

  • 底层依赖二维数组
  • 优点:查询高效
  • 缺点:浪费内存

• 邻接表:类似散列表的存储结构

广度优先搜索(BFS):"地毯式"层层推进的搜索策略,即先查找离起始顶点最近的,然后是次近的,依次往外搜索

深度优先搜索(DFS):"走迷宫",不撞南墙不回头

数据结构.png