数据结构整理

常用数据结构时间复杂度

数据结构	新增	查询/Find	删除/Delete	GetByIndex
数组 Array (T[])	O(n)	O(n)	O(n)	O(1)
链表 Linked list (LinkedList<T>)	O(1)	O(n)	O(n)	O(n)
Resizable array list (List<T>)	O(1)	O(n)	O(n)	O(1)
Stack (Stack<T>)	O(1)	-	O(1)	-
Queue (Queue<T>)	O(1)	-	O(1)	-
Hash table (Dictionary<K,T>)	O(1)	O(1)	O(1)	-
Tree-based dictionary(SortedDictionary<K,T>)	O(log n)	O(log n)	O(log n)	-
Hash table based set (HashSet<T>)	O(1)	O(1)	O(1)	-
Tree based set (SortedSet<T>)	O(log n)	O(log n)	O(log n)	-

Map

map用来存储k、v结构数据，相信大家使用的都比较熟练了，现在我们就深入分析一下它的细节。

Java中的Map

map都有哪些方法？

image.png

这个是map的接口规定了一系列的操作方法以及一个Entity接口。

image.png

这个是Java集合的类图，可以看到Map的一些主要实现。

HashMap的原理

在HashMap中存储的元素定义如下

static class Node<K,V> implements Map.Entry<K,V> {
    final int hash;  // key的hash值
    final K key;     //  key值
    V value;         //  value值
    Node<K,V> next;  // 下一个node
    ... ...
}

HashMap中定义了一个Node数组，用来存放Node，这些Node根据key的hash值均匀分布在数组上，但是不可避免的存在hash冲突（不同Node它们的key的hash值相同），那么就在每个数组元素上向后拓展链表结构。
查询的时候，先根据key的hash确定数组下标，然后再使用equals方法遍历链表比较值最终找到想要的Node并返回。
这里有一些关键数据，Node数组的初始大小为16（2的n次方），hash冲突链表长度超过8将转换为红黑树（红黑树查询速度比链表快），map会记录一共存了多少个Node就是size，同时规定了一个加载因子loadFactor默认为0.75，利用这个加载因子来估算当前map最大能存多少个Node比较合理就是threshold（最大容量）。
插入的时候一旦size>threshold了就需要扩容，扩容时Node数组大小*2，并将所有的Node重新hash存一遍，这部分开销较大。每次结构发生改变会记录到变量modCount（结构变化次数）中。

TreeMap

参考： TreeMap原理实现及常用方法

树

基础概念

结点：树中的每个元素称为结点
根结点：最顶上的结点，一个树只有一个根结点
每个结点可以拥有子树，一个结点的所有子树都不想交
普通树：

image.png
结点的度：一个结点有几个子节点就有几度
结点关系：父结点、子结点、兄弟结点
结点层次：最大层数表示树的深度
image.png
二叉树：结点的度不超过2，结点在左在右是有顺序的
左斜树：左左左左左
右斜树：右右右右右
满二叉树：最后一层结点的度为0，其他层结点的度都为2
image.png
完全二叉树：把满二叉树按层、从左到右编号。按编号新填充一个二叉树，这个树就是个完全二叉树
按顺序填充ABCDEF就是个完全二叉树
image.png

二叉树

二叉树存储结构：如果每一层用一个数组存，显然有的地方没有结点，会浪费数组资源。
所以使用二叉链表

image.png
代码表示：

typedef struct BiTNode{
    TElemType data;//数据
    struct BiTNode *lchild, *rchild;//左右孩子指针
} BiTNode, *BiTree;

image.png
二叉树遍历
image.png
前序遍历：根左右
ABDECF
中序遍历：左根右
DBEAFC
后序遍历：左右根
DEBFCA
层序遍历：逐层从左到右
[A]
[BC]
[DEF]

二叉搜索树BST

二叉搜索树（二叉查找树）BST：左结点<根结点<右结点

image.png
每个结点结构如下：
image.png

