The use of red and black trees

Question

What are the uses of red-black (RB) trees? Is there any application in which only RB trees can be used but no other data structures?

Answer 1

The red-black tree is a special implementation of the self-balancing binary search tree , and today it seems to be the most popular implementation option.

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

Balancing the tree is necessary to ensure good performance, because otherwise the tree may degenerate into a list, for example, if you insert keys that are already sorted.

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

AVL trees are another variant of balanced binary search trees. They were popular before red-black trees became known. They are more carefully balanced, with a maximum difference of one between the heights of the left and right subtree (RB trees guarantee a maximum of two times). Their main disadvantage is that more effort is needed to restore balance.

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

Answer 2

The Red Black Trees are taken from a class of self-balancing BSTs, and, as others say, any such balancing tree can be used. I would like to add that red-black trees are widely used as system symbol tables. For example, they are used when implementing the following:

• Java: java.util.TreeMap, java.util.TreeSet.
• C ++ STL: map, multimap, multiset.
• Linux kernel: a completely fair scheduler, linux / rbtree.h

Answer 3

Unless you have specific performance requirements, the RB tree can be replaced with some other self-balancing binary tree, such as the AVL tree. The choice between them is basically a performance optimization - they offer the same basic operations.

It’s not that any of them was finally “faster” than the other, simply because they are different, that their use will have slightly different performance, all other things being equal. Therefore, if you carefully draw your requirements or just by accident, you may find yourself in one of them “fast enough” for your use, and the other not. RB offers a slightly faster installation than AVL, due to a slightly slower search.

Answer 4

There is no such rule as red black, it can be used only in a specific case, it depends on the application in such cases as when you have to build a tree only once, and you have to request it many times, then you can go to the AVL tree, because searching for an AVL tree is pretty fast. But it is strictly balanced, so inserting and deleting can take some time. The AVl tree can be used for language dictopies, where you need to build the data structure only once and the red ebony is used in the completely fair scheduler used in current Linux kernels for several days .

the restrictions applied to red ebony also ensure that the path from the root to the farthest leaf is no more than two times the path from the root to the nearest leaf.

By the way, you can find a different vision and paste, etc. the time required for red ebony is here.

Average Worst case Space O(n) O(n) Search O(log n) O(log n) Insert O(log n) O(log n) Delete O(log n) O(log n) 

Answer 5

Linux process scheduler uses Red Black Trees. Red black trees replace queue queues that have priority for processes in the queue for the scheduler.

Fully Fair Scheduler (CFS) is the name of the process scheduler that has been integrated with the Linux 2.6.23 kernel release. It manages the allocation of processor resources for executing processes and aims to maximize overall CPU utilization, as well as maximum interactive performance.