数据结构摘要

只有重点、简洁的介绍，方便查阅！

数据结构可视化网站：部分结构如树，点击后需要手动添加节点，且能看到其变化的过程。
另一个可视化数据结构和算法的网站：visualgo.net/zh

树

树是由根节点和若干颗子树构成。
每个节点都只有有限个子节点或无子节点。
没有父节点的节点称为根节点。没有子节点的节点称为叶子节点。
树的深度/高度：根节点到最远叶子节点的最长路径上的节点数。

二叉树

每个节点最多只有两个子节点的树。

满二叉树

树中的每个节点仅包含 0 或 2 个子节点。

完全二叉树

除最后一层外，每一层上的结点数均达到最大值；在最后一层上只缺少右边的若干结点。
重要性质：
1. 在二叉树上的第i层上至多有 $2^{i-1}, i>=1$个节点。
2. 深度为k的二叉树至多有 $2^k-1, k >= 1$个节点。
3. 具有n个节点的完全二叉树的深度为 floor{ log2(n) } + 1 。
对一颗具有n个节点的完全二叉树中的节点从0开始按层序编号，对任意节点i：
- 其父节点编号为：floor{ (i-1)/2 }
- 若2i < n-1，则其左孩子编号为：2i + 1
对一颗具有n个节点的完全二叉树中的节点从1开始按层序编号，对任意节点i：
- 其父节点编号为：floor{ i/2 }
- 若2i < n，则其左孩子编号为：2i
- 为便于计算，推荐从1开始（数组的第0位不用）。

完美二叉树

二叉树中的每个节点（除叶子节点外）都拥有两个子节点，并且具有相同的高度。

二叉搜索树

二叉搜索树又称二叉排序树、二叉查找树，简统称BST。
一种特殊的二叉树，其任何节点中的值都会大于等于其左子节点并且小于等于其右子节点。

二叉平衡树

它可以是一颗空树，或者具有以下性质的二叉排序树：它的左子树和右子树的高度之差的绝对值不超过1且它的左子树和右子树都是一颗平衡二叉树。
平衡二叉树查询、插入、删除的时间复杂度都是 O(logN)。

但是平衡二叉树也不是完美的，AVL树最大的缺点就是删除节点时有可能因为失衡，导致需要从删除节点的父节点开始，不断的回溯到根节点，如果这棵AVL树很高的话，那中间就要判断很多个节点，效率就显然变的低下！

红黑树

红黑树是一种含有红黑结点并能自平衡的二叉查找树，也是一种弱二叉平衡树，弱是指红黑树不是严格平衡的。二叉平衡树的左子树和右子树的高度之差的绝对值不超过1，但红黑树在某些时刻可能会超过1，只要符合红黑树的五个条件即可。

性质1：每个节点要么是黑色，要么是红色。
性质2：根节点是黑色。
性质3：每个叶子节点（NIL）是黑色。
性质4：每个红色结点的两个子结点一定都是黑色。
性质5：任意一结点到每个叶子结点的路径都包含数量相同的黑结点。
- 性质5.1：如果一个结点存在黑子结点，那么该结点肯定有两个子结点。

红黑树和二叉平衡树的区别：

红黑树放弃了追求完全平衡，追求大致平衡，在与平衡二叉树的时间复杂度相差不大的情况下，保证每次插入最多只需要三次旋转就能达到平衡，实现起来也更为简单。
平衡二叉树追求绝对平衡，条件比较苛刻，实现起来比较麻烦，每次插入新节点之后需要旋转的次数不能预知。

字典树（Trie树，前缀树）

从根节点到某一个节点，路过的字符连起来就是该节点对应的字符串。
利用字符串的公共前缀来减少查询时间，最大限度地减少无谓的字符串比较，查询效率比哈希树高。
常用于搜索提示。如当输入部分内容，可以自动搜索出可能的选择。

栈

后进先出

单调栈

要求是每次入栈的元素必须要有序（如果新元素入栈不符合要求，则将之前的元素出栈，直到符合要求再入栈），使之形成单调递增/单调递减的一个栈。
单调递增栈：只有比栈顶小的才能入栈，否则就把栈顶出栈后，再入栈。出栈时可能会有一些计算。适用于求解第一个大于该位置元素的数。
单调递减栈：与单调递增栈相反。适用于求解第一个小于该位置元素的数。
哨兵技巧：例如在 {1, 3, 4, 5, 2, 9, 6} 末尾添加一个 -1 作为哨兵，变成了 {1, 3, 4, 5, 2, 9, 6, -1} ，这种技巧可以简化代码逻辑。

队列

先进先出

优先队列

优先队列一般使用二叉堆实现。

堆

堆总是一棵完全二叉树，用数组存储，根据完全二叉树的性质可以很方便地找到某个节点的子节点或父节点的下标。
堆中某个结点的值总是不大于或不小于其父结点的值。
堆排序。

大顶堆（大根堆）

堆中某个结点的值总是不大于其父结点的值；根节点的值最大！

小顶堆（小根堆）

堆中某个结点的值总是不小于其父结点的值；根节点的值最小！