[数据结构与算法]数据结构(java)

分类

线性与非线性

1. 线性：线性表、栈、队列、双队列、一维数组、串
   1. 定义：除首尾元素外，其余元素都有唯一前驱后继节点，是一对一；
2. 非线性：多维数组、广义表、树、图
   1. 定义：元素不再保持在同一线性序列中(一个元素可以有多个前驱后继元素)；

结构划分

1. 集合结构：数据元素间的关系是属于同一个集合。
2. 线性结构：数据元素之间存在着一对一的关系。
3. 树状结构：数据元素之间存在着一对多的关系。
4. 网状结构：数据元素之间存在着多对多的关系，也称网状结构。

数据存储结构------------------------------就记这个就行

1. 顺序储存结构：数组、顺序表、栈、队列
   1. 定义：连续的储存空间，只存储数据，不储存地址；
   2. 优点：节省储存空间，索引查找速度快；
   3. 缺点：插入删除效率低(需移动后续节点)，按内容查找慢(需遍历对比)；空间要求高(大数组需连续空间大);
2. 链式储存结构：链表、树
   1. 定义：节点=数据域+指针域；非连续地址；
   2. 优点：插入删除灵活，可利用碎片空间；
   3. 缺点：查询稍慢，按链路查找(单、双向)；
3. 索引储存结构：建立储存节点信息，并建立附加索引表来标识节点的地址；(二级(辅助)索引:查询出key再去聚簇索引搜索)
4. 散列储存结构：hash表，计算hash值得到节点位置，查询快。

常用的数据结构

数组：静态初始化：{元素1、2···}  与 动态初始化：new 类型[长度]
链表(单向链表、双向链表、循环链表) 
栈 
队列  
散列表 
树(BST、AVL、RB-Tree)  
堆(树的一种) 
图

1.数组Array

? 是最简单的数据类型；是储存一组相同类型的元素的容器；

1. 内存地址连续(内存要求比较高)：通过下标查找元素快；
2. 增删元素效率慢(内存连续-需要移动元素)，按内容查找慢(需要遍历)

2.链表LinkedList

? 链表也是线性的顺序存储数据。

• 单向链表：每个节点都包含下一个节点的指针；
• 双向链表：每个节点都有两个指针；

3.栈Stack

Vector的子类Stack已弃用，方法： push()  pop() peek(返回栈顶元素) empty()查看栈是否为空
java实现：使用数组，使用链表
Deque双端队列接口实现：ArrayDeque与LinkedList实现类，

为什么不用Stack：因为Vector几乎所有方法加了synchronized关键字(除私有/构造方法)，官方也建议用Deque接口定义；
如果非要保证线程安全，也可以自己实现Deque接口并使用读写锁(自己的思路-未比较其它方法)
注意：push pop peek都是针对 操作 栈顶

4.队列Queue

Queue是Deque的子接口：是FIFO；
方法：add() offer(false) peek(null) poll(null) remove(异常)

5.散列表(Hash Table)

定义：通过给定的关键字的值直接访问到具体对应的值的一个数据结构。
通常关键字叫key，对应值为value ----- 而HashSet与HashMap或者说map(映射)是基于散列表的
Collision：hash碰撞，解决办法有

1. 链地址法：链表，HashMap等等都是这样解决hash冲突(数组节点Entry内部类:有key-value与next与hash属性)；
2. 开放地址法：发生Collision时，往后移动一个位置(数组节点同时储存key-value)；
3. 再哈希法：使用关键字key的其它部分再次hash(散列函数-时间花销更大)；
4. 建立公共溢出区：把Collision的地址(新的那一个)放在公共溢出区；

树

二叉树-二叉查找树BST-平衡二叉树AVL-红黑树RBT

遍历

1. 前序遍历：根-左-右
2. 中序遍历：左-根-右 在二叉查找树中为从小到大输出；
3. 后序遍历：左-右-根
4. 层次遍历：从上到下，从左到右

前驱后继节点(这里只看BST)

找寻A节点的前驱后继节点： 通俗讲就是A的前后相邻值；
前驱节点：中序遍历中，A节点前一个节点 (解读：在BST中,即找左子树最大的值；若无左子树，找血缘最近有右子树到此A节点的长辈节点)
后继结点：中序遍历中，A节点后一个节点(解读：在BST中,即找右子树最小的值；若无右子树，找血缘最近有左子树到此A节点的长辈节点)

注意：BST中，删除一个A节点，可以让 节点A与其后续节点B 值互换，然后删除B节点；
———— 原理是：相同中序遍历的结果中，可以有很多种二叉搜索树的结构；所以，直接与后续节点B 值互换，然后删除B节点，就是将一种二叉树结构换成另一种结构，并无大碍；

二叉树

1. 二叉树BST：子树最多两个，分左右(顺序确定不颠倒)子树

2. 满二叉树：所有叶子节点在同一高度，且非叶子节点都有俩子节点

3. 完全二叉树：除去底层为满二叉树，底层从左到右依次排去(满二叉树<完全二叉树)

   ---

4. 二叉查找树(搜索树Binary Search Tree)BST:

   1. 节点值大于左子树所有值，小于右子树所有值
   2. 查找：效率在O(log n)~O(n)，二分法与直线链表
   3. 插入：与根节点比较大小(小放于左子树，大于放右子树，等于抛弃),与子树节点继续到合适位置。
   4. 删除：寻找左子树最大元素 或 右子树最小元素（左右子树都不为空的策略）
      1. 叶子节点：只需要修改父节点的next属性即可
      2. 删除节点只有左右子树一个时：将子树补上去即可
      3. 删除节点左右子树不为空：两种方法本质是一样的
         1. pL代替p(删除目标),将 pR 设为 pL树的最右子节点(即设置为pL的最大值的右子树-可能是pL根节点值最大)
         2. pR代替p，将pL设为pR树的最左字节点(即设置为pR树的最小值的左子树-可能是pR根节点值最小)

