Graphs, trees, hash tables(1.4.2 b)

Question 1

What are the three parts of trees?

Answer 1

root nodes
nodes
edges/pointers

Question 2

How many ways in a tree to get from root to subnodes?

Answer 2

one way

Question 3

Tree diagram

Answer 3

Question 4

How many children do binary trees have?

Answer 4

only two

Question 5

Binary tree

Answer 5

all other regular trees apply
every node having two children we terminate the tree at a leaf node

Question 6

Binary tree

Answer 6

Question 7

Uses of binary trees

Answer 7

searching algorithms
sorting algorithms
compression algorithms

Question 8

What are the two parts of graphs?

Answer 8

nodes
edges/pointers

Question 9

Graphs

Answer 9

edges can be weighted, be directed, create cycles
doesn’t have a root node
when using graphs we must define where to start traversing from

Question 10

How does a traversal differ from a search?

Answer 10

returns all values in the tree

Question 11

What does a search return?

Answer 11

only value searching for or not found

Question 12

Breath first traversal

Answer 12

goes from root node and goes down line by line
will print out on order starting at root node and reading nodes from left to right top to bottom

Question 13

Breath first traversal diagram

Answer 13

Question 14

Depth first traversal

Answer 14

start at root node and go left to next node until leaf node then goes back up to next unexplored node

Question 15

Depth first pre order search

Answer 15

reads nodes as first hits its

Question 16

Depth first pre order search diagram

Answer 16

Question 17

Depth first in order search

Answer 17

returns node after all left tree explored

Question 18

Depth first in order search diagram

Answer 18

Question 19

Depth first post order search

Answer 19

return node after all children have been explored
always ends with root

Question 20

Depth first post order search diagram

Answer 20

Question 21

What is hash?

Answer 21

refers to a hashing algorithm an irreversible process

Question 22

Hashing

Answer 22

irreversible
used for hashtables and cryptography
maps arbitary data to a fixed size output
similar inputs provide a very different output

Question 23

What is collsion in hashing?

Answer 23

sometimes different inputs can result in the same output

Question 24

How hashtables work

Answer 24

each key value is hashed by going in a hashing algorithm
the result of the hash algorithm turns into the list index of the relevant value

Question 25

Hashtable diagram

Answer 25

Question 26

Why do we use hashtables

Answer 26

no need to search through the array (as arrays get bigger searching takes a lot longer)
however we trade time for memory usage (unused space)

Question 27

Hashtable collisions

Answer 27

biggest difficulty dealing with hashtables

Question 28

Linear probing

Answer 28

put the data in the next available space
when we are searching for a value that has collided we search down the table until we find the value we’re looking for

Question 29

Chaining

Answer 29

each item in the hashtable is part of a linked list
we traverse the linked list until we find what we’re looking for

Question 30

Overflow table

Answer 30

if we detect a collision we search an overflow table
place/find the item in the first available space of the overflow table

Question 31

Choice of hash algorithm

Answer 31

poor hashing algorithm = lots of collision
if have lots of collisions we must spend precious time searching for the actual value
good hash algorithms take more computation time (and usually have many more possible outputs meaning hashtable is bigger)