RedBlack trees Flashcards
What is a Red-Black Tree, and why is it significant
A Red-Black Tree is a type of self-balancing binary search tree (BST) that ensures the tree remains “approximately” balanced, allowing operations like insertion, deletion, and search to have a worst-case time complexity of O(log n). It achieves balance through a set of properties, with nodes having a color attribute (red or black), ensuring no path from the root to a leaf is more than twice as long as any other path.
What are the five properties of Red-Black Trees?
The five properties of Red-Black Trees are:
Every node is either red or black.
The root is black.
All leaves (nil nodes) are black.
If a node is red, then its children must be black (no two consecutive red nodes).
For each node, all paths from the node to its descendant leaves must contain the same number of black nodes (i.e., have the same black height).
What is the black-height of a node in a Red-Black Tree?
The black-height of a node in a Red-Black Tree is the number of black nodes (including nil nodes) on the path from that node to a leaf, excluding the node itself. The black-height property ensures that all paths from any given node to its descendant leaves contain the same number of black nodes, contributing to the balanced nature of Red-Black Trees.
What are the common operations for Red-Black Trees, and what is their time complexity?
The common operations for Red-Black Trees are:
Insert: Inserts a node while maintaining the Red-Black Tree properties. It involves BST insertion and then fixing the tree with re-coloring and rotations. The worst-case time complexity is O(log n).
Delete: Deletes a node while maintaining the Red-Black Tree properties. This operation also involves re-coloring and rotations, with a worst-case time complexity of O(log n).
Search: Searches for a specific key in the tree with a worst-case time complexity of O(log n).
Describe the basic process for inserting a node into a Red-Black Tree.
Insertion in a Red-Black Tree involves the following steps:
Insert the node as in a standard binary search tree (BST).
Color the inserted node red.
Fix the tree to maintain the Red-Black properties, using the following:
Re-coloring nodes to avoid consecutive red nodes.
Rotations to ensure the tree is balanced.
The fix-up process is iterative and ensures that the Red-Black properties are preserved.
What is a Right Rotation in a Red-Black Tree, and why is it used?
A Right Rotation in a Red-Black Tree is an operation where the left child of a node becomes the new root, and the original root becomes the right child of the new root. This rotation is used to maintain the Red-Black Tree properties, particularly to correct imbalances where the left subtree is deeper than allowed, helping restore the tree’s balance.
What are the cases for fixing up Red-Black Trees after insertion, and how do they differ?
The cases for fixing up Red-Black Trees after insertion are:
Case 1: When the uncle of the newly inserted node is red. This leads to re-coloring and possibly more iterations in the fix-up process.
Case 2: When the uncle is black, and the new node is a right child. A left rotation is performed.
Case 3: When the uncle is black, and the new node is a left child. A right rotation is performed.
These cases correct imbalances in the tree, restoring the Red-Black properties.
What is the worst-case height of a Red-Black Tree, and how does it compare to other balanced trees?
The worst-case height of a Red-Black Tree is O(2 * log n), which is no more than twice the height of the corresponding balanced tree. This height allows Red-Black Trees to maintain efficient operations for insertion, deletion, and search, ensuring no path from the root to a leaf is significantly longer than others.
What is the difference between AVL trees and Red-Black Trees?
The main differences between AVL trees and Red-Black Trees are:
Balance: AVL trees are more strictly balanced, leading to faster search operations. Red-Black Trees have fewer constraints, requiring less effort for insertion and deletion, making them faster for these operations.
Height: AVL trees maintain stricter balance, often resulting in shorter trees. Red-Black Trees can have slightly taller trees due to more flexible balancing rules.
Storage: AVL trees require additional storage for balance factors or heights, while Red-Black Trees use only one extra bit for node color.
What is the complexity of insertion in a Red-Black Tree, and why is it efficient?
The complexity of insertion in a Red-Black Tree is O(log n). This efficiency is due to the self-balancing nature of Red-Black Trees, where the fix-up process ensures the tree retains its balanced properties through re-coloring and rotations. Insertion requires at most two rotations, and the fix-up process ensures the Red-Black properties are maintained with each iteration.
