一、数组

什么是数组：数组是定义在连续空 间上相同数据类型的集合。
特点：增删慢，因为插入元素和删除元素需要移动整个数组，而查找的话，因为是连续空间的地址，所以查找很快。
注意二维数组的地址是否相同呢，这跟语言相关，c++二维数组的地址空间是连续的，而java的则不是，比如三行四列的数组，每行的地址是连续的，而列之间没有关系。
数组删除时间复杂度O（n），查询时间复杂度O（1）
上面表述不准确：数组随机按照下标随机访问的时间复杂度为O(1),或者已知下标情况下查找元素的时间复杂度为O(1)。因为要找到待查元素的时间复杂度也是O(n)，如果是有序数组用二分法查找时间复杂度也是O(logn)

二、链表

什么是链表：链表是一种通过指针串联在一起的线性结构，分为两个区域，一个数据域，一个指针域。
链表的类型：
单链表：只有一个指针域，用于指向下一个节点，只能单向查询。
双链表：有两个指针域，一个指向上个节点，一个指向下个节点，可以双向查询。
循环链表：就是将单链表的首尾相连。
存储方式：
链表在内存中存储非连续的，通过指针串联在一起
定义：

  1. class ListNode{
  2.     int val;
  3.     ListNode next;
  4.     public ListNode(int val){
  5.         this.val = val;
  6.     }
  7. }

链表插入时间复杂度：O（1），查询时间复杂度O（n）
上面表述不准确：如果已知待删节点的先驱节点，删除节点的时间复杂度为O(1)，如果是通过下标来删除节点的话得先找到待删节点，那么这里的时间复杂度也是O(n)

三、哈希表

什么是哈希表？ 哈希表是根据关键码值而直接进行访问的数据结构。68747470733a2f2f696d672d626c6f672e6373646e696d672e636e2f32303231303130343233343830353136382e706e67.png
哈希表能够根据哈希值直接定位到元素所在位置。哈希值通过哈希函数计算得到，内部原理是将对象的属性方法等映射称为一个独一无二的数字。
数据结构 - 图2
如果不同对象哈希值的余数相等，就到了同一个哈希表中的位置了，这种情况叫做哈希碰撞。
解决办法
拉链法：在那个位置用链表来存储。
线性探测法：如果当前位置有元素了，就找下一个空位来存放。
常见的三种哈希结构

  • 数组
  • set
  • map

什么时候使用：当需要判断一个元素是否在集合中的时候优先考虑哈希结构。哈希表用空间换来了时间。
hashmap扩容为什么是两倍？
hashmap计算添加元素的时候用的是位运算，是很高效的运算，扩容是两倍二进制的话就是向左移了一位，其他位置的二进制数都没变。

四、栈和队列

什么是栈？是一种线性结构，数据按照先进后出的顺序获取。
什么是队列？也是一种线性结构，数据按照先进先出的顺序获取。
可以用数组和链表实现。
数据结构 - 图3
Deque是双端队列，可以从队尾插入或者删除数据，ArrayDeque和LinkedList是实现类，都是双端的。
PriorityQueue是优先队列，有最大优先队列和最小优先队列，最大优先队列：无论入队顺序如何，都是当前最大元素优先出对。
Stack的方法：

  • peek() 查看栈顶元素，不移除
  • pop() 移除顶部元素，并返回
  • push() 压入一个元素

Queue的方法：

  • 添加 ：add() 从队尾增加元素，如果队列满了就抛异常；

    offer() 如果队列满了就返回false

  • 删除： remove()移除头部元素，如果队列为空抛异常；

  • 得到： element() 返回头部元素，如果队列为空抛异常，

    peek() 返回头部元素，为空返回null，
    poll()移除头部元素并返回，为空返回null
    优先队列（PriorityQueue）：在优先队列中，元素被赋予优先级，当访问元素时，具有最高优先级的元素最先删除，优先队列具有最高级先出的特征。
    优先队列的添加是add()方法

五、二叉树

