Unit 7 - Data Structures

Tree

A tree is a connected, undirected graph with no cycles

Binary Tree

A rooted tree with a maximum of 2 children.

Ways to traverse a tree

Pre-order, In-order, Post-Order

Balanced Tree

The nodes are distributed in a way that eight is kept to a minimum

Elementary data type

Data types provided by programming languages

Examples of Elementary Data Types

Characters, integers, boolean, float,

Composite Data Type

Combination of elementary data types, they store multiple values.

Examples of Composite Data Types

String, Array,

Abstract Data Type

Operations that can be performed on data structures

Examples of Abstract Data Types

Queues, Lists, Stacks, Tree, Graph, Dictionary

Queue

Its an array that only allows data to be inserted from one end and retrieved from the other.

What structure is Queues?

FIFO

Examples of where queues are used in real life

At a checkout, entering a cinema, school lunch line

What are some examples of queue operations

1. Enqueue(item)

2. Dequeue

3. isEmpty

4. isFull

5. Size

6. Maxsize

Static data structure

They cannot grow or shrink in size

Dynamic Data Structure

They can grow and shrink in size

Advantage of linear queue

Simple to program

Disadvantage Linear Queues

Can’t reuse space

Usage for Linear Queues

School lunch line

Advantage of Circular Queue

Can reuse spaces

Disadvantage of Circular Queues

More complex to program

Usage of Circular Queues

Documents waiting to be printed

Advantage of Priority Queue

Gives importance to items

Disadvantage of Priority Queue

Additional processing required

Usage of Priority Queue

Accidents and Emergencies