数据结构
分类
- 线性结构：数组、栈、队列、链表、哈希表
- 树结构：二叉树、二分搜索树、AVL、红黑树、Treap、堆、Trie、并查集、哈夫曼树
- 图结构：邻接表、邻接矩阵
线性常用结构
数组 Array：把数据码成一排进行存放。
栈 Stack：相当于数组的子集，只能从一端添加元素，也只能从一端取出元素。后进先出。
队列 Queue ：相当于数组的子集，只能从一端（队尾）添加元素，只能从另一端（队首）取出元素。先进先出。（优先队列：出队顺序和入队顺序无关，和优先级相关。）
链表 Linked List：最简单的动态数据结构。
哈希表 Hash Table ： 是根据关键码值(Key value)而直接进行访问的数据结构。（1哈希函数设计2解决哈希冲突）
树结构
二分搜索树 Binary Search Tree
二叉树：
- 由一个个节点组成，每个节点最多有两个子节点
- 有且只有一个根节点
- 具有天然递归结构（每个节点左右子树也是二叉树）
二分搜索树是二叉树，独特的性质：每个节点的值，大于其左子树所有节点的值，小于其右子树的所有节点的值。
二分搜索树的遍历：
- 前序遍历
- 中序遍历（结果是顺序排列的）
- 后续遍历
- 层序遍历（广度优先遍历，可用队列方式）
线段树 Segment Tree
线段树，是一种二叉树。它将一段区间划分为若干单位区间，每一个节点都储存着一个区间。
适用范围，可以在线维护修改以及查询区间上的最值，求和等。
字典树 Trie
是一个多叉树。
- 根节点不包含字符，除根节点外每一个节点都只包含一个字符；
- 从根节点到某一节点，路径上经过的字符连接起来，为该节点对应的字符串；
- 每个节点的所有子节点包含的字符都不相同。 应用场景：字符串检索/文本预测/词频统计等。
并查集
并查集是一种树型的数据结构，用于处理一些不相交集合的合并及查询问题。
对于一组数据，主要支持2个操作
- 合并(union)：合并两个集合。
- 查询(isConnected)：查询元素所属集合。
性能优化：路径压缩。
AVL 树
最早的自平衡二分搜索树结构。
相关概念：
- 满二叉树：除了叶子节点，其他的所有节点都有左右2个子节点。
- 完全二叉树：叶子节点的最大深度和最小深度相差不会超过1，其空缺的部分一定在节点右下角。
- 平衡二叉树：它是一棵空树或它的左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是一棵平衡二叉树。
计算每个节点平衡因子来判断：左右2棵子树的高度相减。
平衡方式：计算平衡因子/左旋转/右旋转
红黑树
是一种自平衡的二分搜索树，有以下性质：
- 每个节点或者是红色，或者是黑色的
- 根节点是黑色的
- 每一个叶子节点（意思不一样，最后的空节点）是黑色的
- 如果一个节点是红色的，那么他的孩子节点都是黑色的
- 从任意一个节点到叶子节点，经过的黑色节点是一样的