满二叉树：是一颗只有度为2和度为0的节点，其中度为0的节点在同一层。一颗深度为k的满二叉树（2^k）-1个几点。
完全二叉树：一颗深度为k的二叉树，除了第k层没有节点数没有满之外，其余各层的节点数都满了，每层节点为2^(k-1)个，并且第k层的节点都集中在左边。
数据结构 - 图4
二叉搜索树：二叉搜索树是每个节点有数值的树，一个节点的左子树的所有节点都要小于该节点值，右子树的所有节点的值都要大于该节点值。
数据结构 - 图5
平衡二叉搜索树(AVL:Adelson-Velsky and Landis):除了是一颗搜索树，它可以是一颗空树或者左子树和右子树的深度差不超过1。
数据结构 - 图6

图中第三棵树的左子树深度为2，右子树深度为0，差超过了1。
AVL插入值出现以下几种情况需要做旋转处理：
左左型
左左型.png
右右型
右右型.png
左右型
左右型.png
右左型
右左型.png右左型2.png
总结：左左型—-右旋
右右型—-左旋
左右型—-先左旋，后右旋
右左型—-先右旋，后左旋
AVL的效率：N个节点的AVL，高度可以保持在log2n，插入/查找/删除的时间复杂度也是log2n。
红黑树：

  • 每个节点数不是红色就是黑色
  • 根节点和叶子节点null为黑色
  • 从一个节点到每个叶子节点的黑色节点数量相同
  • 红色节点的子节点为黑色

数据结构 - 图12
在java中的TreeMap和TreeSet的底层原理就是红黑树，用于存储有序数组的，操作效率为O(logn)
AVL和红黑树的区别？
红黑树是一种弱平衡树，如果有相同节点AVL的高度比红黑树低，所以红黑树降低了对旋转的要求更适合，红黑树适合插入删除较多的情况，AVL更适合查找更多的情况。
树节点的定义：

  1. class TreeNode{
  2.     int val;
  3.     TreeNode left;
  4.     TreeNode right;
  5.     public TreeNode(){}
  6.     public TreeNode(int val){
  7.         this.val = val;
  8.     }
  9.     public TreeNode(int val, TreeNode left, TreeNode right){
  10.         this.value = value;
  11.         this.left = left;
  12.         this.right = right;
  13.     }
  14. }

用数组表示树怎么遍历的呢？
a = {1,2,3,4,5,6}， 一般根节点为1,左子节点2，右子节点3，左子节点的左子节点4，左子节点的右子节点5，右子节点的左子节点6。用数组表示树比较少，一般用链式结构比较多。
二叉树的遍历：

  • 深度优先：先往深走，遇到子节点返回
    • 前序遍历（递归法，迭代法）
    • 中序遍历（递归法，迭代法）
    • 后序遍历（递归法，迭代法）

前序遍历：中左右； 中序遍历：左中右； 后序遍历：左右中； 前中后指的就是中的位置。
数据结构 - 图13
因为栈先进后出适合模拟深度优先的遍历方法，可以用栈来做迭代法。队列的先进先出又适合一层一层的广度优先遍历。

  • 广度优先：一层一层的遍历
    • 层次遍历（迭代法）

队列法：层次遍历的思路是用一个队列记录每层的节点，然后取出每层节点的值。然后把这层每个节点的的下两个节点放到队列里面去。

  1.     public List<List<Integer>> breadthTracerse(TreeNode root){
  2.         if(root == null){
  3.             return null;
  4.         }
  5.         Queue<TreeNode> queue = new LinkedList<>();
  6.         queue.offer(root);
  7.         //用来存放每层的节点
  8.         List<List<Integer>> result = new ArrayList<>();
  9.         while(!queue.isEmpty()){
  10.             List<Integer> temp = new ArrayList<>();
  11.             int size = queue.size();
  12.             //取出当前这层所有节点，顺便连把下一层的节点全部放到队列里面
  13.             for(int i = 0; i < size; ++i){
  14.                 TreeNode t = queue.poll();
  15.                 temp.add(t.val);
  16.                 if(t.left != null){
  17.                     queue.offer(t.left);
  18.                 }
  19.                 if(t.right != null){
  20.                     queue.offer(t.right);
  21.                 }
  22.             }
  23.             result.add(temp);
  24.         }
  25.         return result;
  26.     }

