Unit 7 - Data Structures

Binary Tree

A rooted tree where each node has a maximum of 2 children.

What data type is a tree?

Abstract data type

What is a tree?

A tree is a connected, undirected graph with no cycles. (There is a unique path from one node to another)

What is a rooted tree?

One node is identified as the root. The root has no parent.

What can pre-order be used for?

Used if you want to duplicate a binary tree

What is post-order?

Reads children first before parents

What can post-order be used for?

Used if you need to delete data

What can in-order be used for?

Used when you want to read data in order

Balanced tree

Each subtree has approximately same number of nodes to the left and the right.

Queue

It's an array that only allows data to be inserted from one end and retrieved from the other. Uses FIFO data structure.

Graph

Data structure that has a series of nodes connected together through edges Edges can be directed/undirected or unweighted/weighted

What are vectors used for?

Vectors are used for vector graphic images and computer games.

Vector addition

Adding 2 vectors

X+Y + X+Y = X+Y

Scalar multiplication

Increases or decreases a vector in size

a = (2,1)

b = 3a = (3x2, 3x1) = (6,3)

Convex combination:

w = αu + βv

Dot product

Method for multiplying 2 vectors. Represented as a •

Dot product formula

cos Ɵ = u • v

—-------

(ǁuǁ • ǁvǁ)

Adjacency matrix

2D array used to store info about a directed/undirected graph

Adjacency list

2D array used to store info on a large and sparse graph

Graph

A set of nodes/vertices connected to edges/arcs.

Edges

Edges can be undirected/directed or weighted/unweighted.

1 advantage of adjacency matrix

Adding an edge to it is simple

1 disadvantage of adjacency matrix

Wastes memory space on large, sparse graphs

1 advantage of adjacency list

Uses less memory space in a sparse graph

Vector

Ordered sequence of numbers. Shows magnitude and direction

Vector addition

Adding together 2 vectors

Scalar-vector multiplication

Changes the size of a vector, smaller or larger

Dot/scalar product

Multiplying 2 vectors together

Array

Collection of data with the same data type.

Circular Linked List

A variation of a linked list where the last node points back to the first node, forming a circle.

Priority Queue

An abstract data type similar to a regular queue but with elements that have priorities, allowing higher priority elements to be dequeued before lower priority ones.

What is a binary tree?

A binary tree is a rooted tree with a maximum of 2 children.

What is pre-order?

Reads parent first then the children

What is in-order?

Reads data on the tree alphabetically/numerically

Elementary data type

Data types provided by programming languages

Composite data type

Combination of elementary data types. They store multiple data types

Abstract data type

A model that defines how a data structure works. It uses information hiding to show only relevant/useful info.

Where are queues used irl?

At a checkout, entering a cinema, school lunch line

What is an advantage of a linear queue?

Simple to program

What is an disadvantage of a linear queue?

Fixed length size, Can't reuse spaces

Where can you use linear queues?

School lunch line

What is an advantage of a circular queue?

Can reuse spaces

What is an disadvantage of a circular queue?

More complex to program because of pointers.

Where can you use circular queues?

Documents waiting to be printed

What is an advantage of a priority queue?

Gives importance to items

What is an disadvantage of a priority queue?

Additional processing required

here can you use priority queues?

Accidents and Emergencies

Static data structure

Fixed in size. They cannot grow/shrink in size

Dynamic data structure

Can grow/shrink in size

Stacks

LIFO data structure. Adds data on the top of the stack and removes data from the top

Overflow

Attempting to push onto a stack that is full

Underflow

Attempting to pop from a stack that is empty

List

Lists store a collection of related data. The same item can occur more than once

Is a list mutable or immutable

Mutable

Mutable

Can be changed

Immutable

Cannot be changed

Linked list

A linked list is a dynamic list that allows you to add new data anywhere. The data points to the next data to create a chain

Advantages of linked lists

Dynamic

Easy to insert/delete data

The order of the data doesn't matter as the pointer points to the next node

Hash table

Collection of items stored in a way that can be quickly located. Can be implemented as an array or list.

Hashing algorithm

It has a key that performs operations on data to find out what index it should be stored in, in the hash table.

Collision

When more than 1 piece of data has the same hash value after being put into the hashing algorithm.

Folding method

Divides the data into equal parts then adds them together to get a hash value, then %.

Rehashing

Finding an empty slot for data that occurred in a collision.

What 2 ways of dealing with collisions in a hash table?

1. Add the data under the index in a list

2. Find an empty spot above the index in that table

Dictionary

Collection of associated pairs of items, each pair has a key and a value.

Represent vectors

LIST, DICTIONARY, 1D ARRAY.

Represent Dictionary

Hash tables, useful in graphs