我正在研究 CFS 的调度算法，它在此链接 http://www.ibm.com/developerworks/linux/library/l-completely-fair-scheduler上使用 RED-BLACK_TREE 数据结构
我的问题是：在 CFS 中使用红黑树的目的是什么，为什么不能使用 AVL 树。？
问问题
1380 次
3 回答
2
注意：我是从纯算法的角度回答这个问题（在实践中基本搜索树操作的性能），我不知道 Linux 开发人员是否有其他内部原因选择 RB 树（它可能让他们做某些事情 AVL树没有）。
一般来说，两者是可以互换的，就功能而言，它们也可以与基本的搜索树、treaps、splay树等互换。不同之处在于实际性能，因为所有平衡搜索树（AVL 和 RB 树都是平衡的）具有相同的理论性能。
根据两种数据结构（AVL、RB）的 wiki 页面，AVL 树在查询方面表现更好，而在插入和删除方面表现更差。如果您查看一个实现，这很容易注意到：平衡 AVL 树涉及更多，导致实践中的性能较慢。
所以我的猜测是，他们可以使用 AVL 树（除非他们利用结构属性 RB 树有而 AVL 树没有，这是不太可能的），但他们更关心插入和删除性能而不是查询性能，所以他们选择了RB代替。
还值得一提的是，C++、Java 和 .NET 中的许多内置数据结构在其实现中使用红黑树，这可能也是因为它们在所有操作中的性能相似。
于 2012-06-27T12:26:12.910 回答
1
CFS Linux 调度程序实际上使用定制的 RB 树 ( linux/rbtree.h)。但这里的关键是，CFS 基本上想知道接下来要选择哪个任务。这是通过从树中选择最左边的节点来实现的（因为它将是具有较小切片时间的节点）。但是，为方便起见，CFS 使用的 RBT 也有指向此类节点的指针。
在这一点上，您可以说 AVL 树可以以相同的复杂性完成相同的任务。另一方面，在添加或删除任务条目时，您必须重新平衡并遍历 RBT。我知道，在这里，RBT 比 AVL 更适合这项工作。
于 2014-06-23T01:20:49.863 回答
0
由于 RB 树是自平衡的，因此由于树的自平衡特性，树中的任何路径都不会是任何其他路径的两倍，因此，所有操作都是 O (log n)，因此插入和删除树中的任务可以快速高效地完成。
于 2020-12-12T08:51:52.063 回答