查：1.查找到空没结果；2.值相等查找成功；3.小于结点递归查找其左子树，大于结点递归查找其右子树；
增：1.存在不插入；2.不存在，执行查找时执行到哪个位置就插入到哪个位置；
删：1.若为叶子结点直接删；2.若只有左子树或右子树，将左子树或右子树代替该结点；3.若左右子树都存在，找到左子树中最大值结点，替换到待删除的位置

平衡二叉树AVL

平衡二叉树AVL：
当结点数目一定时，保持树的左右两端平衡，树的查找效率最高。这种左右子树层级相差不超过1的树叫平衡二叉树。 AVL是通过平衡深度来解决BST的搜索效率降低的策略。

image.png
平衡因子：结点的左子树与右子树的高度（深度）差叫做平衡因子（0，-1,1）
平衡二叉树代码结构：

typedef struct AVLNode *Tree;
typedef int ElementType;
struct AVLNode
{
    int depth; //深度，这里计算每个结点的深度，通过深度的比较可得出是否平衡
    Tree parent; //该结点的父节点，方便操作
    ElementType val; //结点值
    Tree lchild;
    Tree rchild;
    AVLNode(int val=0) //默认构造函数
    {
        parent=NULL;
        depth=0;
        lchild=rchild=NULL;
        this->val=val;
    }
};

左旋：右子树过深，要平衡到左边去

image.png
因为右子树深度超出左子树深度2，要进行左旋平衡，流程：
1.原根结点的右结点代替根节点
2.现根节点的左子树变为原根节点的右子树
3.原根节点变为现根节点的左子树
右旋：左子树过深，要平衡到右边去
方向相反，流程同上
image.png
插入结点
在根结点的左孩子的左子树插入结点LL：直接右旋
在根结点的右孩子的右子树插入结点RR：直接左旋
在根结点的左孩子的右子树插入结点LR：先对根结点的左孩子左旋，在对根结点右旋
在根结点的右孩子的左子树插入结点RL：先对根结点的右孩子右旋，在对根结点左旋
删除：
删除流程同二叉搜索树，但要考虑删除后是否平衡，不平衡要进行调整。

2-3树

2-3树：AVL虽然解决了BST的查询效率降低问题，但是却引入了插入、删除时的繁琐操作，这些性能的损耗可能会大于检索带来的提升。所以引入了2-3树。存在2度、3度结点，2度结点结构同BST，3度结点数据域a、b，3个指针，左子树所有结点小于a，中子树所有结点在ab之间，右子树所有结点大于b。
2-3树的查找：同BST，都是通过比较选定路线继续查找。

image.png
2-3树插入：

2-3-4树

2-3树不再是单纯的二叉树了，因为2-3树中除了2-节点之外还存在3-节点。在2-3树的基础上进一步扩展，2-3-4树在2-3树的基础上添加4-节点。4-节点可以存储3个键值，最多可以拥有4棵子树。

image.png

红黑树

2-3-4树和红黑树是完全等价的，但是2-3-4树的编程实现相对复杂，所以一般是通过实现红黑树来实现替代2-3-4树，而红黑树也同样保证在O(logN)的时间内完成查找、插入和删除操作。

image.png

B树

数据量大如数据库时，不能全放内存，需要放磁盘，每一个结点代表一个磁盘页，访问一次新结点代表一次磁盘io，那么树的高度决定磁盘io的次数，所以让每个结点增加key值，就可以将“瘦高”的树变为“矮胖”的树。

image.png

B+树

在B树的基础上优化，分为索引结点（只存key不存data）、叶子结点（key、data），叶子结点使用链表连接。

image.png

（1）B+树中索引节点只存储key值，不存储数据，则相同的大小磁盘页中，使用B+树可以存储更多的节点元素，使得B+树比B树更为矮胖，减少磁盘IO次数。

（2）在查找单一元素时，B树最好情况是在根节点查找成功，最坏情况是查找至叶子节点，导致B树的查找过程是不稳定的。而使用B+—树的查找最终查找节点为叶子节点，使得B+树查找稳定。

（3）在进行某个范围内数据查找，B树需要进行中序遍历，而B+树的叶子节点采用单链表形式链接，只需按顺序遍历链表即可完成范围查找，提高了查找效率。