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 collision 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