15

我正在寻找一些用于商业/自由软件项目的树结构示例，无论是现代的还是旧的。我可以在 wikipedia 上看到示例，但我正在寻找更具体的示例以及它们的使用方式。例如，数据库中的主键（根据我的阅读）存储在 BST 结构或 BST 的变体中（请随时纠正我）

我的问题不限于二叉搜索树 (BST)，它可以包括任何变体，例如红黑、AVL 等。

4

17 回答 17

35

如果这些示例有点通用，即与图形相关而不一定与树相关，可以吗？如果是，请继续阅读。

  • 不用说大多数 XML/标记解析器都使用树。例如，参见 Apache Xerces。或者，Xalan XSLT 解析器。感谢mathewsdave26提醒我！

  • PDF 是一种基于树的格式。它有一个root节点，后跟一个catalog节点（它们通常是相同的），然后是一个pages具有多个子节点的page节点。生产者/消费者经常使用平衡树实现将文档存储在内存中。

  • 计算机国际象棋游戏构建了一个巨大的树（训练），他们在运行时使用启发式方法对其进行修剪以达到最佳移动。

  • Flare是一个用 AS 编写的可视化库。您可能想查看数据对象的映射方式。特别是该flare.analytics包大量使用了图形结构、生成树等。

  • 社交网络是当前 CS 研究中的流行语。不用说，连接/关系非常自然地使用图形建模。通常，树用于表示/识别更有趣的现象。你如何回答诸如“哈利和莎莉有共同的朋友吗？”之类的问题？

  • 一些非常成功的物理/游戏引擎会构建树木来准确模拟人体运动。在这种情况下，一棵树通常对应一组动作；上下文将确定采用哪条路径来呈现特定响应。

  • 基于决策树的学习实际上形成了数据挖掘研究的一个强大领域。存在许多著名的方法，例如 bagging、boosting 和它们的修改，它们适用于树。此类工作通常用于生成预测模型。

  • 生物信息学中的一个常见问题是搜索大型数据库以查找给定查询字符串的匹配项。尝试在那里很常见。

  • 相当多的成功（股票）交易者在他们的日常交易中使用决策树——选择交易，退出交易。很多时候，这些并没有编入计算机程序，而是写在笔记本背面的某个地方。

欺骗。看到这个和这个。

于 2009-02-23T13:40:50.057 回答
11

数据库索引 B* 树中的 B 代表平衡，而不是二进制。树保持在统一的深度以确保访问时间均匀。

于 2009-02-23T13:44:51.467 回答
7

  • 您的文件系统是一个树形结构。因此，请查看任何免费文件系统的源代码。

  • 您的编译器会从您的源代码生成一个AST，作为中间阶段。因此，请查看任何免费编译器的源代码。

于 2009-03-03T18:14:34.077 回答
6

数据库索引通常存储为 B* 树的变体，尽管它们的名称不是二叉树。

于 2009-02-23T13:40:35.487 回答
5

二叉树已被用于旧 3D 游戏中的空间分区和隐藏表面移除，我相信在游戏 Doom 中使用过二叉树。

于 2009-02-23T14:59:24.223 回答
4

  • 编写一个简单的递归下降解析器，并让它生成一个解析树。

  • 制造中使用的材料清单结构（就像汽车由子组件组成，递归地，直到螺母和螺栓）。

  • 符号表（在编译器中使用）。

  • 项目管理中使用的会计科目表。一个整体项目有子项目，可以对其进行收费。

  • 公司组织架构：事业部、部门等

  • 文档的目录。

  • 一个人的后裔，一个人的祖先。

  • 任何 Lisp s 表达式，包括任何 Lisp 程序。

于 2009-03-03T17:59:59.977 回答
3

软件中的自动完成功能（例如搜索引擎“建议”、IDE 类型/符号完成、电子邮件和地址簿名称等）通常作为树结构的 Tries 实现。

于 2009-03-03T20:31:47.273 回答
1

