CODEWITHSUNDEEP
prologbinary-search-tree
AlexDragos
AlexDragos

Reputation: 91

Create a binary search tree from a list of integers

Is there a way to implement a Prolog program that receives as input a list of integers and create a binary search tree? If the input is 3 6 1 5 the program should output (node 3 null) (node 6 3) (node 1 3) (node 5 6), the output is one node at a time, including its parent.

Upvotes: 2

Views: 220

Answers (1)

Guy Coder
Guy Coder

Reputation: 24976

Trees already exist in the SWI-Prolog library(assoc): Association lists.

Example:

?- empty_assoc(Tree0),put_assoc(3,Tree0,three,Tree1),put_assoc(6,Tree1,six,Tree2),put_assoc(1,Tree2,one,Tree3),put_assoc(5,Tree3,five,Tree).
Tree0 = t,
Tree1 = t(3, three, -, t, t),
Tree2 = t(3, three, >, t, t(6, six, -, t, t)),
Tree3 = t(3, three, -, t(1, one, -, t, t), t(6, six, -, t, t)),
Tree = t(3, three, >, t(1, one, -, t, t), t(6, six, <, t(5, five, -, t, t), t)).

The tree is implemented as as AVL tree which is a balanced binary tree.

Upvotes: 2

Related Questions