Best way to implement Binary Search Trees with 'parent' slot


I am trying to implement a BST library for teaching purposes, and I am a bit stuck. First of all, I am trying to implement the ‘insert’ operation as a ‘persistent’ one; i.e., by rebuilding the path to the newly inserted node.
Given this setup, what would be the best way to handle “parent” nodes without making the code very hairy?

I feel I am missing something either obvious or too subtle (or technically sophisticate).

Any suggestions?

Thank you

All the best

Marco Antoniotti

When you add the Parent field, the DAG of your data structure suddenly becomes a cyclic graph with bidirectional links to every node.

Parent = node(Value, Left, Right, GrandParent),
Left = node(_, _,_, Parent).

This is doable, provided you are doing insert only and not rebalancing. But if you delete or change a parent, the entire tree would need to be rebuilt. Or you use setarg to modify the terms.

1 Like

See section 9.3 “Insertion and deletion in binary dictionary” of Ivan Bratko’s Prolog Programming for Artificial Intelligence (I have an old edition - 1986 Addison-Wesley - so the chapters might have changed).