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


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
描述 一种树数据结构,其节点存储字母表中的字母。从根到叶的每条路径构成一个词。一个节点的所有后代共享一个与该节点关联的公共前缀。
用途:
  • - 用于自动完成文字系统
  • - 用于实现拼写检查
  • - 用于解决文字游戏