数据结构
树
概念
- 高度(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
