Question

Find and share an algorithm about red/black trees. Explain it, give 2 real-world usages, and discuss its efficiency.

Answer 1

red/black tree

A red-black tree is a binary search tree with one extra attribute for each node: the colour, which is either red or black. We also need to keep track of the parent of each node, so that a red-black tree's node structure would be:

struct t_red_black_node {
enum { red, black } colour;
void *item;
struct t_red_black_node *left,
*right,
*parent;
}

A red-black tree is a binary search tree which has the following red-black properties:
1.Every node is either red or black.
2.Every leaf (NULL) is black.
3.If a node is red, then both its children are black.
4.Every simple path from a node to a descendant leaf contains the same number of black nodes.

give 2 real-world usages

1. They are common in the Linux kernel. For example in a process scheduler or for keeping track of the virtual memory segments for a process

2.They are also used in map, multimap, multiset from C++ STL and java.