5. 平衡二叉树AVL：叶子节点高度差不超过一的二叉搜索树，非完全二叉树。最差情况O(logn)效率。

   1. 出现原因：防止二叉搜索树退化为普通链表而降低查询效率。(平衡因子=叶节点高度差)
   2. 旋转 （左旋=右子树为根）
      1. LL:插入节点到AVL的最左节点，平衡因子变2，需要右旋。
      2. LR:插入节点到根的左子树的右子树，需要先左旋，再右旋。
      3. RR:插入节点到AVL的最右节点，需要左旋。
      4. RL:插入节点到AVL的右子树的左子树，需要先右旋，再左旋。

6. 红黑树：高效的二叉搜索树: 另一篇博客详细说明

   1. 满足：
      1. 节点非红必黑；
      2. 根节点是黑色；
      3. 每个叶子节点是黑色； （实体叶子都接上黑NULL或NIL节点)
      4. 一个节点为红色，那存在的父子节点为黑色；(无红红连接)
      5. 任意一节点到其叶子节点都有相同黑色高度；
   2. 插入操作
      首先，插入位置一定是 叶子节点；其次，插入的是红节点，此时父节点若为黑则不用调整红黑树；
      父节点为红时，爷爷节点一定为黑；此时考虑 两种主要变量：
      p父节点是 右子树 还是 左子树
      u叔节点是红 还是 NIL (不可能为黑，因为黑节点的深度)
   3. 删除操作
      前提：如果删除的节点右两个子节点，此时需要找到前驱节点或者后继节点可以替换变为 删除叶子节点 与 一个子节点 的情况

---------------这里是根据p节点左旋操作
/**		p				 pr
 *    / \				/ \
 *  pl    pr   =>	   p   rr
 *       / \		  /\	
 *  	rl	 rr		pl	rl	
*/
----------------这里是插入操作情况
/**
  * 插入节点后的调整处理(新增开始为红色节点)
  *   红黑树：新增红节点c+爷爷黑节点g+父叔为红p 调整为爷红，父叔为黑；若爷为root则调为黑；
  *					自己理解：while循环-c不能为null与root且c.parent为红==需调整
  	*		g			插入节点c为红(左右两种情况),p是为红(非红不调整),u为红|NIL(黑色深度),g黑
    *	   / \			1. p为右子树，u为红(g调红，u与p调黑=深度不变=将c=g当成插入红节点调整)	
	(红|NIL)u  p红      2. p为右子树，u为NIL(这里需要区分c为左右子节点)
    *	      / \		 		2.1 c为左边，先右旋变为2.2的情况，再干；
    *		c红	 c红			  2.2 c为右，p黑,g红，再根据g左旋(变成爷节点黑，两父辈红)；
    *					3. p为左子树，u为红与u为NIL 同1与2的分类，区别在于左右与左右旋
    */
----------------这里是删除操作情况
/** 分两大类：删除节点D为左右子树两大类(都是非root的黑节点)
  * 左子树： 1. B红时：P为黑，PB互换颜色，以P左旋变成2、3、4的情况。
  * 		2. B黑l、r为黑：B设为红，P指向D循环。
  * 		3. B黑r黑l红：Bl互换颜色，以B右旋变成4的情况。
  * 		4. B黑r红：PB互换颜色，r变黑，以p进行左旋(终止D=root)。
  * 右子树：同左子树
  */

7. 堆(二叉堆)
   本质上是完全二叉树，实际上是一个数组：数组下标为n的节点 的两个子树下标是 2n+1与2n+2；
   可以自己实现 二叉堆(有最小、大堆)：也可使用继承抽象类AbstractQueue的优先队列PriorityQueue(是基于优先堆的队列)；
   PriorityQueue<>：
   ** 优先队列是无界的，但默认初始容量11,构造方法有参数调整；
   ** 元素按照其自然顺序进行排序，可通过构造方法的实现Comparator接口的compare方法定义排序；(默认小顶堆)
   扩展：Comparator接口的compare(r1,r2)方法返回值：正数调整顺序，负数不调整(冷静思考)；
   TopK问题：小顶堆(与堆顶比较，大于则替换堆顶，而后调整“二叉树结构”)
   offer(n)添加会自动调整，poll(n)提取删除元素

8. 图Graph
   图是多对多，树一对多，线性表一对一；
   分类：无向图-有向图-简单图-完全无向图-有向完全图
   图的遍历：深度优先(Depth First Search)和广度优先(Breadth First Search)搜索

扩展-跳表(redis中的)

后续补充中！！！

问题

1. 为什么会有AVL而非直接用BST？
   1. BST搜索树查找时效率是看深度，可能存在链表结构(一条线路),查询效率降低。
2. 为什么会出现红黑树，AVL哪里不完美(删除操作不好)？
   1. 首先，红黑树并非AVL。在插入一个node引起树的不平衡时，AVL与RBTree都是最多两次旋转解决，操作都是O(1)。但删除引起不平衡时，AVL最坏下，需要维护删除node到root这条路径上所有node的平衡性，需要O(logN)次旋转，而RB-Tree最多3次，即O(1)的复杂度。
3. 为什么AVL在删除时会有可能出现O(logN)次旋转。