递归法：递归法用一个层次变量来记录当前递归到了哪层，如果到了到那层就把数据加到哪层。

  1.     public void breadthTraverse(TreeNode node,int deep,List<List<Integer>> result2){
  2.         if(node == null){
  3.             return;
  4.         }
  5.         deep++;
  6.         //如果当前层没有容器来装里面就新建一个容器
  7.         if(result2.size() < deep){
  8.             result2.add(new ArrayList<Integer>());
  9.         }
  10.         result2.get(deep-1).add(node.val);
  11.         breadthTraverse(node.left,deep,result2);
  12.         breadthTraverse(node.right,deep,result2);
  13.     }

层序遍历思路，就遍历每层节点，遇到节点就把节点的左右子节点交换一下就OK啦。

  1.     public void reverseTree1(TreeNode root){
  2.         if(root == null){
  3.             return;
  4.         }
  5.         Queue<TreeNode> queue = new LinkedList();
  6.         queue.offer(root);
  7.         while(!queue.isEmpty()){
  8.             int size = queue.size();
  9.             for(int i = 0; i < size; ++i){
  10.                 TreeNode t = queue.poll();
  11.                 TreeNode temp = t.left;
  12.                 t.left = t.right;
  13.                 t.right = temp;
  14.                 if(t.left != null){
  15.                     queue.offer(t.left);
  16.                 }
  17.                 if(t.right != null){
  18.                     queue.offer(t.right);
  19.                 }
  20.             }
  21.         }
  22.         return;
  23.     }

总结：层序遍历很强大。

六、B树

B树相当于一颗多叉查找树，对于一颗m阶的B数具有具有如下特性：

  1. 根节点至少有两个孩子；
  2. 每个中间节点都包含k-1个元素和k个孩子，其中m/2<=k<=m；
  3. 每一个叶子都包含k-1个元素，其中m/2<=k<=m；
  4. 所有的叶子节点都位于同一侧；
  5. 每个节点中的元素从小到大排列，节点中的k-1个元素正好是k个孩子包含的元素的值域划分。

b树.jpg
对于这棵m=3的B树，这个树中是是有多个元素的，并且和二叉树一样，左节点的所有元素的值都比父亲元素小，对于[3,7]这个节点，2个节点刚好分成了三个域，对应三个孩子，2相当于3的左孩子节点，[4,6]相当于3的右孩子节点且是7的左孩子节点，9是7的右孩子节点。只是B树每个节点中可以装多个元素，且有多个分支。
为什么用B+树不用二叉树和哈希表？
从查找次数来说B+树和二叉树的查找时间差不多，但是树的节点在磁盘中的存储是不连续的，磁盘中的数据是以页为单位加载到内存中的，不同节点很可能分配到不同的磁盘页中，而B+树节点中的元素地址是连续的，所以在磁盘中的寻址次数减少了许多。
如果要进行模糊查询的话，hash表也只能遍历所有数据，如果哈希碰撞太多的话，查找效率也会降低很多。
B+树
先看定义，一个m阶的k子树有如下几个特征：

  1. 有k个子树的中间节点包含有k个元素（B树是k-1个），每个元素不保存数据，只用来索引，所有数据都保存在叶子节点中；
  2. 所有叶子节点包含了全部元素的信息，及指向含有这些元素记录的指针，且叶子节点本身依关键字的大小自小而大顺序链接。
  3. 所有的中间节点元素都同时存在于子节点，在子节点中是最大（或最小）元素

数据结构 - 图15
图中，每个中间节点有几个元素就有几个孩子，并且元素在孩子中是最大值，8是258节点的最大值，8是68节点的最大值。根元素的最大值就是整个b+树的最大值，以后无论插入删除多少元素，都要保持最大元素在根节点中。每个叶子节点中都有指向下一个节点的指针形成一个有序链表。
卫星数据：索引元素指向的数据记录，比如数据表中的某一行，B-树中无论中间节点还是叶子节点中都有卫星数据，B+树中只有叶子节点带有卫星数据，其余中间节点仅仅是索引，没有任何数据关联。
B+树中的卫星数据：
数据结构 - 图16
在数据库中的聚集索引（Clustered Index）中，叶子节点直接包含卫星数据，在非聚集索引中，叶子节点直接指向卫星数据的指针。
聚集索引是在B+中存储所有数据；非聚集索引叶子节点中存储的是主键，需要再根据主键查找数据。
B+树好处：范围查询更方便；
磁盘IO查询更少，因为中间节点不存储数据。