Why do many binary tree data structures in C not have a parent node pointer?

Question

I am new to C programming and I am learning C algorithms with C.

Here my problem is how to define the data structure of the binary node tree.

Use or DO NOT use the node parent pointer

Here are two typical code examples for defining a node data structure.

No parent pointer node

 typedef struct binaryTreeNode_{ int key; void *data; binaryTreeNode_ *leftNode; binaryTreeNode_ *rightNode; } binaryTreeNode; 

With parent pointer node

 typedef struct binaryTreeNode_{ int key; void *data; binaryTreeNode_ *leftNode; binaryTreeNode_ *rightNode; binaryTreeNode_ *parentNode; } binaryTreeNode; 

My question

Obviously, using a node structure with a parent node pointer will make things much easier. Similar to moving a node / a tree, DFS / BFS with a binary tree. So my question is why there are some solutions, based on the structure without a parent node? .

Are there any historical reasons? If it is simply because RAM / DISK capacity limitation, I think we can refuse a solution that does not have a parent node, right?

Maybe not relavent

Like the Linked List and the Doubly Linked List, should the Doubly Linked List be used to implement Stack and Queue ?

Answer 1

A tree rarely requires a parent pointer for regular / simple operations. This only happens when you do something exotic (for example, return the path back from the sheet to node), which may require a parent pointer.

Are there any historical reasons? If it is simply because there is a RAM / DISK limitation, I think we can refuse a solution that does not have a parent node, can we?

Some historical reasons too. In addition, memory limitations will require you to use the smallest, most compact structures. Even to this day, there are embedded systems with stringent memory requirements. Also, you really don't want to mess with existing code that works, so these things will stick.

So my question is, why are there some solutions based on a structure without a parent node?

Perhaps because their applications did not require frequent contact with parents. Note that this is a typical space-time tradeoff.

Like the Linked List and the Doubly Linked List, should the Doubly Linked List be used to implement Stack and Queue?

It depends on your application and the guarantors that your data structures must provide per operation. Also, you might be interested to see the linked XOR list !

Answer 2

There are very good reasons to use a tree without parent pointers, and memory usage is not a problem.

In the world of functional programming (I think Lisp, schema, standard ML, OCaml, Haskell, F #, etc.) trees and linked lists are very common data structures, so even in C they think a lot about trees and lists are influenced FP. Trees and lists are recursively defined (the tree is either a leaf or a node interior whose children are trees, and the list is nil or node with a data element and list attached) and they are almost always implemented as immutable data structures. Consistency is useful because it does parallelism cleanup (without visible programmers), data sharing between functions is better (no need to copy data) and simple.

The problem with the parent pointer or doubly linked list is that the sudden immutability exits the window. With an immutable object, you must specify everything about the object at the time of creation. So, if you want to maintain immutability, you cannot create a node until its children are created (since these children must be specified at creation time), but you also cannot set parent pointers to children before the parent was created ( as the parent does not exist). In other words, immutability does not play well with circular dependencies. Similarly, you cannot create a doubly linked list without any mutation, because without a mutation you cannot create the first node until the second node is created, and you cannot set the previous pointer to the second node until the first node is created.

FP users manage to write a lot of code with strictly unchanged data structures and prove many useful properties for loading. Of course, saving parent pointers makes the programmer’s life difficult, because as soon as you change one node in the tree, you have to make changes to all the parent pointers of your children, which is a pain.

Because reflections on lists and trees are influenced by FP, which does not include parent pointers or doubly linked lists, and because parent pointer support is a complex business that can introduce errors, many C-tree implementations do not use parent pointers.

---

Also, another note: you are asking about using linked lists compared to doubly linked lists for stacks and queues. There is no need to use a doubly linked list to implement the stack, because you do not need efficiency when traversing any element except the first (and the second if the stack is changed). There is a cute trick for implementing a two-stack queue that provides amortization for operations of a constant time queue. However, if you do not use this, the queue is also a decent use case for a doubly linked list or array.

Answer 3

For many algorithms, parent pointers are redundant. However, they incur memory costs and additional algorithmic complexity.

Just like the Linked List and the Doubly Linked List ...

The difference is that the latter can perform more operations with time complexity O(1) . Cost - Additional memory overhead. In other words, there is a compilation of memory over time .

Should I use a Doubly Linked List to implement Stack and Queue?

Both can be implemented using a doubly linked list. However, for one of two structures (I will leave it to you to find out if there is a stack or a queue!), The additional overhead of a doubly linked list does not buy anything.

Answer 4

You need a parent node only if you have code that jumps right into the tree. For example, in web browsers, you always get the DOM element in event handlers and must cross the DOM tree up from there to find some parent HTML element.

However, in many data structures you usually start from the root and go down, first in depth or in width - it doesn’t matter, you KNOW where you started, so there is no need to have parent links.

http://en.wikipedia.org/wiki/Depth-first_search

http://en.wikipedia.org/wiki/Breadth-first_search

Basically, your algorithm determines your data structure. Both go together, it is not useful to consider one without the other.

Answer 5

The binary tree does not define operations that require references to the parent node. You always go from top to bottom.

Answer 6

Some implementation of balanced trees supports a pointer to a parent. Obviously, Glib Balanced Trees contain nodes containing such a pointer.

But, when you have an internal recursive function passing through the tree, you can encode it so that it passes both the tree and its immediate parent during recursive calls.

Answer 7

Most balanced trees, such as red-black and AVL trees, do have parent pointers built into the node structure. And these are binary search trees with some additional properties. The reason is that it makes rebalancing a lot easier.

There are also some scripts that are very cumbersome without parent pointers.

Consider a binary search tree, and you arbitrarily choose a node victim. How to remove it from a tree? Without the parent’s pointer, you don’t know where in the tree it sits, so you need to search to find its parent so that you know which edge to update. With a parent pointer, you would do something like this:

 parent = victim->parent; if (parent) { if (parent->left == victim) { parent->left = NULL; } else { parent->right = NULL; } } ... free(victim); 

Another operation that is complicated without parent pointers is to look for a successor to the nodes. Especially if the tree allows you to store several objects with the same key value, which is necessary if you are implementing a multiset. But with them it’s easy:

 bstree *successor(bstree *node) { // If node has a right child, the successor is the minimum // node of that subtree. if (node->right) { return minimum(node->right); } // If node hasn't, we look upwards. bstree *x = node->parent; while (x && node == x->right) { node = x; x = node->parent; } return x; } 

Parent pointers take away the beauty of the data structure. They do this so that you can no longer treat the tree as a composition of trees, which is a shame. But in most practical implementations of tree structures, I saw that they are, because they are very useful.