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

查看:172
本文介绍了二叉树有哪些应用?的处理方法,对大家解决问题具有一定的参考价值,需要的朋友们下面随着小编来一起学习吧!

问题描述

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

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.

  • 二进制搜索树-在许多搜索应用程序中用于数据不断进入/离开,例如许多语言库中的mapset对象.
  • 二进制空间分区-几乎在每个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屋!

查看全文
登录 关闭
扫码关注1秒登录
发送“验证码”获取 | 15天全站免登陆