Problem Statement
How can memory be saved when storing colour information in a Red-Black tree?
Explanation
In Red-Black trees, each node needs to store color information which is either red or black, requiring just one bit. Memory can be saved by using the least significant bit of a pointer because pointers are typically aligned to word boundaries.
Pointer alignment means the last few bits are always zero for aligned addresses. For example, with 4-byte alignment, the last 2 bits are always zero. We can use the least significant bit to store the color where 0 represents black and 1 represents red. When dereferencing the pointer, we mask out the color bit to get the actual address. This technique saves memory compared to adding a separate boolean field which typically uses a full byte or more.
Code Solution
SolutionRead Only
// Traditional approach - uses extra memory
class RBNode {
int data;
RBNode left, right, parent;
boolean isRed; // Uses 1 byte typically
}
// Memory-efficient approach
class RBNode {
int data;
long leftPtr; // Pointer with color in LSB
long rightPtr; // Pointer with color in LSB
RBNode parent;
}
// Pointer operations:
// Store: ptr = (address | colorBit)
// Get address: address = (ptr & ~1)
// Get color: color = (ptr & 1)
// Example:
// Address: 0x1000 (binary: ...0000)
// Red node: 0x1001 (binary: ...0001)
// Extract address: 0x1001 & ~1 = 0x1000
// Extract color: 0x1001 & 1 = 1 (red)Practice Sets
This question appears in the following practice sets:
