数据结构大纲

1、线性表

1.1、数组

1.1.1、简介

数组是一段连续的内存

1.1.2、动态数组

有动态扩容功能和动态缩容功能。
添加元素超过申请的最大空间数后，会重新申请一个更大的空间，如原空间的1.5倍，来装载这些元素。
删除元素，少于申请的空间数的某个百分比的时候，如25%，将会重新申请一个更小的空间，来装载这些元素，达到节约空间的目的。

1.2、链表

1.2.1、单向链表

有next指针
first指针指向第一个节点
查数据要从第一个节点一直找下一个节点

图片.png

1.2.2、双向链表

有pre指针和next指针
first指针指向第一个节点，last指针指向最后一个节点

图片.png

查数据的时候可以计算要查询的位置是从第一个节点往后查快，还是从最后一个节点往前查快。
所以双向链表查询某个节点的时候，平均时间要比单向链表节省一半。

1.2.3、单向循环链表

最后一个节点的next又指向第一个节点形成循环。

图片.png

只有一个节点时：

图片.png

1.2.4、双向循环链表

图片.png

经典面试题：
如何判断一个链表是否有环？
翻转链表

1.3、栈

栈是一种特殊的线性表，只能在一端进行操作
往栈中添加元素的操作，一般叫做push,入栈
从栈中移除元素的操作，一般叫做pop，出栈(只能移除栈顶元素,也叫做:弹出栈顶元素)
后进先出的原则，Last In First Out， LIFO

图片.png

比如浏览器前进后退，软件的撤销恢复都是栈的应用。使用2个栈来做到这种功能。

1.4、队列

1.4.1、简介

队列是一种特殊的线性表，只能在头尾两端进行操作
队尾(rear) :只能从队尾添加元素，一般叫做enQueue,入队
队头(front) :只能从队头移除元素，一般叫做deQueue, 出队

1.4.2、双端队列

双端队列是能在头尾两端添加、删除的队列

1.4.3、循环队列

• 和队列一样，只能在队尾加入元素，队首移除元素。
  可以使用动态数组来实现循环队列功能，加一个指针，指向队首元素。
  移除队首元素就将该元素置空，然后指针往后挪一位。
  队尾添加的元素超过最大值后再从第一个内存空间往后加。

1.4.4、循环双端队列

• 可以在队首添加删除，也可以在队尾添加删除元素。
  有一个队首指针，队尾位置是根据队首指针的位置计算出来的，具体为：

//  frontIndex：队首指针位置，
// size：队列元素数量
// elements.length：数组总长度
(front + size - 1) % elements.length

2、树

节点、根节点、父节点、子节点、兄弟节点
空树：没有任何节点
子树、左子树、右子树
节点的度：子树的个数
树的度：所有节点的度中最大的值
叶子节点：度为0的节点
层数(level) :根节点在第1层，根节点的子节点在第2层，以此类推(有些教程也从第0层开始计算)
节点的深度(depth) :从根节点到当前节点的唯一路径上的节点总数
节点的高度(height) :从当前节点到最远子叶子节点的路径上的节点总数
树的深度:所有节点深度中的最大值
树的高度:所有节点高度中的最大值
树的深度等于树的高度

有序树：
树中任意节点的子节点之间有顺序关系
无序树：
树中任意节点的子节点之间没有顺序关系
也称为“自由树”
森林：
由m (m≥0)棵互不相交的树组成的集合

2.1、二叉树

• 二叉树的特点
  每个节点的度最大为2 (最多拥有2棵子树)
  左子树和右子树是有顺序的
  即使某节点只有一棵子树，也要区分左右子树

2.2、多叉树

每个节点的度最大超过2

2.3、真二叉树

所有节点的度要么为0要么为2

图片.png

2.4、满二叉树

所有节点的度都要么为0，要么为2。且所有的叶子节点都在最后一层

图片.png

2.5、完全二叉树

叶子节点只会出现最后2层，且最后1层的叶子结点都靠左对齐
从根结点至倒数第2层是一棵满二叉树

图片.png

2.6、二叉搜索树

