二叉树有哪些应用？
本文翻译自：What are the applications of binary trees?
I am wondering what the particular applications of binary trees are. 我想知道二叉树的特殊应用是什么。 Could you give some real examples? 你能举一些真实的例子吗？
#1楼
参考：https://stackoom.com/question/8wDY/二叉树有哪些应用
#2楼
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. 在二叉树中，每个节点的度最大为2。
Binary trees are useful, because as you can see in the picture, if you want to find any node in the tree, you only have to look a maximum of 6 times. 二叉树很有用，因为如您在图片中所见，如果要在树中查找任何节点，则最多只需要查找6次。 If you wanted to search for node 24, for example, you would start at the root. 例如，如果要搜索节点24，则应从根节点开始。
- The root has a value of 31, which is greater than 24, so you go to the left node. 根的值31大于24，因此您转到左节点。
- The left node has a value of 15, which is less than 24, so you go to the right node. 左侧节点的值为15，小于24，因此您转到右侧节点。
- The right node has a value of 23, which is less than 24, so you go to the right node. 右边的节点的值为23，小于24，因此您转到右边的节点。
- The right node has a value of 27, which is greater than 24, so you go to the left node. 右侧节点的值为27，该值大于24，因此您将转到左侧节点。
- The left node has a value of 25, which is greater than 24, so you go to the left node. 左侧节点的值25大于24，因此您将转到左侧节点。
- The node has a value of 24, which is the key we are looking for. 该节点的值为24，这是我们正在寻找的关键。
This search is illustrated below: 该搜索如下所示：
You can see that you can exclude half of the nodes of the entire tree on the first pass. 您可以看到在第一遍中可以排除整个树的一半节点。 and half of the left subtree on the second. 左子树的一半放在第二个树上。 This makes for very effective searches. 这使得搜索非常有效。 If this was done on 4 billion elements, you would only have to search a maximum of 32 times. 如果对40 亿个元素执行此操作，则最多只需搜索32次。 Therefore, the more elements contained in the tree, the more efficient your search can be. 因此，树中包含的元素越多，搜索的效率就越高。
Deletions can become complex. 删除会变得很复杂。 If the node has 0 or 1 child, then it's simply a matter of moving some pointers to exclude the one to be deleted. 如果节点有0或1个子节点，则只需移动一些指针以排除要删除的节点即可。 However, you can not easily delete a node with 2 children. 但是，您无法轻松删除具有2个子节点的节点。 So we take a short cut. 因此，我们采取捷径。 Let's say we wanted to delete node 19. 假设我们要删除节点19。
Since trying to determine where to move the left and right pointers to is not easy, we find one to substitute it with. 由于尝试确定向左和向右指针移动的位置并不容易，因此我们找到了一个替代它。 We go to the left sub-tree, and go as far right as we can go. 我们转到左侧的子树，然后尽可能向右移动。 This gives us the next greatest value of the node we want to delete. 这为我们提供了要删除的节点的下一个最大值。
Now we copy all of 18's contents, except for the left and right pointers, and delete the original 18 node. 现在，我们复制18的所有内容（左右指针除外），并删除原始的18节点。
To create these images, I implemented an AVL tree, a self balancing tree, so that at any point in time, the tree has at most one level of difference between the leaf nodes (nodes with no children). 为了创建这些图像，我实现了一个AVL树，即一个自平衡树，以便在任何时间点，该树在叶节点（没有子节点的节点）之间最多具有一个差异级别。 This keeps the tree from becoming skewed and maintains the maximum O(log n) search time, with the cost of a little more time required for insertions and deletions. 这样可以防止树倾斜，并保持最大O(log n)搜索时间，并且插入和删除操作需要花费更多时间。
Here is a sample showing how my AVL tree has kept itself as compact and balanced as possible. 这是显示我的AVL树如何尽可能保持紧凑和平衡的示例。
In a sorted array, lookups would still take O(log(n)) , just like a tree, but random insertion and removal would take O(n) instead of the tree's O(log(n)) . 在排序数组中，查找仍将像树一样使用O(log(n)) ，但是随机插入和删除将使用O（n）而不是树的O(log(n)) 。 Some STL containers use these performance characteristics to their advantage so insertion and removal times take a maximum of O(log n) , which is very fast. 一些STL容器充分利用了这些性能特征，因此插入和移除时间最多占用O(log n)的最大值，这非常快。 Some of these containers are map , multimap , set , and multiset . 其中一些容器是map ， multimap ， set和multiset 。
Example code for an AVL tree can be found at http://ideone.com/MheW8 有关AVL树的示例代码，请参见http://ideone.com/MheW8。
#3楼
Applications of Binary tree: 二叉树的应用：
- Implementing routing table in router . 在路由器中实现路由表 。
- Data compression code 数据压缩码
- Implementation of Expression parsers and expression solvers 表达式解析器和表达式求解器的实现
- To solve database problem such as indexing . 解决索引等数据库问题 。
- Expression evaluation 表达评估
#4楼
One of the most important application of binary trees are balanced binary search trees like: 二进制树的最重要应用之一是平衡的二进制搜索树，例如：
These type of trees have the property that the difference in heights of left subtree and right subtree is maintained small by doing operations like rotations each time a node is inserted or deleted. 这些类型的树具有以下性质：通过在每次插入或删除节点时进行诸如旋转之类的操作，可以使左子树和右子树的高度差保持较小。
Due to this, the overall height of the tree remains of the order of log n and the operations such as search, insertion and deletion of the nodes are performed in O(log n) time. 因此，树的整体高度保持为log n的顺序，并且在O（log n）时间内执行诸如搜索，插入和删除节点之类的操作。 The STL of C++ also implements these trees in the form of sets and maps. C ++的STL还以集合和映射的形式实现这些树。
#5楼
In C++ STL, and many other standard libraries in other languages, like Java and C#. 在C ++ STL和许多其他语言的标准库中，例如Java和C＃。 Binary search trees are used to implement set and map. 二叉搜索树用于实现集合和映射。
#6楼
The main application is binary search trees . 主要应用是二叉搜索树 。 These are a data structure in which searching, insertion, and removal are all very fast (about log(n) operations) 这些是数据结构，其中搜索，插入和删除都非常快（关于log(n)操作）