What are the advantages of binary search trees with parent pointers?

Question

Up until this point, I've been implementing Binary Search Trees with left and right pointers, like:

template<typename T>
struct BSTNode{
    BSTNode* left;
    BSTNode* right;
    T data;
}

I came across implementations where nodes also had pointers to the parent node. Why would you want to do that? And what are the trade-offs?

Chazan

check out this tutorial: delorie.com/gnu/docs/avl/libavl_227.html – Ringnecked

Answer 1

From one point of view your question is valid because the parent pointer introduces a redundancy into the structure which is avoidable in several situations. But in case of binary trees this gives you the huge benefit that you can jump "up" one level (i.e. from a node to its parent) without remembering the parent node's address. Several algorithms (for example, getting the number of nodes between to two values) can be implemented very effectively and simple if the parent node of a node is known.

The trade-off is the redundancy: if you modify the structure of the tree (for example by balancing the tree) you must remember to update both the left/right and the parent pointers to keep the consistency of the tree.

Niple

Answer 2

Binary search tree refers to quite a general class of binary trees. For the binary search tree there is no reason to have a parent pointer.

There are more specialized variants of binary trees, however, where the parent pointer is beneficial. Look for AVL trees or red black trees for example. These specializations impose further restrictions on the tree's layout to achieve various goals, such as guaranteed O(log n) complexity for lookup/insert/removal in a red black tree by ensuring the tree is always balanced.

To fulfill these restrictions, the parent pointer comes in handy sometimes. Of course it does so by trading memory (the pointer) for speed (looking up the parent by algorithm).

Consider your favourite book on data structures to see how and why, or wikipedia.

Wynellwynn

Answer 3

It gives you simpler and smaller iterators that aren't invalidated by tree mutation. Without a parent node, a traversal routine needs a stack sized equal to the tree depth to remember where it's been. If nodes are added or deleted this stack becomes stale and the iterator no longer works correctly e.g. it may remember to revisit an ancestor node that has been deleted.

Of course the trade-off to keeping parent pointers is a bigger tree in memory. I can't make any claims about performance since updating a parent pointer takes time but also eliminates the step to remember the parent in some algorithms. So the tradeoff boils down to having a smaller tree with big fragile iterators on one hand, or having a larger tree with small robust iterators on the other.

Pathic

Answer 4

It is a speed-for-space trade, that conceptually does not have to be made, i.e. it is an implementation detail. You can always write a function, that returns the parent of any given node in a BST, but invoking such a function takes time, just looking up a value is usually faster.

If you are unwilling to make the trade, consider using an XOR BST, which is a kind of compromise.

Hiltonhilum