红黑树的应用 [英] Applications of red-black trees

问题描述

红黑树的应用是什么？有没有任何应用程序只能使用RB树，没有其他数据结构？

解决方案

A 红黑树是自平衡二叉搜索树的特定实现，今天似乎是最受欢迎的实施选择。

二进制搜索树用于实现有限地图，其中存储一组具有关联值的键。您也可以仅使用密钥实现集合，而不是存储任何值。

需要平衡树以保证良好的性能，否则树可能会退化为列表例如，如果您插入已经排序的键。

搜索树在哈希表上的优点是可以按排序顺序遍历树。 >

AVL-trees 是平衡二进制的另一个变体搜索树。他们在已知的红黑树之前很受欢迎。它们更仔细地平衡，左右子树高度之间的最大差异（RB树保证最多为二分之一）。他们的主要缺点是重新平衡需要更多的努力。

所以红黑树肯定是一个很好但不是这个应用程序的唯一选择。

What are the applications of red-black trees? Is there any application where only RB Trees can be used and no other data structures?

解决方案

A red-black tree is a particular implementation of a self-balancing binary search tree, and today it seems to be the most popular choice of implementation.

Binary search trees are used to implement finite maps, where you store a set of keys with associated values. You can also implement sets by only using the keys and not storing any values.

Balancing the tree is needed to guarantee good performance, as otherwise the tree could degenerate into a list, for example if you insert keys which are already sorted.

The advantage of search trees over hash tables is that you can traverse the tree efficiently in sort order.

AVL-trees are another variant of balanced binary search trees. They were popular before red-black trees where known. They are more carefully balanced, with a maximal difference of one between the heights of the left and right subtree (RB trees guarantee at most a factor of two). Their main drawback is that rebalancing takes more effort.

So red-black trees are certainly a good but not the only choice for this application.

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