数据结构与算法中，树一般会应用在哪些方面？为什么？ 第1页

DOM, AST 等应用都是对人脑分层分类认知的建模, 都是树, 不过其中没多少算法可以讲...

------

树的一个大类是自平衡二叉搜索树 (self-balanced BST), 变种特别多:

• RB 树是每个节点是红色或者黑色, 颜色隔代遗传
  
• AVL 树是每个节点包含平衡因子, 等于左高-右高
  
• Splay 树是每个节点带个父节点的指针
  
• Treap 是每个节点都带个随机的 priority number, parent priority >= child priority
  

... (其实说白了都是为了方便平衡操作给节点附加一个字段)

自平衡二叉搜索树在面试中经常出现, 但做网页的互联网码农却很少用得上... 如果是当 Map 用, 往往还不如直接上哈希表. 如果是当排序用, 不如直接用排序算法... 不过也有有用的时候, 例如查找一个数字的上下界.

------

树的另一个大类是 Trie, 特点是能保证字典序, 存储词典的空间压缩率高, 能做前缀搜索. 在正则匹配, 数据压缩, 构建索引都可能用到. Trie 也有不少变种:

• Double Array - trie 的一个经典实现 (这实现其实不算树, 也不适合处理非 ascii 字符的情况)
  
• Patricia Trie (Radix-Tree) - 每个节点可以存一段字符串而不限于一个字符
  
• Judy Array - 基于 256-ary radix tree, 用了 20 种压缩方式, 极其复杂...
  
• Burst Trie - 如果一个子树足够小, 就用 binary 堆的方式存储, 不过压缩效果一般
• HAT Trie - 压缩率高而且不容易出现 CPU cache miss, 查速接近哈希表而耗内存少得多. 节点可以是以下三种之一: Array Hash, 序列化的 Bucket, 传统 Trie node
  
• MARISA Trie - 压缩率最高, 支持 mmap 载入, 也是用了很多压缩技巧的复杂实现, 就是构建比较花时间, 也不能动态更新
  

------

Clojure 是伴随着不少 persistent (immutable) data structure 而出现的, 尤其是考虑到 Immutable 的数据结构的时候, 树好像就变成了你的唯一选择... immutable 的树也是天生方便并行操作的.

• HAMT 的技巧是利用 CPU 指令 popcnt 做快速的小表查询, 实现了 immutable 哈希表/动态数组
  
• RRB tree 实现了 immutable 的动态数组, 实现更复杂一点, 去掉了 n-way 的限制
  

------

还有各种各样的树, 例如空间索引就有几十种变种, 举不动了...