In this post, we will talk about What is Red-Black Tree?
Red-Black Tree is usually a self-balancing Binary Search Tree (BST), In red-black trees, each node is associated with an extra attribute: the color, which is either red or black. To get logarithmic complexity we impose the following restrictions.
- Root Property: The root is black
- External Property: Every leaf is black
- Internal Property: The children of a red node are aways black
- Depth Property: All the leaves are black
- Usually, every path from the root to a NULL node has the same number of black nodes.
- There are usually no two adjacent red nodes (A red node cannot have a red parent or red child).
Red Back Tree Example:
Why Red-Black Trees?
Many of the BST operations like insert, delete, search, max, min etc.takes O(h) time where h is the height of the BST. The complexity of these operations may become O(n) for a skewed Binary tree. If we make sure that the height of the tree remains O(log n) after every insertion and deletion then we can guarantees an upper bound of O(log n) for all these operations. The height of a Red-Black tree has complexity O(log n) where n is the number of nodes in the tree.
Comparison between Red-Black & AVL Tree
The AVL(Adelson-Velskii and Landis) trees are usually more balanced compared to Red-Black Trees, but they may create more rotations during insertion and deletion so if your application requires many frequent insertions and deletions operations then Red-Black trees should be preferred. And if the insertions and deletions are less frequent and search is a more frequent operation in your application then AVL tree should be preferred over Red-Black Tree.
You May Also Like:
Binary Tree Traversals
PreOrder traversal of binary tree implementation in Java
InOrder traversal of binary tree implementation in Java
PostOrder traversal of binary tree implementation in Java
Find the node with minimum and maximum values in a Binary Search Tree
Find a mirror image of a binary tree
That’s all about What is Red-Black Tree?
If you have any feedback or suggestion please feel free to drop in below comment box.