数据结构

分类

• 线性结构：数组、栈、队列、链表、哈希表
• 树结构：二叉树、二分搜索树、AVL、红黑树、Treap、堆、Trie、并查集、哈夫曼树
• 图结构：邻接表、邻接矩阵

线性常用结构

数组 Array：把数据码成一排进行存放。

栈 Stack：相当于数组的子集，只能从一端添加元素，也只能从一端取出元素。后进先出。

队列 Queue ：相当于数组的子集，只能从一端（队尾）添加元素，只能从另一端（队首）取出元素。先进先出。（优先队列：出队顺序和入队顺序无关，和优先级相关。）

链表 Linked List：最简单的动态数据结构。

哈希表 Hash Table ： 是根据关键码值(Key value)而直接进行访问的数据结构。（1哈希函数设计2解决哈希冲突）

树结构

---

二分搜索树 Binary Search Tree

二叉树：

• 由一个个节点组成，每个节点最多有两个子节点
• 有且只有一个根节点
• 具有天然递归结构（每个节点左右子树也是二叉树）

二分搜索树是二叉树，独特的性质：每个节点的值，大于其左子树所有节点的值，小于其右子树的所有节点的值。

二分搜索树的遍历：

• 前序遍历
• 中序遍历（结果是顺序排列的）
• 后续遍历
• 层序遍历（广度优先遍历，可用队列方式）

相关代码

线段树 Segment Tree

线段树，是一种二叉树。它将一段区间划分为若干单位区间，每一个节点都储存着一个区间。

适用范围，可以在线维护修改以及查询区间上的最值，求和等。

相关代码

字典树 Trie

是一个多叉树。

• 根节点不包含字符，除根节点外每一个节点都只包含一个字符；
• 从根节点到某一节点，路径上经过的字符连接起来，为该节点对应的字符串；
• 每个节点的所有子节点包含的字符都不相同。 应用场景：字符串检索/文本预测/词频统计等。

相关代码

并查集

并查集是一种树型的数据结构，用于处理一些不相交集合的合并及查询问题。

对于一组数据，主要支持2个操作

1. 合并(union)：合并两个集合。
2. 查询(isConnected)：查询元素所属集合。

性能优化：路径压缩。

相关代码

AVL 树

最早的自平衡二分搜索树结构。

相关概念：

• 满二叉树：除了叶子节点，其他的所有节点都有左右2个子节点。
• 完全二叉树：叶子节点的最大深度和最小深度相差不会超过1，其空缺的部分一定在节点右下角。
• 平衡二叉树：它是一棵空树或它的左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是一棵平衡二叉树。

计算每个节点平衡因子来判断：左右2棵子树的高度相减。

平衡方式：计算平衡因子/左旋转/右旋转

相关代码

红黑树

是一种自平衡的二分搜索树，有以下性质：

1. 每个节点或者是红色，或者是黑色的
2. 根节点是黑色的
3. 每一个叶子节点（意思不一样，最后的空节点）是黑色的
4. 如果一个节点是红色的，那么他的孩子节点都是黑色的
5. 从任意一个节点到叶子节点，经过的黑色节点是一样的

相关代码

---

图结构

图论相关