值得了解的九种树形数据结构 - Franco

值得了解的九种树形数据结构 - Franco

Franco总结了九种常见的树形数据结构 ：

• binary search tree
• red-black tree
• generic tree
• binary tree
• splay tree
• AVL tree
• B-tree
• Treap

通用树

表示不同节点之间关系的分层数据结构。它可以不包含节点或 1 个具有 0 个或多个子树的特殊节点（根）。每个节点只有 1 个父节点，但可以有多个子节点。

• 层次结构没有限制。
• 通常可存储任何分层数据（即文件夹结构）

二叉树

描述树数据结构，其中一个节点最多可以有 2 个子节点。节点的孩子被称为左孩子和右孩子。

• 由编译器用于构建语法树 
• 用于实现表达式解析和评估 
• 用于在网络中存储路由表链接路由器
• 用于数据压缩编码算法

二叉搜索树

具有唯一属性的二叉树的受限扩展。给定一个节点，其左子节点的值小于或等于父节点的值。其右孩子的值大于或等于父值。

• 用于实现简单的排序算法
• 用于维护已排序的数据流
• 用于实现双端优先级队列
• 用于数据不断进入和离开的搜索应用程序

AVL 树

描述一种自平衡二叉搜索树。每个节点都关联了一个值，表示其左右子树之间的高度差。操作后，如果这些差值大于 1，则执行旋转以平衡树。

• - 用于需要在树中频繁插入的每种情况
• - 在 Linux 内核的内存管理子系统中用于在抢占期间搜索进程的内存区域

红黑树 

描述自平衡二叉搜索树。每个节点要么是红色，要么是黑色。根和叶是黑色的。如果一个节点是红色的，它的两个孩子都是黑色的。从给定节点到任何叶子的每条路径都必须具有相同数量的黑色节点。

• - 用于计算几何以降低算法的时间复杂度
• - 用于在 Linux 中实现 CPU 进程调度程序
• - 用于关联数据结构的各种实现（即 C++ 映射、集合、Java HashMap）

展开splay树 

描述一种自平衡二叉搜索树。最近访问的节点可以快速再次访问。在插入或搜索之后，称为 splaying 的操作重新排列树（使用旋转），以便将涉及的元素作为根放置。

• - 用于实现缓存
• - 用于垃圾收集器
• - 用于数据压缩

Treap

描述混合堆和树的二叉搜索树。每个节点都有一个键和一个优先级。键遵循二叉搜索树属性。优先级（通常是随机值）遵循堆属性。

• - 用于维护基于非对称加密的应用程序中的授权证书
• - 用于执行快速设置操作（即联合、相交）

B 树

描述包含多个节点的自平衡搜索树，这些节点按排序顺序保存数据。每个节点有 n 个键（按升序存储）和 n+1 个子节点。键分离了存储在每个子树中的键的范围

• - 用于数据库索引以加快搜索
• - 用于文件系统以实现目录

Trie

描述 一种树数据结构，其节点存储字母表中的字母。从根到叶的每条路径构成一个词。一个节点的所有后代共享一个与该节点关联的公共前缀。

• - 用于自动完成文字系统
• - 用于实现拼写检查
• - 用于解决文字游戏