又被称为二叉查找树，二叉排序树
任意一个节点的值都大于其左子树所有节点的值
任意一个节点的值都小于其右子树所有节点的值
它的左右子树也是一棵二叉搜索树
二叉搜索树可以大大提高搜索数据的效率
二叉搜索树存储的元素必须具备可比较性

图片.png

2.7、二叉树的遍历

2.7.1、前序遍历

访问顺序：根节点、前序遍历左子树、前序遍历右子树

图片.png

• 实现思路: 使用递归

public void preorderTraversal() {
  preorderTraversal(root);
}
private void preorderTraversal(Node<E> node) {
  if (node == null) return;
  System.out.println(node.element);
  preorderTraversal(node.left);
  preorderTraversal(node.right);
}

2.7.2、中序遍历

访问顺序：中序遍历左子树、根节点、中序遍历右子树

图片.png

规律：二叉搜索树的中序遍历结果是升序或者降序的

• 实现思路: 使用递归

public void inorderTraversal() {
  inorderTraversal(root);
}
private void inorderTraversal(Node<E> node) {
  if (node == null) return;
  inorderTraversal(node.left);
  System.out.println(node. element);
  inorderTraversal(node.right);
}

2.7.3、后续遍历

访问顺序：后序遍历左子树、后序遍历右子树、根节点

图片.png

• 实现思路: 使用递归

public void postorderTraversal() {
  postorderTraversal(root) ;
}
private void postorderTraversal(Node<E> node) {
  if (node == null) return;
  postorderTraversal(node.left);
  postorderTraversal(node.right);
  System.out.println(node.element) ;
}

规律：
为了方便记忆前中后序遍历，先遍历父节点的叫前序遍历，先遍历一个子节点再到父节点的叫中序遍历，先遍历全部子节点最后到父节点的叫后序遍历。

2.7.4、层序遍历

访问顺序：从上到下、从左到右依次访问每一个节点

图片.png

• 实现思路: 使用队列
  1、将根节点入队
  2、循环执行以下操作，直到队列为空
  --- 2.1、将队头节点A出队，进行访问
  --- 2.2、将A的左子节点入队
  --- 2.3、将A的右子节点入队

public void levelOrderTranversal( ) {
  if (root == null) return;
  Queue<Node<E>> queue = new LinkedList<>();
  queue.offer(root);
  while (!queue. isEmpty()) {
    Node<E> node = queue.poll();
    System.out.println(node.element);
    if (node. right != null) {
        queue.offer(node.right);
    }
  }
}

• 经典面试题：
  翻转二叉树

2.7.5、重构二叉树

• 以下结果可以保证重构出唯一的一棵二叉树
  前序遍历+中序遍历
  后序遍历+中序遍历

• 前序遍历+后序遍历
  如果它是一棵真二叉树(Proper Binary Tree)，结果是唯一的
  不然结果不唯一

2.7.6、前驱节点

中序遍历时的前一个节点

如果是二叉搜索树，前驱节点就是前一个比它小的节点

比如下图中序遍历的顺序是1、2、3、4、5、6、7、8、9、10、11、12、13
那么8的前驱节点就是7， 13的前驱节点是12

图片.png

2.7.7、后继节点

中序遍历时的后一个节点

如果是二叉搜索树，后继节点就是后一个比它大的节点

2.7.8、删除二叉搜索树的某个节点

2.7.8.1、删除叶子节点

直接删除叶子节点

如果是父节点的左节点
node.parent.left = null
如果是父节点的右节点
node.parent.right = null
如果有父节点
node.parent = null

2.7.8.2、删除度为1的节点

用子节点替代原节点的位置
如果要删除的节点是根节点，那么让根节点指向它的子节点

图片.png

2.7.8.3、删除度为2的节点

1、先用前驱或者后继节点的值覆盖原节点的值
2、然后删除相应的前驱或者后继节点
如果一个节点的度为2，那么它的前驱、后继节点的度只可能是1或0

2.7.9、二叉搜索树的复杂度

搜索一个节点的复杂度和树的高度有关

图片.png 图片.png

2.7.10、平衡二叉搜索树（Balanced Binary Search Tree）

英文简称为: BBST

• 经典常见的平衡二叉搜索树有
  1、AVL树
  Windows NT内核中广泛使用
  2、红黑树
