Scribd
Upload
15 views8 pages

lec-20,21 tries data structure - Copy (2)

Uploaded by

akyadav123
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PPT, PDF, TXT or read online on Scribd
15 views8 pages

lec-20,21 tries data structure - Copy (2)

Uploaded by

akyadav123
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PPT, PDF, TXT or read online on Scribd
You are on page 1/ 8

Sets

 A Set is a collection of members (or


elements).

 Each member of a set is either itself a set


or is a primitive element called an atom.

 All elements of a set are different.


Sets
 Set can be integers, characters or strings.
 All elements can be of the same type.
 Atoms in a set can be linearly ordered.
 A linear order (denoted by <) on a set S
(“less than” or precedes”) satisfies two
properties:
 For any a and b in S, exactly one of a < b, a = b,
or b < a is true.
 For all a, b and c in S, if a < b and b < c, then a <
c (transitivity).
Set Notation
 A set of atoms is generally exhibited by
putting curly brackets around its members.
 Example: {1,4}, denotes the set whose
members are 1 and 4.

 Set is not a list, since order of elements in


a set is not important.
 {4,1} is the same set as {1,4}
Operations on Set
 UNION: If A and B are sets then A  B is
the set of elements that are members of A or
B or both.
 INTERSECTION: A  B is the set of
elements, that are present both in A and B.
 DIFFERENCE: A – B is the set of elements
that are members of A but are not members
of B.
Abstract Data Types Based on Sets

The Set ADT can incorporate some other


operations as well.
 MERGE(A,B,C): Assigns to the set variable C
the value A  B, the operator is not defined if
ABØ
 MEMBER(x,A): Returns true if x A and
returns false if x  A.
 MAKENULL(A): makes the Null set be the
value for set variable A.
Abstract Data Types Based on Sets

 INSERT(x,A): x is an element of the type


of A’s members. Makes x a member of A.
A = A  {x}
 DELETE(x,A): removes x from A.
A=A–{x}
 ASSIGN(A,B): sets the value of set
variable A to be equal to the value of set
variable B.
Abstract Data Types Based on Sets
 MIN(A): Returns the least element in set A.This
operator is applicable only when the member of A
are linearly ordered.
 MAX(A): Returns the largest element in set A.This
operator is applicable only when the member of A
are linearly ordered.
 EQUAL(A,B): Returns true if and only if sets A
and B consists of the same elements.
 FIND(x): Works for collection of disjoint sets.
Returns the name of the unique set of which x is a
member.
Reference
 “Data Structures and Algorithms” by A. V.
Aho, J. E. Hopcroft, J. D. Ullman.

You might also like