二叉树有哪些应用? [英] What are the applications of binary trees?

问题描述

我想知道二叉树的特殊应用是什么.你能举一些真实的例子吗?

I am wondering what the particular applications of binary trees are. Could you give some real examples?

推荐答案

对二叉树的性能进行争论是没有意义的-它们不是数据结构，而是一系列数据结构，所有具有不同的性能特征.确实，不平衡二叉树的搜索性能比自平衡二叉树差很多，但是有许多二叉树(例如二叉尝试)，其中平衡" 没有任何意义.

To squabble about the performance of binary-trees is meaningless - they are not a data structure, but a family of data structures, all with different performance characteristics. While it is true that unbalanced binary trees perform much worse than self-balancing binary trees for searching, there are many binary trees (such as binary tries) for which "balancing" has no meaning.

• 二进制搜索树-在许多搜索应用程序中用于数据不断进入/离开，例如许多语言库中的map和set对象.
• 二进制空间分区-几乎在每个3D视频游戏中用于确定需要放置哪些对象呈现.
• 二进制尝试-几乎在每个高带宽路由器中用于存储路由器表./li>
• 哈希树-用于p2p程序和专用的图像签名中，其中哈希需要进行验证，但整个文件不可用.
• 堆-用于实现有效的优先级队列，依次使用这些优先级队列用于在许多操作系统中调度进程，在路由器中提供服务质量以及A * (用于AI应用程序(包括机器人和视频游戏)的路径查找算法).也用于堆排序.
• 霍夫曼编码树( GGM树-在密码应用程序中用于生成密码伪随机数树.
• 语法树-由编译器和(隐式)计算器构造，用于解析表达式.
• 捕获-无线网络和内存分配中使用的随机数据结构.
• T树-尽管大多数数据库使用某种形式的B树来存储驱动器上的数据，将所有(大部分)数据保存在内存中的数据库通常使用T树来实现.

• Binary Search Tree - Used in many search applications where data is constantly entering/leaving, such as the map and set objects in many languages' libraries.
• Binary Space Partition - Used in almost every 3D video game to determine what objects need to be rendered.
• Binary Tries - Used in almost every high-bandwidth router for storing router-tables.
• Hash Trees - used in p2p programs and specialized image-signatures in which a hash needs to be verified, but the whole file is not available.
• Heaps - Used in implementing efficient priority-queues, which in turn are used for scheduling processes in many operating systems, Quality-of-Service in routers, and A* (path-finding algorithm used in AI applications, including robotics and video games). Also used in heap-sort.
• Huffman Coding Tree (Chip Uni) - used in compression algorithms, such as those used by the .jpeg and .mp3 file-formats.
• GGM Trees - Used in cryptographic applications to generate a tree of pseudo-random numbers.
• Syntax Tree - Constructed by compilers and (implicitly) calculators to parse expressions.
• Treap - Randomized data structure used in wireless networking and memory allocation.
• T-tree - Though most databases use some form of B-tree to store data on the drive, databases which keep all (most) their data in memory often use T-trees to do so.

二元树比n元树更常用于搜索的原因是n元树更复杂，但通常没有实际的速度优势.

The reason that binary trees are used more often than n-ary trees for searching is that n-ary trees are more complex, but usually provide no real speed advantage.

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

In a (balanced) binary tree with m nodes, moving from one level to the next requires one comparison, and there are log_2(m) levels, for a total of log_2(m) comparisons.

相反，一棵n元树将需要log_2(n)个比较(使用二进制搜索)才能进入下一个级别.由于总共有log_n(m)个级别，因此搜索将总共需要log_2(n)*log_n(m) = log_2(m)个比较.因此，尽管n元树比较复杂，但在进行必要的总比较方面却没有优势.

In contrast, an n-ary tree will require log_2(n) comparisons (using a binary search) to move to the next level. Since there are log_n(m) total levels, the search will require log_2(n)*log_n(m) = log_2(m) comparisons total. So, though n-ary trees are more complex, they provide no advantage in terms of total comparisons necessary.

(但是，n元树在特殊环境中仍然有用.想到的例子是

(However, n-ary trees are still useful in niche-situations. The examples that come immediately to mind are quad-trees and other space-partitioning trees, where divisioning space using only two nodes per level would make the logic unnecessarily complex; and B-trees used in many databases, where the limiting factor is not how many comparisons are done at each level but how many nodes can be loaded from the hard-drive at once)

这篇关于二叉树有哪些应用?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！