• C++ STL (比如map、set )
• Java的TreeMap、 TreeSet、 HashMap、 HashSet
• Linux的进程调度
• Ngix的timer管理
  一般也称它们为:自平衡的二叉搜索树(Self-balancing Binary Search Tree)

2.7.10.1、平衡

为了提高搜索树的搜索效率，要尽量防止它退化成链表，所以就要平衡二叉搜索树。
当节点数量固定时，左右子树的高度越接近，这棵二叉树就越平衡(高度越低)

图片.png

2.7.10.2、如何平衡？

图片.png

2.7.10.3、 AVL树

• 平衡因子(Balance Factor) :某结点的左右子树的高度差

平衡因子

• AVL树的特点
  1、每个节点的平衡因子只可能是1、0、-1 (绝对值≤1，如果超过1,称之为“失衡”)
  2、每个节点的左右子树高度差不超过1
  3、搜索、添加、删除的时间复杂度是O(logn)

AVL树

2.7.10.3.1、LL-右旋转（单旋）

LL表示失衡节点在某节点的左节点(L)的左节点(L)下

旋转过程

2.7.10.3.2、RR-左旋转（单旋）

RR表示失衡节点在某节点的右节点(R)的右节点(R)下

旋转过程

2.7.10.3.3、LR-RR左旋转，LL右旋转（双旋）

LR表示失衡节点在某节点的左节点(L)的右节点(R)下
先进行RR-左旋转，变为了2.7.10.3.1、LL-右旋转（单旋）中的情况
再进行LL-右旋转，恢复平衡

旋转过程

2.7.10.3.4、RL-LL右旋转，RR左旋转（双旋）

RL表示失衡节点在某节点的右节点(R)的左节点(L)下
先进行LL-右旋转，变为了2.7.10.3.2、RR-左旋转（单旋）中的情况
再进行RR-左旋转，恢复平衡

旋转过程

2.7.10.3.5、恢复平衡统一处理

恢复平衡可以不判断上面的四种情况，而直接用一套方法统一处理。

图片.png

通过观察上图，可以发现，这四种失衡的情况，平衡后的样子是一样的。

规律：
1、都会让d节点到最中间，成为这棵树的根节点。
2、让b节点加上a子树和c子树成为一棵子树，成为d节点的左子树。
3、让f节点加上e子树和g子树成为一棵子树，成为d节点的右子树。

2.7.10.3.6、AVL树平衡总结

• 在AVL树中添加一个节点，如果导致失衡，只要让高度最低的失衡节点恢复平衡，整棵树就恢复平衡。

• 但是如果是删除一个节点，只会导致父节点或者祖先节点失衡（只有一个节点会失衡），让父节点或者祖先节点恢复平衡后，可能会导致更高层的祖先节点失衡（最多需要O(logn)次调整）

2.7.11、 红黑树

2.7.12、B树

2.7.12.1、简介

B树是一种平衡的多路搜索树，多用于文件系统、数据库的实现

图片.png

2.7.12.2、特点

• 1个节点可以存储超过2个元素、可以拥有超过2个子节点
• 拥有二叉搜索树的一些性质
• 平衡，每个节点的所有子树高度一致
• 比较矮

2.7.12.3、m阶B树的性质

• 假设一个节点存储的元素个数为X
• 根节点:1 ≤ X ≤ m - 1
• 非根节点:┌m / 2┐ - 1 ≤ x ≤ m - 1
• 如果有子节点，子节点个数y = x + 1
  Δ 根节点: 2 ≤ y ≤ m
  Δ 非根节点: ┌m / 2┐ ≤ y ≤ m
  ○ 比如m = 3, 2 ≤ y ≤ 3,因此可以称为(2, 3) 树、2-3树
  ○ 比如m = 4, 2 ≤ y ≤ 4,因此可以称为(2, 4)树、2-3-4树
  ○ 比如m = 5, 3 ≤ y ≤ 5,因此可以称为(3, 5) 树
  ○ 比如m = 6, 3 ≤ y ≤ 6,因此可以称为(3, 6) 树
  ○ 比如m = 7, 4 ≤ y ≤ 7,因此可以称为(4, 7) 树

注：┌m / 2┐表示m / 2向上取整