Skip to main content

线段树、字典树和并查集

· 4 min read
Zeffon Wu

线段树、字典树和并查集

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 字典树

  1. 字典树是一种有序树,用于保存关联数组,其中的键通常是字符串
  2. 字典树与二叉查找树不同,不是直接保存在节点中,而是由节点在树中的位置决定。
  3. 一个节点的所有子孙都有相同的前缀,也就是这个节点对应的字符串,而根节点对应空字符串。一般情况下,不是所有的节点都有对应的值,只有叶子节点部分内部节点所对应的键才有相关的值。
  4. trie 树常用于搜索提示。如当输入一个网址,可以自动搜索出可能的选择。当没有完全匹配的搜索结果,可以返回前缀最相似的可能。

UnionFind 并查集

  1. 在计算机科学中,并查集是一种树型的数据结构,用于处理一些不交集(Disjoint Sets)的合并及查询问题。
  2. 对一组数据,主要支持两个动作 :
  • Union(p, q):将两个子集合并成同一个集合。
  • isConnected(p, q):查询给定两个元素他们是否属于同一个集合。它可以被用来确定两个元素是否属于同一子集。

参考文献