java.util.Set的实现

最常见的应用之一是高效地以排序形式存储数据，以便快速访问和搜索存储的元素。例如，std::map或std::set在c++标准库中。

二叉树作为一种数据结构，对于表达式解析器和表达式求解器的各种实现非常有用。

它也可以用来解决一些数据库问题，例如，索引。

一般来说，二叉树是一种特定的基于树的数据结构的一般概念，各种特定类型的二叉树可以构造成具有不同性质的二叉树。

我认为“纯”二叉树没有任何用处。(教育用途除外) 平衡二叉树，如红黑树或AVL树更有用，因为它们保证O(logn)运算。普通的二叉树最终可能是一个列表(或几乎是列表)，在使用大量数据的应用程序中并没有真正的用处。

平衡树通常用于实现映射或集合。 它们也可以用于O(nlogn)排序，即使存在更好的方法。

也可以用于搜索/插入/删除哈希表，它通常比二叉搜索树(平衡与否)有更好的性能。

在需要搜索/插入/删除和排序的应用程序中，(平衡的)二叉搜索树将是有用的。排序可以在适当的位置(几乎，忽略递归所需的堆栈空间)，给定一个就绪的构建平衡树。它仍然是O(nlogn)，但有一个更小的常数因子，不需要额外的空间(除了新的数组，假设数据必须放入数组中)。另一方面，哈希表不能排序(至少不能直接排序)。

也许它们在一些复杂的算法中也很有用，但说实话，我什么也想不起来。如果我发现更多，我会编辑我的帖子。

其他树如f.e.b +树也广泛应用于数据库中

几乎所有的数据库(和类数据库)程序都使用二叉树来实现它们的索引系统。

A binary tree is a tree data structure in which each node has at most two child nodes, usually distinguished as "left" and "right". Nodes with children are parent nodes, and child nodes may contain references to their parents. Outside the tree, there is often a reference to the "root" node (the ancestor of all nodes), if it exists. Any node in the data structure can be reached by starting at root node and repeatedly following references to either the left or right child. In a binary tree a degree of every node is maximum two.

二叉树很有用，因为正如你在图中看到的，如果你想找到树中的任何节点，你最多只需要找6次。例如，如果您想搜索节点24，您将从根节点开始。

根节点的值为31，大于24，所以要到左边的节点。 左边节点的值为15，小于24，所以要转到右边节点。 右边节点的值为23，小于24，所以您要转到右边节点。 右边节点的值是27，大于24，所以要转到左边节点。 左边节点的值是25，比24大，所以你到左边节点。 节点的值为24，这是我们要查找的键。

如下图所示:

您可以看到，在第一次传递时就可以排除整个树的一半节点。左边子树的一半在第二个。这使得搜索非常有效。如果这是在40亿个元素上进行的，那么您最多只需要搜索32次。因此，树中包含的元素越多，搜索的效率就越高。

删除会变得很复杂。如果节点有0或1个子节点，那么只需移动一些指针来排除要删除的指针。但是，不能轻易删除具有2个子节点的节点。所以我们走捷径。假设我们要删除节点19。

由于试图确定将左右指针移动到哪里并不容易，所以我们找到一个替换它的指针。我们到左边的子树，尽可能地向右移动。这就给出了我们想要删除的节点的下一个最大值。

现在我们复制18的所有内容，除了左指针和右指针，并删除原来的18节点。

为了创建这些图像，我实现了一棵AVL树，一棵自平衡树，这样在任何时间点，树的叶节点(没有子节点)之间最多有一层差异。这可以防止树变得倾斜，并保持最大的O(log n)搜索时间，而插入和删除需要更多的时间。

下面是一个示例，显示我的AVL树如何保持自己尽可能紧凑和平衡。

在排序数组中，查找仍然需要O(log(n))，就像树一样，但是随机插入和删除将需要O(n)，而不是树的O(log(n))。一些STL容器利用这些性能特征来发挥它们的优势，因此插入和删除时间最多为O(log n)，非常快。这些容器包括map、multimap、set和multiset。

AVL树的示例代码可以在http://ideone.com/MheW8上找到

在现代硬件上，由于糟糕的缓存和空间行为，二叉树几乎总是次优的。这也适用于(半)平衡的变种。如果您发现了它们，则说明性能不重要(或由比较函数主导)，或者更可能是由于历史或无知的原因。