Java常见的8种数据结构

大家好，欢迎来到IT知识分享网。

一、线性结构：数组、链表、哈希表；队列、栈

 1.数组：

 2.链表：

 3.哈希表：

 4.队列：先进先出

 5.栈：先进后出

 二、非线性结构有：堆、树(二叉树、B树、B+树、红黑树)

1.二叉树分类

　　时间复杂度最好情况是O(logn) ，最坏情况下时间复杂度O(n)

　　1）满二叉树：如果一个二叉树的层数为K，且结点总数是(2^k) -1 ，则它就是满二叉树。

　　2）完全二叉树：如果一个二叉树的深度为h，除第 h 层外，其它各层 (1～h-1) 的结点数都达到最大个数，第 h 层所有的结点都连续集中在最左边，这就是完全二叉树。

       3）二叉查找树：左子树上的值都比其根节点小，右子树上的值都比其根节点大。

　　　  二叉查找树的中序遍历一定是从小到大排序的。

　　4）平衡二叉树（红黑树）：是一棵空树或它的左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是一棵平衡二叉树。

　　　 平衡二叉树必须是二叉查找树

　　     性能：平衡二叉树在添加和删除时需要进行复杂的旋转保持整个树的平衡，最终，插入、查找的时间复杂度都是 O(logn)，性能已经相当好了。

 　　5）最优二叉树(哈夫曼树): 树的带权路径长度达到最小，称这样的二叉树为最优二叉树，也称为哈夫曼树(Huffman Tree)。

　　　　哈夫曼树是带权路径长度最短的树，权值较大的结点离根较近。应用：哈夫曼编码。

2.红黑树：是一种自平衡二叉查找树。应用内存排序。

插入和删除的最坏的时间复杂度是O(log N) 。

红黑树左旋和右旋的目的是为了自平衡。

参考：1.红黑树、B+树 2.红黑树在什么时候左旋 右旋 如何旋转

　　1）每个节点非红即黑；

　　2）根节点是黑的；

　　3）每个叶节点(叶节点即树尾端NULL指针或NULL节点)都是黑的；

　　4）如果一个节点是红的,那么它的两儿子都是黑的；

　　5）对于任意节点而言，其到叶子点树NULL指针的每条路径都包含相同数目的黑节点；

　　6）高度始终保持在h = logn

　　7）红黑树的查找、插入、删除的时间复杂度最坏为O(log n)

 2.1 变色规则  红黑树使用红黑二色进行“着色”,目的是利用颜色值作为二叉树的平衡对称性的检查。
 当前结点的父亲是红色，且它的祖父结点的另一个子结点也是红色（叔叔结点）：
（1）把父节点设为黑色
（2）把叔叔也设为黑色
（3）把祖父也就是父亲的父亲设为红色（爷爷）
（4）把指针定义到祖父结点设为当前要操作的（爷爷）分析的点变换的规则
 这里我们新插入一个值 6 ( 插入的节点都是红色的 所以 6 是红色的节点 ) ，变色后的图形。

红黑树的创建：节点的初始颜色为红色。

 2.2 左旋：以某个结点作为支点(旋转结点)，其右子结点变为旋转结点的父结点，右子结点的左子结点变为旋转结点的右子结点，左子结点保持不变。

 2.3 右旋：以某个结点作为支点(旋转结点)，其左子结点变为旋转结点的父结点，左子结点的右子结点变为旋转结点的左子结点，右子结点保持不变。

 2.4 红黑树查找：和二叉平衡树的查找一样

3.B树(多叉树)：平衡多路查找树（查找路径不只两个），不同于常见的二叉树，它是一种多叉树。O(logN)

4.B+树：是一种自平衡树数据结构，它保持数据排序；在进行搜索、顺序访问、插入和删除的复杂度是O(log n)且B+树只在叶子节点中存放数据，所以消除了一些B树的缺陷。非叶子节点只保存索引,不保存实际的数据,数据都保存在叶子节点中。O(nlogn)

 4.1 B+树查找：树的高度低，支持范围查找

 4.2 mysql为什么采用B+树

　　1）磁盘IO的次数更少

　　2）支持范围查找

 4.3 B树与B+树的区别

三、图(对现实世界建模)

四、mysql

 1.mysql底层数据结构：B+树

   1.1 索引的最左前缀原则:mysql建立多列索引（联合索引）有最左前缀的原则，即最左优先。

   1.2 explain(sql执行计划):避免全表扫描，尽量走索引。

　　1) type: system > const > eq_ref > ref > range(范围) > index(索引) >  all (性能好->差)

  2.Mysql锁与事务隔离级别