binary-tree - 二叉树有哪些应用？

Question

我想知道二叉树的具体应用是什么。你能举一些真实的例子吗？

Answer 1

争论二叉树的性能是没有意义的——它们不是一种数据结构，而是一系列数据结构，都具有不同的性能特征。虽然不平衡二叉树的搜索性能确实比自平衡二叉树差很多，但有很多二叉树(例如二叉树) em> 对于其中“平衡”没有任何意义。

二叉树的应用

• Binary Search Tree - 用于许多数据不断进入/离开的搜索应用程序，例如许多语言库中的map和set对象。<
• Binary Space Partition - 几乎在所有 3D 视频游戏中都使用它来确定需要渲染哪些对象。
• Binary Tries - 几乎在每个高带宽路由器中用于存储路由器表。
• Hash Trees - 用于种子和专门的图像签名，其中需要验证散列，但整个文件不可用。也用于区 block 链，例如。比特币。
• Heaps - 用于实现高效的优先级队列，而优先级队列又用于许多操作系统中的调度进程、路由器中的服务质量以及 A* (人工智能应用中使用的路径查找算法，包括机器人和视频游戏)。也用于堆排序。
• Huffman Coding Tree ( Chip Uni ) - 用于压缩算法，例如 .jpeg 和 .mp3 文件格式使用的算法。
• GGM Trees - 在加密应用程序中用于生成伪随机数树。
• Syntax Tree - 由编译器和(隐式)计算器构造来解析表达式。
• Treap - 用于无线网络和内存分配的随机数据结构。
• T-tree - 虽然大多数数据库使用某种形式的 B 树在驱动器上存储数据，但将所有(大部分)数据保存在内存中的数据库通常使用 T 树来实现这一点。

<小时/>

二叉树比 n 叉树更常用于搜索的原因是 n 叉树更复杂，但通常无法提供真正的速度优势。

在具有 m 个节点的(平衡)二叉树中，从一个级别移动到下一个级别需要一次比较，并且有 log_2(m) 个级别，对于总共 log_2(m) 次比较。

相比之下，n 叉树将需要 log_2(n) 比较(使用二分搜索)才能移动到下一个级别。由于总共有 log_n(m) 个级别，因此搜索需要 log_2(n)*log_n(m) = log_2(m) 比较全部的。因此，尽管 n 叉树更复杂，但它们在必要的总比较方面没有提供任何优势。

(但是，n 叉树在特定情况下仍然有用。立即想到的例子是 quad-trees 和其他空间划分树，其中每层仅使用两个节点来划分空间将使得逻辑不必要地复杂；并且 B-trees 在许多数据库中使用，其中限制因素不是每个级别进行多少次比较，而是一次可以从硬盘驱动器加载多少个节点)