Red Black Tree

Mô tả của Red Black Tree

/*
This Application was made during Summer 2015.
Tauqueer Ahmad
Computer Science and Engineering,
Under Graduate,
IIT Roorkee, Uttarakhand
Guidance: Dr. Balasubramanian Raman,
Computer Scienec Professor,
IIT Roorkee, Uttarakhand
*/
Red-Black Tree is a self-balancing binary search tree.
In case of Binary Search Tree (BST) if the tree is skewed then operations like search, insert, delete take O(n) time. (n is the number of nodes). Red-Black Tree on the other hand maintains its O(log(n)) height.
AVL trees are also an alternative for self-balancing trees, but both have their own pros and cons. AVL trees are good when there is frequent number of search operations. Red-Black Trees are good when there is frequent number of insertion or deletion
.
This application animates insertion, deletion and search operations performed on Red-Black Tree.
A complete description about Red-Black trees is also there in this app.
Source of description: www.geeksforgeeks.com
Red-Black Trees have got a lot of applications in Computer science.
The process scheduler in Linux uses Red Black Trees.
The Complete Fair Scheduler in Linux handles CPU resource allocation for executing processes, and aims to maximize overall utilization while also maximizing interactive performance.
C STL uses Red-Black Tree internally to implement Set and Map.
Red Black Trees are also used in Computational Geometry