My Question: (From Chapter 11 of Programming Languages Principles and Practices,

Question

My Question: (From Chapter 11 of Programming Languages Principles and Practices, 3rd ed Louden, Lambert)

Write an algebraic specification for an abstract data type bstree (binary search tree) with the following operations:

Create:bstree

Make:bstree x element 3 bstree ->bstree

Empty:bstree -> Boolean

Left: bstree -> bstree

Right : bstree -> bstree

Data : bstree -> element

Isin: bstree x element -> Boolean

Insert : bstree x element -> bstree

What does one need to know about the element data type in order for a bstree data type to be possible.

Explanation / Answer

Algebraic specifications provide a mathematical framework for describing abstract data types. This framework offers:

Types:

define  Binary_Stree

uses Boolean, integer

Exceptions:
novalue

Syntax:

1. create : create Binary_Stree
2. make : make (Binary_Stree, Elem, Binary_Stree) --> Binary_Stree
3. empty : Is_empty--> Boolean
4. Left : Left (Binary_Stree) --> Binary_Stree
5. Right : Right (Binary_Stree) --> Binary_Stree
6.Data :Data (Binary_tree) -->Elem
7.Isin : isin (Binary_Stree, Elem) --> Boolean
8.Insert : insert (Binary_Stree, Elem) --> Binary_Stree

Equations:

insert(Create, E) =make(Create, E, Create)
insert(B, E) = if E < Data (B) then insert(Left (B), E) else insert (Right (B), E)
Is_empty ( Create) = true
Left (Create) = Create
Right (Create) = Create
Data (Create) = Undefined
Contains (Create, E) = false

Related Questions

Navigate

• Browse (All)
• Browse M
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.