Franco总结了九种常见的树形数据结构 :
- binary search tree
- red-black tree
- generic tree
- binary tree
- splay tree
- AVL tree
- B-tree
- Treap
- Trie
通用树
表示不同节点之间关系的分层数据结构。它可以不包含节点或 1 个具有 0 个或多个子树的特殊节点(根)。每个节点只有 1 个父节点,但可以有多个子节点。
用途:
- 层次结构没有限制。
- 通常可存储任何分层数据(即文件夹结构)
二叉树
描述树数据结构,其中一个节点最多可以有 2 个子节点。节点的孩子被称为左孩子和右孩子。
用途:
- 由编译器用于构建语法树
- 用于实现表达式解析和评估
- 用于在网络中存储路由表链接路由器
- 用于数据压缩编码算法
二叉搜索树
具有唯一属性的二叉树的受限扩展。给定一个节点,其左子节点的值小于或等于父节点的值。其右孩子的值大于或等于父值。
用途:
- 用于实现简单的排序算法
- 用于维护已排序的数据流
- 用于实现双端优先级队列
- 用于数据不断进入和离开的搜索应用程序
AVL 树
描述一种自平衡二叉搜索树。每个节点都关联了一个值,表示其左右子树之间的高度差。操作后,如果这些差值大于 1,则执行旋转以平衡树。
用途:
- - 用于需要在树中频繁插入的每种情况
- - 在 Linux 内核的内存管理子系统中用于在抢占期间搜索进程的内存区域
红黑树
描述自平衡二叉搜索树。每个节点要么是红色,要么是黑色。根和叶是黑色的。如果一个节点是红色的,它的两个孩子都是黑色的。从给定节点到任何叶子的每条路径都必须具有相同数量的黑色节点。
用途:
- - 用于计算几何以降低算法的时间复杂度
- - 用于在 Linux 中实现 CPU 进程调度程序
- - 用于关联数据结构的各种实现(即 C++ 映射、集合、Java HashMap)
展开splay树
描述一种自平衡二叉搜索树。最近访问的节点可以快速再次访问。在插入或搜索之后,称为 splaying 的操作重新排列树(使用旋转),以便将涉及的元素作为根放置。
用途:
- - 用于实现缓存
- - 用于垃圾收集器
- - 用于数据压缩
Treap
描述混合堆和树的二叉搜索树。每个节点都有一个键和一个优先级。键遵循二叉搜索树属性。优先级(通常是随机值)遵循堆属性。
用途:
- - 用于维护基于非对称加密的应用程序中的授权证书
- - 用于执行快速设置操作(即联合、相交)
B 树
描述包含多个节点的自平衡搜索树,这些节点按排序顺序保存数据。每个节点有 n 个键(按升序存储)和 n+1 个子节点。键分离了存储在每个子树中的键的范围
用途:
- - 用于数据库索引以加快搜索
- - 用于文件系统以实现目录
Trie
描述 一种树数据结构,其节点存储字母表中的字母。从根到叶的每条路径构成一个词。一个节点的所有后代共享一个与该节点关联的公共前缀。
用途:
- - 用于自动完成文字系统
- - 用于实现拼写检查
- - 用于解决文字游戏