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

发布网友发布时间：2022-04-21 19:22

共1个回答

热心网友时间：2022-07-13 06:22

数据结构的算法，并没有多少种算法，关于树，其实都是对DOM, AST 等应用，对人脑分层分类认知的建模,。树的一个大类是自平衡二叉搜索树 (self-balanced BST), 变种特别多:RB 树是每个节点是红色或者黑色, 颜色隔代遗传AVL 树是每个节点包含平衡因子, 等于左高-右高Splay 树是每个节点带个父节点的指针

Treap 是每个节点都带个随机的 priority number, parent priority >= child priority

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 载入, 也是用了很多压缩技巧的复杂实现, 就是构建比较花时间, 也不能动态更新。

总的来说，只要有序列的地方就可以应用树，因为树结构即是一种序列索引结构。序列的核心接口就是三个cha：插、查、X。