我想知道二叉树的具体应用是什么 . 你能举一些真实的例子吗？
在C STL中，还有许多其他语言的标准库，如Java和C＃ . 二叉搜索树用于实现集合和映射 .
争论二进制树的性能是没有意义的 - 它们不是数据结构，而是一系列数据结构，都具有不同的性能特征 . 虽然不 balancer 二叉树确实比自 balancer 二叉树执行搜索要糟糕得多，但是有许多二元树（例如二进制尝试），其中"balancing"没有任何意义 .
Binary Search Tree - 用于许多不断进入/离开数据的搜索应用程序，例如许多语言库中的 map 和 set 对象 .
map
set
Binary Space Partition - 几乎在每个3D视频游戏中用于确定需要渲染的对象 .
Binary Tries - 几乎在每个高带宽路由器中用于存储路由器表 .
Hash Trees - 用于需要验证哈希的p2p程序和专用图像签名，但整个文件不可用 .
Heaps - 用于实现高效的优先级队列，后者又用于调度许多操作系统中的进程，路由器中的服务质量和A *（AI应用程序中使用的路径查找算法，包括机器人和视频游戏） ） . 也用于堆排序 .
Huffman Coding Tree（Chip Uni） - 用于压缩算法，例如.jpeg和.mp3文件格式使用的算法 .
GGM Trees - 在加密应用程序中用于生成伪随机数树 .
Syntax Tree - 由编译器和（隐式）计算器构造来解析表达式 .
Treap - 无线网络和内存分配中使用的随机数据结构 .
T-tree - 虽然大多数数据库使用某种形式的B树来存储驱动器上的数据，但是将所有（大多数）数据保存在内存中的数据库通常使用T树来执行此操作 .
二元树比n-ary树更常用于搜索的原因是n-ary树更复杂，但通常没有提供真正的速度优势 .
在具有 m 节点的（ balancer ）二叉树中，从一个级别移动到下一个级别需要一个比较，并且有 log_2(m) 个级别，总共 log_2(m) 个比较 .
m
log_2(m)
相反，n-ary树将需要 log_2(n) 比较（使用二分搜索）移动到下一级别 . 由于总共有 log_n(m) 个级别，因此搜索将需要 log_2(n)*log_n(m) = log_2(m) 比较总计 . 因此，虽然n-ary树更复杂，但它们在必要的总比较方面没有任何优势 .
log_2(n)
log_n(m)
log_2(n)*log_n(m)
（然而，n-ary树在利基情况下仍然有用 . 立即想到的例子是quad-trees和其他空间分区树，其中每个级别仅使用两个节点的分区空间将使逻辑不必要地复杂;并且B-trees使用在许多数据库中，限制因素不是每个级别进行多少次比较，而是一次可以从硬盘驱动器加载多少个节点）
当大多数人谈论二叉树时，他们往往不会考虑二元搜索树，所以我将首先介绍它 .
非 balancer 二叉搜索树实际上对于教育学生数据结构只是有用的 . 这是因为，除非数据以相对随机的顺序进入，否则树很容易退化为最坏情况形式，这是一个链表，因为简单的二叉树不 balancer .
一个很好的例子：我曾经不得不修复一些将其数据加载到二叉树中进行操作和搜索的软件 . 它以排序的形式写出数据：
Alice Bob Chloe David Edwina Frank
因此，当重新阅读时，最后得到以下树：
Alice / \ = Bob / \ = Chloe / \ = David / \ = Edwina / \ = Frank / \ = =
这是堕落的形式 . 如果你在那棵树上寻找弗兰克，你必须在找到他之前搜索所有六个节点 .
当您 balancer 它们时，二叉树变得非常有用 . 这涉及通过其根节点旋转子树，以便任何两个子树之间的高度差小于或等于1.将这些名称一次一个地添加到 balancer 树中将为您提供以下序列：
1. Alice / \ = =
2. Alice / \ = Bob / \ = =
3. Bob _/ \_ Alice Chloe / \ / \ = = = =
4. Bob _/ \_ Alice Chloe / \ / \ = = = David / \ = =
5. Bob ____/ \____ Alice David / \ / \ = = Chloe Edwina / \ / \ = = = =
6. Chloe ___/ \___ Bob Edwina / \ / \ Alice = David Frank / \ / \ / \ = = = = = =
实际上，当添加条目时，您可以看到整个子树向左旋转（在步骤3和6中），这为您提供了一个 balancer 的二叉树，其中最坏情况查找是 O(log N) 而不是简并形式给出的 O(N . 在任何时候，最高NULL（ = ）与最低值相差多于一个级别 . 而且，在上面的最后一棵树中，你可以通过仅查看三个节点（ Chloe ， Edwina ，最后是 Frank ）找到Frank .
O(log N)
O(N
=
Chloe
Edwina
Frank
当然，当你制作 balancer 的多路树而不是二元树时，它们会变得更有用 . 这意味着每个节点包含多个项目（从技术上讲，它们包含N个项目和N 1指针，二叉树是单向多路树的一个特例，有1个项目和2个指针） .
使用三向树，您最终得到：
Alice Bob Chloe / | | \ = = = David Edwina Frank / | | \ = = = =
这通常用于维护项目索引的键 . 我编写了针对硬件优化的数据库软件，其中节点的大小与磁盘块的大小完全相同（例如，512字节），并且您可以将尽可能多的密钥放入单个节点中 . 在这种情况下，指针实际上是记录数字到与索引文件分开的固定长度记录直接访问文件中（因此只需寻找 X * record_length 就可以找到记录号 X ） .
X * record_length
X
例如，如果指针是4个字节并且密钥大小是10，则512字节节点中的密钥数是36.这是36个密钥（360个字节）和37个指针（148个字节），总共508个字节每个节点浪费4个字节 .
多路密钥的使用引入了两阶段搜索的复杂性（多路搜索找到正确的节点结合小的顺序（或线性二进制）搜索以找到节点中的正确密钥）但优势在于减少磁盘I / O比弥补这一点要多 .
我认为没有理由为内存结构做这件事，你最好坚持使用 balancer 的二叉树并保持代码简单 .
另外请记住， O(log N) 使用多路树将十五个人存储在地址簿中的优势，它可以存储过去十年来您的十万个客户的每个订单 .
大O符号的重点在于表明当_743242接近无穷大时会发生什么 . 有些人可能不同意，但只要没有别的东西可以随时可用，确保数据集保持在一定的范围内:-)
至于二叉树的其他用途，有很多，例如：
二进制堆，其中较高的键高于或等于较低的键而不是左侧（或低于或等于和等于）;
哈希树，类似于哈希表;
用于编译计算机语言的抽象语法树;
用于压缩数据的霍夫曼树;
为网络流量路由树 .
鉴于我为搜索树生成了多少解释，我不愿详细讨论其他问题，但如果您愿意，这应该足以研究它们 .
二叉树是树数据结构，其中每个节点最多具有两个子节点，通常被区分为“左”和“右” . 具有子节点的节点是父节点，子节点可以包含对其父节点的引用 . 在树之外，通常会引用“根”节点（所有节点的祖先）（如果存在） . 可以通过从根节点开始并反复跟随对左子节点或右子节点的引用来到达数据结构中的任何节点 . 在二叉树中，每个节点的度数最大为2 .
二叉树很有用，因为正如您在图片中看到的那样，如果要在树中找到任何节点，则只需要查看最多6次 . 例如，如果要搜索节点24，则应从根目录开始 .
根的值为31，大于24，因此您转到左侧节点 .
左侧节点的值为15，小于24，因此您转到右侧节点 .
右侧节点的值为23，小于24，因此您转到右侧节点 .
右侧节点的值为27，大于24，因此您转到左侧节点 .
左侧节点的值为25，大于24，因此您转到左侧节点 .
节点的值为24，这是我们要查找的密钥 .
此搜索如下所示：
您可以看到，您可以在第一次传递时排除整个树的一半节点 . 第二个是左子树的一半 . 这使得搜索非常有效 . 如果这是在40亿个元素上完成的，那么你最多只能搜索32次 . 因此，树中包含的元素越多，搜索效率就越高 .
删除可能会变得复杂 . 如果节点有0或1个子节点，那么只需移动一些指针即可排除要删除的节点 . 但是，您无法轻松删除包含2个子节点的节点 . 所以我们采取捷径 . 假设我们想要删除节点19 .
由于试图确定左右指针的移动位置并不容易，因此我们找到一个用它来代替它 . 我们去左侧的子树，尽可能向右走 . 这为我们提供了我们想要删除的节点的下一个最大 Value .
现在我们复制除了左右指针之外的所有18个内容，并删除原始的18个节点 .
为了创建这些图像，我实现了一个AVL树，一个自 balancer 树，这样在任何时间点，树在叶节点（没有子节点的节点）之间至多有一个级别的差异 . 这使树不会变得歪斜保持最大 O(log n) 搜索时间，插入和删除所需的时间稍长 .
O(log n)
这是一个示例，展示了我的AVL树如何保持自己尽可能紧凑和 balancer .
在排序数组中，查找仍然需要 O(log(n)) ，就像树一样，但随机插入和删除将需要O（n）而不是树的 O(log(n)) . 一些STL容器使用这些性能特性，因此插入和移除时间最多为 O(log n) ，这非常快 . 其中一些容器是 map ， multimap ， set 和 multiset .
O(log(n))
multimap
multiset
可以在http://ideone.com/MheW8找到AVL树的示例代码
Morse code的组织是二叉树 .
主要应用是binary search trees . 这些是一种数据结构，其中搜索，插入和删除都非常快（关于 log(n) 操作）
log(n)
在Huffman coding中使用二进制树，它们用作压缩代码 .
二进制树在Binary search trees中使用，这对于维护数据记录非常有用，而没有太多额外空间 .
未提及的二叉树的一个有趣示例是递归计算的数学表达式 . 从实际的角度来看，它基本上是无用的，但它是一种思考这种表达的有趣方式 .
基本上，树的每个节点都有一个值本身固有的值，或者通过对其子节点值进行操作来递归计算 .
例如，表达式 (1+3)*2 可以表示为：
(1+3)*2
* / \ + 2 / \ 1 3
为了评估表达式，我们要求父级的值 . 该节点依次从其子节点，加号运算符和仅包含“2”的节点获取其值 . 加号运算符依次从值为“1”和“3”的子项获取其值并将它们相加，并将4返回到乘法节点，该节点返回8 .
这种二叉树的使用在某种意义上类似于反向抛光符号，因为执行操作的顺序是相同的 . 还有一点需要注意的是，它不一定必须是二叉树，它只是最常用的运算符是二进制 . 在最基本的层面上，这里的二叉树实际上只是一种非常简单的纯函数式编程语言 .
最常见的应用之一是以有序的形式有效地存储数据，以便快速访问和搜索存储的元素 . 例如，C标准库中的 std::map 或 std::set .
std::map
std::set
作为数据结构的二叉树对表达式解析器和表达式求解器的各种实现很有用 .
它还可以用于解决一些数据库问题，例如索引 .
通常，二叉树是特定的基于树的数据结构的一般概念，并且可以构造具有不同属性的各种特定类型的二叉树 .
二叉树的应用：
Implementing routing table in router .
Data compression code
Implementation of Expression parsers and expression solvers
To solve database problem such as indexing .
Expression evaluation
我不认为"pure"二进制树有任何用处 . （除了教育目的） balancer 二叉树，例如Red-Black trees或AVL trees更有用，因为它们保证O（logn）操作 . 正常的二叉树可能最终成为一个列表（或几乎列表），并且在使用大量数据的应用程序中并不真正有用 .
balancer 树通常用于实现 Map 或集合 . 它们也可以用于O（nlogn）中的排序，即使存在更好的方法 .
也可以使用搜索/插入/删除Hash tables，它通常具有比二叉搜索树更好的性能（ balancer 或不 balancer ） .
如果需要搜索/插入/删除和排序，那么（ balancer 的）二进制搜索树将有用的应用程序将是有用的 . 给定一个现成的 balancer 树，Sort可以就地（几乎忽略递归所需的堆栈空间） . 它仍然是O（nlogn）但是具有较小的常数因子并且不需要额外的空间（除了新数组之外，假设数据必须放入数组中） . 另一方面，哈希表无法排序（至少不能直接排序） .
也许它们在一些复杂的算法中也很有用，但是我没有想到什么 . 如果我找到更多，我将编辑我的帖子 .
其他树如f.e. B+trees广泛用于数据库
二叉树最重要的应用之一是 balanced 二进制搜索树，如：
Red-Black trees
AVL trees
Scapegoat trees
这些类型的树具有这样的特性：通过在每次插入或删除节点时执行诸如旋转之类的操作，左子树和右子树的高度差保持较小 .
因此，树的总高度保持为log n和操作的顺序例如，在O（log n）时间内执行节点的搜索，插入和删除 . C的STL也以集合和映射的形式实现这些树 .
它们可以用作快速排序数据的方法 . 将数据插入O（log（n））的二叉搜索树中 . 然后遍历树以对它们进行排序 .
您的程序语法，或者就此而言，可以使用二叉树（尽管不一定）解析许多其他事物，例如自然语言 .
java.util.Set 的实现
java.util.Set
在现代硬件上，由于缓存和空间行为不良，二叉树几乎总是次优的 . 这也适用于（半） balancer 变体 . 如果你找到它们，那就是性能不计算（或者由比较函数支配），或者更有可能出于历史或无知的原因 .
使用二叉树表示AST的编译器可以使用已知的算法来解析像后序的树一样 . 编程人员不需要提出它自己的算法 . 因为源文件的二叉树高于n-ary树，所以它的构建需要更多时间 . 采取这个 生产环境 ：selstmnt：=“if”“（”expr“）”stmnt“ELSE”stmnt在二叉树中它将有3个级别的节点，但是n-ary树将有1个级别（chids）
这就是为什么基于Unix的操作系统很慢的原因 .
17 回答
在C STL中，还有许多其他语言的标准库，如Java和C＃ . 二叉搜索树用于实现集合和映射 .
争论二进制树的性能是没有意义的 - 它们不是数据结构，而是一系列数据结构，都具有不同的性能特征 . 虽然不 balancer 二叉树确实比自 balancer 二叉树执行搜索要糟糕得多，但是有许多二元树（例如二进制尝试），其中"balancing"没有任何意义 .
二叉树的应用
Binary Search Tree - 用于许多不断进入/离开数据的搜索应用程序，例如许多语言库中的
map和set对象 .Binary Space Partition - 几乎在每个3D视频游戏中用于确定需要渲染的对象 .
Binary Tries - 几乎在每个高带宽路由器中用于存储路由器表 .
Hash Trees - 用于需要验证哈希的p2p程序和专用图像签名，但整个文件不可用 .
Heaps - 用于实现高效的优先级队列，后者又用于调度许多操作系统中的进程，路由器中的服务质量和A *（AI应用程序中使用的路径查找算法，包括机器人和视频游戏） ） . 也用于堆排序 .
Huffman Coding Tree（Chip Uni） - 用于压缩算法，例如.jpeg和.mp3文件格式使用的算法 .
GGM Trees - 在加密应用程序中用于生成伪随机数树 .
Syntax Tree - 由编译器和（隐式）计算器构造来解析表达式 .
Treap - 无线网络和内存分配中使用的随机数据结构 .
T-tree - 虽然大多数数据库使用某种形式的B树来存储驱动器上的数据，但是将所有（大多数）数据保存在内存中的数据库通常使用T树来执行此操作 .
二元树比n-ary树更常用于搜索的原因是n-ary树更复杂，但通常没有提供真正的速度优势 .
在具有
m节点的（ balancer ）二叉树中，从一个级别移动到下一个级别需要一个比较，并且有log_2(m)个级别，总共log_2(m)个比较 .相反，n-ary树将需要
log_2(n)比较（使用二分搜索）移动到下一级别 . 由于总共有log_n(m)个级别，因此搜索将需要log_2(n)*log_n(m)=log_2(m)比较总计 . 因此，虽然n-ary树更复杂，但它们在必要的总比较方面没有任何优势 .（然而，n-ary树在利基情况下仍然有用 . 立即想到的例子是quad-trees和其他空间分区树，其中每个级别仅使用两个节点的分区空间将使逻辑不必要地复杂;并且B-trees使用在许多数据库中，限制因素不是每个级别进行多少次比较，而是一次可以从硬盘驱动器加载多少个节点）
当大多数人谈论二叉树时，他们往往不会考虑二元搜索树，所以我将首先介绍它 .
非 balancer 二叉搜索树实际上对于教育学生数据结构只是有用的 . 这是因为，除非数据以相对随机的顺序进入，否则树很容易退化为最坏情况形式，这是一个链表，因为简单的二叉树不 balancer .
一个很好的例子：我曾经不得不修复一些将其数据加载到二叉树中进行操作和搜索的软件 . 它以排序的形式写出数据：
因此，当重新阅读时，最后得到以下树：
这是堕落的形式 . 如果你在那棵树上寻找弗兰克，你必须在找到他之前搜索所有六个节点 .
当您 balancer 它们时，二叉树变得非常有用 . 这涉及通过其根节点旋转子树，以便任何两个子树之间的高度差小于或等于1.将这些名称一次一个地添加到 balancer 树中将为您提供以下序列：
实际上，当添加条目时，您可以看到整个子树向左旋转（在步骤3和6中），这为您提供了一个 balancer 的二叉树，其中最坏情况查找是
O(log N)而不是简并形式给出的O(N. 在任何时候，最高NULL（=）与最低值相差多于一个级别 . 而且，在上面的最后一棵树中，你可以通过仅查看三个节点（Chloe，Edwina，最后是Frank）找到Frank .当然，当你制作 balancer 的多路树而不是二元树时，它们会变得更有用 . 这意味着每个节点包含多个项目（从技术上讲，它们包含N个项目和N 1指针，二叉树是单向多路树的一个特例，有1个项目和2个指针） .
使用三向树，您最终得到：
这通常用于维护项目索引的键 . 我编写了针对硬件优化的数据库软件，其中节点的大小与磁盘块的大小完全相同（例如，512字节），并且您可以将尽可能多的密钥放入单个节点中 . 在这种情况下，指针实际上是记录数字到与索引文件分开的固定长度记录直接访问文件中（因此只需寻找
X * record_length就可以找到记录号X） .例如，如果指针是4个字节并且密钥大小是10，则512字节节点中的密钥数是36.这是36个密钥（360个字节）和37个指针（148个字节），总共508个字节每个节点浪费4个字节 .
多路密钥的使用引入了两阶段搜索的复杂性（多路搜索找到正确的节点结合小的顺序（或线性二进制）搜索以找到节点中的正确密钥）但优势在于减少磁盘I / O比弥补这一点要多 .
我认为没有理由为内存结构做这件事，你最好坚持使用 balancer 的二叉树并保持代码简单 .
另外请记住，
O(log N)使用多路树将十五个人存储在地址簿中的优势，它可以存储过去十年来您的十万个客户的每个订单 .大O符号的重点在于表明当_743242接近无穷大时会发生什么 . 有些人可能不同意，但只要没有别的东西可以随时可用，确保数据集保持在一定的范围内:-)
至于二叉树的其他用途，有很多，例如：
二进制堆，其中较高的键高于或等于较低的键而不是左侧（或低于或等于和等于）;
哈希树，类似于哈希表;
用于编译计算机语言的抽象语法树;
用于压缩数据的霍夫曼树;
为网络流量路由树 .
鉴于我为搜索树生成了多少解释，我不愿详细讨论其他问题，但如果您愿意，这应该足以研究它们 .
二叉树是树数据结构，其中每个节点最多具有两个子节点，通常被区分为“左”和“右” . 具有子节点的节点是父节点，子节点可以包含对其父节点的引用 . 在树之外，通常会引用“根”节点（所有节点的祖先）（如果存在） . 可以通过从根节点开始并反复跟随对左子节点或右子节点的引用来到达数据结构中的任何节点 . 在二叉树中，每个节点的度数最大为2 .
二叉树很有用，因为正如您在图片中看到的那样，如果要在树中找到任何节点，则只需要查看最多6次 . 例如，如果要搜索节点24，则应从根目录开始 .
根的值为31，大于24，因此您转到左侧节点 .
左侧节点的值为15，小于24，因此您转到右侧节点 .
右侧节点的值为23，小于24，因此您转到右侧节点 .
右侧节点的值为27，大于24，因此您转到左侧节点 .
左侧节点的值为25，大于24，因此您转到左侧节点 .
节点的值为24，这是我们要查找的密钥 .
此搜索如下所示：
您可以看到，您可以在第一次传递时排除整个树的一半节点 . 第二个是左子树的一半 . 这使得搜索非常有效 . 如果这是在40亿个元素上完成的，那么你最多只能搜索32次 . 因此，树中包含的元素越多，搜索效率就越高 .
删除可能会变得复杂 . 如果节点有0或1个子节点，那么只需移动一些指针即可排除要删除的节点 . 但是，您无法轻松删除包含2个子节点的节点 . 所以我们采取捷径 . 假设我们想要删除节点19 .
由于试图确定左右指针的移动位置并不容易，因此我们找到一个用它来代替它 . 我们去左侧的子树，尽可能向右走 . 这为我们提供了我们想要删除的节点的下一个最大 Value .
现在我们复制除了左右指针之外的所有18个内容，并删除原始的18个节点 .
为了创建这些图像，我实现了一个AVL树，一个自 balancer 树，这样在任何时间点，树在叶节点（没有子节点的节点）之间至多有一个级别的差异 . 这使树不会变得歪斜保持最大
O(log n)搜索时间，插入和删除所需的时间稍长 .这是一个示例，展示了我的AVL树如何保持自己尽可能紧凑和 balancer .
在排序数组中，查找仍然需要
O(log(n))，就像树一样，但随机插入和删除将需要O（n）而不是树的O(log(n)). 一些STL容器使用这些性能特性，因此插入和移除时间最多为O(log n)，这非常快 . 其中一些容器是map，multimap，set和multiset.可以在http://ideone.com/MheW8找到AVL树的示例代码
Morse code的组织是二叉树 .
主要应用是binary search trees . 这些是一种数据结构，其中搜索，插入和删除都非常快（关于
log(n)操作）在Huffman coding中使用二进制树，它们用作压缩代码 .
二进制树在Binary search trees中使用，这对于维护数据记录非常有用，而没有太多额外空间 .
未提及的二叉树的一个有趣示例是递归计算的数学表达式 . 从实际的角度来看，它基本上是无用的，但它是一种思考这种表达的有趣方式 .
基本上，树的每个节点都有一个值本身固有的值，或者通过对其子节点值进行操作来递归计算 .
例如，表达式
(1+3)*2可以表示为：为了评估表达式，我们要求父级的值 . 该节点依次从其子节点，加号运算符和仅包含“2”的节点获取其值 . 加号运算符依次从值为“1”和“3”的子项获取其值并将它们相加，并将4返回到乘法节点，该节点返回8 .
这种二叉树的使用在某种意义上类似于反向抛光符号，因为执行操作的顺序是相同的 . 还有一点需要注意的是，它不一定必须是二叉树，它只是最常用的运算符是二进制 . 在最基本的层面上，这里的二叉树实际上只是一种非常简单的纯函数式编程语言 .
最常见的应用之一是以有序的形式有效地存储数据，以便快速访问和搜索存储的元素 . 例如，C标准库中的
std::map或std::set.作为数据结构的二叉树对表达式解析器和表达式求解器的各种实现很有用 .
它还可以用于解决一些数据库问题，例如索引 .
通常，二叉树是特定的基于树的数据结构的一般概念，并且可以构造具有不同属性的各种特定类型的二叉树 .
二叉树的应用：
Implementing routing table in router .
Data compression code
Implementation of Expression parsers and expression solvers
To solve database problem such as indexing .
Expression evaluation
我不认为"pure"二进制树有任何用处 . （除了教育目的） balancer 二叉树，例如Red-Black trees或AVL trees更有用，因为它们保证O（logn）操作 . 正常的二叉树可能最终成为一个列表（或几乎列表），并且在使用大量数据的应用程序中并不真正有用 .
balancer 树通常用于实现 Map 或集合 . 它们也可以用于O（nlogn）中的排序，即使存在更好的方法 .
也可以使用搜索/插入/删除Hash tables，它通常具有比二叉搜索树更好的性能（ balancer 或不 balancer ） .
如果需要搜索/插入/删除和排序，那么（ balancer 的）二进制搜索树将有用的应用程序将是有用的 . 给定一个现成的 balancer 树，Sort可以就地（几乎忽略递归所需的堆栈空间） . 它仍然是O（nlogn）但是具有较小的常数因子并且不需要额外的空间（除了新数组之外，假设数据必须放入数组中） . 另一方面，哈希表无法排序（至少不能直接排序） .
也许它们在一些复杂的算法中也很有用，但是我没有想到什么 . 如果我找到更多，我将编辑我的帖子 .
其他树如f.e. B+trees广泛用于数据库
二叉树最重要的应用之一是 balanced 二进制搜索树，如：
Red-Black trees
AVL trees
Scapegoat trees
这些类型的树具有这样的特性：通过在每次插入或删除节点时执行诸如旋转之类的操作，左子树和右子树的高度差保持较小 .
因此，树的总高度保持为log n和操作的顺序例如，在O（log n）时间内执行节点的搜索，插入和删除 . C的STL也以集合和映射的形式实现这些树 .
它们可以用作快速排序数据的方法 . 将数据插入O（log（n））的二叉搜索树中 . 然后遍历树以对它们进行排序 .
您的程序语法，或者就此而言，可以使用二叉树（尽管不一定）解析许多其他事物，例如自然语言 .
java.util.Set的实现在现代硬件上，由于缓存和空间行为不良，二叉树几乎总是次优的 . 这也适用于（半） balancer 变体 . 如果你找到它们，那就是性能不计算（或者由比较函数支配），或者更有可能出于历史或无知的原因 .
使用二叉树表示AST的编译器可以使用已知的算法来解析像后序的树一样 . 编程人员不需要提出它自己的算法 . 因为源文件的二叉树高于n-ary树，所以它的构建需要更多时间 . 采取这个 生产环境 ：selstmnt：=“if”“（”expr“）”stmnt“ELSE”stmnt在二叉树中它将有3个级别的节点，但是n-ary树将有1个级别（chids）
这就是为什么基于Unix的操作系统很慢的原因 .