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

Help! Data Structure
1

Hi

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

2

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
3

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).