Graphs, trees, hash tables(1.4.2 b) Flashcards
What are the three parts of trees?
root nodes
nodes
edges/pointers
How many ways in a tree to get from root to subnodes?
one way
Tree diagram
How many children do binary trees have?
only two
Binary tree
all other regular trees apply
every node having two children we terminate the tree at a leaf node
Binary tree
Uses of binary trees
searching algorithms
sorting algorithms
compression algorithms
What are the two parts of graphs?
nodes
edges/pointers
Graphs
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
How does a traversal differ from a search?
returns all values in the tree
What does a search return?
only value searching for or not found
Breath first traversal
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
Breath first traversal diagram
Depth first traversal
start at root node and go left to next node until leaf node then goes back up to next unexplored node
Depth first pre order search
reads nodes as first hits its
Depth first pre order search diagram
Depth first in order search
returns node after all left tree explored
Depth first in order search diagram
Depth first post order search
return node after all children have been explored
always ends with root
Depth first post order search diagram
What is hash?
refers to a hashing algorithm an irreversible process
Hashing
irreversible
used for hashtables and cryptography
maps arbitary data to a fixed size output
similar inputs provide a very different output
What is collsion in hashing?
sometimes different inputs can result in the same output
How hashtables work
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
Hashtable diagram
Why do we use hashtables
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)
Hashtable collisions
biggest difficulty dealing with hashtables
Linear probing
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
Chaining
each item in the hashtable is part of a linked list
we traverse the linked list until we find what we’re looking for
Overflow table
if we detect a collision we search an overflow table
place/find the item in the first available space of the overflow table
Choice of hash algorithm
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)
