I was studying about scheduling algorithm of CFS which uses RED-BLACK_TREE data structure on this link http://www.ibm.com/developerworks/linux/library/l-completely-fair-scheduler
我正在研究CFS的调度算法，它使用这个链接http://www.ibm.com/developerworks/linux/library/l completelly -fair-scheduler上的红黑树数据结构
My question is :What is the purpose of using red-black-tree in CFS ,why cannot use AVL tree.?
我的问题是:在CFS中使用红黑树的目的是什么，为什么不能使用AVL树。
2 个解决方案
#1
2
Note: I am answering this from a purely algorithmic point of view (performance of the basic search tree operations in practice), I have no idea if the Linux devs have other inside reasons for choosing RB trees (it might let them do certain things AVL trees don't).
注意:我是从纯粹的算法角度(实践中基本搜索树操作的性能)回答这个问题的，我不知道Linux开发人员是否有其他内部原因来选择RB树(它可能让他们做AVL树没有的某些事情)。
Generally, the two are interchangeable, and they are also interchangeable with basic search trees, treaps, splay trees etc. as far as functionality is concerned. The difference is in practical performance, as all balanced search trees (AVL and RB trees are both balanced) have the same theoretical performance.
一般来说，两者是可以互换的，就功能而言，它们也可以与基本的搜索树、树、树等互换。不同之处在于实际性能，因为所有的均衡搜索树(AVL和RB树都是均衡的)都具有相同的理论性能。
According to the wiki pages for the two data structures (AVL, RB), AVL trees perform better for querying and worse for insertion and removal. This is pretty easy to notice if you look at an implementation: balancing the AVL tree is more involved, leading to slower performance in practice.
根据这两个数据结构(AVL, RB)的wiki页面，AVL树在查询方面表现更好，在插入和删除方面表现更差。如果您查看实现:平衡AVL树，这很容易注意到，在实践中导致性能下降。
So my guess is, they CAN use AVL trees (unless they make use of a structural property RB trees have and AVL trees don't, which is unlikely), but they care more about insertion and removal performance than query performance, so they chose RB instead.
所以我猜，他们可以使用AVL树(除非他们使用RB树具有的结构属性，而AVL树不具有的结构属性，这是不可能的)，但是他们更关心插入和删除性能，而不是查询性能，所以他们选择了RB。
It's also worth mentioning that a lot of the built in data structures in C++, Java and .NET use red-black trees in their implementation, probably also because of their similar performance for all operations.
值得一提的是，在c++、Java和。net中构建的许多数据结构在实现中都使用红黑树，这可能也是因为它们在所有操作上的性能相似。
#2
1
The CFS Linux scheduler actually uses a customised RB Tree (linux/rbtree.h). But the key here is that CFS basically wants to know which task to pick next. This is achieved picking the left-most node from the tree (since it will be the one with minor slice time). However, the RBT used by CFS also has a pointer to such node for convenience.
CFS Linux调度器实际上使用了一个定制的RB树(Linux /rbtree.h)。但这里的关键是CFS基本上想知道接下来要选择哪个任务。这可以从树中选择最左的节点(因为它将是具有小片时间的节点)。但是，为了方便，CFS使用的RBT也有指向此类节点的指针。
At this point you could say that AVL tree could do the same task with equivalent complexity. In the other hand you have to rebalance and traverse the RBT when adding or removing task entries. Here, I understand, is where RBT suits better for the job than AVL.
此时，您可以说AVL树可以完成同样的任务，但复杂度相当。另一方面，在添加或删除任务条目时，必须重新平衡和遍历RBT。在这里，我明白了，RBT比AVL更适合这份工作。
#1
2
Note: I am answering this from a purely algorithmic point of view (performance of the basic search tree operations in practice), I have no idea if the Linux devs have other inside reasons for choosing RB trees (it might let them do certain things AVL trees don't).
注意:我是从纯粹的算法角度(实践中基本搜索树操作的性能)回答这个问题的，我不知道Linux开发人员是否有其他内部原因来选择RB树(它可能让他们做AVL树没有的某些事情)。
Generally, the two are interchangeable, and they are also interchangeable with basic search trees, treaps, splay trees etc. as far as functionality is concerned. The difference is in practical performance, as all balanced search trees (AVL and RB trees are both balanced) have the same theoretical performance.
一般来说，两者是可以互换的，就功能而言，它们也可以与基本的搜索树、树、树等互换。不同之处在于实际性能，因为所有的均衡搜索树(AVL和RB树都是均衡的)都具有相同的理论性能。
According to the wiki pages for the two data structures (AVL, RB), AVL trees perform better for querying and worse for insertion and removal. This is pretty easy to notice if you look at an implementation: balancing the AVL tree is more involved, leading to slower performance in practice.
根据这两个数据结构(AVL, RB)的wiki页面，AVL树在查询方面表现更好，在插入和删除方面表现更差。如果您查看实现:平衡AVL树，这很容易注意到，在实践中导致性能下降。
So my guess is, they CAN use AVL trees (unless they make use of a structural property RB trees have and AVL trees don't, which is unlikely), but they care more about insertion and removal performance than query performance, so they chose RB instead.
所以我猜，他们可以使用AVL树(除非他们使用RB树具有的结构属性，而AVL树不具有的结构属性，这是不可能的)，但是他们更关心插入和删除性能，而不是查询性能，所以他们选择了RB。
It's also worth mentioning that a lot of the built in data structures in C++, Java and .NET use red-black trees in their implementation, probably also because of their similar performance for all operations.
值得一提的是，在c++、Java和。net中构建的许多数据结构在实现中都使用红黑树，这可能也是因为它们在所有操作上的性能相似。
#2
1
The CFS Linux scheduler actually uses a customised RB Tree (linux/rbtree.h). But the key here is that CFS basically wants to know which task to pick next. This is achieved picking the left-most node from the tree (since it will be the one with minor slice time). However, the RBT used by CFS also has a pointer to such node for convenience.
CFS Linux调度器实际上使用了一个定制的RB树(Linux /rbtree.h)。但这里的关键是CFS基本上想知道接下来要选择哪个任务。这可以从树中选择最左的节点(因为它将是具有小片时间的节点)。但是，为了方便，CFS使用的RBT也有指向此类节点的指针。
At this point you could say that AVL tree could do the same task with equivalent complexity. In the other hand you have to rebalance and traverse the RBT when adding or removing task entries. Here, I understand, is where RBT suits better for the job than AVL.
此时，您可以说AVL树可以完成同样的任务，但复杂度相当。另一方面，在添加或删除任务条目时，必须重新平衡和遍历RBT。在这里，我明白了，RBT比AVL更适合这份工作。