Monthly Archives: January 2015

Red-black tree

Red-black tree is a binary search tree which garanties searching, insertion and deletion in logarithmic time. As all extensions of BST it has additional properties which helps to keep tree balanced:

  1. A node has color either black or red.
  2. The root node is black.
  3. All leaves are black and don’t contain data. Sometimes to reduce memory consumption a single node performs the role of all leaves.
  4. Every red node must have two black child. This implies that on any path there can’t be two consecutive red nodes or in other words a red node can’t have a red child.
  5. Every path from a node to a descendant leaf contains the same number of black nodes. This number is called black height.

rbt

The best way to get the idea of these properties is an example. Let’s say we have inserted three elements in a plain vanilla binary search tree: Continue reading Red-black tree