查看任何 Datawarehousing 产品，您都会发现存储和钻取树形维度的巧妙方法。您将获得位置（国家、地区、州、县、镇等）和时间（年、月、日、小时）的树结构。这两个维度在许多领域都很常见，但许多其他现实世界的数据也适用于树。

例如，在食品零售业中，在树的根部可以有杂货，可以深入到乳制品、水果和蔬菜等。只要一根线，你就可以拥有。豆罐头，在顶层，你会用卡车装载，然后你会下到托盘、盒子、罐头尺寸。所有不同的 SKU（库存单位）对商店或公司内的人都很重要。然后是不同类型的豆子、不同的供应商、制造商——所有相同维度的树的例子。

所有不同的产品形成一棵巨大的树，具有不同的切片和切丁方式。

于 2009-02-23T13:53:13.757 回答
1

C++ 包含许多集合（set、multi_set、map、multi_map），它们通常实现为红黑树，一种平衡树。

（C++ 标准没有明确要求这种实现，但这是满足复杂性要求的最简单的设计。）

于 2009-02-23T14:01:45.203 回答
1

在我以前工作的路由器/交换机地方，我们使用了一堆树结构，对于软件路由表，我们使用基数树（IP 路由表的常见选择）。

我们的 OSPF 实现使用了红黑树，我们的 BGP 实现使用了跳过列表。

从技术上讲，skiplists 不是树结构，但它们在实践中非常相似，而且它们真的很酷。

我们确实在考虑它时使用了很多堆，自从我在那里工作已经有一段时间了。

于 2009-02-26T13:13:21.503 回答
1

DNS查询..任何使用地图的东西都使用AVL

于 2009-03-02T21:49:22.853 回答
1

System.Collections.Generic.SortedList<T>使用二叉搜索树作为底层实现。System.Collections.GenericSortedDictionary<T>也是如此。任何使用 SortedList<T> 或 SortedDictionary<T> 的代码都使用二叉搜索树。

于 2009-03-03T16:35:39.587 回答
0

在我的项目中，一个调查/人口普查数据的编辑和估算系统，我们使用二叉决策树来决定记录的哪些变量要估算或不估算。二叉决策树允许我们有效地决定我们应该和不应该采取的树上的路径。

我认为这种方法（尽管可能不仅仅是二叉树）也用于人工智能应用程序

于 2009-02-23T14:30:49.970 回答
0

我们使用树结构来建模零件分类系统。零件被分类为具有父类的“类”等。顶级类驱动我们目录 UI 中选项卡的文本。类还用于应用定价规则，识别车辆上的“热点”，其中零件显示在“配置器”中，等等。我们使用 Joe Celko 的嵌套集在 SQL 中对树进行建模，并按需将它们加载到内存中以获得更好的效果表现。我们最常见的查询是“谁是我的后代”和“这个班级是我的祖先吗？”

非常便利

于 2009-03-03T18:19:30.477 回答
0

ActionScript 中实现了一个陷阱。资料来源：

treap 是AS3Commons Collections 框架的一部分。修改后的 treap 用于支持包含的 SortedSet 和 SortedMap 集合。

于 2010-02-05T08:36:05.163 回答
0

通常，对象的分类通常使用树来完成。很多时候，图比树更合适，但是树比图有两个很大的优势：

  • 它可以表示为（嵌套）列表。例如，在纸上（带有标题、副标题、段落和嵌套列表）或计算机屏幕上显示一棵大树比显示图表要容易得多。
  • 您可以使用简单的路径字符串（或堆栈）指向树中的一个项目，例如“http/StackOverflow.com/Users/Dimitri C”，这在图中很难做到。
于 2010-02-05T08:43:20.220 回答
0

Put yourself as the root of tree and now make your parents as children of tree and parents of parents as their children of tree and this can make a full use case of tree.

So implementing something where the complete hierarchy of family require you can use tree to implement that.

于 2018-04-29T17:48:16.910 回答