CODEWITHSUNDEEP
binary-search-treered-black-tree
zbh2047
zbh2047

Reputation: 453

Why do we need to store a parent pointer for every node in red-black tree?

A red-black tree is an efficient data structure to maintain an ordered set. However, all the implementations I see (such as c++ STL, or the book "Introduction to Algorithms") seem to store a parent pointer for every node. It will lead to a larger memory cost.

I think such father pointer can be removed. Besides the memory concern, we don't need to manage the father pointer of each node. Then every node only stores the left child pointer, the right child pointer, the key and the color. Without the father pointer, insertion and deletion can still be implemented using an extra stack.

For a given key $x$, we first start from the root and find $x$. Through this process we use a stack to record all the node on the path. After that, if we need to rotate some node, the father information can be looked up using the stack. It is still efficient and the time complexity per operation is still O(log n).

So I don't know why current implementations all store father pointer in every node.

Upvotes: 2

Views: 966

Answers (2)

dbird
dbird

Reputation: 336

Nodes in this Java implementation of a left-leaning red-black tree, co-authored by the inventor of the left-leaning red-black tree, do not have parent pointers.

Upvotes: 0

SoronelHaetir
SoronelHaetir

Reputation: 15182

Having a parent pointer makes certain operations much easier to implement, the most notable being moving to the next or prior item from a given element of the tree. If you have parent pointers with each node it is possible to simply implement those operations without needing to locate the path from the root to your current item each time.

Upvotes: 1

Related Questions