线段树、字典树和并查集
线段树、字典树和并查集
Segment Tree 线段树
- 线段树也称区间树。字典树是多叉树，也称为前缀树。并查集是一种树型的数据结构。
- 线段树就是对于一棵
二叉树，每一个节点其实存储的是每一个线段或者是一个区间相应的信息。 - 线段树
不是完全二叉树，线段树是平衡二叉树，堆也是平衡二叉树。
完全二叉树
本身就是平衡二叉树。平衡二叉树概念: 对于整棵树来说，最大的深度和最小的深度他们之间的差最多只有可能为1。
- 经典的线段树问题：
区间染色、区间查询。用数组来实现这两个问题的话，更新和查询都是O(n)，而线段树则是O(log n)。 - 区间有 n 个元素，用数组表示的话需要
4n的空间来存储。
0层：1
1层：2
2层：4 对于满二叉树：
3层：8 h层，一共有2^h-1节点(大约是2^h)
... 最后一层(h-1层)，有2^(h-1)个节点
h-1层：2^(h-1) 最后一层的节点数大致等于前面所有层节点之和
如果n=2^k(满二叉树) 只需要2n的空间
最坏的情况，如果n=2^k+1 需要4n的空间
Trie 字典树
- 字典树是一种
有序树，用于保存关联数组，其中的键通常是字符串。 - 字典树与
二叉查找树不同，键不是直接保存在节点中，而是由节点在树中的位置决定。 - 一个节点的所有子孙都有
相同的前缀，也就是这个节点对应的字符串，而根节点对应空字符串。一般情况下，不是所有的节点都有对应的值，只有叶子节点和部分内部节点所对应的键才有相关的值。 - trie 树常用于
搜索提示。如当输入一个网址，可以自动搜索出可能的选择。当没有完全匹配的搜索结果，可以返回前缀最相似的可能。
UnionFind 并查集
- 在计算机科学中，并查集是一种
树型的数据结构，用于处理一些不交集（Disjoint Sets）的合并及查询问题。 - 对一组数据，主要支持
两个动作:
- Union(p, q)：将两个子集
合并成同一个集合。 - isConnected(p, q)：查询给定两个元素他们是否属于同一个集合。它可以被用来确定两个元素是否属于同一子集。